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