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