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