[gnutls-dev] Re: bug in _gnutls_pkcs1_rsa_encrypt

[Simon Josefsson]

Robey Pointer <address@hidden> writes:

> I just figured out what was causing a rare (once every 1000 or so) 
> failure in the TLS handshake in our tests.
>
> In the "case 2" section of _gnutls_pkcs1_rsa_encrypt(), there's a big 
> loop that attempts to replace any zero bytes with a non-zero random 
> number.   This line in particular:
>
>                if (i<2) ps[i] = rnd[i];
>                else ps[i] = GMAX( rnd[2] + ps[i-1] + ps[i-2], rnd[1]);
>
> is wrong, because in some cases "rnd[2] + ps[i-1] + ps[i-2]" is 256 or 
> 512, which will be greater than the random byte, but end up being stored 
> as zero.

Right.

Further, the CPP macros GMIN/GMAX was using unquoted arguments.  I
fixed this in the development branch.

> After poking around in this function, I have to raise the question:  Is 
> this loop's complexity absolutely necessary?  For every byte in the 
> random buffer, 3 new random bytes are fetched from the random pool, and 
> almost always only the 3rd byte is used.  This seems like a waste of the 
> random pool

I agree.

> and my hunch is that the fetch of 3 random bytes was meant to go
> OUTSIDE the loop.

I'm not sure about this, but in either case, it appears to me that the
replaced zero byte would have a skewed bias (that is, more skewed than
might be expected from the knowledge that it must be 1-255).  Not that
this make any critical difference, though.

> Attached is a patch against 1.0.19 which moves the 3-random-byte fetch 
> outside the loop, and adds a mask inside the GMAX so that only the lower 
> 8 bits count.

Whatever the intention was, IMHO, the logic was convoluted, I have now
installed code which says:

        if ((ret =
             _gnutls_get_random(ps, psize, GNUTLS_STRONG_RANDOM)) < 0) {
            gnutls_assert();
            gnutls_afree(edata);
            return ret;
        }
        for (i = 0; i < psize; i++)
          while (ps[i] == 0) {
            if ((ret =
                 _gnutls_get_random(&ps[i], 1, GNUTLS_STRONG_RANDOM)) < 0) {
                gnutls_assert();
                gnutls_afree(edata);
                return ret;
            }
          }
        }

It seems easier to argue for correctness of the above.  As this is
important code, more eyes on it would be appreciated.  One might have
qualms about a possible infinite loop.  I looked at PKCS#1 1.5 type 2
padding in OpenSSL, and it also loop until non-zero random data is
generated.  Nettle just replace 0 with 1.  People that want to review
the code might find it helpful to review RFC 2313 section 8 and 8.1:

   A block type BT, a padding string PS, and the data D shall be
   formatted into an octet string EB, the encryption block.

              EB = 00 || BT || PS || 00 || D .           (1)

   The block type BT shall be a single octet indicating the structure of
   the encryption block. For this version of the document it shall have
   value 00, 01, or 02. For a private- key operation, the block type
   shall be 00 or 01. For a public-key operation, it shall be 02.

   The padding string PS shall consist of k-3-||D|| octets. For block
   type 00, the octets shall have value 00; for block type 01, they
   shall have value FF; and for block type 02, they shall be
   pseudorandomly generated and nonzero. This makes the length of the
   encryption block EB equal to k.

Thanks,
Simon