[gnutls-dev] bug in _gnutls_pkcs1_rsa_encrypt

[Robey Pointer]

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.

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, and my hunch is that the fetch of 3 random bytes was meant 
to go OUTSIDE the loop.

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.

This bug appears to be in gnutls 1.1.16 too, though the code has been 
reformatted.

robey

--- gnutls-1.0.19/lib/gnutls_pk.c.orig  2004-08-04 14:36:02.000000000 -0700
+++ gnutls-1.0.19/lib/gnutls_pk.c       2004-08-16 16:47:35.000000000 -0700
@@ -54,6 +54,7 @@
        int ret;
        GNUTLS_MPI m, res;
        opaque *edata, *ps;
+       opaque rnd[3];
        size_t k, psize;
        size_t mod_bits;
 
@@ -95,23 +96,22 @@
                        gnutls_afree(edata);
                        return ret;
                }
-               for (i = 0; i < psize; i++) {
-                       opaque rnd[3];
 
-                       /* Read three random bytes that will be
-                        * used to replace the zeros.
-                        */
-                       if ( (ret=_gnutls_get_random( rnd, 3, 
GNUTLS_STRONG_RANDOM)) < 0) {
-                               gnutls_assert();
-                               gnutls_afree(edata);
-                               return ret;
-                       }
-                       /* use non zero values for 
-                        * the first two.
-                        */
-                       if (rnd[0]==0) rnd[0] = 0xaf;
-                       if (rnd[1]==0) rnd[1] = 0xae;
+               /* Read three random bytes that will be
+                * used to replace the zeros.
+                */
+               if ( (ret=_gnutls_get_random( rnd, 3, GNUTLS_STRONG_RANDOM)) < 
0) {
+                       gnutls_assert();
+                       gnutls_afree(edata);
+                       return ret;
+               }
+               /* use non zero values for 
+                * the first two.
+                */
+               if (rnd[0]==0) rnd[0] = 0xaf;
+               if (rnd[1]==0) rnd[1] = 0xae;
 
+               for (i = 0; i < psize; i++) {
                        if (ps[i] == 0) {
                                /* If the first one is zero then set it to 
rnd[0].
                                 * If the second one is zero then set it to 
rnd[1].
@@ -119,7 +119,7 @@
                                 * rnd[1] if the value == 0.
                                 */
                                if (i<2) ps[i] = rnd[i];
-                               else ps[i] = GMAX( rnd[2] + ps[i-1] + ps[i-2], 
rnd[1]);
+                               else ps[i] = GMAX( (rnd[2] + ps[i-1] + ps[i-2]) 
& 0xff, rnd[1]);
                        }
                }
                break;