SKEYID derivation based on libstrongswan
[strongswan.git] / src / pluto / pkcs1.c
1 /* Support of PKCS#1 private key data structures
2 * Copyright (C) 2005 Jan Hutter, Martin Willi
3 * Copyright (C) 2002-2005 Andreas Steffen
4 * Hochschule fuer Technik Rapperswil, Switzerland
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2 of the License, or (at your
9 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * for more details.
15 */
16
17 #include <stddef.h>
18 #include <stdlib.h>
19 #include <string.h>
20
21 #include <freeswan.h>
22 #include <libsha2/sha2.h>
23
24 #include <library.h>
25 #include <asn1/asn1.h>
26 #include <asn1/asn1_parser.h>
27 #include <asn1/oid.h>
28 #include <crypto/rngs/rng.h>
29 #include <crypto/hashers/hasher.h>
30
31 #include "constants.h"
32 #include "defs.h"
33 #include "mp_defs.h"
34 #include "log.h"
35 #include "pkcs1.h"
36
37 const struct fld RSA_private_field[] =
38 {
39 { "Modulus", offsetof(RSA_private_key_t, pub.n) },
40 { "PublicExponent", offsetof(RSA_private_key_t, pub.e) },
41
42 { "PrivateExponent", offsetof(RSA_private_key_t, d) },
43 { "Prime1", offsetof(RSA_private_key_t, p) },
44 { "Prime2", offsetof(RSA_private_key_t, q) },
45 { "Exponent1", offsetof(RSA_private_key_t, dP) },
46 { "Exponent2", offsetof(RSA_private_key_t, dQ) },
47 { "Coefficient", offsetof(RSA_private_key_t, qInv) },
48 };
49
50 /**
51 * ASN.1 definition of a PKCS#1 RSA private key
52 */
53 static const asn1Object_t privkeyObjects[] = {
54 { 0, "RSAPrivateKey", ASN1_SEQUENCE, ASN1_NONE }, /* 0 */
55 { 1, "version", ASN1_INTEGER, ASN1_BODY }, /* 1 */
56 { 1, "modulus", ASN1_INTEGER, ASN1_BODY }, /* 2 */
57 { 1, "publicExponent", ASN1_INTEGER, ASN1_BODY }, /* 3 */
58 { 1, "privateExponent", ASN1_INTEGER, ASN1_BODY }, /* 4 */
59 { 1, "prime1", ASN1_INTEGER, ASN1_BODY }, /* 5 */
60 { 1, "prime2", ASN1_INTEGER, ASN1_BODY }, /* 6 */
61 { 1, "exponent1", ASN1_INTEGER, ASN1_BODY }, /* 7 */
62 { 1, "exponent2", ASN1_INTEGER, ASN1_BODY }, /* 8 */
63 { 1, "coefficient", ASN1_INTEGER, ASN1_BODY }, /* 9 */
64 { 1, "otherPrimeInfos", ASN1_SEQUENCE, ASN1_OPT |
65 ASN1_LOOP }, /* 10 */
66 { 2, "otherPrimeInfo", ASN1_SEQUENCE, ASN1_NONE }, /* 11 */
67 { 3, "prime", ASN1_INTEGER, ASN1_BODY }, /* 12 */
68 { 3, "exponent", ASN1_INTEGER, ASN1_BODY }, /* 13 */
69 { 3, "coefficient", ASN1_INTEGER, ASN1_BODY }, /* 14 */
70 { 1, "end opt or loop", ASN1_EOC, ASN1_END }, /* 15 */
71 { 0, "exit", ASN1_EOC, ASN1_EXIT }
72 };
73 #define PKCS1_PRIV_KEY_VERSION 1
74 #define PKCS1_PRIV_KEY_MODULUS 2
75 #define PKCS1_PRIV_KEY_PUB_EXP 3
76 #define PKCS1_PRIV_KEY_COEFF 9
77
78 /**
79 * Forms the FreeS/WAN keyid from the public exponent e and modulus n
80 */
81 void form_keyid(chunk_t e, chunk_t n, char* keyid, unsigned *keysize)
82 {
83 /* eliminate leading zero bytes in modulus from ASN.1 coding */
84 while (n.len > 1 && *n.ptr == 0x00)
85 {
86 n.ptr++; n.len--;
87 }
88
89 /* form the FreeS/WAN keyid */
90 keyid[0] = '\0'; /* in case of splitkeytoid failure */
91 splitkeytoid(e.ptr, e.len, n.ptr, n.len, keyid, KEYID_BUF);
92
93 /* return the RSA modulus size in octets */
94 *keysize = n.len;
95 }
96
97 /**
98 * Initialize an RSA_public_key_t object
99 */
100 void init_RSA_public_key(RSA_public_key_t *rsa, chunk_t e, chunk_t n)
101 {
102 n_to_mpz(&rsa->e, e.ptr, e.len);
103 n_to_mpz(&rsa->n, n.ptr, n.len);
104
105 form_keyid(e, n, rsa->keyid, &rsa->k);
106 }
107
108 #ifdef DEBUG
109 static void RSA_show_key_fields(RSA_private_key_t *k, int fieldcnt)
110 {
111 const struct fld *p;
112
113 DBG_log(" keyid: *%s", k->pub.keyid);
114
115 for (p = RSA_private_field; p < &RSA_private_field[fieldcnt]; p++)
116 {
117 MP_INT *n = (MP_INT *) ((char *)k + p->offset);
118 size_t sz = mpz_sizeinbase(n, 16);
119 char buf[RSA_MAX_OCTETS * 2 + 2]; /* ought to be big enough */
120
121 passert(sz <= sizeof(buf));
122 mpz_get_str(buf, 16, n);
123
124 DBG_log(" %s: 0x%s", p->name, buf);
125 }
126 }
127
128 /**
129 * debugging info that compromises security!
130 */
131 void RSA_show_private_key(RSA_private_key_t *k)
132 {
133 RSA_show_key_fields(k, countof(RSA_private_field));
134 }
135
136 void RSA_show_public_key(RSA_public_key_t *k)
137 {
138 /* Kludge: pretend that it is a private key, but only display the
139 * first two fields (which are the public key).
140 */
141 passert(offsetof(RSA_private_key_t, pub) == 0);
142 RSA_show_key_fields((RSA_private_key_t *)k, 2);
143 }
144 #endif
145
146 err_t RSA_private_key_sanity(RSA_private_key_t *k)
147 {
148 /* note that the *last* error found is reported */
149 err_t ugh = NULL;
150 mpz_t t, u, q1;
151
152 #ifdef DEBUG /* debugging info that compromises security */
153 DBG(DBG_PRIVATE, RSA_show_private_key(k));
154 #endif
155
156 /* PKCS#1 1.5 section 6 requires modulus to have at least 12 octets.
157 * We actually require more (for security).
158 */
159 if (k->pub.k < RSA_MIN_OCTETS)
160 return RSA_MIN_OCTETS_UGH;
161
162 /* we picked a max modulus size to simplify buffer allocation */
163 if (k->pub.k > RSA_MAX_OCTETS)
164 return RSA_MAX_OCTETS_UGH;
165
166 mpz_init(t);
167 mpz_init(u);
168 mpz_init(q1);
169
170 /* check that n == p * q */
171 mpz_mul(u, &k->p, &k->q);
172 if (mpz_cmp(u, &k->pub.n) != 0)
173 ugh = "n != p * q";
174
175 /* check that e divides neither p-1 nor q-1 */
176 mpz_sub_ui(t, &k->p, 1);
177 mpz_mod(t, t, &k->pub.e);
178 if (mpz_cmp_ui(t, 0) == 0)
179 ugh = "e divides p-1";
180
181 mpz_sub_ui(t, &k->q, 1);
182 mpz_mod(t, t, &k->pub.e);
183 if (mpz_cmp_ui(t, 0) == 0)
184 ugh = "e divides q-1";
185
186 /* check that d is e^-1 (mod lcm(p-1, q-1)) */
187 /* see PKCS#1v2, aka RFC 2437, for the "lcm" */
188 mpz_sub_ui(q1, &k->q, 1);
189 mpz_sub_ui(u, &k->p, 1);
190 mpz_gcd(t, u, q1); /* t := gcd(p-1, q-1) */
191 mpz_mul(u, u, q1); /* u := (p-1) * (q-1) */
192 mpz_divexact(u, u, t); /* u := lcm(p-1, q-1) */
193
194 mpz_mul(t, &k->d, &k->pub.e);
195 mpz_mod(t, t, u);
196 if (mpz_cmp_ui(t, 1) != 0)
197 ugh = "(d * e) mod (lcm(p-1, q-1)) != 1";
198
199 /* check that dP is d mod (p-1) */
200 mpz_sub_ui(u, &k->p, 1);
201 mpz_mod(t, &k->d, u);
202 if (mpz_cmp(t, &k->dP) != 0)
203 ugh = "dP is not congruent to d mod (p-1)";
204
205 /* check that dQ is d mod (q-1) */
206 mpz_sub_ui(u, &k->q, 1);
207 mpz_mod(t, &k->d, u);
208 if (mpz_cmp(t, &k->dQ) != 0)
209 ugh = "dQ is not congruent to d mod (q-1)";
210
211 /* check that qInv is (q^-1) mod p */
212 mpz_mul(t, &k->qInv, &k->q);
213 mpz_mod(t, t, &k->p);
214 if (mpz_cmp_ui(t, 1) != 0)
215 ugh = "qInv is not conguent ot (q^-1) mod p";
216
217 mpz_clear(t);
218 mpz_clear(u);
219 mpz_clear(q1);
220 return ugh;
221 }
222
223 /**
224 * Check the equality of two RSA public keys
225 */
226 bool same_RSA_public_key(const RSA_public_key_t *a, const RSA_public_key_t *b)
227 {
228 return a == b
229 || (a->k == b->k && mpz_cmp(&a->n, &b->n) == 0 && mpz_cmp(&a->e, &b->e) == 0);
230 }
231
232 /**
233 * Parses a PKCS#1 private key
234 */
235 bool pkcs1_parse_private_key(chunk_t blob, RSA_private_key_t *key)
236 {
237 asn1_parser_t *parser;
238 chunk_t object, modulus, exp;
239 int objectID;
240 bool success = FALSE;
241
242 parser = asn1_parser_create(privkeyObjects, blob);
243 parser->set_flags(parser, FALSE, TRUE);
244
245 while (parser->iterate(parser, &objectID, &object))
246 {
247 if (objectID == PKCS1_PRIV_KEY_VERSION)
248 {
249 if (object.len > 0 && *object.ptr != 0)
250 {
251 plog(" wrong PKCS#1 private key version");
252 goto end;
253 }
254 }
255 else if (objectID >= PKCS1_PRIV_KEY_MODULUS &&
256 objectID <= PKCS1_PRIV_KEY_COEFF)
257 {
258 MP_INT *u = (MP_INT *) ((char *)key
259 + RSA_private_field[objectID - PKCS1_PRIV_KEY_MODULUS].offset);
260
261 n_to_mpz(u, object.ptr, object.len);
262
263 if (objectID == PKCS1_PRIV_KEY_MODULUS)
264 modulus = object;
265 else if (objectID == PKCS1_PRIV_KEY_PUB_EXP)
266 exp = object;
267 }
268 }
269 success = parser->success(parser);
270
271 end:
272 parser->destroy(parser);
273
274 if (success)
275 {
276 err_t ugh;
277
278 form_keyid(exp, modulus, key->pub.keyid, &key->pub.k);
279 ugh = RSA_private_key_sanity(key);
280 success = (ugh == NULL);
281 }
282 return success;
283 }
284
285 /**
286 * Compute a digest over a binary blob
287 */
288 bool compute_digest(chunk_t tbs, int oid, chunk_t *digest)
289 {
290 hasher_t *hasher;
291 hash_algorithm_t alg = hasher_algorithm_from_oid(oid);
292
293 if (alg == HASH_UNKNOWN)
294 {
295 digest->len = 0;
296 return FALSE;
297 }
298
299 hasher = lib->crypto->create_hasher(lib->crypto, alg);
300 if (hasher == NULL)
301 {
302 digest->len = 0;
303 return FALSE;
304 }
305 digest->len = hasher->get_hash_size(hasher);
306 hasher->get_hash(hasher, tbs, digest->ptr);
307 hasher->destroy(hasher);
308 return TRUE;
309 }
310
311 /**
312 * Compute an RSA signature with PKCS#1 padding
313 */
314 void sign_hash(const RSA_private_key_t *k, const u_char *hash_val,
315 size_t hash_len, u_char *sig_val, size_t sig_len)
316 {
317 chunk_t ch;
318 mpz_t t1, t2;
319 size_t padlen;
320 u_char *p = sig_val;
321
322 DBG(DBG_CONTROL | DBG_CRYPT,
323 DBG_log("signing hash with RSA Key *%s", k->pub.keyid)
324 )
325 /* PKCS#1 v1.5 8.1 encryption-block formatting */
326 *p++ = 0x00;
327 *p++ = 0x01; /* BT (block type) 01 */
328 padlen = sig_len - 3 - hash_len;
329 memset(p, 0xFF, padlen);
330 p += padlen;
331 *p++ = 0x00;
332 memcpy(p, hash_val, hash_len);
333 passert(p + hash_len - sig_val == (ptrdiff_t)sig_len);
334
335 /* PKCS#1 v1.5 8.2 octet-string-to-integer conversion */
336 n_to_mpz(t1, sig_val, sig_len); /* (could skip leading 0x00) */
337
338 /* PKCS#1 v1.5 8.3 RSA computation y = x^c mod n
339 * Better described in PKCS#1 v2.0 5.1 RSADP.
340 * There are two methods, depending on the form of the private key.
341 * We use the one based on the Chinese Remainder Theorem.
342 */
343 mpz_init(t2);
344
345 mpz_powm(t2, t1, &k->dP, &k->p); /* m1 = c^dP mod p */
346
347 mpz_powm(t1, t1, &k->dQ, &k->q); /* m2 = c^dQ mod Q */
348
349 mpz_sub(t2, t2, t1); /* h = qInv (m1 - m2) mod p */
350 mpz_mod(t2, t2, &k->p);
351 mpz_mul(t2, t2, &k->qInv);
352 mpz_mod(t2, t2, &k->p);
353
354 mpz_mul(t2, t2, &k->q); /* m = m2 + h q */
355 mpz_add(t1, t1, t2);
356
357 /* PKCS#1 v1.5 8.4 integer-to-octet-string conversion */
358 ch = mpz_to_n(t1, sig_len);
359 memcpy(sig_val, ch.ptr, sig_len);
360 free(ch.ptr);
361
362 mpz_clear(t1);
363 mpz_clear(t2);
364 }
365
366 /**
367 * Encrypt data with an RSA public key after padding
368 */
369 chunk_t RSA_encrypt(const RSA_public_key_t *key, chunk_t in)
370 {
371 u_char padded[RSA_MAX_OCTETS];
372 u_char *pos = padded;
373 int padding = key->k - in.len - 3;
374 int i;
375 rng_t *rng;
376
377 if (padding < 8 || key->k > RSA_MAX_OCTETS)
378 return chunk_empty;
379
380 /* add padding according to PKCS#1 7.2.1 1.+2. */
381 *pos++ = 0x00;
382 *pos++ = 0x02;
383
384 /* pad with pseudo random bytes unequal to zero */
385 rng = lib->crypto->create_rng(lib->crypto, RNG_WEAK);
386 for (i = 0; i < padding; i++)
387 {
388 rng->get_bytes(rng, padding, pos);
389 while (!*pos)
390 {
391 rng->get_bytes(rng, 1, pos);
392 }
393 pos++;
394 }
395 rng->destroy(rng);
396
397 /* append the padding terminator */
398 *pos++ = 0x00;
399
400 /* now add the data */
401 memcpy(pos, in.ptr, in.len);
402 DBG(DBG_RAW,
403 DBG_dump_chunk("data for rsa encryption:\n", in);
404 DBG_dump("padded data for rsa encryption:\n", padded, key->k)
405 )
406
407 /* convert chunk to integer (PKCS#1 7.2.1 3.a) */
408 {
409 chunk_t out;
410 mpz_t m, c;
411
412 mpz_init(c);
413 n_to_mpz(m, padded, key->k);
414
415 /* encrypt(PKCS#1 7.2.1 3.b) */
416 mpz_powm(c, m, &key->e, &key->n);
417
418 /* convert integer back to a chunk (PKCS#1 7.2.1 3.c) */
419 out = mpz_to_n(c, key->k);
420 mpz_clear(c);
421 mpz_clear(m);
422
423 DBG(DBG_RAW,
424 DBG_dump_chunk("rsa encrypted data:\n", out)
425 )
426 return out;
427 }
428 }
429
430 /**
431 * Decrypt data with an RSA private key and remove padding
432 */
433 bool RSA_decrypt(const RSA_private_key_t *key, chunk_t in, chunk_t *out)
434 {
435 chunk_t padded, plaintext;
436 u_char *pos;
437 mpz_t t1, t2;
438
439 n_to_mpz(t1, in.ptr,in.len);
440
441 /* PKCS#1 v1.5 8.3 RSA computation y = x^c mod n
442 * Better described in PKCS#1 v2.0 5.1 RSADP.
443 * There are two methods, depending on the form of the private key.
444 * We use the one based on the Chinese Remainder Theorem.
445 */
446 mpz_init(t2);
447
448 mpz_powm(t2, t1, &key->dP, &key->p); /* m1 = c^dP mod p */
449 mpz_powm(t1, t1, &key->dQ, &key->q); /* m2 = c^dQ mod Q */
450
451 mpz_sub(t2, t2, t1); /* h = qInv (m1 - m2) mod p */
452 mpz_mod(t2, t2, &key->p);
453 mpz_mul(t2, t2, &key->qInv);
454 mpz_mod(t2, t2, &key->p);
455
456 mpz_mul(t2, t2, &key->q); /* m = m2 + h q */
457 mpz_add(t1, t1, t2);
458
459 padded = mpz_to_n(t1, key->pub.k);
460 mpz_clear(t1);
461 mpz_clear(t2);
462
463 DBG(DBG_PRIVATE,
464 DBG_dump_chunk("rsa decrypted data with padding:\n", padded)
465 )
466 pos = padded.ptr;
467
468 /* PKCS#1 v1.5 8.1 encryption-block formatting (EB = 00 || 02 || PS || 00 || D) */
469
470 /* check for hex pattern 00 02 in decrypted message */
471 if ((*pos++ != 0x00) || (*(pos++) != 0x02))
472 {
473 plog("incorrect padding - probably wrong RSA key");
474 chunk_clear(&padded);
475 return FALSE;
476 }
477 padded.len -= 2;
478
479 /* the plaintext data starts after first 0x00 byte */
480 while (padded.len-- > 0 && *pos++ != 0x00)
481
482 if (padded.len == 0)
483 {
484 plog("no plaintext data");
485 free(padded.ptr);
486 return FALSE;
487 }
488
489 plaintext = chunk_create(pos, padded.len);
490 *out = chunk_clone(plaintext);
491 chunk_clear(&padded);
492 return TRUE;
493 }
494
495 /**
496 * Build signatureValue
497 */
498 chunk_t pkcs1_build_signature(chunk_t tbs, int hash_alg,
499 const RSA_private_key_t *key, bool bit_string)
500 {
501
502 size_t siglen = key->pub.k;
503
504 u_char digest_buf[MAX_DIGEST_LEN];
505 chunk_t digest = { digest_buf, MAX_DIGEST_LEN };
506 chunk_t digestInfo, signatureValue;
507 u_char *pos;
508
509 if (!compute_digest(tbs, hash_alg, &digest))
510 {
511 return chunk_empty;
512 }
513
514 /* according to PKCS#1 v2.1 digest must be packaged into
515 * an ASN.1 structure for encryption
516 */
517 digestInfo = asn1_wrap(ASN1_SEQUENCE, "cm"
518 , asn1_algorithmIdentifier(hash_alg)
519 , asn1_simple_object(ASN1_OCTET_STRING, digest));
520
521 /* generate the RSA signature */
522 if (bit_string)
523 {
524 pos = asn1_build_object(&signatureValue, ASN1_BIT_STRING, 1 + siglen);
525 *pos++ = 0x00;
526 }
527 else
528 {
529 pos = asn1_build_object(&signatureValue, ASN1_OCTET_STRING, siglen);
530 }
531 sign_hash(key, digestInfo.ptr, digestInfo.len, pos, siglen);
532 free(digestInfo.ptr);
533
534 return signatureValue;
535 }
536
537 /**
538 * Build a DER-encoded PKCS#1 private key object
539 */
540 chunk_t pkcs1_build_private_key(const RSA_private_key_t *key)
541 {
542 chunk_t pkcs1 = asn1_wrap(ASN1_SEQUENCE, "cmmmmmmmm"
543 , ASN1_INTEGER_0
544 , asn1_integer_from_mpz(&key->pub.n)
545 , asn1_integer_from_mpz(&key->pub.e)
546 , asn1_integer_from_mpz(&key->d)
547 , asn1_integer_from_mpz(&key->p)
548 , asn1_integer_from_mpz(&key->q)
549 , asn1_integer_from_mpz(&key->dP)
550 , asn1_integer_from_mpz(&key->dQ)
551 , asn1_integer_from_mpz(&key->qInv));
552
553 DBG(DBG_PRIVATE,
554 DBG_dump_chunk("PKCS#1 encoded private key:", pkcs1)
555 )
556 return pkcs1;
557 }
558
559 /**
560 * Build a DER-encoded PKCS#1 public key object
561 */
562 chunk_t pkcs1_build_public_key(const RSA_public_key_t *rsa)
563 {
564 return asn1_wrap(ASN1_SEQUENCE, "mm"
565 , asn1_integer_from_mpz(&rsa->n)
566 , asn1_integer_from_mpz(&rsa->e));
567 }
568
569 /**
570 * Build a DER-encoded publicKeyInfo object
571 */
572 chunk_t pkcs1_build_publicKeyInfo(const RSA_public_key_t *rsa)
573 {
574 chunk_t publicKey;
575 chunk_t rawKey = pkcs1_build_public_key(rsa);
576 u_char *pos;
577
578 pos = asn1_build_object(&publicKey, ASN1_BIT_STRING, 1 + rawKey.len);
579 *pos++ = 0x00;
580 mv_chunk(&pos, rawKey);
581
582 return asn1_wrap(ASN1_SEQUENCE, "cm"
583 , asn1_algorithmIdentifier(OID_RSA_ENCRYPTION)
584 , publicKey);
585 }
586
587 void free_RSA_public_content(RSA_public_key_t *rsa)
588 {
589 mpz_clear(&rsa->n);
590 mpz_clear(&rsa->e);
591 }
592
593 void free_RSA_private_content(RSA_private_key_t *rsak)
594 {
595 free_RSA_public_content(&rsak->pub);
596 mpz_clear(&rsak->d);
597 mpz_clear(&rsak->p);
598 mpz_clear(&rsak->q);
599 mpz_clear(&rsak->dP);
600 mpz_clear(&rsak->dQ);
601 mpz_clear(&rsak->qInv);
602 }