From 3709bfe9981af43e3cd491c37d300b57e5b26d50 Mon Sep 17 00:00:00 2001 From: simon Date: Thu, 1 Mar 2001 17:41:26 +0000 Subject: [PATCH] Remove the last lingering knowledge, outside sshbn.c, of the internal structure of the Bignum type. Bignum is now a fully opaque type unless you're inside sshbn.c. git-svn-id: svn://svn.tartarus.org/sgt/putty@960 cda61777-01e9-0310-a592-d414129be87e --- ssh.c | 37 ++++++++++-------------- ssh.h | 16 ++++++----- sshbn.c | 82 +++++++++++++++++++++++++++++++++++++++------------- sshdh.c | 97 +++++++++++++++++++++++++++++++++----------------------------- sshdss.c | 51 ++++++--------------------------- sshprime.c | 5 ++-- sshrsa.c | 29 +++++-------------- 7 files changed, 156 insertions(+), 161 deletions(-) diff --git a/ssh.c b/ssh.c index 033a0d27..a6433db5 100644 --- a/ssh.c +++ b/ssh.c @@ -869,20 +869,18 @@ static void ssh2_pkt_addstring(char *data) { } static char *ssh2_mpint_fmt(Bignum b, int *len) { unsigned char *p; - int i, n = b[0]; - p = smalloc(n * 2 + 1); + int i, n = (ssh1_bignum_bitcount(b)+7)/8; + p = smalloc(n + 1); if (!p) fatalbox("out of memory"); p[0] = 0; - for (i = 0; i < n; i++) { - p[i*2+1] = (b[n-i] >> 8) & 0xFF; - p[i*2+2] = (b[n-i] ) & 0xFF; - } + for (i = 1; i <= n; i++) + p[i] = bignum_byte(b, n-i); i = 0; - while (p[i] == 0 && (p[i+1] & 0x80) == 0) + while (i <= n && p[i] == 0 && (p[i+1] & 0x80) == 0) i++; - memmove(p, p+i, n*2+1-i); - *len = n*2+1-i; + memmove(p, p+i, n+1-i); + *len = n+1-i; return p; } static void ssh2_pkt_addmp(Bignum b) { @@ -1041,7 +1039,7 @@ static void ssh2_pkt_getstring(char **p, int *length) { } static Bignum ssh2_pkt_getmp(void) { char *p; - int i, j, length; + int length; Bignum b; ssh2_pkt_getstring(&p, &length); @@ -1051,15 +1049,7 @@ static Bignum ssh2_pkt_getmp(void) { bombout(("internal error: Can't handle negative mpints")); return NULL; } - b = newbn((length+1)/2); - for (i = 0; i < length; i++) { - j = length - 1 - i; - if (j & 1) - b[j/2+1] |= ((unsigned char)p[i]) << 8; - else - b[j/2+1] |= ((unsigned char)p[i]); - } - while (b[0] > 1 && b[b[0]] == 0) b[0]--; + b = bignum_from_bytes(p, length); return b; } @@ -1753,9 +1743,8 @@ static int do_ssh1_login(unsigned char *in, int inlen, int ispkt) response = rsadecrypt(challenge, &pubkey); freebn(pubkey.private_exponent); /* burn the evidence */ - for (i = 0; i < 32; i += 2) { - buffer[i] = response[16-i/2] >> 8; - buffer[i+1] = response[16-i/2] & 0xFF; + for (i = 0; i < 32; i++) { + buffer[i] = bignum_byte(response, 31-i); } MD5Init(&md5c); @@ -2388,6 +2377,8 @@ static int do_ssh2_transport(unsigned char *in, int inlen, int ispkt) /* * Now we begin the fun. Generate and send e for Diffie-Hellman. */ + dh_setup_group1(); + e = dh_create_e(); ssh2_pkt_init(SSH2_MSG_KEXDH_INIT); ssh2_pkt_addmp(e); @@ -2410,6 +2401,8 @@ static int do_ssh2_transport(unsigned char *in, int inlen, int ispkt) sha_mpint(&exhash, K); SHA_Final(&exhash, exchange_hash); + dh_cleanup(); + #if 0 debug(("Exchange hash is:\r\n")); for (i = 0; i < 20; i++) diff --git a/ssh.h b/ssh.h index 725569cf..320c84e9 100644 --- a/ssh.h +++ b/ssh.h @@ -20,12 +20,9 @@ #define APIEXTRA 0 #endif -/* - * A Bignum is stored as a sequence of `unsigned short' words. The - * first tells how many remain; the remaining ones are digits, LS - * first. - */ -typedef unsigned short *Bignum; +#ifndef BIGNUM_INTERNAL +typedef void *Bignum; +#endif struct RSAKey { int bits; @@ -161,14 +158,16 @@ void random_add_heavynoise(void *noise, int length); void logevent (char *); -Bignum newbn(int length); Bignum copybn(Bignum b); +Bignum bn_power_2(int n); +void bn_restore_invariant(Bignum b); Bignum bignum_from_short(unsigned short n); void freebn(Bignum b); Bignum modpow(Bignum base, Bignum exp, Bignum mod); Bignum modmul(Bignum a, Bignum b, Bignum mod); void decbn(Bignum n); extern Bignum Zero, One; +Bignum bignum_from_bytes(unsigned char *data, int nbytes); int ssh1_read_bignum(unsigned char *data, Bignum *result); int ssh1_bignum_bitcount(Bignum bn); int ssh1_bignum_length(Bignum bn); @@ -181,10 +180,13 @@ unsigned short bignum_mod_short(Bignum number, unsigned short modulus); Bignum bignum_add_long(Bignum number, unsigned long addend); Bignum bigmul(Bignum a, Bignum b); Bignum modinv(Bignum number, Bignum modulus); +Bignum bignum_bitmask(Bignum number); Bignum bignum_rshift(Bignum number, int shift); int bignum_cmp(Bignum a, Bignum b); char *bignum_decimal(Bignum x); +void dh_setup_group1(void); +void dh_cleanup(void); Bignum dh_create_e(void); Bignum dh_find_K(Bignum f); diff --git a/sshbn.c b/sshbn.c index 6615d41d..aea5a82b 100644 --- a/sshbn.c +++ b/sshbn.c @@ -6,6 +6,9 @@ #include #include +#define BIGNUM_INTERNAL +typedef unsigned short *Bignum; + #include "ssh.h" unsigned short bnZero[1] = { 0 }; @@ -27,7 +30,7 @@ unsigned short bnOne[2] = { 1, 1 }; Bignum Zero = bnZero, One = bnOne; -Bignum newbn(int length) { +static Bignum newbn(int length) { Bignum b = smalloc((length+1)*sizeof(unsigned short)); if (!b) abort(); /* FIXME */ @@ -36,6 +39,10 @@ Bignum newbn(int length) { return b; } +void bn_restore_invariant(Bignum b) { + while (b[0] > 1 && b[b[0]] == 0) b[0]--; +} + Bignum copybn(Bignum orig) { Bignum b = smalloc((orig[0]+1)*sizeof(unsigned short)); if (!b) @@ -52,6 +59,12 @@ void freebn(Bignum b) { sfree(b); } +Bignum bn_power_2(int n) { + Bignum ret = newbn((n+15)/16); + bignum_set_bit(ret, n, 1); + return ret; +} + /* * Compute c = a * b. * Input is in the first len words of a and b. @@ -410,41 +423,47 @@ void decbn(Bignum bn) { bn[i]--; } +Bignum bignum_from_bytes(unsigned char *data, int nbytes) { + Bignum result; + int w, i; + + w = (nbytes+1)/2; /* bytes -> words */ + + result = newbn(w); + for (i=1; i<=w; i++) + result[i] = 0; + for (i=nbytes; i-- ;) { + unsigned char byte = *data++; + if (i & 1) + result[1+i/2] |= byte<<8; + else + result[1+i/2] |= byte; + } + + while (result[0] > 1 && result[result[0]] == 0) result[0]--; + return result; +} + /* * Read an ssh1-format bignum from a data buffer. Return the number * of bytes consumed. */ int ssh1_read_bignum(unsigned char *data, Bignum *result) { unsigned char *p = data; - Bignum bn; int i; int w, b; w = 0; for (i=0; i<2; i++) w = (w << 8) + *p++; - b = (w+7)/8; /* bits -> bytes */ - w = (w+15)/16; /* bits -> words */ if (!result) /* just return length */ return b + 2; - bn = newbn(w); + *result = bignum_from_bytes(p, b); - for (i=1; i<=w; i++) - bn[i] = 0; - for (i=b; i-- ;) { - unsigned char byte = *p++; - if (i & 1) - bn[1+i/2] |= byte<<8; - else - bn[1+i/2] |= byte; - } - - *result = bn; - - return p - data; + return p + b - data; } /* @@ -452,7 +471,6 @@ int ssh1_read_bignum(unsigned char *data, Bignum *result) { */ int ssh1_bignum_bitcount(Bignum bn) { int bitcount = bn[0] * 16 - 1; - while (bitcount >= 0 && (bn[bitcount/16+1] >> (bitcount % 16)) == 0) bitcount--; return bitcount + 1; @@ -620,6 +638,30 @@ Bignum bigmul(Bignum a, Bignum b) { } /* + * Create a bignum which is the bitmask covering another one. That + * is, the smallest integer which is >= N and is also one less than + * a power of two. + */ +Bignum bignum_bitmask(Bignum n) { + Bignum ret = copybn(n); + int i; + unsigned short j; + + i = ret[0]; + while (n[i] == 0 && i > 0) + i--; + if (i <= 0) + return ret; /* input was zero */ + j = 1; + while (j < n[i]) + j = 2*j+1; + ret[i] = j; + while (--i > 0) + ret[i] = 0xFFFF; + return ret; +} + +/* * Convert a (max 16-bit) short into a bignum. */ Bignum bignum_from_short(unsigned short n) { @@ -667,7 +709,7 @@ unsigned short bignum_mod_short(Bignum number, unsigned short modulus) { return (unsigned short) r; } -static void diagbn(char *prefix, Bignum md) { +void diagbn(char *prefix, Bignum md) { int i, nibbles, morenibbles; static const char hex[] = "0123456789ABCDEF"; diff --git a/sshdh.c b/sshdh.c index dabed52a..35e66907 100644 --- a/sshdh.c +++ b/sshdh.c @@ -7,57 +7,57 @@ struct ssh_kex ssh_diffiehellman = { /* * The prime p used in the key exchange. */ -static unsigned short P[] = { - 64, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0x5381, 0xECE6, 0x6651, 0x4928, - 0x1FE6, 0x7C4B, 0x2411, 0xAE9F, 0x9FA5, 0x5A89, 0x6BFB, 0xEE38, - 0xB7ED, 0xF406, 0x5CB6, 0x0BFF, 0xED6B, 0xA637, 0x42E9, 0xF44C, - 0x7EC6, 0x625E, 0xB576, 0xE485, 0xC245, 0x6D51, 0x356D, 0x4FE1, - 0x1437, 0xF25F, 0x0A6D, 0x302B, 0x431B, 0xCD3A, 0x19B3, 0xEF95, - 0x04DD, 0x8E34, 0x0879, 0x514A, 0x9B22, 0x3B13, 0xBEA6, 0x020B, - 0xCC74, 0x8A67, 0x4E08, 0x2902, 0x1CD1, 0x80DC, 0x628B, 0xC4C6, - 0xC234, 0x2168, 0xDAA2, 0xC90F, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, +static unsigned char P[] = { + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xC9, 0x0F, 0xDA, 0xA2, + 0x21, 0x68, 0xC2, 0x34, 0xC4, 0xC6, 0x62, 0x8B, 0x80, 0xDC, 0x1C, 0xD1, + 0x29, 0x02, 0x4E, 0x08, 0x8A, 0x67, 0xCC, 0x74, 0x02, 0x0B, 0xBE, 0xA6, + 0x3B, 0x13, 0x9B, 0x22, 0x51, 0x4A, 0x08, 0x79, 0x8E, 0x34, 0x04, 0xDD, + 0xEF, 0x95, 0x19, 0xB3, 0xCD, 0x3A, 0x43, 0x1B, 0x30, 0x2B, 0x0A, 0x6D, + 0xF2, 0x5F, 0x14, 0x37, 0x4F, 0xE1, 0x35, 0x6D, 0x6D, 0x51, 0xC2, 0x45, + 0xE4, 0x85, 0xB5, 0x76, 0x62, 0x5E, 0x7E, 0xC6, 0xF4, 0x4C, 0x42, 0xE9, + 0xA6, 0x37, 0xED, 0x6B, 0x0B, 0xFF, 0x5C, 0xB6, 0xF4, 0x06, 0xB7, 0xED, + 0xEE, 0x38, 0x6B, 0xFB, 0x5A, 0x89, 0x9F, 0xA5, 0xAE, 0x9F, 0x24, 0x11, + 0x7C, 0x4B, 0x1F, 0xE6, 0x49, 0x28, 0x66, 0x51, 0xEC, 0xE6, 0x53, 0x81, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF }; /* - * The order q of the group: (p-1)/2. + * The generator g = 2. */ -static unsigned short Q[] = { - 64, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0x29C0, 0xF673, 0x3328, 0x2494, - 0x8FF3, 0xBE25, 0x9208, 0xD74F, 0xCFD2, 0xAD44, 0x35FD, 0xF71C, - 0x5BF6, 0x7A03, 0xAE5B, 0x85FF, 0xF6B5, 0xD31B, 0x2174, 0x7A26, - 0x3F63, 0x312F, 0xDABB, 0xF242, 0xE122, 0xB6A8, 0x9AB6, 0xA7F0, - 0x8A1B, 0xF92F, 0x8536, 0x9815, 0x218D, 0xE69D, 0x8CD9, 0xF7CA, - 0x026E, 0xC71A, 0x043C, 0x28A5, 0xCD91, 0x1D89, 0xDF53, 0x0105, - 0xE63A, 0x4533, 0x2704, 0x9481, 0x0E68, 0xC06E, 0x3145, 0x6263, - 0x611A, 0x10B4, 0xED51, 0xE487, 0xFFFF, 0xFFFF, 0xFFFF, 0x7FFF, -}; +static unsigned char G[] = { 2 }; /* - * The bitmask covering q (for ease of generation of x). + * Variables. */ -static unsigned short Qmask[] = { - 64, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, - 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0x7FFF, -}; +static Bignum x, e, p, q, qmask, g; +static int need_to_free_pg; /* - * The generator g = 2. + * Common DH initialisation. */ -static unsigned short G[] = { 1, 2 }; +static void dh_init(void) { + q = bignum_rshift(p, 1); + qmask = bignum_bitmask(q); +} /* - * Variables. + * Initialise DH for the standard group1. */ -static Bignum x, e; +void dh_setup_group1(void) { + p = bignum_from_bytes(P, sizeof(P)); + g = bignum_from_bytes(G, sizeof(G)); + dh_init(); +} + +/* + * Clean up. + */ +void dh_cleanup(void) { + freebn(p); + freebn(g); + freebn(q); + freebn(qmask); +} /* * DH stage 1: invent a number x between 1 and q, and compute e = @@ -66,21 +66,28 @@ static Bignum x, e; Bignum dh_create_e(void) { int i; - x = newbn(Q[0]); + int nbytes; + unsigned char *buf; + + nbytes = ssh1_bignum_length(qmask); + buf = smalloc(nbytes); do { /* * Create a potential x, by ANDing a string of random bytes - * with Qmask. + * with qmask. */ - for (i = 1; i <= x[0]; i++) - x[i] = ((random_byte() << 8) + random_byte()) & Qmask[i]; - } while (bignum_cmp(x, One) <= 0 || bignum_cmp(x, Q) >= 0); + if (x) freebn(x); + ssh1_write_bignum(buf, qmask); + for (i = 2; i < nbytes; i++) + buf[i] &= random_byte(); + ssh1_read_bignum(buf, &x); + } while (bignum_cmp(x, One) <= 0 || bignum_cmp(x, q) >= 0); /* * Done. Now compute e = g^x mod p. */ - e = modpow(G, x, P); + e = modpow(g, x, p); return e; } @@ -89,5 +96,5 @@ 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); + return modpow(f, x, p); } diff --git a/sshdss.c b/sshdss.c index bacf68d4..cf7fc3f7 100644 --- a/sshdss.c +++ b/sshdss.c @@ -16,23 +16,6 @@ (cp)[3] = (unsigned char)(value); } #if 0 -/* - * Condition this section in for debugging of DSS. - */ -static void diagbn(char *prefix, Bignum md) { - int i, nibbles, morenibbles; - static const char hex[] = "0123456789ABCDEF"; - - printf("%s0x", prefix ? prefix : ""); - - nibbles = (3 + ssh1_bignum_bitcount(md))/4; if (nibbles<1) nibbles=1; - morenibbles = 4*md[0] - nibbles; - for (i=0; i> (4*(i%2))) & 0xF]); - - if (prefix) putchar('\n'); -} #define DEBUG_DSS #else #define diagbn(x,y) @@ -51,7 +34,7 @@ static void getstring(char **data, int *datalen, char **p, int *length) { } static Bignum getmp(char **data, int *datalen) { char *p; - int i, j, length; + int length; Bignum b; getstring(data, datalen, &p, &length); @@ -59,37 +42,16 @@ static Bignum getmp(char **data, int *datalen) { return NULL; if (p[0] & 0x80) return NULL; /* negative mp */ - b = newbn((length+1)/2); - for (i = 0; i < length; i++) { - j = length - 1 - i; - if (j & 1) - b[j/2+1] |= ((unsigned char)p[i]) << 8; - else - b[j/2+1] |= ((unsigned char)p[i]); - } - while (b[0] > 1 && b[b[0]] == 0) b[0]--; + b = bignum_from_bytes(p, length); return b; } static Bignum get160(char **data, int *datalen) { - char *p; - int i, j, length; Bignum b; - p = *data; + b = bignum_from_bytes(*data, 20); *data += 20; *datalen -= 20; - length = 20; - while (length > 0 && !p[0]) - p++, length--; - b = newbn((length+1)/2); - for (i = 0; i < length; i++) { - j = length - 1 - i; - if (j & 1) - b[j/2+1] |= ((unsigned char)p[i]) << 8; - else - b[j/2+1] |= ((unsigned char)p[i]); - } return b; } @@ -145,7 +107,10 @@ static char *dss_fmtkey(void *key) { if (!dss->p) return NULL; len = 8 + 4 + 1; /* 4 x "0x", punctuation, \0 */ - len += 4 * (dss->p[0] + dss->q[0] + dss->g[0] + dss->y[0]); /* digits */ + len += 4 * (ssh1_bignum_bitcount(dss->p)+15)/16; + len += 4 * (ssh1_bignum_bitcount(dss->q)+15)/16; + len += 4 * (ssh1_bignum_bitcount(dss->g)+15)/16; + len += 4 * (ssh1_bignum_bitcount(dss->y)+15)/16; p = smalloc(len); if (!p) return NULL; @@ -222,7 +187,7 @@ static int dss_verifysig(void *key, char *sig, int siglen, int i; printf("sig:"); for (i=0;i= 0 || bignum_cmp(w, Zero) == 0) { freebn(w); continue; diff --git a/sshrsa.c b/sshrsa.c index 14cf09a6..537d0f1e 100644 --- a/sshrsa.c +++ b/sshrsa.c @@ -48,7 +48,7 @@ int makeprivate(unsigned char *data, struct RSAKey *result) { void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) { Bignum b1, b2; - int w, i; + int i; unsigned char *p; memmove(data+key->bytes-length, data, length); @@ -62,31 +62,13 @@ void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) { } data[key->bytes-length-1] = 0; - w = (key->bytes+1)/2; - - b1 = newbn(w); - - p = data; - for (i=1; i<=w; i++) - b1[i] = 0; - for (i=key->bytes; i-- ;) { - unsigned char byte = *p++; - if (i & 1) - b1[1+i/2] |= byte<<8; - else - b1[1+i/2] |= byte; - } + b1 = bignum_from_bytes(data, key->bytes); b2 = modpow(b1, key->exponent, key->modulus); p = data; for (i=key->bytes; i-- ;) { - unsigned char b; - if (i & 1) - b = b2[1+i/2] >> 8; - else - b = b2[1+i/2] & 0xFF; - *p++ = b; + *p++ = bignum_byte(b2, i); } freebn(b1); @@ -101,10 +83,13 @@ Bignum rsadecrypt(Bignum input, struct RSAKey *key) { int rsastr_len(struct RSAKey *key) { Bignum md, ex; + int mdlen, exlen; md = key->modulus; ex = key->exponent; - return 4 * (ex[0]+md[0]) + 20; + mdlen = (ssh1_bignum_bitcount(md)+15) / 16; + exlen = (ssh1_bignum_bitcount(ex)+15) / 16; + return 4 * (mdlen+exlen) + 20; } void rsastr_fmt(char *str, struct RSAKey *key) { -- 2.11.0