qemu/roms/ipxe/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        = sizeof ( struct rsa_context ),
 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 };