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

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

First release to xenial

File size: 17.4 KB
Line 
1/*
2 * Digital Signature Standard implementation for PuTTY.
3 */
4
5#include <stdio.h>
6#include <stdlib.h>
7#include <assert.h>
8
9#include "ssh.h"
10#include "misc.h"
11
12static void sha_mpint(SHA_State * s, Bignum b)
13{
14    unsigned char lenbuf[4];
15    int len;
16    len = (bignum_bitcount(b) + 8) / 8;
17    PUT_32BIT(lenbuf, len);
18    SHA_Bytes(s, lenbuf, 4);
19    while (len-- > 0) {
20        lenbuf[0] = bignum_byte(b, len);
21        SHA_Bytes(s, lenbuf, 1);
22    }
23    smemclr(lenbuf, sizeof(lenbuf));
24}
25
26static void sha512_mpint(SHA512_State * s, Bignum b)
27{
28    unsigned char lenbuf[4];
29    int len;
30    len = (bignum_bitcount(b) + 8) / 8;
31    PUT_32BIT(lenbuf, len);
32    SHA512_Bytes(s, lenbuf, 4);
33    while (len-- > 0) {
34        lenbuf[0] = bignum_byte(b, len);
35        SHA512_Bytes(s, lenbuf, 1);
36    }
37    smemclr(lenbuf, sizeof(lenbuf));
38}
39
40static void getstring(const char **data, int *datalen,
41                      const char **p, int *length)
42{
43    *p = NULL;
44    if (*datalen < 4)
45        return;
46    *length = toint(GET_32BIT(*data));
47    if (*length < 0)
48        return;
49    *datalen -= 4;
50    *data += 4;
51    if (*datalen < *length)
52        return;
53    *p = *data;
54    *data += *length;
55    *datalen -= *length;
56}
57static Bignum getmp(const char **data, int *datalen)
58{
59    const char *p;
60    int length;
61    Bignum b;
62
63    getstring(data, datalen, &p, &length);
64    if (!p)
65        return NULL;
66    if (p[0] & 0x80)
67        return NULL;                   /* negative mp */
68    b = bignum_from_bytes((const unsigned char *)p, length);
69    return b;
70}
71
72static Bignum get160(const char **data, int *datalen)
73{
74    Bignum b;
75
76    if (*datalen < 20)
77        return NULL;
78
79    b = bignum_from_bytes((const unsigned char *)*data, 20);
80    *data += 20;
81    *datalen -= 20;
82
83    return b;
84}
85
86static void dss_freekey(void *key);    /* forward reference */
87
88static void *dss_newkey(const struct ssh_signkey *self,
89                        const char *data, int len)
90{
91    const char *p;
92    int slen;
93    struct dss_key *dss;
94
95    dss = snew(struct dss_key);
96    getstring(&data, &len, &p, &slen);
97
98#ifdef DEBUG_DSS
99    {
100        int i;
101        printf("key:");
102        for (i = 0; i < len; i++)
103            printf("  %02x", (unsigned char) (data[i]));
104        printf("\n");
105    }
106#endif
107
108    if (!p || slen != 7 || memcmp(p, "ssh-dss", 7)) {
109        sfree(dss);
110        return NULL;
111    }
112    dss->p = getmp(&data, &len);
113    dss->q = getmp(&data, &len);
114    dss->g = getmp(&data, &len);
115    dss->y = getmp(&data, &len);
116    dss->x = NULL;
117
118    if (!dss->p || !dss->q || !dss->g || !dss->y ||
119        !bignum_cmp(dss->q, Zero) || !bignum_cmp(dss->p, Zero)) {
120        /* Invalid key. */
121        dss_freekey(dss);
122        return NULL;
123    }
124
125    return dss;
126}
127
128static void dss_freekey(void *key)
129{
130    struct dss_key *dss = (struct dss_key *) key;
131    if (dss->p)
132        freebn(dss->p);
133    if (dss->q)
134        freebn(dss->q);
135    if (dss->g)
136        freebn(dss->g);
137    if (dss->y)
138        freebn(dss->y);
139    if (dss->x)
140        freebn(dss->x);
141    sfree(dss);
142}
143
144static char *dss_fmtkey(void *key)
145{
146    struct dss_key *dss = (struct dss_key *) key;
147    char *p;
148    int len, i, pos, nibbles;
149    static const char hex[] = "0123456789abcdef";
150    if (!dss->p)
151        return NULL;
152    len = 8 + 4 + 1;                   /* 4 x "0x", punctuation, \0 */
153    len += 4 * (bignum_bitcount(dss->p) + 15) / 16;
154    len += 4 * (bignum_bitcount(dss->q) + 15) / 16;
155    len += 4 * (bignum_bitcount(dss->g) + 15) / 16;
156    len += 4 * (bignum_bitcount(dss->y) + 15) / 16;
157    p = snewn(len, char);
158    if (!p)
159        return NULL;
160
161    pos = 0;
162    pos += sprintf(p + pos, "0x");
163    nibbles = (3 + bignum_bitcount(dss->p)) / 4;
164    if (nibbles < 1)
165        nibbles = 1;
166    for (i = nibbles; i--;)
167        p[pos++] =
168            hex[(bignum_byte(dss->p, i / 2) >> (4 * (i % 2))) & 0xF];
169    pos += sprintf(p + pos, ",0x");
170    nibbles = (3 + bignum_bitcount(dss->q)) / 4;
171    if (nibbles < 1)
172        nibbles = 1;
173    for (i = nibbles; i--;)
174        p[pos++] =
175            hex[(bignum_byte(dss->q, i / 2) >> (4 * (i % 2))) & 0xF];
176    pos += sprintf(p + pos, ",0x");
177    nibbles = (3 + bignum_bitcount(dss->g)) / 4;
178    if (nibbles < 1)
179        nibbles = 1;
180    for (i = nibbles; i--;)
181        p[pos++] =
182            hex[(bignum_byte(dss->g, i / 2) >> (4 * (i % 2))) & 0xF];
183    pos += sprintf(p + pos, ",0x");
184    nibbles = (3 + bignum_bitcount(dss->y)) / 4;
185    if (nibbles < 1)
186        nibbles = 1;
187    for (i = nibbles; i--;)
188        p[pos++] =
189            hex[(bignum_byte(dss->y, i / 2) >> (4 * (i % 2))) & 0xF];
190    p[pos] = '\0';
191    return p;
192}
193
194static int dss_verifysig(void *key, const char *sig, int siglen,
195                         const char *data, int datalen)
196{
197    struct dss_key *dss = (struct dss_key *) key;
198    const char *p;
199    int slen;
200    char hash[20];
201    Bignum r, s, w, gu1p, yu2p, gu1yu2p, u1, u2, sha, v;
202    int ret;
203
204    if (!dss->p)
205        return 0;
206
207#ifdef DEBUG_DSS
208    {
209        int i;
210        printf("sig:");
211        for (i = 0; i < siglen; i++)
212            printf("  %02x", (unsigned char) (sig[i]));
213        printf("\n");
214    }
215#endif
216    /*
217     * Commercial SSH (2.0.13) and OpenSSH disagree over the format
218     * of a DSA signature. OpenSSH is in line with RFC 4253:
219     * it uses a string "ssh-dss", followed by a 40-byte string
220     * containing two 160-bit integers end-to-end. Commercial SSH
221     * can't be bothered with the header bit, and considers a DSA
222     * signature blob to be _just_ the 40-byte string containing
223     * the two 160-bit integers. We tell them apart by measuring
224     * the length: length 40 means the commercial-SSH bug, anything
225     * else is assumed to be RFC-compliant.
226     */
227    if (siglen != 40) {                /* bug not present; read admin fields */
228        getstring(&sig, &siglen, &p, &slen);
229        if (!p || slen != 7 || memcmp(p, "ssh-dss", 7)) {
230            return 0;
231        }
232        sig += 4, siglen -= 4;         /* skip yet another length field */
233    }
234    r = get160(&sig, &siglen);
235    s = get160(&sig, &siglen);
236    if (!r || !s) {
237        if (r)
238            freebn(r);
239        if (s)
240            freebn(s);
241        return 0;
242    }
243
244    if (!bignum_cmp(s, Zero)) {
245        freebn(r);
246        freebn(s);
247        return 0;
248    }
249
250    /*
251     * Step 1. w <- s^-1 mod q.
252     */
253    w = modinv(s, dss->q);
254    if (!w) {
255        freebn(r);
256        freebn(s);
257        return 0;
258    }
259
260    /*
261     * Step 2. u1 <- SHA(message) * w mod q.
262     */
263    SHA_Simple(data, datalen, (unsigned char *)hash);
264    p = hash;
265    slen = 20;
266    sha = get160(&p, &slen);
267    u1 = modmul(sha, w, dss->q);
268
269    /*
270     * Step 3. u2 <- r * w mod q.
271     */
272    u2 = modmul(r, w, dss->q);
273
274    /*
275     * Step 4. v <- (g^u1 * y^u2 mod p) mod q.
276     */
277    gu1p = modpow(dss->g, u1, dss->p);
278    yu2p = modpow(dss->y, u2, dss->p);
279    gu1yu2p = modmul(gu1p, yu2p, dss->p);
280    v = modmul(gu1yu2p, One, dss->q);
281
282    /*
283     * Step 5. v should now be equal to r.
284     */
285
286    ret = !bignum_cmp(v, r);
287
288    freebn(w);
289    freebn(sha);
290    freebn(u1);
291    freebn(u2);
292    freebn(gu1p);
293    freebn(yu2p);
294    freebn(gu1yu2p);
295    freebn(v);
296    freebn(r);
297    freebn(s);
298
299    return ret;
300}
301
302static unsigned char *dss_public_blob(void *key, int *len)
303{
304    struct dss_key *dss = (struct dss_key *) key;
305    int plen, qlen, glen, ylen, bloblen;
306    int i;
307    unsigned char *blob, *p;
308
309    plen = (bignum_bitcount(dss->p) + 8) / 8;
310    qlen = (bignum_bitcount(dss->q) + 8) / 8;
311    glen = (bignum_bitcount(dss->g) + 8) / 8;
312    ylen = (bignum_bitcount(dss->y) + 8) / 8;
313
314    /*
315     * string "ssh-dss", mpint p, mpint q, mpint g, mpint y. Total
316     * 27 + sum of lengths. (five length fields, 20+7=27).
317     */
318    bloblen = 27 + plen + qlen + glen + ylen;
319    blob = snewn(bloblen, unsigned char);
320    p = blob;
321    PUT_32BIT(p, 7);
322    p += 4;
323    memcpy(p, "ssh-dss", 7);
324    p += 7;
325    PUT_32BIT(p, plen);
326    p += 4;
327    for (i = plen; i--;)
328        *p++ = bignum_byte(dss->p, i);
329    PUT_32BIT(p, qlen);
330    p += 4;
331    for (i = qlen; i--;)
332        *p++ = bignum_byte(dss->q, i);
333    PUT_32BIT(p, glen);
334    p += 4;
335    for (i = glen; i--;)
336        *p++ = bignum_byte(dss->g, i);
337    PUT_32BIT(p, ylen);
338    p += 4;
339    for (i = ylen; i--;)
340        *p++ = bignum_byte(dss->y, i);
341    assert(p == blob + bloblen);
342    *len = bloblen;
343    return blob;
344}
345
346static unsigned char *dss_private_blob(void *key, int *len)
347{
348    struct dss_key *dss = (struct dss_key *) key;
349    int xlen, bloblen;
350    int i;
351    unsigned char *blob, *p;
352
353    xlen = (bignum_bitcount(dss->x) + 8) / 8;
354
355    /*
356     * mpint x, string[20] the SHA of p||q||g. Total 4 + xlen.
357     */
358    bloblen = 4 + xlen;
359    blob = snewn(bloblen, unsigned char);
360    p = blob;
361    PUT_32BIT(p, xlen);
362    p += 4;
363    for (i = xlen; i--;)
364        *p++ = bignum_byte(dss->x, i);
365    assert(p == blob + bloblen);
366    *len = bloblen;
367    return blob;
368}
369
370static void *dss_createkey(const struct ssh_signkey *self,
371                           const unsigned char *pub_blob, int pub_len,
372                           const unsigned char *priv_blob, int priv_len)
373{
374    struct dss_key *dss;
375    const char *pb = (const char *) priv_blob;
376    const char *hash;
377    int hashlen;
378    SHA_State s;
379    unsigned char digest[20];
380    Bignum ytest;
381
382    dss = dss_newkey(self, (char *) pub_blob, pub_len);
383    if (!dss)
384        return NULL;
385    dss->x = getmp(&pb, &priv_len);
386    if (!dss->x) {
387        dss_freekey(dss);
388        return NULL;
389    }
390
391    /*
392     * Check the obsolete hash in the old DSS key format.
393     */
394    hashlen = -1;
395    getstring(&pb, &priv_len, &hash, &hashlen);
396    if (hashlen == 20) {
397        SHA_Init(&s);
398        sha_mpint(&s, dss->p);
399        sha_mpint(&s, dss->q);
400        sha_mpint(&s, dss->g);
401        SHA_Final(&s, digest);
402        if (0 != memcmp(hash, digest, 20)) {
403            dss_freekey(dss);
404            return NULL;
405        }
406    }
407
408    /*
409     * Now ensure g^x mod p really is y.
410     */
411    ytest = modpow(dss->g, dss->x, dss->p);
412    if (0 != bignum_cmp(ytest, dss->y)) {
413        dss_freekey(dss);
414        freebn(ytest);
415        return NULL;
416    }
417    freebn(ytest);
418
419    return dss;
420}
421
422static void *dss_openssh_createkey(const struct ssh_signkey *self,
423                                   const unsigned char **blob, int *len)
424{
425    const char **b = (const char **) blob;
426    struct dss_key *dss;
427
428    dss = snew(struct dss_key);
429
430    dss->p = getmp(b, len);
431    dss->q = getmp(b, len);
432    dss->g = getmp(b, len);
433    dss->y = getmp(b, len);
434    dss->x = getmp(b, len);
435
436    if (!dss->p || !dss->q || !dss->g || !dss->y || !dss->x ||
437        !bignum_cmp(dss->q, Zero) || !bignum_cmp(dss->p, Zero)) {
438        /* Invalid key. */
439        dss_freekey(dss);
440        return NULL;
441    }
442
443    return dss;
444}
445
446static int dss_openssh_fmtkey(void *key, unsigned char *blob, int len)
447{
448    struct dss_key *dss = (struct dss_key *) key;
449    int bloblen, i;
450
451    bloblen =
452        ssh2_bignum_length(dss->p) +
453        ssh2_bignum_length(dss->q) +
454        ssh2_bignum_length(dss->g) +
455        ssh2_bignum_length(dss->y) +
456        ssh2_bignum_length(dss->x);
457
458    if (bloblen > len)
459        return bloblen;
460
461    bloblen = 0;
462#define ENC(x) \
463    PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \
464    for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i);
465    ENC(dss->p);
466    ENC(dss->q);
467    ENC(dss->g);
468    ENC(dss->y);
469    ENC(dss->x);
470
471    return bloblen;
472}
473
474static int dss_pubkey_bits(const struct ssh_signkey *self,
475                           const void *blob, int len)
476{
477    struct dss_key *dss;
478    int ret;
479
480    dss = dss_newkey(self, (const char *) blob, len);
481    if (!dss)
482        return -1;
483    ret = bignum_bitcount(dss->p);
484    dss_freekey(dss);
485
486    return ret;
487}
488
489Bignum *dss_gen_k(const char *id_string, Bignum modulus, Bignum private_key,
490                  unsigned char *digest, int digest_len)
491{
492    /*
493     * The basic DSS signing algorithm is:
494     *
495     *  - invent a random k between 1 and q-1 (exclusive).
496     *  - Compute r = (g^k mod p) mod q.
497     *  - Compute s = k^-1 * (hash + x*r) mod q.
498     *
499     * This has the dangerous properties that:
500     *
501     *  - if an attacker in possession of the public key _and_ the
502     *    signature (for example, the host you just authenticated
503     *    to) can guess your k, he can reverse the computation of s
504     *    and work out x = r^-1 * (s*k - hash) mod q. That is, he
505     *    can deduce the private half of your key, and masquerade
506     *    as you for as long as the key is still valid.
507     *
508     *  - since r is a function purely of k and the public key, if
509     *    the attacker only has a _range of possibilities_ for k
510     *    it's easy for him to work through them all and check each
511     *    one against r; he'll never be unsure of whether he's got
512     *    the right one.
513     *
514     *  - if you ever sign two different hashes with the same k, it
515     *    will be immediately obvious because the two signatures
516     *    will have the same r, and moreover an attacker in
517     *    possession of both signatures (and the public key of
518     *    course) can compute k = (hash1-hash2) * (s1-s2)^-1 mod q,
519     *    and from there deduce x as before.
520     *
521     *  - the Bleichenbacher attack on DSA makes use of methods of
522     *    generating k which are significantly non-uniformly
523     *    distributed; in particular, generating a 160-bit random
524     *    number and reducing it mod q is right out.
525     *
526     * For this reason we must be pretty careful about how we
527     * generate our k. Since this code runs on Windows, with no
528     * particularly good system entropy sources, we can't trust our
529     * RNG itself to produce properly unpredictable data. Hence, we
530     * use a totally different scheme instead.
531     *
532     * What we do is to take a SHA-512 (_big_) hash of the private
533     * key x, and then feed this into another SHA-512 hash that
534     * also includes the message hash being signed. That is:
535     *
536     *   proto_k = SHA512 ( SHA512(x) || SHA160(message) )
537     *
538     * This number is 512 bits long, so reducing it mod q won't be
539     * noticeably non-uniform. So
540     *
541     *   k = proto_k mod q
542     *
543     * This has the interesting property that it's _deterministic_:
544     * signing the same hash twice with the same key yields the
545     * same signature.
546     *
547     * Despite this determinism, it's still not predictable to an
548     * attacker, because in order to repeat the SHA-512
549     * construction that created it, the attacker would have to
550     * know the private key value x - and by assumption he doesn't,
551     * because if he knew that he wouldn't be attacking k!
552     *
553     * (This trick doesn't, _per se_, protect against reuse of k.
554     * Reuse of k is left to chance; all it does is prevent
555     * _excessively high_ chances of reuse of k due to entropy
556     * problems.)
557     *
558     * Thanks to Colin Plumb for the general idea of using x to
559     * ensure k is hard to guess, and to the Cambridge University
560     * Computer Security Group for helping to argue out all the
561     * fine details.
562     */
563    SHA512_State ss;
564    unsigned char digest512[64];
565    Bignum proto_k, k;
566
567    /*
568     * Hash some identifying text plus x.
569     */
570    SHA512_Init(&ss);
571    SHA512_Bytes(&ss, id_string, strlen(id_string) + 1);
572    sha512_mpint(&ss, private_key);
573    SHA512_Final(&ss, digest512);
574
575    /*
576     * Now hash that digest plus the message hash.
577     */
578    SHA512_Init(&ss);
579    SHA512_Bytes(&ss, digest512, sizeof(digest512));
580    SHA512_Bytes(&ss, digest, digest_len);
581
582    while (1) {
583        SHA512_State ss2 = ss;         /* structure copy */
584        SHA512_Final(&ss2, digest512);
585
586        smemclr(&ss2, sizeof(ss2));
587
588        /*
589         * Now convert the result into a bignum, and reduce it mod q.
590         */
591        proto_k = bignum_from_bytes(digest512, 64);
592        k = bigmod(proto_k, modulus);
593        freebn(proto_k);
594
595        if (bignum_cmp(k, One) != 0 && bignum_cmp(k, Zero) != 0) {
596            smemclr(&ss, sizeof(ss));
597            smemclr(digest512, sizeof(digest512));
598            return k;
599        }
600
601        /* Very unlikely we get here, but if so, k was unsuitable. */
602        freebn(k);
603        /* Perturb the hash to think of a different k. */
604        SHA512_Bytes(&ss, "x", 1);
605        /* Go round and try again. */
606    }
607}
608
609static unsigned char *dss_sign(void *key, const char *data, int datalen,
610                               int *siglen)
611{
612    struct dss_key *dss = (struct dss_key *) key;
613    Bignum k, gkp, hash, kinv, hxr, r, s;
614    unsigned char digest[20];
615    unsigned char *bytes;
616    int nbytes, i;
617
618    SHA_Simple(data, datalen, digest);
619
620    k = dss_gen_k("DSA deterministic k generator", dss->q, dss->x,
621                  digest, sizeof(digest));
622    kinv = modinv(k, dss->q);          /* k^-1 mod q */
623    assert(kinv);
624
625    /*
626     * Now we have k, so just go ahead and compute the signature.
627     */
628    gkp = modpow(dss->g, k, dss->p);   /* g^k mod p */
629    r = bigmod(gkp, dss->q);           /* r = (g^k mod p) mod q */
630    freebn(gkp);
631
632    hash = bignum_from_bytes(digest, 20);
633    hxr = bigmuladd(dss->x, r, hash);  /* hash + x*r */
634    s = modmul(kinv, hxr, dss->q);     /* s = k^-1 * (hash + x*r) mod q */
635    freebn(hxr);
636    freebn(kinv);
637    freebn(k);
638    freebn(hash);
639
640    /*
641     * Signature blob is
642     *
643     *   string  "ssh-dss"
644     *   string  two 20-byte numbers r and s, end to end
645     *
646     * i.e. 4+7 + 4+40 bytes.
647     */
648    nbytes = 4 + 7 + 4 + 40;
649    bytes = snewn(nbytes, unsigned char);
650    PUT_32BIT(bytes, 7);
651    memcpy(bytes + 4, "ssh-dss", 7);
652    PUT_32BIT(bytes + 4 + 7, 40);
653    for (i = 0; i < 20; i++) {
654        bytes[4 + 7 + 4 + i] = bignum_byte(r, 19 - i);
655        bytes[4 + 7 + 4 + 20 + i] = bignum_byte(s, 19 - i);
656    }
657    freebn(r);
658    freebn(s);
659
660    *siglen = nbytes;
661    return bytes;
662}
663
664const struct ssh_signkey ssh_dss = {
665    dss_newkey,
666    dss_freekey,
667    dss_fmtkey,
668    dss_public_blob,
669    dss_private_blob,
670    dss_createkey,
671    dss_openssh_createkey,
672    dss_openssh_fmtkey,
673    5 /* p,q,g,y,x */,
674    dss_pubkey_bits,
675    dss_verifysig,
676    dss_sign,
677    "ssh-dss",
678    "dss",
679    NULL,
680};
Note: See TracBrowser for help on using the repository browser.