[fdt] Add ability to parse a MAC address from a flattened device tree
[ipxe.git] / src / crypto / rsa.c
1 /*
2 * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA.
18 *
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
22 */
23
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25
26 #include <stdint.h>
27 #include <stdlib.h>
28 #include <stdarg.h>
29 #include <string.h>
30 #include <errno.h>
31 #include <ipxe/asn1.h>
32 #include <ipxe/crypto.h>
33 #include <ipxe/bigint.h>
34 #include <ipxe/random_nz.h>
35 #include <ipxe/rsa.h>
36
37 /** @file
38 *
39 * RSA public-key cryptography
40 *
41 * RSA is documented in RFC 3447.
42 */
43
44 /* Disambiguate the various error causes */
45 #define EACCES_VERIFY \
46 __einfo_error ( EINFO_EACCES_VERIFY )
47 #define EINFO_EACCES_VERIFY \
48 __einfo_uniqify ( EINFO_EACCES, 0x01, "RSA signature incorrect" )
49
50 /** "rsaEncryption" object identifier */
51 static uint8_t oid_rsa_encryption[] = { ASN1_OID_RSAENCRYPTION };
52
53 /** "rsaEncryption" OID-identified algorithm */
54 struct asn1_algorithm rsa_encryption_algorithm __asn1_algorithm = {
55 .name = "rsaEncryption",
56 .pubkey = &rsa_algorithm,
57 .digest = NULL,
58 .oid = ASN1_OID_CURSOR ( oid_rsa_encryption ),
59 };
60
61 /**
62 * Identify RSA prefix
63 *
64 * @v digest Digest algorithm
65 * @ret prefix RSA prefix, or NULL
66 */
67 static struct rsa_digestinfo_prefix *
68 rsa_find_prefix ( struct digest_algorithm *digest ) {
69 struct rsa_digestinfo_prefix *prefix;
70
71 for_each_table_entry ( prefix, RSA_DIGESTINFO_PREFIXES ) {
72 if ( prefix->digest == digest )
73 return prefix;
74 }
75 return NULL;
76 }
77
78 /**
79 * Free RSA dynamic storage
80 *
81 * @v context RSA context
82 */
83 static void rsa_free ( struct rsa_context *context ) {
84
85 free ( context->dynamic );
86 context->dynamic = NULL;
87 }
88
89 /**
90 * Allocate RSA dynamic storage
91 *
92 * @v context RSA context
93 * @v modulus_len Modulus length
94 * @v exponent_len Exponent length
95 * @ret rc Return status code
96 */
97 static int rsa_alloc ( struct rsa_context *context, size_t modulus_len,
98 size_t exponent_len ) {
99 unsigned int size = bigint_required_size ( modulus_len );
100 unsigned int exponent_size = bigint_required_size ( exponent_len );
101 bigint_t ( size ) *modulus;
102 bigint_t ( exponent_size ) *exponent;
103 size_t tmp_len = bigint_mod_exp_tmp_len ( modulus, exponent );
104 struct {
105 bigint_t ( size ) modulus;
106 bigint_t ( exponent_size ) exponent;
107 bigint_t ( size ) input;
108 bigint_t ( size ) output;
109 uint8_t tmp[tmp_len];
110 } __attribute__ (( packed )) *dynamic;
111
112 /* Free any existing dynamic storage */
113 rsa_free ( context );
114
115 /* Allocate dynamic storage */
116 dynamic = malloc ( sizeof ( *dynamic ) );
117 if ( ! dynamic )
118 return -ENOMEM;
119
120 /* Assign dynamic storage */
121 context->dynamic = dynamic;
122 context->modulus0 = &dynamic->modulus.element[0];
123 context->size = size;
124 context->max_len = modulus_len;
125 context->exponent0 = &dynamic->exponent.element[0];
126 context->exponent_size = exponent_size;
127 context->input0 = &dynamic->input.element[0];
128 context->output0 = &dynamic->output.element[0];
129 context->tmp = &dynamic->tmp;
130
131 return 0;
132 }
133
134 /**
135 * Parse RSA integer
136 *
137 * @v integer Integer to fill in
138 * @v raw ASN.1 cursor
139 * @ret rc Return status code
140 */
141 static int rsa_parse_integer ( struct asn1_cursor *integer,
142 const struct asn1_cursor *raw ) {
143
144 /* Enter integer */
145 memcpy ( integer, raw, sizeof ( *integer ) );
146 asn1_enter ( integer, ASN1_INTEGER );
147
148 /* Skip initial sign byte if applicable */
149 if ( ( integer->len > 1 ) &&
150 ( *( ( uint8_t * ) integer->data ) == 0x00 ) ) {
151 integer->data++;
152 integer->len--;
153 }
154
155 /* Fail if cursor or integer are invalid */
156 if ( ! integer->len )
157 return -EINVAL;
158
159 return 0;
160 }
161
162 /**
163 * Parse RSA modulus and exponent
164 *
165 * @v modulus Modulus to fill in
166 * @v exponent Exponent to fill in
167 * @v raw ASN.1 cursor
168 * @ret rc Return status code
169 */
170 static int rsa_parse_mod_exp ( struct asn1_cursor *modulus,
171 struct asn1_cursor *exponent,
172 const struct asn1_cursor *raw ) {
173 struct asn1_bit_string bits;
174 struct asn1_cursor cursor;
175 int is_private;
176 int rc;
177
178 /* Enter subjectPublicKeyInfo/RSAPrivateKey */
179 memcpy ( &cursor, raw, sizeof ( cursor ) );
180 asn1_enter ( &cursor, ASN1_SEQUENCE );
181
182 /* Determine key format */
183 if ( asn1_type ( &cursor ) == ASN1_INTEGER ) {
184
185 /* Private key */
186 is_private = 1;
187
188 /* Skip version */
189 asn1_skip_any ( &cursor );
190
191 } else {
192
193 /* Public key */
194 is_private = 0;
195
196 /* Skip algorithm */
197 asn1_skip ( &cursor, ASN1_SEQUENCE );
198
199 /* Enter subjectPublicKey */
200 if ( ( rc = asn1_integral_bit_string ( &cursor, &bits ) ) != 0 )
201 return rc;
202 cursor.data = bits.data;
203 cursor.len = bits.len;
204
205 /* Enter RSAPublicKey */
206 asn1_enter ( &cursor, ASN1_SEQUENCE );
207 }
208
209 /* Extract modulus */
210 if ( ( rc = rsa_parse_integer ( modulus, &cursor ) ) != 0 )
211 return rc;
212 asn1_skip_any ( &cursor );
213
214 /* Skip public exponent, if applicable */
215 if ( is_private )
216 asn1_skip ( &cursor, ASN1_INTEGER );
217
218 /* Extract publicExponent/privateExponent */
219 if ( ( rc = rsa_parse_integer ( exponent, &cursor ) ) != 0 )
220 return rc;
221
222 return 0;
223 }
224
225 /**
226 * Initialise RSA cipher
227 *
228 * @v ctx RSA context
229 * @v key Key
230 * @v key_len Length of key
231 * @ret rc Return status code
232 */
233 static int rsa_init ( void *ctx, const void *key, size_t key_len ) {
234 struct rsa_context *context = ctx;
235 struct asn1_cursor modulus;
236 struct asn1_cursor exponent;
237 struct asn1_cursor cursor;
238 int rc;
239
240 /* Initialise context */
241 memset ( context, 0, sizeof ( *context ) );
242
243 /* Initialise cursor */
244 cursor.data = key;
245 cursor.len = key_len;
246
247 /* Parse modulus and exponent */
248 if ( ( rc = rsa_parse_mod_exp ( &modulus, &exponent, &cursor ) ) != 0 ){
249 DBGC ( context, "RSA %p invalid modulus/exponent:\n", context );
250 DBGC_HDA ( context, 0, cursor.data, cursor.len );
251 goto err_parse;
252 }
253
254 DBGC ( context, "RSA %p modulus:\n", context );
255 DBGC_HDA ( context, 0, modulus.data, modulus.len );
256 DBGC ( context, "RSA %p exponent:\n", context );
257 DBGC_HDA ( context, 0, exponent.data, exponent.len );
258
259 /* Allocate dynamic storage */
260 if ( ( rc = rsa_alloc ( context, modulus.len, exponent.len ) ) != 0 )
261 goto err_alloc;
262
263 /* Construct big integers */
264 bigint_init ( ( ( bigint_t ( context->size ) * ) context->modulus0 ),
265 modulus.data, modulus.len );
266 bigint_init ( ( ( bigint_t ( context->exponent_size ) * )
267 context->exponent0 ), exponent.data, exponent.len );
268
269 return 0;
270
271 rsa_free ( context );
272 err_alloc:
273 err_parse:
274 return rc;
275 }
276
277 /**
278 * Calculate RSA maximum output length
279 *
280 * @v ctx RSA context
281 * @ret max_len Maximum output length
282 */
283 static size_t rsa_max_len ( void *ctx ) {
284 struct rsa_context *context = ctx;
285
286 return context->max_len;
287 }
288
289 /**
290 * Perform RSA cipher operation
291 *
292 * @v context RSA context
293 * @v in Input buffer
294 * @v out Output buffer
295 */
296 static void rsa_cipher ( struct rsa_context *context,
297 const void *in, void *out ) {
298 bigint_t ( context->size ) *input = ( ( void * ) context->input0 );
299 bigint_t ( context->size ) *output = ( ( void * ) context->output0 );
300 bigint_t ( context->size ) *modulus = ( ( void * ) context->modulus0 );
301 bigint_t ( context->exponent_size ) *exponent =
302 ( ( void * ) context->exponent0 );
303
304 /* Initialise big integer */
305 bigint_init ( input, in, context->max_len );
306
307 /* Perform modular exponentiation */
308 bigint_mod_exp ( input, modulus, exponent, output, context->tmp );
309
310 /* Copy out result */
311 bigint_done ( output, out, context->max_len );
312 }
313
314 /**
315 * Encrypt using RSA
316 *
317 * @v ctx RSA context
318 * @v plaintext Plaintext
319 * @v plaintext_len Length of plaintext
320 * @v ciphertext Ciphertext
321 * @ret ciphertext_len Length of ciphertext, or negative error
322 */
323 static int rsa_encrypt ( void *ctx, const void *plaintext,
324 size_t plaintext_len, void *ciphertext ) {
325 struct rsa_context *context = ctx;
326 void *temp;
327 uint8_t *encoded;
328 size_t max_len = ( context->max_len - 11 );
329 size_t random_nz_len = ( max_len - plaintext_len + 8 );
330 int rc;
331
332 /* Sanity check */
333 if ( plaintext_len > max_len ) {
334 DBGC ( context, "RSA %p plaintext too long (%zd bytes, max "
335 "%zd)\n", context, plaintext_len, max_len );
336 return -ERANGE;
337 }
338 DBGC ( context, "RSA %p encrypting:\n", context );
339 DBGC_HDA ( context, 0, plaintext, plaintext_len );
340
341 /* Construct encoded message (using the big integer output
342 * buffer as temporary storage)
343 */
344 temp = context->output0;
345 encoded = temp;
346 encoded[0] = 0x00;
347 encoded[1] = 0x02;
348 if ( ( rc = get_random_nz ( &encoded[2], random_nz_len ) ) != 0 ) {
349 DBGC ( context, "RSA %p could not generate random data: %s\n",
350 context, strerror ( rc ) );
351 return rc;
352 }
353 encoded[ 2 + random_nz_len ] = 0x00;
354 memcpy ( &encoded[ context->max_len - plaintext_len ],
355 plaintext, plaintext_len );
356
357 /* Encipher the encoded message */
358 rsa_cipher ( context, encoded, ciphertext );
359 DBGC ( context, "RSA %p encrypted:\n", context );
360 DBGC_HDA ( context, 0, ciphertext, context->max_len );
361
362 return context->max_len;
363 }
364
365 /**
366 * Decrypt using RSA
367 *
368 * @v ctx RSA context
369 * @v ciphertext Ciphertext
370 * @v ciphertext_len Ciphertext length
371 * @v plaintext Plaintext
372 * @ret plaintext_len Plaintext length, or negative error
373 */
374 static int rsa_decrypt ( void *ctx, const void *ciphertext,
375 size_t ciphertext_len, void *plaintext ) {
376 struct rsa_context *context = ctx;
377 void *temp;
378 uint8_t *encoded;
379 uint8_t *end;
380 uint8_t *zero;
381 uint8_t *start;
382 size_t plaintext_len;
383
384 /* Sanity check */
385 if ( ciphertext_len != context->max_len ) {
386 DBGC ( context, "RSA %p ciphertext incorrect length (%zd "
387 "bytes, should be %zd)\n",
388 context, ciphertext_len, context->max_len );
389 return -ERANGE;
390 }
391 DBGC ( context, "RSA %p decrypting:\n", context );
392 DBGC_HDA ( context, 0, ciphertext, ciphertext_len );
393
394 /* Decipher the message (using the big integer input buffer as
395 * temporary storage)
396 */
397 temp = context->input0;
398 encoded = temp;
399 rsa_cipher ( context, ciphertext, encoded );
400
401 /* Parse the message */
402 end = ( encoded + context->max_len );
403 if ( ( encoded[0] != 0x00 ) || ( encoded[1] != 0x02 ) )
404 goto invalid;
405 zero = memchr ( &encoded[2], 0, ( end - &encoded[2] ) );
406 if ( ! zero )
407 goto invalid;
408 start = ( zero + 1 );
409 plaintext_len = ( end - start );
410
411 /* Copy out message */
412 memcpy ( plaintext, start, plaintext_len );
413 DBGC ( context, "RSA %p decrypted:\n", context );
414 DBGC_HDA ( context, 0, plaintext, plaintext_len );
415
416 return plaintext_len;
417
418 invalid:
419 DBGC ( context, "RSA %p invalid decrypted message:\n", context );
420 DBGC_HDA ( context, 0, encoded, context->max_len );
421 return -EINVAL;
422 }
423
424 /**
425 * Encode RSA digest
426 *
427 * @v context RSA context
428 * @v digest Digest algorithm
429 * @v value Digest value
430 * @v encoded Encoded digest
431 * @ret rc Return status code
432 */
433 static int rsa_encode_digest ( struct rsa_context *context,
434 struct digest_algorithm *digest,
435 const void *value, void *encoded ) {
436 struct rsa_digestinfo_prefix *prefix;
437 size_t digest_len = digest->digestsize;
438 uint8_t *temp = encoded;
439 size_t digestinfo_len;
440 size_t max_len;
441 size_t pad_len;
442
443 /* Identify prefix */
444 prefix = rsa_find_prefix ( digest );
445 if ( ! prefix ) {
446 DBGC ( context, "RSA %p has no prefix for %s\n",
447 context, digest->name );
448 return -ENOTSUP;
449 }
450 digestinfo_len = ( prefix->len + digest_len );
451
452 /* Sanity check */
453 max_len = ( context->max_len - 11 );
454 if ( digestinfo_len > max_len ) {
455 DBGC ( context, "RSA %p %s digestInfo too long (%zd bytes, max"
456 "%zd)\n",
457 context, digest->name, digestinfo_len, max_len );
458 return -ERANGE;
459 }
460 DBGC ( context, "RSA %p encoding %s digest:\n",
461 context, digest->name );
462 DBGC_HDA ( context, 0, value, digest_len );
463
464 /* Construct encoded message */
465 *(temp++) = 0x00;
466 *(temp++) = 0x01;
467 pad_len = ( max_len - digestinfo_len + 8 );
468 memset ( temp, 0xff, pad_len );
469 temp += pad_len;
470 *(temp++) = 0x00;
471 memcpy ( temp, prefix->data, prefix->len );
472 temp += prefix->len;
473 memcpy ( temp, value, digest_len );
474 temp += digest_len;
475 assert ( temp == ( encoded + context->max_len ) );
476 DBGC ( context, "RSA %p encoded %s digest:\n", context, digest->name );
477 DBGC_HDA ( context, 0, encoded, context->max_len );
478
479 return 0;
480 }
481
482 /**
483 * Sign digest value using RSA
484 *
485 * @v ctx RSA context
486 * @v digest Digest algorithm
487 * @v value Digest value
488 * @v signature Signature
489 * @ret signature_len Signature length, or negative error
490 */
491 static int rsa_sign ( void *ctx, struct digest_algorithm *digest,
492 const void *value, void *signature ) {
493 struct rsa_context *context = ctx;
494 void *temp;
495 int rc;
496
497 DBGC ( context, "RSA %p signing %s digest:\n", context, digest->name );
498 DBGC_HDA ( context, 0, value, digest->digestsize );
499
500 /* Encode digest (using the big integer output buffer as
501 * temporary storage)
502 */
503 temp = context->output0;
504 if ( ( rc = rsa_encode_digest ( context, digest, value, temp ) ) != 0 )
505 return rc;
506
507 /* Encipher the encoded digest */
508 rsa_cipher ( context, temp, signature );
509 DBGC ( context, "RSA %p signed %s digest:\n", context, digest->name );
510 DBGC_HDA ( context, 0, signature, context->max_len );
511
512 return context->max_len;
513 }
514
515 /**
516 * Verify signed digest value using RSA
517 *
518 * @v ctx RSA context
519 * @v digest Digest algorithm
520 * @v value Digest value
521 * @v signature Signature
522 * @v signature_len Signature length
523 * @ret rc Return status code
524 */
525 static int rsa_verify ( void *ctx, struct digest_algorithm *digest,
526 const void *value, const void *signature,
527 size_t signature_len ) {
528 struct rsa_context *context = ctx;
529 void *temp;
530 void *expected;
531 void *actual;
532 int rc;
533
534 /* Sanity check */
535 if ( signature_len != context->max_len ) {
536 DBGC ( context, "RSA %p signature incorrect length (%zd "
537 "bytes, should be %zd)\n",
538 context, signature_len, context->max_len );
539 return -ERANGE;
540 }
541 DBGC ( context, "RSA %p verifying %s digest:\n",
542 context, digest->name );
543 DBGC_HDA ( context, 0, value, digest->digestsize );
544 DBGC_HDA ( context, 0, signature, signature_len );
545
546 /* Decipher the signature (using the big integer input buffer
547 * as temporary storage)
548 */
549 temp = context->input0;
550 expected = temp;
551 rsa_cipher ( context, signature, expected );
552 DBGC ( context, "RSA %p deciphered signature:\n", context );
553 DBGC_HDA ( context, 0, expected, context->max_len );
554
555 /* Encode digest (using the big integer output buffer as
556 * temporary storage)
557 */
558 temp = context->output0;
559 actual = temp;
560 if ( ( rc = rsa_encode_digest ( context, digest, value, actual ) ) !=0 )
561 return rc;
562
563 /* Verify the signature */
564 if ( memcmp ( actual, expected, context->max_len ) != 0 ) {
565 DBGC ( context, "RSA %p signature verification failed\n",
566 context );
567 return -EACCES_VERIFY;
568 }
569
570 DBGC ( context, "RSA %p signature verified successfully\n", context );
571 return 0;
572 }
573
574 /**
575 * Finalise RSA cipher
576 *
577 * @v ctx RSA context
578 */
579 static void rsa_final ( void *ctx ) {
580 struct rsa_context *context = ctx;
581
582 rsa_free ( context );
583 }
584
585 /**
586 * Check for matching RSA public/private key pair
587 *
588 * @v private_key Private key
589 * @v private_key_len Private key length
590 * @v public_key Public key
591 * @v public_key_len Public key length
592 * @ret rc Return status code
593 */
594 static int rsa_match ( const void *private_key, size_t private_key_len,
595 const void *public_key, size_t public_key_len ) {
596 struct asn1_cursor private_modulus;
597 struct asn1_cursor private_exponent;
598 struct asn1_cursor private_cursor;
599 struct asn1_cursor public_modulus;
600 struct asn1_cursor public_exponent;
601 struct asn1_cursor public_cursor;
602 int rc;
603
604 /* Initialise cursors */
605 private_cursor.data = private_key;
606 private_cursor.len = private_key_len;
607 public_cursor.data = public_key;
608 public_cursor.len = public_key_len;
609
610 /* Parse moduli and exponents */
611 if ( ( rc = rsa_parse_mod_exp ( &private_modulus, &private_exponent,
612 &private_cursor ) ) != 0 )
613 return rc;
614 if ( ( rc = rsa_parse_mod_exp ( &public_modulus, &public_exponent,
615 &public_cursor ) ) != 0 )
616 return rc;
617
618 /* Compare moduli */
619 if ( asn1_compare ( &private_modulus, &public_modulus ) != 0 )
620 return -ENOTTY;
621
622 return 0;
623 }
624
625 /** RSA public-key algorithm */
626 struct pubkey_algorithm rsa_algorithm = {
627 .name = "rsa",
628 .ctxsize = RSA_CTX_SIZE,
629 .init = rsa_init,
630 .max_len = rsa_max_len,
631 .encrypt = rsa_encrypt,
632 .decrypt = rsa_decrypt,
633 .sign = rsa_sign,
634 .verify = rsa_verify,
635 .final = rsa_final,
636 .match = rsa_match,
637 };