iPXE
rsa.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 #include <stdint.h>
00027 #include <stdlib.h>
00028 #include <stdarg.h>
00029 #include <string.h>
00030 #include <errno.h>
00031 #include <ipxe/asn1.h>
00032 #include <ipxe/crypto.h>
00033 #include <ipxe/bigint.h>
00034 #include <ipxe/random_nz.h>
00035 #include <ipxe/rsa.h>
00036 
00037 /** @file
00038  *
00039  * RSA public-key cryptography
00040  *
00041  * RSA is documented in RFC 3447.
00042  */
00043 
00044 /* Disambiguate the various error causes */
00045 #define EACCES_VERIFY \
00046         __einfo_error ( EINFO_EACCES_VERIFY )
00047 #define EINFO_EACCES_VERIFY \
00048         __einfo_uniqify ( EINFO_EACCES, 0x01, "RSA signature incorrect" )
00049 
00050 /** "rsaEncryption" object identifier */
00051 static uint8_t oid_rsa_encryption[] = { ASN1_OID_RSAENCRYPTION };
00052 
00053 /** "rsaEncryption" OID-identified algorithm */
00054 struct asn1_algorithm rsa_encryption_algorithm __asn1_algorithm = {
00055         .name = "rsaEncryption",
00056         .pubkey = &rsa_algorithm,
00057         .digest = NULL,
00058         .oid = ASN1_OID_CURSOR ( oid_rsa_encryption ),
00059 };
00060 
00061 /**
00062  * Identify RSA prefix
00063  *
00064  * @v digest            Digest algorithm
00065  * @ret prefix          RSA prefix, or NULL
00066  */
00067 static struct rsa_digestinfo_prefix *
00068 rsa_find_prefix ( struct digest_algorithm *digest ) {
00069         struct rsa_digestinfo_prefix *prefix;
00070 
00071         for_each_table_entry ( prefix, RSA_DIGESTINFO_PREFIXES ) {
00072                 if ( prefix->digest == digest )
00073                         return prefix;
00074         }
00075         return NULL;
00076 }
00077 
00078 /**
00079  * Free RSA dynamic storage
00080  *
00081  * @v context           RSA context
00082  */
00083 static void rsa_free ( struct rsa_context *context ) {
00084 
00085         free ( context->dynamic );
00086         context->dynamic = NULL;
00087 }
00088 
00089 /**
00090  * Allocate RSA dynamic storage
00091  *
00092  * @v context           RSA context
00093  * @v modulus_len       Modulus length
00094  * @v exponent_len      Exponent length
00095  * @ret rc              Return status code
00096  */
00097 static int rsa_alloc ( struct rsa_context *context, size_t modulus_len,
00098                        size_t exponent_len ) {
00099         unsigned int size = bigint_required_size ( modulus_len );
00100         unsigned int exponent_size = bigint_required_size ( exponent_len );
00101         bigint_t ( size ) *modulus;
00102         bigint_t ( exponent_size ) *exponent;
00103         size_t tmp_len = bigint_mod_exp_tmp_len ( modulus, exponent );
00104         struct {
00105                 bigint_t ( size ) modulus;
00106                 bigint_t ( exponent_size ) exponent;
00107                 bigint_t ( size ) input;
00108                 bigint_t ( size ) output;
00109                 uint8_t tmp[tmp_len];
00110         } __attribute__ (( packed )) *dynamic;
00111 
00112         /* Free any existing dynamic storage */
00113         rsa_free ( context );
00114 
00115         /* Allocate dynamic storage */
00116         dynamic = malloc ( sizeof ( *dynamic ) );
00117         if ( ! dynamic )
00118                 return -ENOMEM;
00119 
00120         /* Assign dynamic storage */
00121         context->dynamic = dynamic;
00122         context->modulus0 = &dynamic->modulus.element[0];
00123         context->size = size;
00124         context->max_len = modulus_len;
00125         context->exponent0 = &dynamic->exponent.element[0];
00126         context->exponent_size = exponent_size;
00127         context->input0 = &dynamic->input.element[0];
00128         context->output0 = &dynamic->output.element[0];
00129         context->tmp = &dynamic->tmp;
00130 
00131         return 0;
00132 }
00133 
00134 /**
00135  * Parse RSA integer
00136  *
00137  * @v integer           Integer to fill in
00138  * @v raw               ASN.1 cursor
00139  * @ret rc              Return status code
00140  */
00141 static int rsa_parse_integer ( struct asn1_cursor *integer,
00142                                const struct asn1_cursor *raw ) {
00143 
00144         /* Enter integer */
00145         memcpy ( integer, raw, sizeof ( *integer ) );
00146         asn1_enter ( integer, ASN1_INTEGER );
00147 
00148         /* Skip initial sign byte if applicable */
00149         if ( ( integer->len > 1 ) &&
00150              ( *( ( uint8_t * ) integer->data ) == 0x00 ) ) {
00151                 integer->data++;
00152                 integer->len--;
00153         }
00154 
00155         /* Fail if cursor or integer are invalid */
00156         if ( ! integer->len )
00157                 return -EINVAL;
00158 
00159         return 0;
00160 }
00161 
00162 /**
00163  * Parse RSA modulus and exponent
00164  *
00165  * @v modulus           Modulus to fill in
00166  * @v exponent          Exponent to fill in
00167  * @v raw               ASN.1 cursor
00168  * @ret rc              Return status code
00169  */
00170 static int rsa_parse_mod_exp ( struct asn1_cursor *modulus,
00171                                struct asn1_cursor *exponent,
00172                                const struct asn1_cursor *raw ) {
00173         struct asn1_bit_string bits;
00174         struct asn1_cursor cursor;
00175         int is_private;
00176         int rc;
00177 
00178         /* Enter subjectPublicKeyInfo/RSAPrivateKey */
00179         memcpy ( &cursor, raw, sizeof ( cursor ) );
00180         asn1_enter ( &cursor, ASN1_SEQUENCE );
00181 
00182         /* Determine key format */
00183         if ( asn1_type ( &cursor ) == ASN1_INTEGER ) {
00184 
00185                 /* Private key */
00186                 is_private = 1;
00187 
00188                 /* Skip version */
00189                 asn1_skip_any ( &cursor );
00190 
00191         } else {
00192 
00193                 /* Public key */
00194                 is_private = 0;
00195 
00196                 /* Skip algorithm */
00197                 asn1_skip ( &cursor, ASN1_SEQUENCE );
00198 
00199                 /* Enter subjectPublicKey */
00200                 if ( ( rc = asn1_integral_bit_string ( &cursor, &bits ) ) != 0 )
00201                         return rc;
00202                 cursor.data = bits.data;
00203                 cursor.len = bits.len;
00204 
00205                 /* Enter RSAPublicKey */
00206                 asn1_enter ( &cursor, ASN1_SEQUENCE );
00207         }
00208 
00209         /* Extract modulus */
00210         if ( ( rc = rsa_parse_integer ( modulus, &cursor ) ) != 0 )
00211                 return rc;
00212         asn1_skip_any ( &cursor );
00213 
00214         /* Skip public exponent, if applicable */
00215         if ( is_private )
00216                 asn1_skip ( &cursor, ASN1_INTEGER );
00217 
00218         /* Extract publicExponent/privateExponent */
00219         if ( ( rc = rsa_parse_integer ( exponent, &cursor ) ) != 0 )
00220                 return rc;
00221 
00222         return 0;
00223 }
00224 
00225 /**
00226  * Initialise RSA cipher
00227  *
00228  * @v ctx               RSA context
00229  * @v key               Key
00230  * @v key_len           Length of key
00231  * @ret rc              Return status code
00232  */
00233 static int rsa_init ( void *ctx, const void *key, size_t key_len ) {
00234         struct rsa_context *context = ctx;
00235         struct asn1_cursor modulus;
00236         struct asn1_cursor exponent;
00237         struct asn1_cursor cursor;
00238         int rc;
00239 
00240         /* Initialise context */
00241         memset ( context, 0, sizeof ( *context ) );
00242 
00243         /* Initialise cursor */
00244         cursor.data = key;
00245         cursor.len = key_len;
00246 
00247         /* Parse modulus and exponent */
00248         if ( ( rc = rsa_parse_mod_exp ( &modulus, &exponent, &cursor ) ) != 0 ){
00249                 DBGC ( context, "RSA %p invalid modulus/exponent:\n", context );
00250                 DBGC_HDA ( context, 0, cursor.data, cursor.len );
00251                 goto err_parse;
00252         }
00253 
00254         DBGC ( context, "RSA %p modulus:\n", context );
00255         DBGC_HDA ( context, 0, modulus.data, modulus.len );
00256         DBGC ( context, "RSA %p exponent:\n", context );
00257         DBGC_HDA ( context, 0, exponent.data, exponent.len );
00258 
00259         /* Allocate dynamic storage */
00260         if ( ( rc = rsa_alloc ( context, modulus.len, exponent.len ) ) != 0 )
00261                 goto err_alloc;
00262 
00263         /* Construct big integers */
00264         bigint_init ( ( ( bigint_t ( context->size ) * ) context->modulus0 ),
00265                       modulus.data, modulus.len );
00266         bigint_init ( ( ( bigint_t ( context->exponent_size ) * )
00267                         context->exponent0 ), exponent.data, exponent.len );
00268 
00269         return 0;
00270 
00271         rsa_free ( context );
00272  err_alloc:
00273  err_parse:
00274         return rc;
00275 }
00276 
00277 /**
00278  * Calculate RSA maximum output length
00279  *
00280  * @v ctx               RSA context
00281  * @ret max_len         Maximum output length
00282  */
00283 static size_t rsa_max_len ( void *ctx ) {
00284         struct rsa_context *context = ctx;
00285 
00286         return context->max_len;
00287 }
00288 
00289 /**
00290  * Perform RSA cipher operation
00291  *
00292  * @v context           RSA context
00293  * @v in                Input buffer
00294  * @v out               Output buffer
00295  */
00296 static void rsa_cipher ( struct rsa_context *context,
00297                          const void *in, void *out ) {
00298         bigint_t ( context->size ) *input = ( ( void * ) context->input0 );
00299         bigint_t ( context->size ) *output = ( ( void * ) context->output0 );
00300         bigint_t ( context->size ) *modulus = ( ( void * ) context->modulus0 );
00301         bigint_t ( context->exponent_size ) *exponent =
00302                 ( ( void * ) context->exponent0 );
00303 
00304         /* Initialise big integer */
00305         bigint_init ( input, in, context->max_len );
00306 
00307         /* Perform modular exponentiation */
00308         bigint_mod_exp ( input, modulus, exponent, output, context->tmp );
00309 
00310         /* Copy out result */
00311         bigint_done ( output, out, context->max_len );
00312 }
00313 
00314 /**
00315  * Encrypt using RSA
00316  *
00317  * @v ctx               RSA context
00318  * @v plaintext         Plaintext
00319  * @v plaintext_len     Length of plaintext
00320  * @v ciphertext        Ciphertext
00321  * @ret ciphertext_len  Length of ciphertext, or negative error
00322  */
00323 static int rsa_encrypt ( void *ctx, const void *plaintext,
00324                          size_t plaintext_len, void *ciphertext ) {
00325         struct rsa_context *context = ctx;
00326         void *temp;
00327         uint8_t *encoded;
00328         size_t max_len = ( context->max_len - 11 );
00329         size_t random_nz_len = ( max_len - plaintext_len + 8 );
00330         int rc;
00331 
00332         /* Sanity check */
00333         if ( plaintext_len > max_len ) {
00334                 DBGC ( context, "RSA %p plaintext too long (%zd bytes, max "
00335                        "%zd)\n", context, plaintext_len, max_len );
00336                 return -ERANGE;
00337         }
00338         DBGC ( context, "RSA %p encrypting:\n", context );
00339         DBGC_HDA ( context, 0, plaintext, plaintext_len );
00340 
00341         /* Construct encoded message (using the big integer output
00342          * buffer as temporary storage)
00343          */
00344         temp = context->output0;
00345         encoded = temp;
00346         encoded[0] = 0x00;
00347         encoded[1] = 0x02;
00348         if ( ( rc = get_random_nz ( &encoded[2], random_nz_len ) ) != 0 ) {
00349                 DBGC ( context, "RSA %p could not generate random data: %s\n",
00350                        context, strerror ( rc ) );
00351                 return rc;
00352         }
00353         encoded[ 2 + random_nz_len ] = 0x00;
00354         memcpy ( &encoded[ context->max_len - plaintext_len ],
00355                  plaintext, plaintext_len );
00356 
00357         /* Encipher the encoded message */
00358         rsa_cipher ( context, encoded, ciphertext );
00359         DBGC ( context, "RSA %p encrypted:\n", context );
00360         DBGC_HDA ( context, 0, ciphertext, context->max_len );
00361 
00362         return context->max_len;
00363 }
00364 
00365 /**
00366  * Decrypt using RSA
00367  *
00368  * @v ctx               RSA context
00369  * @v ciphertext        Ciphertext
00370  * @v ciphertext_len    Ciphertext length
00371  * @v plaintext         Plaintext
00372  * @ret plaintext_len   Plaintext length, or negative error
00373  */
00374 static int rsa_decrypt ( void *ctx, const void *ciphertext,
00375                          size_t ciphertext_len, void *plaintext ) {
00376         struct rsa_context *context = ctx;
00377         void *temp;
00378         uint8_t *encoded;
00379         uint8_t *end;
00380         uint8_t *zero;
00381         uint8_t *start;
00382         size_t plaintext_len;
00383 
00384         /* Sanity check */
00385         if ( ciphertext_len != context->max_len ) {
00386                 DBGC ( context, "RSA %p ciphertext incorrect length (%zd "
00387                        "bytes, should be %zd)\n",
00388                        context, ciphertext_len, context->max_len );
00389                 return -ERANGE;
00390         }
00391         DBGC ( context, "RSA %p decrypting:\n", context );
00392         DBGC_HDA ( context, 0, ciphertext, ciphertext_len );
00393 
00394         /* Decipher the message (using the big integer input buffer as
00395          * temporary storage)
00396          */
00397         temp = context->input0;
00398         encoded = temp;
00399         rsa_cipher ( context, ciphertext, encoded );
00400 
00401         /* Parse the message */
00402         end = ( encoded + context->max_len );
00403         if ( ( encoded[0] != 0x00 ) || ( encoded[1] != 0x02 ) )
00404                 goto invalid;
00405         zero = memchr ( &encoded[2], 0, ( end - &encoded[2] ) );
00406         if ( ! zero )
00407                 goto invalid;
00408         start = ( zero + 1 );
00409         plaintext_len = ( end - start );
00410 
00411         /* Copy out message */
00412         memcpy ( plaintext, start, plaintext_len );
00413         DBGC ( context, "RSA %p decrypted:\n", context );
00414         DBGC_HDA ( context, 0, plaintext, plaintext_len );
00415 
00416         return plaintext_len;
00417 
00418  invalid:
00419         DBGC ( context, "RSA %p invalid decrypted message:\n", context );
00420         DBGC_HDA ( context, 0, encoded, context->max_len );
00421         return -EINVAL;
00422 }
00423 
00424 /**
00425  * Encode RSA digest
00426  *
00427  * @v context           RSA context
00428  * @v digest            Digest algorithm
00429  * @v value             Digest value
00430  * @v encoded           Encoded digest
00431  * @ret rc              Return status code
00432  */
00433 static int rsa_encode_digest ( struct rsa_context *context,
00434                                struct digest_algorithm *digest,
00435                                const void *value, void *encoded ) {
00436         struct rsa_digestinfo_prefix *prefix;
00437         size_t digest_len = digest->digestsize;
00438         uint8_t *temp = encoded;
00439         size_t digestinfo_len;
00440         size_t max_len;
00441         size_t pad_len;
00442 
00443         /* Identify prefix */
00444         prefix = rsa_find_prefix ( digest );
00445         if ( ! prefix ) {
00446                 DBGC ( context, "RSA %p has no prefix for %s\n",
00447                        context, digest->name );
00448                 return -ENOTSUP;
00449         }
00450         digestinfo_len = ( prefix->len + digest_len );
00451 
00452         /* Sanity check */
00453         max_len = ( context->max_len - 11 );
00454         if ( digestinfo_len > max_len ) {
00455                 DBGC ( context, "RSA %p %s digestInfo too long (%zd bytes, max"
00456                        "%zd)\n",
00457                        context, digest->name, digestinfo_len, max_len );
00458                 return -ERANGE;
00459         }
00460         DBGC ( context, "RSA %p encoding %s digest:\n",
00461                context, digest->name );
00462         DBGC_HDA ( context, 0, value, digest_len );
00463 
00464         /* Construct encoded message */
00465         *(temp++) = 0x00;
00466         *(temp++) = 0x01;
00467         pad_len = ( max_len - digestinfo_len + 8 );
00468         memset ( temp, 0xff, pad_len );
00469         temp += pad_len;
00470         *(temp++) = 0x00;
00471         memcpy ( temp, prefix->data, prefix->len );
00472         temp += prefix->len;
00473         memcpy ( temp, value, digest_len );
00474         temp += digest_len;
00475         assert ( temp == ( encoded + context->max_len ) );
00476         DBGC ( context, "RSA %p encoded %s digest:\n", context, digest->name );
00477         DBGC_HDA ( context, 0, encoded, context->max_len );
00478 
00479         return 0;
00480 }
00481 
00482 /**
00483  * Sign digest value using RSA
00484  *
00485  * @v ctx               RSA context
00486  * @v digest            Digest algorithm
00487  * @v value             Digest value
00488  * @v signature         Signature
00489  * @ret signature_len   Signature length, or negative error
00490  */
00491 static int rsa_sign ( void *ctx, struct digest_algorithm *digest,
00492                       const void *value, void *signature ) {
00493         struct rsa_context *context = ctx;
00494         void *temp;
00495         int rc;
00496 
00497         DBGC ( context, "RSA %p signing %s digest:\n", context, digest->name );
00498         DBGC_HDA ( context, 0, value, digest->digestsize );
00499 
00500         /* Encode digest (using the big integer output buffer as
00501          * temporary storage)
00502          */
00503         temp = context->output0;
00504         if ( ( rc = rsa_encode_digest ( context, digest, value, temp ) ) != 0 )
00505                 return rc;
00506 
00507         /* Encipher the encoded digest */
00508         rsa_cipher ( context, temp, signature );
00509         DBGC ( context, "RSA %p signed %s digest:\n", context, digest->name );
00510         DBGC_HDA ( context, 0, signature, context->max_len );
00511 
00512         return context->max_len;
00513 }
00514 
00515 /**
00516  * Verify signed digest value using RSA
00517  *
00518  * @v ctx               RSA context
00519  * @v digest            Digest algorithm
00520  * @v value             Digest value
00521  * @v signature         Signature
00522  * @v signature_len     Signature length
00523  * @ret rc              Return status code
00524  */
00525 static int rsa_verify ( void *ctx, struct digest_algorithm *digest,
00526                         const void *value, const void *signature,
00527                         size_t signature_len ) {
00528         struct rsa_context *context = ctx;
00529         void *temp;
00530         void *expected;
00531         void *actual;
00532         int rc;
00533 
00534         /* Sanity check */
00535         if ( signature_len != context->max_len ) {
00536                 DBGC ( context, "RSA %p signature incorrect length (%zd "
00537                        "bytes, should be %zd)\n",
00538                        context, signature_len, context->max_len );
00539                 return -ERANGE;
00540         }
00541         DBGC ( context, "RSA %p verifying %s digest:\n",
00542                context, digest->name );
00543         DBGC_HDA ( context, 0, value, digest->digestsize );
00544         DBGC_HDA ( context, 0, signature, signature_len );
00545 
00546         /* Decipher the signature (using the big integer input buffer
00547          * as temporary storage)
00548          */
00549         temp = context->input0;
00550         expected = temp;
00551         rsa_cipher ( context, signature, expected );
00552         DBGC ( context, "RSA %p deciphered signature:\n", context );
00553         DBGC_HDA ( context, 0, expected, context->max_len );
00554 
00555         /* Encode digest (using the big integer output buffer as
00556          * temporary storage)
00557          */
00558         temp = context->output0;
00559         actual = temp;
00560         if ( ( rc = rsa_encode_digest ( context, digest, value, actual ) ) !=0 )
00561                 return rc;
00562 
00563         /* Verify the signature */
00564         if ( memcmp ( actual, expected, context->max_len ) != 0 ) {
00565                 DBGC ( context, "RSA %p signature verification failed\n",
00566                        context );
00567                 return -EACCES_VERIFY;
00568         }
00569 
00570         DBGC ( context, "RSA %p signature verified successfully\n", context );
00571         return 0;
00572 }
00573 
00574 /**
00575  * Finalise RSA cipher
00576  *
00577  * @v ctx               RSA context
00578  */
00579 static void rsa_final ( void *ctx ) {
00580         struct rsa_context *context = ctx;
00581 
00582         rsa_free ( context );
00583 }
00584 
00585 /**
00586  * Check for matching RSA public/private key pair
00587  *
00588  * @v private_key       Private key
00589  * @v private_key_len   Private key length
00590  * @v public_key        Public key
00591  * @v public_key_len    Public key length
00592  * @ret rc              Return status code
00593  */
00594 static int rsa_match ( const void *private_key, size_t private_key_len,
00595                        const void *public_key, size_t public_key_len ) {
00596         struct asn1_cursor private_modulus;
00597         struct asn1_cursor private_exponent;
00598         struct asn1_cursor private_cursor;
00599         struct asn1_cursor public_modulus;
00600         struct asn1_cursor public_exponent;
00601         struct asn1_cursor public_cursor;
00602         int rc;
00603 
00604         /* Initialise cursors */
00605         private_cursor.data = private_key;
00606         private_cursor.len = private_key_len;
00607         public_cursor.data = public_key;
00608         public_cursor.len = public_key_len;
00609 
00610         /* Parse moduli and exponents */
00611         if ( ( rc = rsa_parse_mod_exp ( &private_modulus, &private_exponent,
00612                                         &private_cursor ) ) != 0 )
00613                 return rc;
00614         if ( ( rc = rsa_parse_mod_exp ( &public_modulus, &public_exponent,
00615                                         &public_cursor ) ) != 0 )
00616                 return rc;
00617 
00618         /* Compare moduli */
00619         if ( asn1_compare ( &private_modulus, &public_modulus ) != 0 )
00620                 return -ENOTTY;
00621 
00622         return 0;
00623 }
00624 
00625 /** RSA public-key algorithm */
00626 struct pubkey_algorithm rsa_algorithm = {
00627         .name           = "rsa",
00628         .ctxsize        = RSA_CTX_SIZE,
00629         .init           = rsa_init,
00630         .max_len        = rsa_max_len,
00631         .encrypt        = rsa_encrypt,
00632         .decrypt        = rsa_decrypt,
00633         .sign           = rsa_sign,
00634         .verify         = rsa_verify,
00635         .final          = rsa_final,
00636         .match          = rsa_match,
00637 };