X-Git-Url: https://git.distorted.org.uk/u/mdw/putty/blobdiff_plain/32874aeac8dacbca26663777b39a79efc5d8dc4b..51e9d3c00a3471f284e89ec1f59f38ca25f10c5f:/sshrsa.c diff --git a/sshrsa.c b/sshrsa.c index 74cfac57..b862d3f6 100644 --- a/sshrsa.c +++ b/sshrsa.c @@ -1,8 +1,5 @@ /* - * RSA implementation just sufficient for ssh client-side - * initialisation step - * - * Rewritten for more speed by Joris van Rantwijk, Jun 1999. + * RSA implementation for PuTTY. */ #include @@ -11,13 +8,16 @@ #include #include "ssh.h" +#include "misc.h" - -int makekey(unsigned char *data, struct RSAKey *result, +int makekey(unsigned char *data, int len, struct RSAKey *result, unsigned char **keystr, int order) { unsigned char *p = data; - int i; + int i, n; + + if (len < 4) + return -1; if (result) { result->bits = 0; @@ -26,36 +26,53 @@ int makekey(unsigned char *data, struct RSAKey *result, } else p += 4; + len -= 4; + /* * order=0 means exponent then modulus (the keys sent by the * server). order=1 means modulus then exponent (the keys * stored in a keyfile). */ - if (order == 0) - p += ssh1_read_bignum(p, result ? &result->exponent : NULL); + if (order == 0) { + n = ssh1_read_bignum(p, len, result ? &result->exponent : NULL); + if (n < 0) return -1; + p += n; + len -= n; + } + + n = ssh1_read_bignum(p, len, result ? &result->modulus : NULL); + if (n < 0 || (result && bignum_bitcount(result->modulus) == 0)) return -1; if (result) - result->bytes = (((p[0] << 8) + p[1]) + 7) / 8; + result->bytes = n - 2; if (keystr) *keystr = p + 2; - p += ssh1_read_bignum(p, result ? &result->modulus : NULL); - if (order == 1) - p += ssh1_read_bignum(p, result ? &result->exponent : NULL); - + p += n; + len -= n; + + if (order == 1) { + n = ssh1_read_bignum(p, len, result ? &result->exponent : NULL); + if (n < 0) return -1; + p += n; + len -= n; + } return p - data; } -int makeprivate(unsigned char *data, struct RSAKey *result) +int makeprivate(unsigned char *data, int len, struct RSAKey *result) { - return ssh1_read_bignum(data, &result->private_exponent); + return ssh1_read_bignum(data, len, &result->private_exponent); } -void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) +int rsaencrypt(unsigned char *data, int length, struct RSAKey *key) { Bignum b1, b2; int i; unsigned char *p; + if (key->bytes < length + 4) + return 0; /* RSA key too short! */ + memmove(data + key->bytes - length, data, length); data[0] = 0; data[1] = 2; @@ -78,15 +95,149 @@ void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) freebn(b1); freebn(b2); + + return 1; } -Bignum rsadecrypt(Bignum input, struct RSAKey *key) +static void sha512_mpint(SHA512_State * s, Bignum b) +{ + unsigned char lenbuf[4]; + int len; + len = (bignum_bitcount(b) + 8) / 8; + PUT_32BIT(lenbuf, len); + SHA512_Bytes(s, lenbuf, 4); + while (len-- > 0) { + lenbuf[0] = bignum_byte(b, len); + SHA512_Bytes(s, lenbuf, 1); + } + memset(lenbuf, 0, sizeof(lenbuf)); +} + +/* + * This function is a wrapper on modpow(). It has the same effect + * as modpow(), but employs RSA blinding to protect against timing + * attacks. + */ +static Bignum rsa_privkey_op(Bignum input, struct RSAKey *key) { + Bignum random, random_encrypted, random_inverse; + Bignum input_blinded, ret_blinded; Bignum ret; - ret = modpow(input, key->private_exponent, key->modulus); + + SHA512_State ss; + unsigned char digest512[64]; + int digestused = lenof(digest512); + int hashseq = 0; + + /* + * Start by inventing a random number chosen uniformly from the + * range 2..modulus-1. (We do this by preparing a random number + * of the right length and retrying if it's greater than the + * modulus, to prevent any potential Bleichenbacher-like + * attacks making use of the uneven distribution within the + * range that would arise from just reducing our number mod n. + * There are timing implications to the potential retries, of + * course, but all they tell you is the modulus, which you + * already knew.) + * + * To preserve determinism and avoid Pageant needing to share + * the random number pool, we actually generate this `random' + * number by hashing stuff with the private key. + */ + while (1) { + int bits, byte, bitsleft, v; + random = copybn(key->modulus); + /* + * Find the topmost set bit. (This function will return its + * index plus one.) Then we'll set all bits from that one + * downwards randomly. + */ + bits = bignum_bitcount(random); + byte = 0; + bitsleft = 0; + while (bits--) { + if (bitsleft <= 0) { + bitsleft = 8; + /* + * Conceptually the following few lines are equivalent to + * byte = random_byte(); + */ + if (digestused >= lenof(digest512)) { + unsigned char seqbuf[4]; + PUT_32BIT(seqbuf, hashseq); + SHA512_Init(&ss); + SHA512_Bytes(&ss, "RSA deterministic blinding", 26); + SHA512_Bytes(&ss, seqbuf, sizeof(seqbuf)); + sha512_mpint(&ss, key->private_exponent); + SHA512_Final(&ss, digest512); + hashseq++; + + /* + * Now hash that digest plus the signature + * input. + */ + SHA512_Init(&ss); + SHA512_Bytes(&ss, digest512, sizeof(digest512)); + sha512_mpint(&ss, input); + SHA512_Final(&ss, digest512); + + digestused = 0; + } + byte = digest512[digestused++]; + } + v = byte & 1; + byte >>= 1; + bitsleft--; + bignum_set_bit(random, bits, v); + } + + /* + * Now check that this number is strictly greater than + * zero, and strictly less than modulus. + */ + if (bignum_cmp(random, Zero) <= 0 || + bignum_cmp(random, key->modulus) >= 0) { + freebn(random); + continue; + } else { + break; + } + } + + /* + * RSA blinding relies on the fact that (xy)^d mod n is equal + * to (x^d mod n) * (y^d mod n) mod n. We invent a random pair + * y and y^d; then we multiply x by y, raise to the power d mod + * n as usual, and divide by y^d to recover x^d. Thus an + * attacker can't correlate the timing of the modpow with the + * input, because they don't know anything about the number + * that was input to the actual modpow. + * + * The clever bit is that we don't have to do a huge modpow to + * get y and y^d; we will use the number we just invented as + * _y^d_, and use the _public_ exponent to compute (y^d)^e = y + * from it, which is much faster to do. + */ + random_encrypted = modpow(random, key->exponent, key->modulus); + random_inverse = modinv(random, key->modulus); + input_blinded = modmul(input, random_encrypted, key->modulus); + ret_blinded = modpow(input_blinded, key->private_exponent, key->modulus); + ret = modmul(ret_blinded, random_inverse, key->modulus); + + freebn(ret_blinded); + freebn(input_blinded); + freebn(random_inverse); + freebn(random_encrypted); + freebn(random); + return ret; } +Bignum rsadecrypt(Bignum input, struct RSAKey *key) +{ + return rsa_privkey_op(input, key); +} + int rsastr_len(struct RSAKey *key) { Bignum md, ex; @@ -217,6 +368,49 @@ int rsa_verify(struct RSAKey *key) return 1; } +/* Public key blob as used by Pageant: exponent before modulus. */ +unsigned char *rsa_public_blob(struct RSAKey *key, int *len) +{ + int length, pos; + unsigned char *ret; + + length = (ssh1_bignum_length(key->modulus) + + ssh1_bignum_length(key->exponent) + 4); + ret = snewn(length, unsigned char); + + PUT_32BIT(ret, bignum_bitcount(key->modulus)); + pos = 4; + pos += ssh1_write_bignum(ret + pos, key->exponent); + pos += ssh1_write_bignum(ret + pos, key->modulus); + + *len = length; + return ret; +} + +/* Given a public blob, determine its length. */ +int rsa_public_blob_len(void *data, int maxlen) +{ + unsigned char *p = (unsigned char *)data; + int n; + + if (maxlen < 4) + return -1; + p += 4; /* length word */ + maxlen -= 4; + + n = ssh1_read_bignum(p, maxlen, NULL); /* exponent */ + if (n < 0) + return -1; + p += n; + + n = ssh1_read_bignum(p, maxlen, NULL); /* modulus */ + if (n < 0) + return -1; + p += n; + + return p - (unsigned char *)data; +} + void freersakey(struct RSAKey *key) { if (key->modulus) @@ -233,18 +427,6 @@ void freersakey(struct RSAKey *key) * Implementation of the ssh-rsa signing key type. */ -#define GET_32BIT(cp) \ - (((unsigned long)(unsigned char)(cp)[0] << 24) | \ - ((unsigned long)(unsigned char)(cp)[1] << 16) | \ - ((unsigned long)(unsigned char)(cp)[2] << 8) | \ - ((unsigned long)(unsigned char)(cp)[3])) - -#define PUT_32BIT(cp, value) { \ - (cp)[0] = (unsigned char)((value) >> 24); \ - (cp)[1] = (unsigned char)((value) >> 16); \ - (cp)[2] = (unsigned char)((value) >> 8); \ - (cp)[3] = (unsigned char)(value); } - static void getstring(char **data, int *datalen, char **p, int *length) { *p = NULL; @@ -268,7 +450,7 @@ static Bignum getmp(char **data, int *datalen) getstring(data, datalen, &p, &length); if (!p) return NULL; - b = bignum_from_bytes(p, length); + b = bignum_from_bytes((unsigned char *)p, length); return b; } @@ -278,7 +460,7 @@ static void *rsa2_newkey(char *data, int len) int slen; struct RSAKey *rsa; - rsa = smalloc(sizeof(struct RSAKey)); + rsa = snew(struct RSAKey); if (!rsa) return NULL; getstring(&data, &len, &p, &slen); @@ -309,7 +491,7 @@ static char *rsa2_fmtkey(void *key) int len; len = rsastr_len(rsa); - p = smalloc(len); + p = snewn(len, char); rsastr_fmt(p, rsa); return p; } @@ -329,7 +511,7 @@ static unsigned char *rsa2_public_blob(void *key, int *len) * (three length fields, 12+7=19). */ bloblen = 19 + elen + mlen; - blob = smalloc(bloblen); + blob = snewn(bloblen, unsigned char); p = blob; PUT_32BIT(p, 7); p += 4; @@ -365,7 +547,7 @@ static unsigned char *rsa2_private_blob(void *key, int *len) * sum of lengths. */ bloblen = 16 + dlen + plen + qlen + ulen; - blob = smalloc(bloblen); + blob = snewn(bloblen, unsigned char); p = blob; PUT_32BIT(p, dlen); p += 4; @@ -413,7 +595,7 @@ static void *rsa2_openssh_createkey(unsigned char **blob, int *len) char **b = (char **) blob; struct RSAKey *rsa; - rsa = smalloc(sizeof(struct RSAKey)); + rsa = snew(struct RSAKey); if (!rsa) return NULL; rsa->comment = NULL; @@ -469,6 +651,18 @@ static int rsa2_openssh_fmtkey(void *key, unsigned char *blob, int len) return bloblen; } +static int rsa2_pubkey_bits(void *blob, int len) +{ + struct RSAKey *rsa; + int ret; + + rsa = rsa2_newkey((char *) blob, len); + ret = bignum_bitcount(rsa->modulus); + rsa2_freekey(rsa); + + return ret; +} + static char *rsa2_fingerprint(void *key) { struct RSAKey *rsa = (struct RSAKey *) key; @@ -479,7 +673,7 @@ static char *rsa2_fingerprint(void *key) int numlen, i; MD5Init(&md5c); - MD5Update(&md5c, "\0\0\0\7ssh-rsa", 11); + MD5Update(&md5c, (unsigned char *)"\0\0\0\7ssh-rsa", 11); #define ADD_BIGNUM(bignum) \ numlen = (bignum_bitcount(bignum)+8)/8; \ @@ -498,7 +692,7 @@ static char *rsa2_fingerprint(void *key) for (i = 0; i < 16; i++) sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "", digest[i]); - ret = smalloc(strlen(buffer) + 1); + ret = snewn(strlen(buffer) + 1, char); if (ret) strcpy(ret, buffer); return ret; @@ -528,7 +722,7 @@ static char *rsa2_fingerprint(void *key) * iso(1) identified-organization(3) oiw(14) secsig(3) * algorithms(2) 26 } */ -static unsigned char asn1_weird_stuff[] = { +static const unsigned char asn1_weird_stuff[] = { 0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B, 0x0E, 0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14, }; @@ -555,7 +749,7 @@ static int rsa2_verifysig(void *key, char *sig, int siglen, ret = 1; - bytes = bignum_bitcount(rsa->modulus) / 8; + bytes = (bignum_bitcount(rsa->modulus)+7) / 8; /* Top (partial) byte should be zero. */ if (bignum_byte(out, bytes - 1) != 0) ret = 0; @@ -578,11 +772,13 @@ static int rsa2_verifysig(void *key, char *sig, int siglen, if (bignum_byte(out, i) != hash[j]) ret = 0; } + freebn(out); return ret; } -unsigned char *rsa2_sign(void *key, char *data, int datalen, int *siglen) +static unsigned char *rsa2_sign(void *key, char *data, int datalen, + int *siglen) { struct RSAKey *rsa = (struct RSAKey *) key; unsigned char *bytes; @@ -594,7 +790,8 @@ unsigned char *rsa2_sign(void *key, char *data, int datalen, int *siglen) SHA_Simple(data, datalen, hash); nbytes = (bignum_bitcount(rsa->modulus) - 1) / 8; - bytes = smalloc(nbytes); + assert(1 <= nbytes - 20 - ASN1_LEN); + bytes = snewn(nbytes, unsigned char); bytes[0] = 1; for (i = 1; i < nbytes - 20 - ASN1_LEN; i++) @@ -607,11 +804,11 @@ unsigned char *rsa2_sign(void *key, char *data, int datalen, int *siglen) in = bignum_from_bytes(bytes, nbytes); sfree(bytes); - out = modpow(in, rsa->private_exponent, rsa->modulus); + out = rsa_privkey_op(in, rsa); freebn(in); nbytes = (bignum_bitcount(out) + 7) / 8; - bytes = smalloc(4 + 7 + 4 + nbytes); + bytes = snewn(4 + 7 + 4 + nbytes, unsigned char); PUT_32BIT(bytes, 7); memcpy(bytes + 4, "ssh-rsa", 7); PUT_32BIT(bytes + 4 + 7, nbytes); @@ -632,6 +829,7 @@ const struct ssh_signkey ssh_rsa = { rsa2_createkey, rsa2_openssh_createkey, rsa2_openssh_fmtkey, + rsa2_pubkey_bits, rsa2_fingerprint, rsa2_verifysig, rsa2_sign,