From 7bd5a86050fa6fb39e2928b25f46df4f7dc24600 Mon Sep 17 00:00:00 2001 From: simon Date: Sat, 10 Mar 2001 11:04:07 +0000 Subject: [PATCH] Add support for using Diffie-Hellman with short exponents (sshdh.c contains a reference to a paper on the subject). Reduces time taken for DH group exchange to the point where it's viable to enable it all the time, so I have. :-) git-svn-id: svn://svn.tartarus.org/sgt/putty@991 cda61777-01e9-0310-a592-d414129be87e --- ssh.c | 46 ++++++++++++++++++++++++---------------------- ssh.h | 2 +- sshdh.c | 40 ++++++++++++++++++++++++++++++++++------ 3 files changed, 59 insertions(+), 29 deletions(-) diff --git a/ssh.c b/ssh.c index ea1fe02a..cc20f3bd 100644 --- a/ssh.c +++ b/ssh.c @@ -179,9 +179,7 @@ const static struct ssh2_ciphers *ciphers[] = { }; const static struct ssh_kex *kex_algs[] = { -#ifdef DO_DIFFIE_HELLMAN_GEX &ssh_diffiehellman_gex, -#endif &ssh_diffiehellman }; const static struct ssh_signkey *hostkey_algs[] = { &ssh_rsa, &ssh_dss }; @@ -2331,7 +2329,7 @@ static void ssh2_mkkey(Bignum K, char *H, char *sessid, char chr, char *keyspace */ static int do_ssh2_transport(unsigned char *in, int inlen, int ispkt) { - static int i, j, len, nbits; + static int i, j, len, nbits, pbits; static char *str; static Bignum p, g, e, f, K; static int kex_init_value, kex_reply_value; @@ -2554,30 +2552,34 @@ static int do_ssh2_transport(unsigned char *in, int inlen, int ispkt) } /* + * Work out the number of bits of key we will need from the key + * exchange. We start with the maximum key length of either + * cipher... + */ + { + int csbits, scbits; + + csbits = cscipher_tobe->keylen; + scbits = sccipher_tobe->keylen; + nbits = (csbits > scbits ? csbits : scbits); + } + /* The keys only have 160-bit entropy, since they're based on + * a SHA-1 hash. So cap the key size at 160 bits. */ + if (nbits > 160) nbits = 160; + + /* * If we're doing Diffie-Hellman group exchange, start by * requesting a group. */ if (kex == &ssh_diffiehellman_gex) { - int csbits, scbits; - logevent("Doing Diffie-Hellman group exchange"); /* - * Work out number of bits. We start with the maximum key - * length of either cipher... - */ - csbits = cscipher_tobe->keylen; - scbits = sccipher_tobe->keylen; - nbits = (csbits > scbits ? csbits : scbits); - /* The keys only have 160-bit entropy, since they're based on - * a SHA-1 hash. So cap the key size at 160 bits. */ - if (nbits > 160) nbits = 160; - /* - * ... and then work out how big a DH group we will need to - * allow that much data. - */ - nbits = 512 << ((nbits-1) / 64); + * Work out how big a DH group we will need to allow that + * much data. + */ + pbits = 512 << ((nbits-1) / 64); ssh2_pkt_init(SSH2_MSG_KEX_DH_GEX_REQUEST); - ssh2_pkt_adduint32(nbits); + ssh2_pkt_adduint32(pbits); ssh2_pkt_send(); crWaitUntil(ispkt); @@ -2600,7 +2602,7 @@ static int do_ssh2_transport(unsigned char *in, int inlen, int ispkt) /* * Now generate and send e for Diffie-Hellman. */ - e = dh_create_e(); + e = dh_create_e(nbits*2); ssh2_pkt_init(kex_init_value); ssh2_pkt_addmp(e); ssh2_pkt_send(); @@ -2618,7 +2620,7 @@ static int do_ssh2_transport(unsigned char *in, int inlen, int ispkt) sha_string(&exhash, hostkeydata, hostkeylen); if (kex == &ssh_diffiehellman_gex) { - sha_uint32(&exhash, nbits); + sha_uint32(&exhash, pbits); sha_mpint(&exhash, p); sha_mpint(&exhash, g); } diff --git a/ssh.h b/ssh.h index 4a674936..82e5acd0 100644 --- a/ssh.h +++ b/ssh.h @@ -222,7 +222,7 @@ char *bignum_decimal(Bignum x); void dh_setup_group1(void); void dh_setup_group(Bignum pval, Bignum gval); void dh_cleanup(void); -Bignum dh_create_e(void); +Bignum dh_create_e(int nbits); Bignum dh_find_K(Bignum f); int loadrsakey(char *filename, struct RSAKey *key, char *passphrase); diff --git a/sshdh.c b/sshdh.c index f1d709f5..0beac6cf 100644 --- a/sshdh.c +++ b/sshdh.c @@ -75,8 +75,19 @@ void dh_cleanup(void) { /* * DH stage 1: invent a number x between 1 and q, and compute e = * g^x mod p. Return e. + * + * If `nbits' is greater than zero, it is used as an upper limit + * for the number of bits in x. This is safe provided that (a) you + * use twice as many bits in x as the number of bits you expect to + * use in your session key, and (b) the DH group is a safe prime + * (which SSH demands that it must be). + * + * P. C. van Oorschot, M. J. Wiener + * "On Diffie-Hellman Key Agreement with Short Exponents". + * Advances in Cryptology: Proceedings of Eurocrypt '96 + * Springer-Verlag, May 1996. */ -Bignum dh_create_e(void) { +Bignum dh_create_e(int nbits) { int i; int nbytes; @@ -91,10 +102,25 @@ Bignum dh_create_e(void) { * with qmask. */ if (x) freebn(x); - ssh1_write_bignum(buf, qmask); - for (i = 2; i < nbytes; i++) - buf[i] &= random_byte(); - ssh1_read_bignum(buf, &x); + if (nbits == 0 || nbits > ssh1_bignum_bitcount(qmask)) { + ssh1_write_bignum(buf, qmask); + for (i = 2; i < nbytes; i++) + buf[i] &= random_byte(); + ssh1_read_bignum(buf, &x); + } else { + int b, nb; + x = bn_power_2(nbits); + nb = 0; + for (i = 0; i < nbits; i++) { + if (nb == 0) { + nb = 8; + b = random_byte(); + } + bignum_set_bit(x, i, b & 1); + b >>= 1; + nb--; + } + } } while (bignum_cmp(x, One) <= 0 || bignum_cmp(x, q) >= 0); /* @@ -109,5 +135,7 @@ Bignum dh_create_e(void) { * DH stage 2: given a number f, compute K = f^x mod p. */ Bignum dh_find_K(Bignum f) { - return modpow(f, x, p); + Bignum ret; + ret = modpow(f, x, p); + return ret; } -- 2.11.0