Make modinv able to return NULL if its inputs are not coprime, and

check for that return value everywhere it is used.

git-svn-id: svn://svn.tartarus.org/sgt/putty@9990 cda61777-01e9-0310-a592-d414129be87e

diff --git a/sshbn.c b/sshbn.c
index 76529cf..a206783 100644 (file)
--- a/sshbn.c
+++ b/sshbn.c
@@ -869,6 +869,7 @@ Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
     len = mod[0];
     r = bn_power_2(BIGNUM_INT_BITS * len);
     inv = modinv(mod, r);
+    assert(inv); /* cannot fail, since mod is odd and r is a power of 2 */
 
     /*
      * Multiply the base by r mod n, to get it into Montgomery
@@ -1634,8 +1635,18 @@ Bignum modinv(Bignum number, Bignum modulus)
     assert(modulus[modulus[0]] != 0);
 
     while (bignum_cmp(b, One) != 0) {
-       Bignum t = newbn(b[0]);
-       Bignum q = newbn(a[0]);
+       Bignum t, q;
+
+        if (bignum_cmp(b, Zero) == 0) {
+            /*
+             * Found a common factor between the inputs, so we cannot
+             * return a modular inverse at all.
+             */
+            return NULL;
+        }
+
+        t = newbn(b[0]);
+       q = newbn(a[0]);
        bigdivmod(a, b, t, q);
        while (t[0] > 1 && t[t[0]] == 0)
            t[0]--;

diff --git a/sshdss.c b/sshdss.c
index 3ea3695..84fcdac 100644 (file)
--- a/sshdss.c
+++ b/sshdss.c
@@ -286,6 +286,11 @@ static int dss_verifysig(void *key, char *sig, int siglen,
      * Step 1. w <- s^-1 mod q.
      */
     w = modinv(s, dss->q);
+    if (!w) {
+        freebn(r);
+        freebn(s);
+        return 0;
+    }
 
     /*
      * Step 2. u1 <- SHA(message) * w mod q.
@@ -609,16 +614,32 @@ static unsigned char *dss_sign(void *key, char *data, int datalen, int *siglen)
     SHA512_Init(&ss);
     SHA512_Bytes(&ss, digest512, sizeof(digest512));
     SHA512_Bytes(&ss, digest, sizeof(digest));
-    SHA512_Final(&ss, digest512);
 
-    smemclr(&ss, sizeof(ss));
+    while (1) {
+        SHA512_State ss2 = ss;         /* structure copy */
+        SHA512_Final(&ss2, digest512);
+
+        smemclr(&ss2, sizeof(ss2));
+
+        /*
+         * Now convert the result into a bignum, and reduce it mod q.
+         */
+        proto_k = bignum_from_bytes(digest512, 64);
+        k = bigmod(proto_k, dss->q);
+        freebn(proto_k);
+        kinv = modinv(k, dss->q);             /* k^-1 mod q */
+        if (!kinv) {                           /* very unlikely */
+            freebn(k);
+            /* Perturb the hash to think of a different k. */
+            SHA512_Bytes(&ss, "x", 1);
+            /* Go round and try again. */
+            continue;
+        }
+
+        break;
+    }
 
-    /*
-     * Now convert the result into a bignum, and reduce it mod q.
-     */
-    proto_k = bignum_from_bytes(digest512, 64);
-    k = bigmod(proto_k, dss->q);
-    freebn(proto_k);
+    smemclr(&ss, sizeof(ss));
 
     smemclr(digest512, sizeof(digest512));
 
@@ -630,7 +651,6 @@ static unsigned char *dss_sign(void *key, char *data, int datalen, int *siglen)
     freebn(gkp);
 
     hash = bignum_from_bytes(digest, 20);
-    kinv = modinv(k, dss->q);         /* k^-1 mod q */
     hxr = bigmuladd(dss->x, r, hash);  /* hash + x*r */
     s = modmul(kinv, hxr, dss->q);     /* s = k^-1 * (hash + x*r) mod q */
     freebn(hxr);

diff --git a/sshrsa.c b/sshrsa.c
index 3bd971f..fb0bcaa 100644 (file)
--- a/sshrsa.c
+++ b/sshrsa.c
@@ -273,9 +273,18 @@ static Bignum rsa_privkey_op(Bignum input, struct RSAKey *key)
            bignum_cmp(random, key->modulus) >= 0) {
            freebn(random);
            continue;
-       } else {
-           break;
        }
+
+        /*
+         * Also, make sure it has an inverse mod modulus.
+         */
+        random_inverse = modinv(random, key->modulus);
+        if (!random_inverse) {
+           freebn(random);
+           continue;
+        }
+
+        break;
     }
 
     /*
@@ -294,7 +303,6 @@ static Bignum rsa_privkey_op(Bignum input, struct RSAKey *key)
      */
     random_encrypted = crt_modpow(random, key->exponent,
                                   key->modulus, key->p, key->q, key->iqmp);
-    random_inverse = modinv(random, key->modulus);
     input_blinded = modmul(input, random_encrypted, key->modulus);
     ret_blinded = crt_modpow(input_blinded, key->private_exponent,
                              key->modulus, key->p, key->q, key->iqmp);
@@ -443,6 +451,8 @@ int rsa_verify(struct RSAKey *key)
 
        freebn(key->iqmp);
        key->iqmp = modinv(key->q, key->p);
+        if (!key->iqmp)
+            return 0;
     }
 
     /*

diff --git a/sshrsag.c b/sshrsag.c
index dbe8940..d754890 100644 (file)
--- a/sshrsag.c
+++ b/sshrsag.c
@@ -2,6 +2,8 @@
  * RSA key generation.
  */
 
+#include <assert.h>
+
 #include "ssh.h"
 
 #define RSA_EXPONENT 37                       /* we like this prime */
@@ -92,8 +94,10 @@ int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn,
     freebn(pm1);
     freebn(qm1);
     key->private_exponent = modinv(key->exponent, phi_n);
+    assert(key->private_exponent);
     pfn(pfnparam, PROGFN_PROGRESS, 3, 4);
     key->iqmp = modinv(key->q, key->p);
+    assert(key->iqmp);
     pfn(pfnparam, PROGFN_PROGRESS, 3, 5);
 
     /*