generate a 2*need size (~300 instead of 1024/2048) random private

exponent during the DH key agreement. according to Niels (the great
german advisor) this is safe since /etc/primes contains strong
primes only.

References:
        P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key
        agreement with short exponents, In Advances in Cryptology
        - EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332-343.

4 files changed, 31 insertions, 13 deletions

diff --git a/usr.bin/ssh/kex.c b/usr.bin/ssh/kex.c
index 1038546cadf..308ffb1b66f 100644
--- a/usr.bin/ssh/kex.c
+++ b/usr.bin/ssh/kex.c
@@ -23,7 +23,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: kex.c,v 1.21 2001/02/11 12:59:24 markus Exp $");
+RCSID("$OpenBSD: kex.c,v 1.22 2001/03/05 17:17:20 markus Exp $");
 
 #include <openssl/crypto.h>
 #include <openssl/bio.h>
@@ -138,15 +138,33 @@ dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 }
 
 void
-dh_gen_key(DH *dh)
+dh_gen_key(DH *dh, int need)
 {
-	int tries = 0;
+	int i, bits_set = 0, tries = 0;
 
+	if (dh->p == NULL)
+		fatal("dh_gen_key: dh->p == NULL");
+	if (2*need >= BN_num_bits(dh->p))
+		fatal("dh_gen_key: group too small: %d (2*need %d)",
+		    BN_num_bits(dh->p), 2*need);
 	do {
+		if (dh->priv_key != NULL)
+			BN_free(dh->priv_key);
+		dh->priv_key = BN_new();
+		if (dh->priv_key == NULL)
+			fatal("dh_gen_key: BN_new failed");
+		/* generate a 2*need bits random private exponent */
+		if (!BN_rand(dh->priv_key, 2*need, 0, 0))
+			fatal("dh_gen_key: BN_rand failed");
 		if (DH_generate_key(dh) == 0)
 			fatal("DH_generate_key");
+		for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
+			if (BN_is_bit_set(dh->priv_key, i))
+				bits_set++;
+		debug("dh_gen_key: priv key bits set: %d/%d",
+		    bits_set, BN_num_bits(dh->priv_key));
 		if (tries++ > 10)
-			fatal("dh_new_group1: too many bad keys: giving up");
+			fatal("dh_gen_key: too many bad keys: giving up");
 	} while (!dh_pub_is_valid(dh, dh->pub_key));
 }
 
diff --git a/usr.bin/ssh/kex.h b/usr.bin/ssh/kex.h
index 90496fbdf46..5004699d9c3 100644
--- a/usr.bin/ssh/kex.h
+++ b/usr.bin/ssh/kex.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kex.h,v 1.14 2001/02/11 12:59:24 markus Exp $	*/
+/*	$OpenBSD: kex.h,v 1.15 2001/03/05 17:17:20 markus Exp $	*/
 
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
@@ -106,7 +106,7 @@ void	packet_set_kex(Kex *k);
 int	dh_pub_is_valid(DH *dh, BIGNUM *dh_pub);
 DH	*dh_new_group_asc(const char *, const char *);
 DH	*dh_new_group(BIGNUM *, BIGNUM *);
-void	dh_gen_key(DH *);
+void	dh_gen_key(DH *, int);
 DH	*dh_new_group1(void);
 
 u_char *
diff --git a/usr.bin/ssh/sshconnect2.c b/usr.bin/ssh/sshconnect2.c
index 8b523232f0c..0baecf0a55d 100644
--- a/usr.bin/ssh/sshconnect2.c
+++ b/usr.bin/ssh/sshconnect2.c
@@ -23,7 +23,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: sshconnect2.c,v 1.49 2001/02/28 09:57:07 markus Exp $");
+RCSID("$OpenBSD: sshconnect2.c,v 1.50 2001/03/05 17:17:21 markus Exp $");
 
 #include <openssl/bn.h>
 #include <openssl/md5.h>
@@ -171,7 +171,7 @@ ssh_dh1_client(Kex *kex, char *host, struct sockaddr *hostaddr,
 	debug("Sending SSH2_MSG_KEXDH_INIT.");
 	/* generate and send 'e', client DH public key */
 	dh = dh_new_group1();
-	dh_gen_key(dh);
+	dh_gen_key(dh, kex->we_need * 8);
 	packet_start(SSH2_MSG_KEXDH_INIT);
 	packet_put_bignum2(dh->pub_key);
 	packet_send();
@@ -316,7 +316,7 @@ ssh_dhgex_client(Kex *kex, char *host, struct sockaddr *hostaddr,
 	u_char *kbuf;
 	u_char *hash;
 
-	nbits = dh_estimate(kex->enc[MODE_OUT].cipher->key_len * 8);
+	nbits = dh_estimate(kex->we_need * 8);
 
 	debug("Sending SSH2_MSG_KEX_DH_GEX_REQUEST.");
 	packet_start(SSH2_MSG_KEX_DH_GEX_REQUEST);
@@ -342,7 +342,7 @@ ssh_dhgex_client(Kex *kex, char *host, struct sockaddr *hostaddr,
 	packet_get_bignum2(g, &dlen);
 	dh = dh_new_group(g, p);
 
-	dh_gen_key(dh);
+	dh_gen_key(dh, kex->we_need * 8);
 
 #ifdef DEBUG_KEXDH
 	fprintf(stderr, "\np= ");
diff --git a/usr.bin/ssh/sshd.c b/usr.bin/ssh/sshd.c
index 3c51916a346..57b7d70a791 100644
--- a/usr.bin/ssh/sshd.c
+++ b/usr.bin/ssh/sshd.c
@@ -40,7 +40,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: sshd.c,v 1.172 2001/03/04 17:42:28 millert Exp $");
+RCSID("$OpenBSD: sshd.c,v 1.173 2001/03/05 17:17:21 markus Exp $");
 
 #include <openssl/dh.h>
 #include <openssl/bn.h>
@@ -1495,7 +1495,7 @@ ssh_dh1_server(Kex *kex, Buffer *client_kexinit, Buffer *server_kexinit)
 /* KEXDH */
 	/* generate DH key */
 	dh = dh_new_group1();			/* XXX depends on 'kex' */
-	dh_gen_key(dh);
+	dh_gen_key(dh, kex->we_need * 8);
 
 	debug("Wait SSH2_MSG_KEXDH_INIT.");
 	packet_read_expect(&payload_len, SSH2_MSG_KEXDH_INIT);
@@ -1638,7 +1638,7 @@ ssh_dhgex_server(Kex *kex, Buffer *client_kexinit, Buffer *server_kexinit)
 
 	/* Compute our exchange value in parallel with the client */
 
-	dh_gen_key(dh);
+	dh_gen_key(dh, kex->we_need * 8);
 
 	debug("Wait SSH2_MSG_KEX_DH_GEX_INIT.");
 	packet_read_expect(&payload_len, SSH2_MSG_KEX_DH_GEX_INIT);