source: filezilla/trunk/fuentes/src/putty/sshrsa.c @ 130

Last change on this file since 130 was 130, checked in by jrpelegrina, 3 years ago

First release to xenial

File size: 27.4 KB
Line 
1/*
2 * RSA implementation for PuTTY.
3 */
4
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8#include <assert.h>
9
10#include "ssh.h"
11#include "misc.h"
12
13int makekey(const unsigned char *data, int len, struct RSAKey *result,
14            const unsigned char **keystr, int order)
15{
16    const unsigned char *p = data;
17    int i, n;
18
19    if (len < 4)
20        return -1;
21
22    if (result) {
23        result->bits = 0;
24        for (i = 0; i < 4; i++)
25            result->bits = (result->bits << 8) + *p++;
26    } else
27        p += 4;
28
29    len -= 4;
30
31    /*
32     * order=0 means exponent then modulus (the keys sent by the
33     * server). order=1 means modulus then exponent (the keys
34     * stored in a keyfile).
35     */
36
37    if (order == 0) {
38        n = ssh1_read_bignum(p, len, result ? &result->exponent : NULL);
39        if (n < 0) return -1;
40        p += n;
41        len -= n;
42    }
43
44    n = ssh1_read_bignum(p, len, result ? &result->modulus : NULL);
45    if (n < 0 || (result && bignum_bitcount(result->modulus) == 0)) return -1;
46    if (result)
47        result->bytes = n - 2;
48    if (keystr)
49        *keystr = p + 2;
50    p += n;
51    len -= n;
52
53    if (order == 1) {
54        n = ssh1_read_bignum(p, len, result ? &result->exponent : NULL);
55        if (n < 0) return -1;
56        p += n;
57        len -= n;
58    }
59    return p - data;
60}
61
62int makeprivate(const unsigned char *data, int len, struct RSAKey *result)
63{
64    return ssh1_read_bignum(data, len, &result->private_exponent);
65}
66
67int rsaencrypt(unsigned char *data, int length, struct RSAKey *key)
68{
69    Bignum b1, b2;
70    int i;
71    unsigned char *p;
72
73    if (key->bytes < length + 4)
74        return 0;                      /* RSA key too short! */
75
76    memmove(data + key->bytes - length, data, length);
77    data[0] = 0;
78    data[1] = 2;
79
80    for (i = 2; i < key->bytes - length - 1; i++) {
81        do {
82            data[i] = random_byte();
83        } while (data[i] == 0);
84    }
85    data[key->bytes - length - 1] = 0;
86
87    b1 = bignum_from_bytes(data, key->bytes);
88
89    b2 = modpow(b1, key->exponent, key->modulus);
90
91    p = data;
92    for (i = key->bytes; i--;) {
93        *p++ = bignum_byte(b2, i);
94    }
95
96    freebn(b1);
97    freebn(b2);
98
99    return 1;
100}
101
102static void sha512_mpint(SHA512_State * s, Bignum b)
103{
104    unsigned char lenbuf[4];
105    int len;
106    len = (bignum_bitcount(b) + 8) / 8;
107    PUT_32BIT(lenbuf, len);
108    SHA512_Bytes(s, lenbuf, 4);
109    while (len-- > 0) {
110        lenbuf[0] = bignum_byte(b, len);
111        SHA512_Bytes(s, lenbuf, 1);
112    }
113    smemclr(lenbuf, sizeof(lenbuf));
114}
115
116/*
117 * Compute (base ^ exp) % mod, provided mod == p * q, with p,q
118 * distinct primes, and iqmp is the multiplicative inverse of q mod p.
119 * Uses Chinese Remainder Theorem to speed computation up over the
120 * obvious implementation of a single big modpow.
121 */
122Bignum crt_modpow(Bignum base, Bignum exp, Bignum mod,
123                  Bignum p, Bignum q, Bignum iqmp)
124{
125    Bignum pm1, qm1, pexp, qexp, presult, qresult, diff, multiplier, ret0, ret;
126
127    /*
128     * Reduce the exponent mod phi(p) and phi(q), to save time when
129     * exponentiating mod p and mod q respectively. Of course, since p
130     * and q are prime, phi(p) == p-1 and similarly for q.
131     */
132    pm1 = copybn(p);
133    decbn(pm1);
134    qm1 = copybn(q);
135    decbn(qm1);
136    pexp = bigmod(exp, pm1);
137    qexp = bigmod(exp, qm1);
138
139    /*
140     * Do the two modpows.
141     */
142    presult = modpow(base, pexp, p);
143    qresult = modpow(base, qexp, q);
144
145    /*
146     * Recombine the results. We want a value which is congruent to
147     * qresult mod q, and to presult mod p.
148     *
149     * We know that iqmp * q is congruent to 1 * mod p (by definition
150     * of iqmp) and to 0 mod q (obviously). So we start with qresult
151     * (which is congruent to qresult mod both primes), and add on
152     * (presult-qresult) * (iqmp * q) which adjusts it to be congruent
153     * to presult mod p without affecting its value mod q.
154     */
155    if (bignum_cmp(presult, qresult) < 0) {
156        /*
157         * Can't subtract presult from qresult without first adding on
158         * p.
159         */
160        Bignum tmp = presult;
161        presult = bigadd(presult, p);
162        freebn(tmp);
163    }
164    diff = bigsub(presult, qresult);
165    multiplier = bigmul(iqmp, q);
166    ret0 = bigmuladd(multiplier, diff, qresult);
167
168    /*
169     * Finally, reduce the result mod n.
170     */
171    ret = bigmod(ret0, mod);
172
173    /*
174     * Free all the intermediate results before returning.
175     */
176    freebn(pm1);
177    freebn(qm1);
178    freebn(pexp);
179    freebn(qexp);
180    freebn(presult);
181    freebn(qresult);
182    freebn(diff);
183    freebn(multiplier);
184    freebn(ret0);
185
186    return ret;
187}
188
189/*
190 * This function is a wrapper on modpow(). It has the same effect as
191 * modpow(), but employs RSA blinding to protect against timing
192 * attacks and also uses the Chinese Remainder Theorem (implemented
193 * above, in crt_modpow()) to speed up the main operation.
194 */
195static Bignum rsa_privkey_op(Bignum input, struct RSAKey *key)
196{
197    Bignum random, random_encrypted, random_inverse;
198    Bignum input_blinded, ret_blinded;
199    Bignum ret;
200
201    SHA512_State ss;
202    unsigned char digest512[64];
203    int digestused = lenof(digest512);
204    int hashseq = 0;
205
206    /*
207     * Start by inventing a random number chosen uniformly from the
208     * range 2..modulus-1. (We do this by preparing a random number
209     * of the right length and retrying if it's greater than the
210     * modulus, to prevent any potential Bleichenbacher-like
211     * attacks making use of the uneven distribution within the
212     * range that would arise from just reducing our number mod n.
213     * There are timing implications to the potential retries, of
214     * course, but all they tell you is the modulus, which you
215     * already knew.)
216     *
217     * To preserve determinism and avoid Pageant needing to share
218     * the random number pool, we actually generate this `random'
219     * number by hashing stuff with the private key.
220     */
221    while (1) {
222        int bits, byte, bitsleft, v;
223        random = copybn(key->modulus);
224        /*
225         * Find the topmost set bit. (This function will return its
226         * index plus one.) Then we'll set all bits from that one
227         * downwards randomly.
228         */
229        bits = bignum_bitcount(random);
230        byte = 0;
231        bitsleft = 0;
232        while (bits--) {
233            if (bitsleft <= 0) {
234                bitsleft = 8;
235                /*
236                 * Conceptually the following few lines are equivalent to
237                 *    byte = random_byte();
238                 */
239                if (digestused >= lenof(digest512)) {
240                    unsigned char seqbuf[4];
241                    PUT_32BIT(seqbuf, hashseq);
242                    SHA512_Init(&ss);
243                    SHA512_Bytes(&ss, "RSA deterministic blinding", 26);
244                    SHA512_Bytes(&ss, seqbuf, sizeof(seqbuf));
245                    sha512_mpint(&ss, key->private_exponent);
246                    SHA512_Final(&ss, digest512);
247                    hashseq++;
248
249                    /*
250                     * Now hash that digest plus the signature
251                     * input.
252                     */
253                    SHA512_Init(&ss);
254                    SHA512_Bytes(&ss, digest512, sizeof(digest512));
255                    sha512_mpint(&ss, input);
256                    SHA512_Final(&ss, digest512);
257
258                    digestused = 0;
259                }
260                byte = digest512[digestused++];
261            }
262            v = byte & 1;
263            byte >>= 1;
264            bitsleft--;
265            bignum_set_bit(random, bits, v);
266        }
267        bn_restore_invariant(random);
268
269        /*
270         * Now check that this number is strictly greater than
271         * zero, and strictly less than modulus.
272         */
273        if (bignum_cmp(random, Zero) <= 0 ||
274            bignum_cmp(random, key->modulus) >= 0) {
275            freebn(random);
276            continue;
277        }
278
279        /*
280         * Also, make sure it has an inverse mod modulus.
281         */
282        random_inverse = modinv(random, key->modulus);
283        if (!random_inverse) {
284            freebn(random);
285            continue;
286        }
287
288        break;
289    }
290
291    /*
292     * RSA blinding relies on the fact that (xy)^d mod n is equal
293     * to (x^d mod n) * (y^d mod n) mod n. We invent a random pair
294     * y and y^d; then we multiply x by y, raise to the power d mod
295     * n as usual, and divide by y^d to recover x^d. Thus an
296     * attacker can't correlate the timing of the modpow with the
297     * input, because they don't know anything about the number
298     * that was input to the actual modpow.
299     *
300     * The clever bit is that we don't have to do a huge modpow to
301     * get y and y^d; we will use the number we just invented as
302     * _y^d_, and use the _public_ exponent to compute (y^d)^e = y
303     * from it, which is much faster to do.
304     */
305    random_encrypted = crt_modpow(random, key->exponent,
306                                  key->modulus, key->p, key->q, key->iqmp);
307    input_blinded = modmul(input, random_encrypted, key->modulus);
308    ret_blinded = crt_modpow(input_blinded, key->private_exponent,
309                             key->modulus, key->p, key->q, key->iqmp);
310    ret = modmul(ret_blinded, random_inverse, key->modulus);
311
312    freebn(ret_blinded);
313    freebn(input_blinded);
314    freebn(random_inverse);
315    freebn(random_encrypted);
316    freebn(random);
317
318    return ret;
319}
320
321Bignum rsadecrypt(Bignum input, struct RSAKey *key)
322{
323    return rsa_privkey_op(input, key);
324}
325
326int rsastr_len(struct RSAKey *key)
327{
328    Bignum md, ex;
329    int mdlen, exlen;
330
331    md = key->modulus;
332    ex = key->exponent;
333    mdlen = (bignum_bitcount(md) + 15) / 16;
334    exlen = (bignum_bitcount(ex) + 15) / 16;
335    return 4 * (mdlen + exlen) + 20;
336}
337
338void rsastr_fmt(char *str, struct RSAKey *key)
339{
340    Bignum md, ex;
341    int len = 0, i, nibbles;
342    static const char hex[] = "0123456789abcdef";
343
344    md = key->modulus;
345    ex = key->exponent;
346
347    len += sprintf(str + len, "0x");
348
349    nibbles = (3 + bignum_bitcount(ex)) / 4;
350    if (nibbles < 1)
351        nibbles = 1;
352    for (i = nibbles; i--;)
353        str[len++] = hex[(bignum_byte(ex, i / 2) >> (4 * (i % 2))) & 0xF];
354
355    len += sprintf(str + len, ",0x");
356
357    nibbles = (3 + bignum_bitcount(md)) / 4;
358    if (nibbles < 1)
359        nibbles = 1;
360    for (i = nibbles; i--;)
361        str[len++] = hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF];
362
363    str[len] = '\0';
364}
365
366/*
367 * Generate a fingerprint string for the key. Compatible with the
368 * OpenSSH fingerprint code.
369 */
370void rsa_fingerprint(char *str, int len, struct RSAKey *key)
371{
372    struct MD5Context md5c;
373    unsigned char digest[16];
374    char buffer[16 * 3 + 40];
375    int numlen, slen, i;
376
377    MD5Init(&md5c);
378    numlen = ssh1_bignum_length(key->modulus) - 2;
379    for (i = numlen; i--;) {
380        unsigned char c = bignum_byte(key->modulus, i);
381        MD5Update(&md5c, &c, 1);
382    }
383    numlen = ssh1_bignum_length(key->exponent) - 2;
384    for (i = numlen; i--;) {
385        unsigned char c = bignum_byte(key->exponent, i);
386        MD5Update(&md5c, &c, 1);
387    }
388    MD5Final(digest, &md5c);
389
390    sprintf(buffer, "%d ", bignum_bitcount(key->modulus));
391    for (i = 0; i < 16; i++)
392        sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",
393                digest[i]);
394    strncpy(str, buffer, len);
395    str[len - 1] = '\0';
396    slen = strlen(str);
397    if (key->comment && slen < len - 1) {
398        str[slen] = ' ';
399        strncpy(str + slen + 1, key->comment, len - slen - 1);
400        str[len - 1] = '\0';
401    }
402}
403
404/*
405 * Verify that the public data in an RSA key matches the private
406 * data. We also check the private data itself: we ensure that p >
407 * q and that iqmp really is the inverse of q mod p.
408 */
409int rsa_verify(struct RSAKey *key)
410{
411    Bignum n, ed, pm1, qm1;
412    int cmp;
413
414    /* n must equal pq. */
415    n = bigmul(key->p, key->q);
416    cmp = bignum_cmp(n, key->modulus);
417    freebn(n);
418    if (cmp != 0)
419        return 0;
420
421    /* e * d must be congruent to 1, modulo (p-1) and modulo (q-1). */
422    pm1 = copybn(key->p);
423    decbn(pm1);
424    ed = modmul(key->exponent, key->private_exponent, pm1);
425    freebn(pm1);
426    cmp = bignum_cmp(ed, One);
427    freebn(ed);
428    if (cmp != 0)
429        return 0;
430
431    qm1 = copybn(key->q);
432    decbn(qm1);
433    ed = modmul(key->exponent, key->private_exponent, qm1);
434    freebn(qm1);
435    cmp = bignum_cmp(ed, One);
436    freebn(ed);
437    if (cmp != 0)
438        return 0;
439
440    /*
441     * Ensure p > q.
442     *
443     * I have seen key blobs in the wild which were generated with
444     * p < q, so instead of rejecting the key in this case we
445     * should instead flip them round into the canonical order of
446     * p > q. This also involves regenerating iqmp.
447     */
448    if (bignum_cmp(key->p, key->q) <= 0) {
449        Bignum tmp = key->p;
450        key->p = key->q;
451        key->q = tmp;
452
453        freebn(key->iqmp);
454        key->iqmp = modinv(key->q, key->p);
455        if (!key->iqmp)
456            return 0;
457    }
458
459    /*
460     * Ensure iqmp * q is congruent to 1, modulo p.
461     */
462    n = modmul(key->iqmp, key->q, key->p);
463    cmp = bignum_cmp(n, One);
464    freebn(n);
465    if (cmp != 0)
466        return 0;
467
468    return 1;
469}
470
471/* Public key blob as used by Pageant: exponent before modulus. */
472unsigned char *rsa_public_blob(struct RSAKey *key, int *len)
473{
474    int length, pos;
475    unsigned char *ret;
476
477    length = (ssh1_bignum_length(key->modulus) +
478              ssh1_bignum_length(key->exponent) + 4);
479    ret = snewn(length, unsigned char);
480
481    PUT_32BIT(ret, bignum_bitcount(key->modulus));
482    pos = 4;
483    pos += ssh1_write_bignum(ret + pos, key->exponent);
484    pos += ssh1_write_bignum(ret + pos, key->modulus);
485
486    *len = length;
487    return ret;
488}
489
490/* Given a public blob, determine its length. */
491int rsa_public_blob_len(void *data, int maxlen)
492{
493    unsigned char *p = (unsigned char *)data;
494    int n;
495
496    if (maxlen < 4)
497        return -1;
498    p += 4;                            /* length word */
499    maxlen -= 4;
500
501    n = ssh1_read_bignum(p, maxlen, NULL);    /* exponent */
502    if (n < 0)
503        return -1;
504    p += n;
505
506    n = ssh1_read_bignum(p, maxlen, NULL);    /* modulus */
507    if (n < 0)
508        return -1;
509    p += n;
510
511    return p - (unsigned char *)data;
512}
513
514void freersakey(struct RSAKey *key)
515{
516    if (key->modulus)
517        freebn(key->modulus);
518    if (key->exponent)
519        freebn(key->exponent);
520    if (key->private_exponent)
521        freebn(key->private_exponent);
522    if (key->p)
523        freebn(key->p);
524    if (key->q)
525        freebn(key->q);
526    if (key->iqmp)
527        freebn(key->iqmp);
528    if (key->comment)
529        sfree(key->comment);
530}
531
532/* ----------------------------------------------------------------------
533 * Implementation of the ssh-rsa signing key type.
534 */
535
536static void getstring(const char **data, int *datalen,
537                      const char **p, int *length)
538{
539    *p = NULL;
540    if (*datalen < 4)
541        return;
542    *length = toint(GET_32BIT(*data));
543    if (*length < 0)
544        return;
545    *datalen -= 4;
546    *data += 4;
547    if (*datalen < *length)
548        return;
549    *p = *data;
550    *data += *length;
551    *datalen -= *length;
552}
553static Bignum getmp(const char **data, int *datalen)
554{
555    const char *p;
556    int length;
557    Bignum b;
558
559    getstring(data, datalen, &p, &length);
560    if (!p)
561        return NULL;
562    b = bignum_from_bytes((unsigned char *)p, length);
563    return b;
564}
565
566static void rsa2_freekey(void *key);   /* forward reference */
567
568static void *rsa2_newkey(const struct ssh_signkey *self,
569                         const char *data, int len)
570{
571    const char *p;
572    int slen;
573    struct RSAKey *rsa;
574
575    rsa = snew(struct RSAKey);
576    getstring(&data, &len, &p, &slen);
577
578    if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
579        sfree(rsa);
580        return NULL;
581    }
582    rsa->exponent = getmp(&data, &len);
583    rsa->modulus = getmp(&data, &len);
584    rsa->private_exponent = NULL;
585    rsa->p = rsa->q = rsa->iqmp = NULL;
586    rsa->comment = NULL;
587
588    if (!rsa->exponent || !rsa->modulus) {
589        rsa2_freekey(rsa);
590        return NULL;
591    }
592
593    return rsa;
594}
595
596static void rsa2_freekey(void *key)
597{
598    struct RSAKey *rsa = (struct RSAKey *) key;
599    freersakey(rsa);
600    sfree(rsa);
601}
602
603static char *rsa2_fmtkey(void *key)
604{
605    struct RSAKey *rsa = (struct RSAKey *) key;
606    char *p;
607    int len;
608
609    len = rsastr_len(rsa);
610    p = snewn(len, char);
611    rsastr_fmt(p, rsa);
612    return p;
613}
614
615static unsigned char *rsa2_public_blob(void *key, int *len)
616{
617    struct RSAKey *rsa = (struct RSAKey *) key;
618    int elen, mlen, bloblen;
619    int i;
620    unsigned char *blob, *p;
621
622    elen = (bignum_bitcount(rsa->exponent) + 8) / 8;
623    mlen = (bignum_bitcount(rsa->modulus) + 8) / 8;
624
625    /*
626     * string "ssh-rsa", mpint exp, mpint mod. Total 19+elen+mlen.
627     * (three length fields, 12+7=19).
628     */
629    bloblen = 19 + elen + mlen;
630    blob = snewn(bloblen, unsigned char);
631    p = blob;
632    PUT_32BIT(p, 7);
633    p += 4;
634    memcpy(p, "ssh-rsa", 7);
635    p += 7;
636    PUT_32BIT(p, elen);
637    p += 4;
638    for (i = elen; i--;)
639        *p++ = bignum_byte(rsa->exponent, i);
640    PUT_32BIT(p, mlen);
641    p += 4;
642    for (i = mlen; i--;)
643        *p++ = bignum_byte(rsa->modulus, i);
644    assert(p == blob + bloblen);
645    *len = bloblen;
646    return blob;
647}
648
649static unsigned char *rsa2_private_blob(void *key, int *len)
650{
651    struct RSAKey *rsa = (struct RSAKey *) key;
652    int dlen, plen, qlen, ulen, bloblen;
653    int i;
654    unsigned char *blob, *p;
655
656    dlen = (bignum_bitcount(rsa->private_exponent) + 8) / 8;
657    plen = (bignum_bitcount(rsa->p) + 8) / 8;
658    qlen = (bignum_bitcount(rsa->q) + 8) / 8;
659    ulen = (bignum_bitcount(rsa->iqmp) + 8) / 8;
660
661    /*
662     * mpint private_exp, mpint p, mpint q, mpint iqmp. Total 16 +
663     * sum of lengths.
664     */
665    bloblen = 16 + dlen + plen + qlen + ulen;
666    blob = snewn(bloblen, unsigned char);
667    p = blob;
668    PUT_32BIT(p, dlen);
669    p += 4;
670    for (i = dlen; i--;)
671        *p++ = bignum_byte(rsa->private_exponent, i);
672    PUT_32BIT(p, plen);
673    p += 4;
674    for (i = plen; i--;)
675        *p++ = bignum_byte(rsa->p, i);
676    PUT_32BIT(p, qlen);
677    p += 4;
678    for (i = qlen; i--;)
679        *p++ = bignum_byte(rsa->q, i);
680    PUT_32BIT(p, ulen);
681    p += 4;
682    for (i = ulen; i--;)
683        *p++ = bignum_byte(rsa->iqmp, i);
684    assert(p == blob + bloblen);
685    *len = bloblen;
686    return blob;
687}
688
689static void *rsa2_createkey(const struct ssh_signkey *self,
690                            const unsigned char *pub_blob, int pub_len,
691                            const unsigned char *priv_blob, int priv_len)
692{
693    struct RSAKey *rsa;
694    const char *pb = (const char *) priv_blob;
695
696    rsa = rsa2_newkey(self, (char *) pub_blob, pub_len);
697    rsa->private_exponent = getmp(&pb, &priv_len);
698    rsa->p = getmp(&pb, &priv_len);
699    rsa->q = getmp(&pb, &priv_len);
700    rsa->iqmp = getmp(&pb, &priv_len);
701
702    if (!rsa_verify(rsa)) {
703        rsa2_freekey(rsa);
704        return NULL;
705    }
706
707    return rsa;
708}
709
710static void *rsa2_openssh_createkey(const struct ssh_signkey *self,
711                                    const unsigned char **blob, int *len)
712{
713    const char **b = (const char **) blob;
714    struct RSAKey *rsa;
715
716    rsa = snew(struct RSAKey);
717    rsa->comment = NULL;
718
719    rsa->modulus = getmp(b, len);
720    rsa->exponent = getmp(b, len);
721    rsa->private_exponent = getmp(b, len);
722    rsa->iqmp = getmp(b, len);
723    rsa->p = getmp(b, len);
724    rsa->q = getmp(b, len);
725
726    if (!rsa->modulus || !rsa->exponent || !rsa->private_exponent ||
727        !rsa->iqmp || !rsa->p || !rsa->q) {
728        rsa2_freekey(rsa);
729        return NULL;
730    }
731
732    if (!rsa_verify(rsa)) {
733        rsa2_freekey(rsa);
734        return NULL;
735    }
736
737    return rsa;
738}
739
740static int rsa2_openssh_fmtkey(void *key, unsigned char *blob, int len)
741{
742    struct RSAKey *rsa = (struct RSAKey *) key;
743    int bloblen, i;
744
745    bloblen =
746        ssh2_bignum_length(rsa->modulus) +
747        ssh2_bignum_length(rsa->exponent) +
748        ssh2_bignum_length(rsa->private_exponent) +
749        ssh2_bignum_length(rsa->iqmp) +
750        ssh2_bignum_length(rsa->p) + ssh2_bignum_length(rsa->q);
751
752    if (bloblen > len)
753        return bloblen;
754
755    bloblen = 0;
756#define ENC(x) \
757    PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \
758    for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i);
759    ENC(rsa->modulus);
760    ENC(rsa->exponent);
761    ENC(rsa->private_exponent);
762    ENC(rsa->iqmp);
763    ENC(rsa->p);
764    ENC(rsa->q);
765
766    return bloblen;
767}
768
769static int rsa2_pubkey_bits(const struct ssh_signkey *self,
770                            const void *blob, int len)
771{
772    struct RSAKey *rsa;
773    int ret;
774
775    rsa = rsa2_newkey(self, (const char *) blob, len);
776    ret = bignum_bitcount(rsa->modulus);
777    rsa2_freekey(rsa);
778
779    return ret;
780}
781
782/*
783 * This is the magic ASN.1/DER prefix that goes in the decoded
784 * signature, between the string of FFs and the actual SHA hash
785 * value. The meaning of it is:
786 *
787 * 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself
788 *
789 * 30 21 -- a constructed SEQUENCE of length 0x21
790 *    30 09 -- a constructed sub-SEQUENCE of length 9
791 *       06 05 -- an object identifier, length 5
792 *          2B 0E 03 02 1A -- object id { 1 3 14 3 2 26 }
793 *                            (the 1,3 comes from 0x2B = 43 = 40*1+3)
794 *       05 00 -- NULL
795 *    04 14 -- a primitive OCTET STRING of length 0x14
796 *       [0x14 bytes of hash data follows]
797 *
798 * The object id in the middle there is listed as `id-sha1' in
799 * ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1d2.asn (the
800 * ASN module for PKCS #1) and its expanded form is as follows:
801 *
802 * id-sha1                OBJECT IDENTIFIER ::= {
803 *    iso(1) identified-organization(3) oiw(14) secsig(3)
804 *    algorithms(2) 26 }
805 */
806static const unsigned char asn1_weird_stuff[] = {
807    0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B,
808    0x0E, 0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14,
809};
810
811#define ASN1_LEN ( (int) sizeof(asn1_weird_stuff) )
812
813static int rsa2_verifysig(void *key, const char *sig, int siglen,
814                          const char *data, int datalen)
815{
816    struct RSAKey *rsa = (struct RSAKey *) key;
817    Bignum in, out;
818    const char *p;
819    int slen;
820    int bytes, i, j, ret;
821    unsigned char hash[20];
822
823    getstring(&sig, &siglen, &p, &slen);
824    if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
825        return 0;
826    }
827    in = getmp(&sig, &siglen);
828    if (!in)
829        return 0;
830    out = modpow(in, rsa->exponent, rsa->modulus);
831    freebn(in);
832
833    ret = 1;
834
835    bytes = (bignum_bitcount(rsa->modulus)+7) / 8;
836    /* Top (partial) byte should be zero. */
837    if (bignum_byte(out, bytes - 1) != 0)
838        ret = 0;
839    /* First whole byte should be 1. */
840    if (bignum_byte(out, bytes - 2) != 1)
841        ret = 0;
842    /* Most of the rest should be FF. */
843    for (i = bytes - 3; i >= 20 + ASN1_LEN; i--) {
844        if (bignum_byte(out, i) != 0xFF)
845            ret = 0;
846    }
847    /* Then we expect to see the asn1_weird_stuff. */
848    for (i = 20 + ASN1_LEN - 1, j = 0; i >= 20; i--, j++) {
849        if (bignum_byte(out, i) != asn1_weird_stuff[j])
850            ret = 0;
851    }
852    /* Finally, we expect to see the SHA-1 hash of the signed data. */
853    SHA_Simple(data, datalen, hash);
854    for (i = 19, j = 0; i >= 0; i--, j++) {
855        if (bignum_byte(out, i) != hash[j])
856            ret = 0;
857    }
858    freebn(out);
859
860    return ret;
861}
862
863static unsigned char *rsa2_sign(void *key, const char *data, int datalen,
864                                int *siglen)
865{
866    struct RSAKey *rsa = (struct RSAKey *) key;
867    unsigned char *bytes;
868    int nbytes;
869    unsigned char hash[20];
870    Bignum in, out;
871    int i, j;
872
873    SHA_Simple(data, datalen, hash);
874
875    nbytes = (bignum_bitcount(rsa->modulus) - 1) / 8;
876    assert(1 <= nbytes - 20 - ASN1_LEN);
877    bytes = snewn(nbytes, unsigned char);
878
879    bytes[0] = 1;
880    for (i = 1; i < nbytes - 20 - ASN1_LEN; i++)
881        bytes[i] = 0xFF;
882    for (i = nbytes - 20 - ASN1_LEN, j = 0; i < nbytes - 20; i++, j++)
883        bytes[i] = asn1_weird_stuff[j];
884    for (i = nbytes - 20, j = 0; i < nbytes; i++, j++)
885        bytes[i] = hash[j];
886
887    in = bignum_from_bytes(bytes, nbytes);
888    sfree(bytes);
889
890    out = rsa_privkey_op(in, rsa);
891    freebn(in);
892
893    nbytes = (bignum_bitcount(out) + 7) / 8;
894    bytes = snewn(4 + 7 + 4 + nbytes, unsigned char);
895    PUT_32BIT(bytes, 7);
896    memcpy(bytes + 4, "ssh-rsa", 7);
897    PUT_32BIT(bytes + 4 + 7, nbytes);
898    for (i = 0; i < nbytes; i++)
899        bytes[4 + 7 + 4 + i] = bignum_byte(out, nbytes - 1 - i);
900    freebn(out);
901
902    *siglen = 4 + 7 + 4 + nbytes;
903    return bytes;
904}
905
906const struct ssh_signkey ssh_rsa = {
907    rsa2_newkey,
908    rsa2_freekey,
909    rsa2_fmtkey,
910    rsa2_public_blob,
911    rsa2_private_blob,
912    rsa2_createkey,
913    rsa2_openssh_createkey,
914    rsa2_openssh_fmtkey,
915    6 /* n,e,d,iqmp,q,p */,
916    rsa2_pubkey_bits,
917    rsa2_verifysig,
918    rsa2_sign,
919    "ssh-rsa",
920    "rsa2",
921    NULL,
922};
923
924void *ssh_rsakex_newkey(char *data, int len)
925{
926    return rsa2_newkey(&ssh_rsa, data, len);
927}
928
929void ssh_rsakex_freekey(void *key)
930{
931    rsa2_freekey(key);
932}
933
934int ssh_rsakex_klen(void *key)
935{
936    struct RSAKey *rsa = (struct RSAKey *) key;
937
938    return bignum_bitcount(rsa->modulus);
939}
940
941static void oaep_mask(const struct ssh_hash *h, void *seed, int seedlen,
942                      void *vdata, int datalen)
943{
944    unsigned char *data = (unsigned char *)vdata;
945    unsigned count = 0;
946
947    while (datalen > 0) {
948        int i, max = (datalen > h->hlen ? h->hlen : datalen);
949        void *s;
950        unsigned char counter[4], hash[SSH2_KEX_MAX_HASH_LEN];
951
952        assert(h->hlen <= SSH2_KEX_MAX_HASH_LEN);
953        PUT_32BIT(counter, count);
954        s = h->init();
955        h->bytes(s, seed, seedlen);
956        h->bytes(s, counter, 4);
957        h->final(s, hash);
958        count++;
959
960        for (i = 0; i < max; i++)
961            data[i] ^= hash[i];
962
963        data += max;
964        datalen -= max;
965    }
966}
967
968void ssh_rsakex_encrypt(const struct ssh_hash *h, unsigned char *in, int inlen,
969                        unsigned char *out, int outlen,
970                        void *key)
971{
972    Bignum b1, b2;
973    struct RSAKey *rsa = (struct RSAKey *) key;
974    int k, i;
975    char *p;
976    const int HLEN = h->hlen;
977
978    /*
979     * Here we encrypt using RSAES-OAEP. Essentially this means:
980     *
981     *  - we have a SHA-based `mask generation function' which
982     *    creates a pseudo-random stream of mask data
983     *    deterministically from an input chunk of data.
984     *
985     *  - we have a random chunk of data called a seed.
986     *
987     *  - we use the seed to generate a mask which we XOR with our
988     *    plaintext.
989     *
990     *  - then we use _the masked plaintext_ to generate a mask
991     *    which we XOR with the seed.
992     *
993     *  - then we concatenate the masked seed and the masked
994     *    plaintext, and RSA-encrypt that lot.
995     *
996     * The result is that the data input to the encryption function
997     * is random-looking and (hopefully) contains no exploitable
998     * structure such as PKCS1-v1_5 does.
999     *
1000     * For a precise specification, see RFC 3447, section 7.1.1.
1001     * Some of the variable names below are derived from that, so
1002     * it'd probably help to read it anyway.
1003     */
1004
1005    /* k denotes the length in octets of the RSA modulus. */
1006    k = (7 + bignum_bitcount(rsa->modulus)) / 8;
1007
1008    /* The length of the input data must be at most k - 2hLen - 2. */
1009    assert(inlen > 0 && inlen <= k - 2*HLEN - 2);
1010
1011    /* The length of the output data wants to be precisely k. */
1012    assert(outlen == k);
1013
1014    /*
1015     * Now perform EME-OAEP encoding. First set up all the unmasked
1016     * output data.
1017     */
1018    /* Leading byte zero. */
1019    out[0] = 0;
1020    /* At position 1, the seed: HLEN bytes of random data. */
1021    for (i = 0; i < HLEN; i++)
1022        out[i + 1] = random_byte();
1023    /* At position 1+HLEN, the data block DB, consisting of: */
1024    /* The hash of the label (we only support an empty label here) */
1025    h->final(h->init(), out + HLEN + 1);
1026    /* A bunch of zero octets */
1027    memset(out + 2*HLEN + 1, 0, outlen - (2*HLEN + 1));
1028    /* A single 1 octet, followed by the input message data. */
1029    out[outlen - inlen - 1] = 1;
1030    memcpy(out + outlen - inlen, in, inlen);
1031
1032    /*
1033     * Now use the seed data to mask the block DB.
1034     */
1035    oaep_mask(h, out+1, HLEN, out+HLEN+1, outlen-HLEN-1);
1036
1037    /*
1038     * And now use the masked DB to mask the seed itself.
1039     */
1040    oaep_mask(h, out+HLEN+1, outlen-HLEN-1, out+1, HLEN);
1041
1042    /*
1043     * Now `out' contains precisely the data we want to
1044     * RSA-encrypt.
1045     */
1046    b1 = bignum_from_bytes(out, outlen);
1047    b2 = modpow(b1, rsa->exponent, rsa->modulus);
1048    p = (char *)out;
1049    for (i = outlen; i--;) {
1050        *p++ = bignum_byte(b2, i);
1051    }
1052    freebn(b1);
1053    freebn(b2);
1054
1055    /*
1056     * And we're done.
1057     */
1058}
1059
1060static const struct ssh_kex ssh_rsa_kex_sha1 = {
1061    "rsa1024-sha1", NULL, KEXTYPE_RSA, &ssh_sha1, NULL,
1062};
1063
1064static const struct ssh_kex ssh_rsa_kex_sha256 = {
1065    "rsa2048-sha256", NULL, KEXTYPE_RSA, &ssh_sha256, NULL,
1066};
1067
1068static const struct ssh_kex *const rsa_kex_list[] = {
1069    &ssh_rsa_kex_sha256,
1070    &ssh_rsa_kex_sha1
1071};
1072
1073const struct ssh_kexes ssh_rsa_kex = {
1074    sizeof(rsa_kex_list) / sizeof(*rsa_kex_list),
1075    rsa_kex_list
1076};
Note: See TracBrowser for help on using the repository browser.