From de81309dd32ec364fcd1fe351beb69859574a3ba Mon Sep 17 00:00:00 2001
From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Sun, 4 Aug 2013 19:34:07 +0000
Subject: [PATCH] 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
---
 sshbn.c   | 15 +++++++++++++--
 sshdss.c  | 38 +++++++++++++++++++++++++++++---------
 sshrsa.c  | 16 +++++++++++++---
 sshrsag.c |  4 ++++
 4 files changed, 59 insertions(+), 14 deletions(-)

diff --git a/sshbn.c b/sshbn.c
index 76529cfa..a2067831 100644
--- 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 3ea36952..84fcdac7 100644
--- 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 3bd971f8..fb0bcaa9 100644
--- 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 dbe89409..d754890d 100644
--- 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);
 
     /*
-- 
2.11.0