# HG changeset patch
# User Matt Johnston <matt@ucc.asn.au>
# Date 1115265501 0
# Node ID c9483550701bc5b15997ac0fed72847d754722d7
# Parent  c44df7123b0a3b4ab2e8042484b013bb27d1250c
- refactored random mp_int generation and byte->mp_int code
- added RSA blinding

diff -r c44df7123b0a -r c9483550701b bignum.c
--- a/bignum.c	Wed May 04 15:31:17 2005 +0000
+++ b/bignum.c	Thu May 05 03:58:21 2005 +0000
@@ -52,9 +52,9 @@
     va_end(args);
 }
 
-void bytestomp(mp_int *mp, unsigned char* bytes, unsigned int len) {
+void bytes_to_mp(mp_int *mp, const unsigned char* bytes, unsigned int len) {
 
-	if (mp_read_unsigned_bin(mp, bytes, len) != MP_OKAY) {
+	if (mp_read_unsigned_bin(mp, (unsigned char*)bytes, len) != MP_OKAY) {
 		dropbear_exit("mem alloc error");
 	}
 }
diff -r c44df7123b0a -r c9483550701b bignum.h
--- a/bignum.h	Wed May 04 15:31:17 2005 +0000
+++ b/bignum.h	Thu May 05 03:58:21 2005 +0000
@@ -29,7 +29,7 @@
 
 void m_mp_init(mp_int *mp);
 void m_mp_init_multi(mp_int *mp, ...);
-void bytestomp(mp_int *mp, unsigned char* bytes, unsigned int len);
+void bytes_to_mp(mp_int *mp, const unsigned char* bytes, unsigned int len);
 void sha1_process_mp(hash_state *hs, mp_int *mp);
 
 #endif /* _BIGNUM_H_ */
diff -r c44df7123b0a -r c9483550701b common-kex.c
--- a/common-kex.c	Wed May 04 15:31:17 2005 +0000
+++ b/common-kex.c	Thu May 05 03:58:21 2005 +0000
@@ -469,18 +469,13 @@
 	DEF_MP_INT(dh_p);
 	DEF_MP_INT(dh_q);
 	DEF_MP_INT(dh_g);
-	unsigned char randbuf[DH_P_LEN];
-	int dh_q_len;
 
 	TRACE(("enter send_msg_kexdh_reply"))
 	
 	m_mp_init_multi(&dh_g, &dh_p, &dh_q, NULL);
 
 	/* read the prime and generator*/
-	if (mp_read_unsigned_bin(&dh_p, (unsigned char*)dh_p_val, DH_P_LEN)
-			!= MP_OKAY) {
-		dropbear_exit("Diffie-Hellman error");
-	}
+	bytes_to_mp(&dh_p, (unsigned char*)dh_p_val, DH_P_LEN);
 	
 	if (mp_set_int(&dh_g, DH_G_VAL) != MP_OKAY) {
 		dropbear_exit("Diffie-Hellman error");
@@ -495,16 +490,8 @@
 		dropbear_exit("Diffie-Hellman error");
 	}
 
-	dh_q_len = mp_unsigned_bin_size(&dh_q);
-
-	/* calculate our random value dh_y */
-	do {
-		assert((unsigned int)dh_q_len <= sizeof(randbuf));
-		genrandom(randbuf, dh_q_len);
-		if (mp_read_unsigned_bin(dh_priv, randbuf, dh_q_len) != MP_OKAY) {
-			dropbear_exit("Diffie-Hellman error");
-		}
-	} while (mp_cmp(dh_priv, &dh_q) == MP_GT || mp_cmp_d(dh_priv, 0) != MP_GT);
+	/* Generate a private portion 0 < dh_priv < dh_q */
+	gen_random_mpint(&dh_q, dh_priv);
 
 	/* f = g^y mod p */
 	if (mp_exptmod(&dh_g, dh_priv, &dh_p, dh_pub) != MP_OKAY) {
@@ -526,10 +513,7 @@
 
 	/* read the prime and generator*/
 	mp_init(&dh_p);
-	if (mp_read_unsigned_bin(&dh_p, (unsigned char*)dh_p_val, DH_P_LEN)
-			!= MP_OKAY) {
-		dropbear_exit("Diffie-Hellman error");
-	}
+	bytes_to_mp(&dh_p, dh_p_val, DH_P_LEN);
 
 	/* Check that dh_pub_them (dh_e or dh_f) is in the range [1, p-1] */
 	if (mp_cmp(dh_pub_them, &dh_p) != MP_LT 
diff -r c44df7123b0a -r c9483550701b dss.c
--- a/dss.c	Wed May 04 15:31:17 2005 +0000
+++ b/dss.c	Thu May 05 03:58:21 2005 +0000
@@ -190,10 +190,8 @@
 	/* create the signature - s' and r' are the received signatures in buf */
 	/* w = (s')-1 mod q */
 	/* let val1 = s' */
-	if (mp_read_unsigned_bin(&val1, &string[SHA1_HASH_SIZE], SHA1_HASH_SIZE)
-			!= MP_OKAY) {
-		goto out;
-	}
+	bytes_to_mp(&val1, &string[SHA1_HASH_SIZE], SHA1_HASH_SIZE);
+
 	if (mp_cmp(&val1, key->q) != MP_LT) {
 		TRACE(("verify failed, s' >= q"))
 		goto out;
@@ -205,9 +203,8 @@
 
 	/* u1 = ((SHA(M')w) mod q */
 	/* let val1 = SHA(M') = msghash */
-	if (mp_read_unsigned_bin(&val1, msghash, SHA1_HASH_SIZE) != MP_OKAY) {
-		goto out;
-	}
+	bytes_to_mp(&val1, msghash, SHA1_HASH_SIZE);
+
 	/* let val3 = u1 = ((SHA(M')w) mod q */
 	if (mp_mulmod(&val1, &val2, key->q, &val3) != MP_OKAY) {
 		goto out;
@@ -215,10 +212,7 @@
 
 	/* u2 = ((r')w) mod q */
 	/* let val1 = r' */
-	if (mp_read_unsigned_bin(&val1, &string[0], SHA1_HASH_SIZE)
-			!= MP_OKAY) {
-		goto out;
-	}
+	bytes_to_mp(&val1, &string[0], SHA1_HASH_SIZE);
 	if (mp_cmp(&val1, key->q) != MP_LT) {
 		TRACE(("verify failed, r' >= q"))
 		goto out;
@@ -306,8 +300,6 @@
 	unsigned char *privkeytmp;
 	unsigned char proto_k[SHA512_HASH_SIZE];
 	DEF_MP_INT(dss_protok);
-#else
-	unsigned char kbuf[SHA1_HASH_SIZE];
 #endif
 	DEF_MP_INT(dss_k);
 	DEF_MP_INT(dss_m);
@@ -345,22 +337,16 @@
 
 	/* generate k */
 	m_mp_init(&dss_protok);
-	bytestomp(&dss_protok, proto_k, SHA512_HASH_SIZE);
+	bytes_to_mp(&dss_protok, proto_k, SHA512_HASH_SIZE);
 	mp_mod(&dss_protok, key->q, &dss_k);
 	mp_clear(&dss_protok);
 	m_burn(proto_k, SHA512_HASH_SIZE);
 #else /* DSS_PROTOK not defined*/
-	do {
-		genrandom(kbuf, SHA1_HASH_SIZE);
-		if (mp_read_unsigned_bin(&dss_k, kbuf, SHA1_HASH_SIZE) != MP_OKAY) {
-			dropbear_exit("dss error");
-		}
-	} while (mp_cmp(&dss_k, key->q) == MP_GT || mp_cmp_d(&dss_k, 0) != MP_GT);
-	m_burn(kbuf, SHA1_HASH_SIZE);
+	gen_random_mpint(key->q, &dss_k);
 #endif
 
 	/* now generate the actual signature */
-	bytestomp(&dss_m, msghash, SHA1_HASH_SIZE);
+	bytes_to_mp(&dss_m, msghash, SHA1_HASH_SIZE);
 
 	/* g^k mod p */
 	if (mp_exptmod(key->g, &dss_k, key->p, &dss_temp1) !=  MP_OKAY) {
diff -r c44df7123b0a -r c9483550701b gendss.c
--- a/gendss.c	Wed May 04 15:31:17 2005 +0000
+++ b/gendss.c	Thu May 05 03:58:21 2005 +0000
@@ -77,10 +77,7 @@
 	buf[0] |= 0x80; /* top bit high */
 	buf[QSIZE-1] |= 0x01; /* bottom bit high */
 
-	if (mp_read_unsigned_bin(key->q, buf, QSIZE) != MP_OKAY) {
-		fprintf(stderr, "dss key generation failed\n");
-		exit(1);
-	}
+	bytes_to_mp(key->q, buf, QSIZE);
 
 	/* 18 rounds are required according to HAC */
 	if (mp_prime_next_prime(key->q, 18, 0) != MP_OKAY) {
@@ -116,10 +113,7 @@
 		buf[0] |= 0x80; /* set the top bit high */
 
 		/* X is a random mp_int */
-		if (mp_read_unsigned_bin(&tempX, buf, size) != MP_OKAY) {
-			fprintf(stderr, "dss key generation failed\n");
-			exit(1);
-		}
+		bytes_to_mp(&tempX, buf, size);
 
 		/* C = X mod 2q */
 		if (mp_mod(&tempX, &temp2q, &tempC) != MP_OKAY) {
@@ -147,6 +141,7 @@
 	} while (!result);
 
 	mp_clear_multi(&tempX, &tempC, &tempP, &temp2q, NULL);
+	m_burn(buf, size);
 	m_free(buf);
 }
 
@@ -189,22 +184,7 @@
 
 static void getx(dss_key *key) {
 
-	DEF_MP_INT(val);
-	char buf[QSIZE];
-	
-	m_mp_init(&val);
-	
-	do {
-		genrandom(buf, QSIZE);
-
-		if (mp_read_unsigned_bin(&val, buf, QSIZE) != MP_OKAY) {
-			fprintf(stderr, "dss key generation failed\n");
-		}
-	} while ((mp_cmp_d(&val, 1) == MP_GT) && (mp_cmp(&val, key->q) == MP_LT));
-
-	mp_copy(&val, key->x);
-	mp_clear(&val);
-
+	gen_random_mpint(key->q, key->x);
 }
 
 static void gety(dss_key *key) {
diff -r c44df7123b0a -r c9483550701b genrsa.c
--- a/genrsa.c	Wed May 04 15:31:17 2005 +0000
+++ b/genrsa.c	Thu May 05 03:58:21 2005 +0000
@@ -108,10 +108,7 @@
 		genrandom(buf, size+1);
 		buf[0] |= 0x80; /* MSB set */
 
-		if (mp_read_unsigned_bin(prime, buf, size+1) != MP_OKAY) {
-			fprintf(stderr, "rsa generation failed\n");
-			exit(1);
-		}
+		bytes_to_mp(prime, buf, size+1);
 
 		/* find the next integer which is prime, 8 round of miller-rabin */
 		if (mp_prime_next_prime(prime, 8, 0) != MP_OKAY) {
diff -r c44df7123b0a -r c9483550701b random.c
--- a/random.c	Wed May 04 15:31:17 2005 +0000
+++ b/random.c	Thu May 05 03:58:21 2005 +0000
@@ -25,6 +25,7 @@
 #include "includes.h"
 #include "buffer.h"
 #include "dbutil.h"
+#include "bignum.h"
 
 int donerandinit = 0;
 
@@ -159,3 +160,38 @@
 	}
 	m_burn(hash, sizeof(hash));
 }
+
+/* Generates a random mp_int. 
+ * max is a *mp_int specifying an upper bound.
+ * rand must be an initialised *mp_int for the result.
+ * the result rand satisfies:  0 < rand < max 
+ * */
+void gen_random_mpint(mp_int *max, mp_int *rand) {
+
+	unsigned char *randbuf = NULL;
+	unsigned int len = 0;
+	const char masks[] = {0xff, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f};
+
+	const int size_bits = mp_count_bits(max);
+
+	len = size_bits / 8;
+	if ((size_bits % 8) != 0) {
+		len += 1;
+	}
+
+	randbuf = (unsigned char*)m_malloc(len);
+	do {
+		genrandom(randbuf, len);
+		/* Mask out the unrequired bits - mp_read_unsigned_bin expects
+		 * MSB first.*/
+		randbuf[0] &= masks[size_bits % 8];
+
+		bytes_to_mp(rand, randbuf, len);
+
+		/* keep regenerating until we get one satisfying
+		 * 0 < rand < max    */
+	} while ( ( (max != NULL) && (mp_cmp(rand, max) != MP_LT) )
+			|| (mp_cmp_d(rand, 0) != MP_GT) );
+	m_burn(randbuf, len);
+	m_free(randbuf);
+}
diff -r c44df7123b0a -r c9483550701b random.h
--- a/random.h	Wed May 04 15:31:17 2005 +0000
+++ b/random.h	Thu May 05 03:58:21 2005 +0000
@@ -25,8 +25,11 @@
 #ifndef _RANDOM_H_
 #define _RANDOM_H_
 
+struct mp_int;
+
 void seedrandom();
 void genrandom(unsigned char* buf, int len);
 void addrandom(unsigned char* buf, int len);
+void gen_random_mpint(mp_int *max, mp_int *rand);
 
 #endif /* _RANDOM_H_ */
diff -r c44df7123b0a -r c9483550701b rsa.c
--- a/rsa.c	Wed May 04 15:31:17 2005 +0000
+++ b/rsa.c	Thu May 05 03:58:21 2005 +0000
@@ -38,8 +38,9 @@
 
 #ifdef DROPBEAR_RSA 
 
-static mp_int * rsa_pad_em(rsa_key * key,
-		const unsigned char * data, unsigned int len);
+static void rsa_pad_em(rsa_key * key,
+		const unsigned char * data, unsigned int len,
+		mp_int * rsa_em);
 
 /* Load a public rsa key from a buffer, initialising the values.
  * The key will have the same format as buf_put_rsa_key.
@@ -203,14 +204,14 @@
 	unsigned int slen;
 	DEF_MP_INT(rsa_s);
 	DEF_MP_INT(rsa_mdash);
-	mp_int *rsa_em = NULL;
+	DEF_MP_INT(rsa_em);
 	int ret = DROPBEAR_FAILURE;
 
 	TRACE(("enter buf_rsa_verify"))
 
 	assert(key != NULL);
 
-	m_mp_init_multi(&rsa_mdash, &rsa_s, NULL);
+	m_mp_init_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL);
 
 	slen = buf_getint(buf);
 	if (slen != (unsigned int)mp_unsigned_bin_size(key->n)) {
@@ -231,29 +232,25 @@
 	}
 
 	/* create the magic PKCS padded value */
-	rsa_em = rsa_pad_em(key, data, len);
+	rsa_pad_em(key, data, len, &rsa_em);
 
 	if (mp_exptmod(&rsa_s, key->e, key->n, &rsa_mdash) != MP_OKAY) {
 		TRACE(("failed exptmod rsa_s"))
 		goto out;
 	}
 
-	if (mp_cmp(rsa_em, &rsa_mdash) == MP_EQ) {
+	if (mp_cmp(&rsa_em, &rsa_mdash) == MP_EQ) {
 		/* signature is valid */
 		TRACE(("success!"))
 		ret = DROPBEAR_SUCCESS;
 	}
 
 out:
-	if (rsa_em) {
-		mp_clear(rsa_em);
-		m_free(rsa_em);
-	}
-	mp_clear_multi(&rsa_mdash, &rsa_s, NULL);
+	mp_clear_multi(&rsa_mdash, &rsa_s, &rsa_em, NULL);
 	TRACE(("leave buf_rsa_verify: ret %d", ret))
 	return ret;
+}
 
-}
 #endif /* DROPBEAR_SIGNKEY_VERIFY */
 
 /* Sign the data presented with key, writing the signature contents
@@ -264,22 +261,56 @@
 	unsigned int nsize, ssize;
 	unsigned int i;
 	DEF_MP_INT(rsa_s);
-	mp_int *rsa_em = NULL;
+	DEF_MP_INT(rsa_tmp1);
+	DEF_MP_INT(rsa_tmp2);
+	DEF_MP_INT(rsa_tmp3);
+	unsigned char *tmpbuf;
 	
 	TRACE(("enter buf_put_rsa_sign"))
 	assert(key != NULL);
 
-	rsa_em = rsa_pad_em(key, data, len);
+	m_mp_init_multi(&rsa_s, &rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL);
 
-	m_mp_init(&rsa_s);
+	rsa_pad_em(key, data, len, &rsa_tmp1);
 
 	/* the actual signing of the padded data */
+
+#define RSA_BLINDING
+#ifdef RSA_BLINDING
+
+	/* With blinding, s = (r^(-1))((em)*r^e)^d mod n */
+
+	/* generate the r blinding value */
+	/* rsa_tmp2 is r */
+	gen_random_mpint(key->n, &rsa_tmp2);
+
+	/* rsa_tmp1 is em */
+	/* em' = em * r^e mod n */
+
+	mp_exptmod(&rsa_tmp2, key->e, key->n, &rsa_s); /* rsa_s used as a temp var*/
+	mp_invmod(&rsa_tmp2, key->n, &rsa_tmp3);
+	mp_mulmod(&rsa_tmp1, &rsa_s, key->n, &rsa_tmp2);
+
+	/* rsa_tmp2 is em' */
+	/* s' = (em')^d mod n */
+	mp_exptmod(&rsa_tmp2, key->d, key->n, &rsa_tmp1);
+
+	/* rsa_tmp1 is s' */
+	/* rsa_tmp3 is r^(-1) mod n */
+	/* s = (s')r^(-1) mod n */
+	mp_mulmod(&rsa_tmp1, &rsa_tmp3, key->n, &rsa_s);
+
+#else
+
 	/* s = em^d mod n */
-	if (mp_exptmod(rsa_em, key->d, key->n, &rsa_s) != MP_OKAY) {
+	/* rsa_tmp1 is em */
+	if (mp_exptmod(&rsa_tmp1, key->d, key->n, &rsa_s) != MP_OKAY) {
 		dropbear_exit("rsa error");
 	}
-	mp_clear(rsa_em);
-	m_free(rsa_em);
+
+#endif /* RSA_BLINDING */
+
+	mp_clear_multi(&rsa_tmp1, &rsa_tmp2, &rsa_tmp3, NULL);
 	
 	/* create the signature to return */
 	buf_putstring(buf, SSH_SIGNKEY_RSA, SSH_SIGNKEY_RSA_LEN);
@@ -318,9 +349,12 @@
  *
  * prefix is the ASN1 designator prefix,
  * hex 30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14
+ *
+ * rsa_em must be a pointer to an initialised mp_int.
  */
-static mp_int * rsa_pad_em(rsa_key * key,
-		const unsigned char * data, unsigned int len) {
+static void rsa_pad_em(rsa_key * key,
+		const unsigned char * data, unsigned int len, 
+		mp_int * rsa_em) {
 
 	/* ASN1 designator (including the 0x00 preceding) */
 	const char rsa_asn1_magic[] = 
@@ -330,7 +364,6 @@
 	buffer * rsa_EM = NULL;
 	hash_state hs;
 	unsigned int nsize;
-	mp_int * rsa_em = NULL;
 	
 	assert(key != NULL);
 	assert(data != NULL);
@@ -358,16 +391,9 @@
 
 	/* Create the mp_int from the encoded bytes */
 	buf_setpos(rsa_EM, 0);
-	rsa_em = (mp_int*)m_malloc(sizeof(mp_int));
-	m_mp_init(rsa_em);
-	if (mp_read_unsigned_bin(rsa_em, buf_getptr(rsa_EM, rsa_EM->size),
-				rsa_EM->size) != MP_OKAY) {
-		dropbear_exit("rsa error");
-	}
+	bytes_to_mp(rsa_em, buf_getptr(rsa_EM, rsa_EM->size),
+			rsa_EM->size);
 	buf_free(rsa_EM);
-
-	return rsa_em;
-
 }
 
 #endif /* DROPBEAR_RSA */