| blob | 644f971a22067999d237f1db5820b37e8646c33c |
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 bn_restore_invariant(random);\r
268 \r
269 /*\r
270 * Now check that this number is strictly greater than\r
271 * zero, and strictly less than modulus.\r
272 */\r
273 if (bignum_cmp(random, Zero) <= 0 ||\r
274 bignum_cmp(random, key->modulus) >= 0) {\r
275 freebn(random);\r
276 continue;\r
277 }\r
278 \r
279 /*\r
280 * Also, make sure it has an inverse mod modulus.\r
281 */\r
282 random_inverse = modinv(random, key->modulus);\r
283 if (!random_inverse) {\r
284 freebn(random);\r
285 continue;\r
286 }\r
287 \r
288 break;\r
289 }\r
290 \r
291 /*\r
292 * RSA blinding relies on the fact that (xy)^d mod n is equal\r
293 * to (x^d mod n) * (y^d mod n) mod n. We invent a random pair\r
294 * y and y^d; then we multiply x by y, raise to the power d mod\r
295 * n as usual, and divide by y^d to recover x^d. Thus an\r
296 * attacker can't correlate the timing of the modpow with the\r
297 * input, because they don't know anything about the number\r
298 * that was input to the actual modpow.\r
299 * \r
300 * The clever bit is that we don't have to do a huge modpow to\r
301 * get y and y^d; we will use the number we just invented as\r
302 * _y^d_, and use the _public_ exponent to compute (y^d)^e = y\r
303 * from it, which is much faster to do.\r
304 */\r
305 random_encrypted = crt_modpow(random, key->exponent,\r
306 key->modulus, key->p, key->q, key->iqmp);\r
307 input_blinded = modmul(input, random_encrypted, key->modulus);\r
308 ret_blinded = crt_modpow(input_blinded, key->private_exponent,\r
309 key->modulus, key->p, key->q, key->iqmp);\r
310 ret = modmul(ret_blinded, random_inverse, key->modulus);\r
311 \r
312 freebn(ret_blinded);\r
313 freebn(input_blinded);\r
314 freebn(random_inverse);\r
315 freebn(random_encrypted);\r
316 freebn(random);\r
317 \r
318 return ret;\r
319 }\r
320 \r
321 Bignum rsadecrypt(Bignum input, struct RSAKey *key)\r
322 {\r
323 return rsa_privkey_op(input, key);\r
324 }\r
325 \r
326 int rsastr_len(struct RSAKey *key)\r
327 {\r
328 Bignum md, ex;\r
329 int mdlen, exlen;\r
330 \r
331 md = key->modulus;\r
332 ex = key->exponent;\r
333 mdlen = (bignum_bitcount(md) + 15) / 16;\r
334 exlen = (bignum_bitcount(ex) + 15) / 16;\r
335 return 4 * (mdlen + exlen) + 20;\r
336 }\r
337 \r
338 void rsastr_fmt(char *str, struct RSAKey *key)\r
339 {\r
340 Bignum md, ex;\r
341 int len = 0, i, nibbles;\r
342 static const char hex[] = "0123456789abcdef";\r
343 \r
344 md = key->modulus;\r
345 ex = key->exponent;\r
346 \r
347 len += sprintf(str + len, "0x");\r
348 \r
349 nibbles = (3 + bignum_bitcount(ex)) / 4;\r
350 if (nibbles < 1)\r
351 nibbles = 1;\r
352 for (i = nibbles; i--;)\r
353 str[len++] = hex[(bignum_byte(ex, i / 2) >> (4 * (i % 2))) & 0xF];\r
354 \r
355 len += sprintf(str + len, ",0x");\r
356 \r
357 nibbles = (3 + bignum_bitcount(md)) / 4;\r
358 if (nibbles < 1)\r
359 nibbles = 1;\r
360 for (i = nibbles; i--;)\r
361 str[len++] = hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF];\r
362 \r
363 str[len] = '\0';\r
364 }\r
365 \r
366 /*\r
367 * Generate a fingerprint string for the key. Compatible with the\r
368 * OpenSSH fingerprint code.\r
369 */\r
370 void rsa_fingerprint(char *str, int len, struct RSAKey *key)\r
371 {\r
372 struct MD5Context md5c;\r
373 unsigned char digest[16];\r
374 char buffer[16 * 3 + 40];\r
375 int numlen, slen, i;\r
376 \r
377 MD5Init(&md5c);\r
378 numlen = ssh1_bignum_length(key->modulus) - 2;\r
379 for (i = numlen; i--;) {\r
380 unsigned char c = bignum_byte(key->modulus, i);\r
381 MD5Update(&md5c, &c, 1);\r
382 }\r
383 numlen = ssh1_bignum_length(key->exponent) - 2;\r
384 for (i = numlen; i--;) {\r
385 unsigned char c = bignum_byte(key->exponent, i);\r
386 MD5Update(&md5c, &c, 1);\r
387 }\r
388 MD5Final(digest, &md5c);\r
389 \r
390 sprintf(buffer, "%d ", bignum_bitcount(key->modulus));\r
391 for (i = 0; i < 16; i++)\r
392 sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",\r
393 digest[i]);\r
394 strncpy(str, buffer, len);\r
395 str[len - 1] = '\0';\r
396 slen = strlen(str);\r
397 if (key->comment && slen < len - 1) {\r
398 str[slen] = ' ';\r
399 strncpy(str + slen + 1, key->comment, len - slen - 1);\r
400 str[len - 1] = '\0';\r
401 }\r
402 }\r
403 \r
404 /*\r
405 * Verify that the public data in an RSA key matches the private\r
406 * data. We also check the private data itself: we ensure that p >\r
407 * q and that iqmp really is the inverse of q mod p.\r
408 */\r
409 int rsa_verify(struct RSAKey *key)\r
410 {\r
411 Bignum n, ed, pm1, qm1;\r
412 int cmp;\r
413 \r
414 /* n must equal pq. */\r
415 n = bigmul(key->p, key->q);\r
416 cmp = bignum_cmp(n, key->modulus);\r
417 freebn(n);\r
418 if (cmp != 0)\r
419 return 0;\r
420 \r
421 /* e * d must be congruent to 1, modulo (p-1) and modulo (q-1). */\r
422 pm1 = copybn(key->p);\r
423 decbn(pm1);\r
424 ed = modmul(key->exponent, key->private_exponent, pm1);\r
425 freebn(pm1);\r
426 cmp = bignum_cmp(ed, One);\r
427 freebn(ed);\r
428 if (cmp != 0)\r
429 return 0;\r
430 \r
431 qm1 = copybn(key->q);\r
432 decbn(qm1);\r
433 ed = modmul(key->exponent, key->private_exponent, qm1);\r
434 freebn(qm1);\r
435 cmp = bignum_cmp(ed, One);\r
436 freebn(ed);\r
437 if (cmp != 0)\r
438 return 0;\r
439 \r
440 /*\r
441 * Ensure p > q.\r
442 *\r
443 * I have seen key blobs in the wild which were generated with\r
444 * p < q, so instead of rejecting the key in this case we\r
445 * should instead flip them round into the canonical order of\r
446 * p > q. This also involves regenerating iqmp.\r
447 */\r
448 if (bignum_cmp(key->p, key->q) <= 0) {\r
449 Bignum tmp = key->p;\r
450 key->p = key->q;\r
451 key->q = tmp;\r
452 \r
453 freebn(key->iqmp);\r
454 key->iqmp = modinv(key->q, key->p);\r
455 if (!key->iqmp)\r
456 return 0;\r
457 }\r
458 \r
459 /*\r
460 * Ensure iqmp * q is congruent to 1, modulo p.\r
461 */\r
462 n = modmul(key->iqmp, key->q, key->p);\r
463 cmp = bignum_cmp(n, One);\r
464 freebn(n);\r
465 if (cmp != 0)\r
466 return 0;\r
467 \r
468 return 1;\r
469 }\r
470 \r
471 /* Public key blob as used by Pageant: exponent before modulus. */\r
472 unsigned char *rsa_public_blob(struct RSAKey *key, int *len)\r
473 {\r
474 int length, pos;\r
475 unsigned char *ret;\r
476 \r
477 length = (ssh1_bignum_length(key->modulus) +\r
478 ssh1_bignum_length(key->exponent) + 4);\r
479 ret = snewn(length, unsigned char);\r
480 \r
481 PUT_32BIT(ret, bignum_bitcount(key->modulus));\r
482 pos = 4;\r
483 pos += ssh1_write_bignum(ret + pos, key->exponent);\r
484 pos += ssh1_write_bignum(ret + pos, key->modulus);\r
485 \r
486 *len = length;\r
487 return ret;\r
488 }\r
489 \r
490 /* Given a public blob, determine its length. */\r
491 int rsa_public_blob_len(void *data, int maxlen)\r
492 {\r
493 unsigned char *p = (unsigned char *)data;\r
494 int n;\r
495 \r
496 if (maxlen < 4)\r
497 return -1;\r
498 p += 4; /* length word */\r
499 maxlen -= 4;\r
500 \r
501 n = ssh1_read_bignum(p, maxlen, NULL); /* exponent */\r
502 if (n < 0)\r
503 return -1;\r
504 p += n;\r
505 \r
506 n = ssh1_read_bignum(p, maxlen, NULL); /* modulus */\r
507 if (n < 0)\r
508 return -1;\r
509 p += n;\r
510 \r
511 return p - (unsigned char *)data;\r
512 }\r
513 \r
514 void freersakey(struct RSAKey *key)\r
515 {\r
516 if (key->modulus)\r
517 freebn(key->modulus);\r
518 if (key->exponent)\r
519 freebn(key->exponent);\r
520 if (key->private_exponent)\r
521 freebn(key->private_exponent);\r
522 if (key->p)\r
523 freebn(key->p);\r
524 if (key->q)\r
525 freebn(key->q);\r
526 if (key->iqmp)\r
527 freebn(key->iqmp);\r
528 if (key->comment)\r
529 sfree(key->comment);\r
530 }\r
531 \r
532 /* ----------------------------------------------------------------------\r
533 * Implementation of the ssh-rsa signing key type. \r
534 */\r
535 \r
536 static void getstring(char **data, int *datalen, char **p, int *length)\r
537 {\r
538 *p = NULL;\r
539 if (*datalen < 4)\r
540 return;\r
541 *length = toint(GET_32BIT(*data));\r
542 if (*length < 0)\r
543 return;\r
544 *datalen -= 4;\r
545 *data += 4;\r
546 if (*datalen < *length)\r
547 return;\r
548 *p = *data;\r
549 *data += *length;\r
550 *datalen -= *length;\r
551 }\r
552 static Bignum getmp(char **data, int *datalen)\r
553 {\r
554 char *p;\r
555 int length;\r
556 Bignum b;\r
557 \r
558 getstring(data, datalen, &p, &length);\r
559 if (!p)\r
560 return NULL;\r
561 b = bignum_from_bytes((unsigned char *)p, length);\r
562 return b;\r
563 }\r
564 \r
565 static void rsa2_freekey(void *key); /* forward reference */\r
566 \r
567 static void *rsa2_newkey(char *data, int len)\r
568 {\r
569 char *p;\r
570 int slen;\r
571 struct RSAKey *rsa;\r
572 \r
573 rsa = snew(struct RSAKey);\r
574 getstring(&data, &len, &p, &slen);\r
575 \r
576 if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {\r
577 sfree(rsa);\r
578 return NULL;\r
579 }\r
580 rsa->exponent = getmp(&data, &len);\r
581 rsa->modulus = getmp(&data, &len);\r
582 rsa->private_exponent = NULL;\r
583 rsa->p = rsa->q = rsa->iqmp = NULL;\r
584 rsa->comment = NULL;\r
585 \r
586 if (!rsa->exponent || !rsa->modulus) {\r
587 rsa2_freekey(rsa);\r
588 return NULL;\r
589 }\r
590 \r
591 return rsa;\r
592 }\r
593 \r
594 static void rsa2_freekey(void *key)\r
595 {\r
596 struct RSAKey *rsa = (struct RSAKey *) key;\r
597 freersakey(rsa);\r
598 sfree(rsa);\r
599 }\r
600 \r
601 static char *rsa2_fmtkey(void *key)\r
602 {\r
603 struct RSAKey *rsa = (struct RSAKey *) key;\r
604 char *p;\r
605 int len;\r
606 \r
607 len = rsastr_len(rsa);\r
608 p = snewn(len, char);\r
609 rsastr_fmt(p, rsa);\r
610 return p;\r
611 }\r
612 \r
613 static unsigned char *rsa2_public_blob(void *key, int *len)\r
614 {\r
615 struct RSAKey *rsa = (struct RSAKey *) key;\r
616 int elen, mlen, bloblen;\r
617 int i;\r
618 unsigned char *blob, *p;\r
619 \r
620 elen = (bignum_bitcount(rsa->exponent) + 8) / 8;\r
621 mlen = (bignum_bitcount(rsa->modulus) + 8) / 8;\r
622 \r
623 /*\r
624 * string "ssh-rsa", mpint exp, mpint mod. Total 19+elen+mlen.\r
625 * (three length fields, 12+7=19).\r
626 */\r
627 bloblen = 19 + elen + mlen;\r
628 blob = snewn(bloblen, unsigned char);\r
629 p = blob;\r
630 PUT_32BIT(p, 7);\r
631 p += 4;\r
632 memcpy(p, "ssh-rsa", 7);\r
633 p += 7;\r
634 PUT_32BIT(p, elen);\r
635 p += 4;\r
636 for (i = elen; i--;)\r
637 *p++ = bignum_byte(rsa->exponent, i);\r
638 PUT_32BIT(p, mlen);\r
639 p += 4;\r
640 for (i = mlen; i--;)\r
641 *p++ = bignum_byte(rsa->modulus, i);\r
642 assert(p == blob + bloblen);\r
643 *len = bloblen;\r
644 return blob;\r
645 }\r
646 \r
647 static unsigned char *rsa2_private_blob(void *key, int *len)\r
648 {\r
649 struct RSAKey *rsa = (struct RSAKey *) key;\r
650 int dlen, plen, qlen, ulen, bloblen;\r
651 int i;\r
652 unsigned char *blob, *p;\r
653 \r
654 dlen = (bignum_bitcount(rsa->private_exponent) + 8) / 8;\r
655 plen = (bignum_bitcount(rsa->p) + 8) / 8;\r
656 qlen = (bignum_bitcount(rsa->q) + 8) / 8;\r
657 ulen = (bignum_bitcount(rsa->iqmp) + 8) / 8;\r
658 \r
659 /*\r
660 * mpint private_exp, mpint p, mpint q, mpint iqmp. Total 16 +\r
661 * sum of lengths.\r
662 */\r
663 bloblen = 16 + dlen + plen + qlen + ulen;\r
664 blob = snewn(bloblen, unsigned char);\r
665 p = blob;\r
666 PUT_32BIT(p, dlen);\r
667 p += 4;\r
668 for (i = dlen; i--;)\r
669 *p++ = bignum_byte(rsa->private_exponent, i);\r
670 PUT_32BIT(p, plen);\r
671 p += 4;\r
672 for (i = plen; i--;)\r
673 *p++ = bignum_byte(rsa->p, i);\r
674 PUT_32BIT(p, qlen);\r
675 p += 4;\r
676 for (i = qlen; i--;)\r
677 *p++ = bignum_byte(rsa->q, i);\r
678 PUT_32BIT(p, ulen);\r
679 p += 4;\r
680 for (i = ulen; i--;)\r
681 *p++ = bignum_byte(rsa->iqmp, i);\r
682 assert(p == blob + bloblen);\r
683 *len = bloblen;\r
684 return blob;\r
685 }\r
686 \r
687 static void *rsa2_createkey(unsigned char *pub_blob, int pub_len,\r
688 unsigned char *priv_blob, int priv_len)\r
689 {\r
690 struct RSAKey *rsa;\r
691 char *pb = (char *) priv_blob;\r
692 \r
693 rsa = rsa2_newkey((char *) pub_blob, pub_len);\r
694 rsa->private_exponent = getmp(&pb, &priv_len);\r
695 rsa->p = getmp(&pb, &priv_len);\r
696 rsa->q = getmp(&pb, &priv_len);\r
697 rsa->iqmp = getmp(&pb, &priv_len);\r
698 \r
699 if (!rsa_verify(rsa)) {\r
700 rsa2_freekey(rsa);\r
701 return NULL;\r
702 }\r
703 \r
704 return rsa;\r
705 }\r
706 \r
707 static void *rsa2_openssh_createkey(unsigned char **blob, int *len)\r
708 {\r
709 char **b = (char **) blob;\r
710 struct RSAKey *rsa;\r
711 \r
712 rsa = snew(struct RSAKey);\r
713 rsa->comment = NULL;\r
714 \r
715 rsa->modulus = getmp(b, len);\r
716 rsa->exponent = getmp(b, len);\r
717 rsa->private_exponent = getmp(b, len);\r
718 rsa->iqmp = getmp(b, len);\r
719 rsa->p = getmp(b, len);\r
720 rsa->q = getmp(b, len);\r
721 \r
722 if (!rsa->modulus || !rsa->exponent || !rsa->private_exponent ||\r
723 !rsa->iqmp || !rsa->p || !rsa->q) {\r
724 rsa2_freekey(rsa);\r
725 return NULL;\r
726 }\r
727 \r
728 if (!rsa_verify(rsa)) {\r
729 rsa2_freekey(rsa);\r
730 return NULL;\r
731 }\r
732 \r
733 return rsa;\r
734 }\r
735 \r
736 static int rsa2_openssh_fmtkey(void *key, unsigned char *blob, int len)\r
737 {\r
738 struct RSAKey *rsa = (struct RSAKey *) key;\r
739 int bloblen, i;\r
740 \r
741 bloblen =\r
742 ssh2_bignum_length(rsa->modulus) +\r
743 ssh2_bignum_length(rsa->exponent) +\r
744 ssh2_bignum_length(rsa->private_exponent) +\r
745 ssh2_bignum_length(rsa->iqmp) +\r
746 ssh2_bignum_length(rsa->p) + ssh2_bignum_length(rsa->q);\r
747 \r
748 if (bloblen > len)\r
749 return bloblen;\r
750 \r
751 bloblen = 0;\r
752 #define ENC(x) \\r
753 PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \\r
754 for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i);\r
755 ENC(rsa->modulus);\r
756 ENC(rsa->exponent);\r
757 ENC(rsa->private_exponent);\r
758 ENC(rsa->iqmp);\r
759 ENC(rsa->p);\r
760 ENC(rsa->q);\r
761 \r
762 return bloblen;\r
763 }\r
764 \r
765 static int rsa2_pubkey_bits(void *blob, int len)\r
766 {\r
767 struct RSAKey *rsa;\r
768 int ret;\r
769 \r
770 rsa = rsa2_newkey((char *) blob, len);\r
771 ret = bignum_bitcount(rsa->modulus);\r
772 rsa2_freekey(rsa);\r
773 \r
774 return ret;\r
775 }\r
776 \r
777 static char *rsa2_fingerprint(void *key)\r
778 {\r
779 struct RSAKey *rsa = (struct RSAKey *) key;\r
780 struct MD5Context md5c;\r
781 unsigned char digest[16], lenbuf[4];\r
782 char buffer[16 * 3 + 40];\r
783 char *ret;\r
784 int numlen, i;\r
785 \r
786 MD5Init(&md5c);\r
787 MD5Update(&md5c, (unsigned char *)"\0\0\0\7ssh-rsa", 11);\r
788 \r
789 #define ADD_BIGNUM(bignum) \\r
790 numlen = (bignum_bitcount(bignum)+8)/8; \\r
791 PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \\r
792 for (i = numlen; i-- ;) { \\r
793 unsigned char c = bignum_byte(bignum, i); \\r
794 MD5Update(&md5c, &c, 1); \\r
795 }\r
796 ADD_BIGNUM(rsa->exponent);\r
797 ADD_BIGNUM(rsa->modulus);\r
798 #undef ADD_BIGNUM\r
799 \r
800 MD5Final(digest, &md5c);\r
801 \r
802 sprintf(buffer, "ssh-rsa %d ", bignum_bitcount(rsa->modulus));\r
803 for (i = 0; i < 16; i++)\r
804 sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",\r
805 digest[i]);\r
806 ret = snewn(strlen(buffer) + 1, char);\r
807 if (ret)\r
808 strcpy(ret, buffer);\r
809 return ret;\r
810 }\r
811 \r
812 /*\r
813 * This is the magic ASN.1/DER prefix that goes in the decoded\r
814 * signature, between the string of FFs and the actual SHA hash\r
815 * value. The meaning of it is:\r
816 * \r
817 * 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself\r
818 * \r
819 * 30 21 -- a constructed SEQUENCE of length 0x21\r
820 * 30 09 -- a constructed sub-SEQUENCE of length 9\r
821 * 06 05 -- an object identifier, length 5\r
822 * 2B 0E 03 02 1A -- object id { 1 3 14 3 2 26 }\r
823 * (the 1,3 comes from 0x2B = 43 = 40*1+3)\r
824 * 05 00 -- NULL\r
825 * 04 14 -- a primitive OCTET STRING of length 0x14\r
826 * [0x14 bytes of hash data follows]\r
827 * \r
828 * The object id in the middle there is listed as `id-sha1' in\r
829 * ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1d2.asn (the\r
830 * ASN module for PKCS #1) and its expanded form is as follows:\r
831 * \r
832 * id-sha1 OBJECT IDENTIFIER ::= {\r
833 * iso(1) identified-organization(3) oiw(14) secsig(3)\r
834 * algorithms(2) 26 }\r
835 */\r
836 static const unsigned char asn1_weird_stuff[] = {\r
837 0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B,\r
838 0x0E, 0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14,\r
839 };\r
840 \r
841 #define ASN1_LEN ( (int) sizeof(asn1_weird_stuff) )\r
842 \r
843 static int rsa2_verifysig(void *key, char *sig, int siglen,\r
844 char *data, int datalen)\r
845 {\r
846 struct RSAKey *rsa = (struct RSAKey *) key;\r
847 Bignum in, out;\r
848 char *p;\r
849 int slen;\r
850 int bytes, i, j, ret;\r
851 unsigned char hash[20];\r
852 \r
853 getstring(&sig, &siglen, &p, &slen);\r
854 if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {\r
855 return 0;\r
856 }\r
857 in = getmp(&sig, &siglen);\r
858 if (!in)\r
859 return 0;\r
860 out = modpow(in, rsa->exponent, rsa->modulus);\r
861 freebn(in);\r
862 \r
863 ret = 1;\r
864 \r
865 bytes = (bignum_bitcount(rsa->modulus)+7) / 8;\r
866 /* Top (partial) byte should be zero. */\r
867 if (bignum_byte(out, bytes - 1) != 0)\r
868 ret = 0;\r
869 /* First whole byte should be 1. */\r
870 if (bignum_byte(out, bytes - 2) != 1)\r
871 ret = 0;\r
872 /* Most of the rest should be FF. */\r
873 for (i = bytes - 3; i >= 20 + ASN1_LEN; i--) {\r
874 if (bignum_byte(out, i) != 0xFF)\r
875 ret = 0;\r
876 }\r
877 /* Then we expect to see the asn1_weird_stuff. */\r
878 for (i = 20 + ASN1_LEN - 1, j = 0; i >= 20; i--, j++) {\r
879 if (bignum_byte(out, i) != asn1_weird_stuff[j])\r
880 ret = 0;\r
881 }\r
882 /* Finally, we expect to see the SHA-1 hash of the signed data. */\r
883 SHA_Simple(data, datalen, hash);\r
884 for (i = 19, j = 0; i >= 0; i--, j++) {\r
885 if (bignum_byte(out, i) != hash[j])\r
886 ret = 0;\r
887 }\r
888 freebn(out);\r
889 \r
890 return ret;\r
891 }\r
892 \r
893 static unsigned char *rsa2_sign(void *key, char *data, int datalen,\r
894 int *siglen)\r
895 {\r
896 struct RSAKey *rsa = (struct RSAKey *) key;\r
897 unsigned char *bytes;\r
898 int nbytes;\r
899 unsigned char hash[20];\r
900 Bignum in, out;\r
901 int i, j;\r
902 \r
903 SHA_Simple(data, datalen, hash);\r
904 \r
905 nbytes = (bignum_bitcount(rsa->modulus) - 1) / 8;\r
906 assert(1 <= nbytes - 20 - ASN1_LEN);\r
907 bytes = snewn(nbytes, unsigned char);\r
908 \r
909 bytes[0] = 1;\r
910 for (i = 1; i < nbytes - 20 - ASN1_LEN; i++)\r
911 bytes[i] = 0xFF;\r
912 for (i = nbytes - 20 - ASN1_LEN, j = 0; i < nbytes - 20; i++, j++)\r
913 bytes[i] = asn1_weird_stuff[j];\r
914 for (i = nbytes - 20, j = 0; i < nbytes; i++, j++)\r
915 bytes[i] = hash[j];\r
916 \r
917 in = bignum_from_bytes(bytes, nbytes);\r
918 sfree(bytes);\r
919 \r
920 out = rsa_privkey_op(in, rsa);\r
921 freebn(in);\r
922 \r
923 nbytes = (bignum_bitcount(out) + 7) / 8;\r
924 bytes = snewn(4 + 7 + 4 + nbytes, unsigned char);\r
925 PUT_32BIT(bytes, 7);\r
926 memcpy(bytes + 4, "ssh-rsa", 7);\r
927 PUT_32BIT(bytes + 4 + 7, nbytes);\r
928 for (i = 0; i < nbytes; i++)\r
929 bytes[4 + 7 + 4 + i] = bignum_byte(out, nbytes - 1 - i);\r
930 freebn(out);\r
931 \r
932 *siglen = 4 + 7 + 4 + nbytes;\r
933 return bytes;\r
934 }\r
935 \r
936 const struct ssh_signkey ssh_rsa = {\r
937 rsa2_newkey,\r
938 rsa2_freekey,\r
939 rsa2_fmtkey,\r
940 rsa2_public_blob,\r
941 rsa2_private_blob,\r
942 rsa2_createkey,\r
943 rsa2_openssh_createkey,\r
944 rsa2_openssh_fmtkey,\r
945 rsa2_pubkey_bits,\r
946 rsa2_fingerprint,\r
947 rsa2_verifysig,\r
948 rsa2_sign,\r
949 "ssh-rsa",\r
950 "rsa2"\r
951 };\r
952 \r
953 void *ssh_rsakex_newkey(char *data, int len)\r
954 {\r
955 return rsa2_newkey(data, len);\r
956 }\r
957 \r
958 void ssh_rsakex_freekey(void *key)\r
959 {\r
960 rsa2_freekey(key);\r
961 }\r
962 \r
963 int ssh_rsakex_klen(void *key)\r
964 {\r
965 struct RSAKey *rsa = (struct RSAKey *) key;\r
966 \r
967 return bignum_bitcount(rsa->modulus);\r
968 }\r
969 \r
970 static void oaep_mask(const struct ssh_hash *h, void *seed, int seedlen,\r
971 void *vdata, int datalen)\r
972 {\r
973 unsigned char *data = (unsigned char *)vdata;\r
974 unsigned count = 0;\r
975 \r
976 while (datalen > 0) {\r
977 int i, max = (datalen > h->hlen ? h->hlen : datalen);\r
978 void *s;\r
979 unsigned char counter[4], hash[SSH2_KEX_MAX_HASH_LEN];\r
980 \r
981 assert(h->hlen <= SSH2_KEX_MAX_HASH_LEN);\r
982 PUT_32BIT(counter, count);\r
983 s = h->init();\r
984 h->bytes(s, seed, seedlen);\r
985 h->bytes(s, counter, 4);\r
986 h->final(s, hash);\r
987 count++;\r
988 \r
989 for (i = 0; i < max; i++)\r
990 data[i] ^= hash[i];\r
991 \r
992 data += max;\r
993 datalen -= max;\r
994 }\r
995 }\r
996 \r
997 void ssh_rsakex_encrypt(const struct ssh_hash *h, unsigned char *in, int inlen,\r
998 unsigned char *out, int outlen,\r
999 void *key)\r
1000 {\r
1001 Bignum b1, b2;\r
1002 struct RSAKey *rsa = (struct RSAKey *) key;\r
1003 int k, i;\r
1004 char *p;\r
1005 const int HLEN = h->hlen;\r
1006 \r
1007 /*\r
1008 * Here we encrypt using RSAES-OAEP. Essentially this means:\r
1009 * \r
1010 * - we have a SHA-based `mask generation function' which\r
1011 * creates a pseudo-random stream of mask data\r
1012 * deterministically from an input chunk of data.\r
1013 * \r
1014 * - we have a random chunk of data called a seed.\r
1015 * \r
1016 * - we use the seed to generate a mask which we XOR with our\r
1017 * plaintext.\r
1018 * \r
1019 * - then we use _the masked plaintext_ to generate a mask\r
1020 * which we XOR with the seed.\r
1021 * \r
1022 * - then we concatenate the masked seed and the masked\r
1023 * plaintext, and RSA-encrypt that lot.\r
1024 * \r
1025 * The result is that the data input to the encryption function\r
1026 * is random-looking and (hopefully) contains no exploitable\r
1027 * structure such as PKCS1-v1_5 does.\r
1028 * \r
1029 * For a precise specification, see RFC 3447, section 7.1.1.\r
1030 * Some of the variable names below are derived from that, so\r
1031 * it'd probably help to read it anyway.\r
1032 */\r
1033 \r
1034 /* k denotes the length in octets of the RSA modulus. */\r
1035 k = (7 + bignum_bitcount(rsa->modulus)) / 8;\r
1036 \r
1037 /* The length of the input data must be at most k - 2hLen - 2. */\r
1038 assert(inlen > 0 && inlen <= k - 2*HLEN - 2);\r
1039 \r
1040 /* The length of the output data wants to be precisely k. */\r
1041 assert(outlen == k);\r
1042 \r
1043 /*\r
1044 * Now perform EME-OAEP encoding. First set up all the unmasked\r
1045 * output data.\r
1046 */\r
1047 /* Leading byte zero. */\r
1048 out[0] = 0;\r
1049 /* At position 1, the seed: HLEN bytes of random data. */\r
1050 for (i = 0; i < HLEN; i++)\r
1051 out[i + 1] = random_byte();\r
1052 /* At position 1+HLEN, the data block DB, consisting of: */\r
1053 /* The hash of the label (we only support an empty label here) */\r
1054 h->final(h->init(), out + HLEN + 1);\r
1055 /* A bunch of zero octets */\r
1056 memset(out + 2*HLEN + 1, 0, outlen - (2*HLEN + 1));\r
1057 /* A single 1 octet, followed by the input message data. */\r
1058 out[outlen - inlen - 1] = 1;\r
1059 memcpy(out + outlen - inlen, in, inlen);\r
1060 \r
1061 /*\r
1062 * Now use the seed data to mask the block DB.\r
1063 */\r
1064 oaep_mask(h, out+1, HLEN, out+HLEN+1, outlen-HLEN-1);\r
1065 \r
1066 /*\r
1067 * And now use the masked DB to mask the seed itself.\r
1068 */\r
1069 oaep_mask(h, out+HLEN+1, outlen-HLEN-1, out+1, HLEN);\r
1070 \r
1071 /*\r
1072 * Now `out' contains precisely the data we want to\r
1073 * RSA-encrypt.\r
1074 */\r
1075 b1 = bignum_from_bytes(out, outlen);\r
1076 b2 = modpow(b1, rsa->exponent, rsa->modulus);\r
1077 p = (char *)out;\r
1078 for (i = outlen; i--;) {\r
1079 *p++ = bignum_byte(b2, i);\r
1080 }\r
1081 freebn(b1);\r
1082 freebn(b2);\r
1083 \r
1084 /*\r
1085 * And we're done.\r
1086 */\r
1087 }\r
1088 \r
1089 static const struct ssh_kex ssh_rsa_kex_sha1 = {\r
1090 "rsa1024-sha1", NULL, KEXTYPE_RSA, NULL, NULL, 0, 0, &ssh_sha1\r
1091 };\r
1092 \r
1093 static const struct ssh_kex ssh_rsa_kex_sha256 = {\r
1094 "rsa2048-sha256", NULL, KEXTYPE_RSA, NULL, NULL, 0, 0, &ssh_sha256\r
1095 };\r
1096 \r
1097 static const struct ssh_kex *const rsa_kex_list[] = {\r
1098 &ssh_rsa_kex_sha256,\r
1099 &ssh_rsa_kex_sha1\r
1100 };\r
1101 \r
1102 const struct ssh_kexes ssh_rsa_kex = {\r
1103 sizeof(rsa_kex_list) / sizeof(*rsa_kex_list),\r
1104 rsa_kex_list\r
1105 };\r