lib/hcrypto/rsa.c

   1 /*
   2  * Copyright (c) 2006 - 2008 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #include <config.h>
  35 #include <roken.h>
  36 #include <krb5-types.h>
  37 #include <rfc2459_asn1.h>
  38
  39 #include <der.h>
  40
  41 #include <rsa.h>
  42
  43 #include "common.h"
  44
  45 /**
  46  * @page page_rsa RSA - public-key cryptography
  47  *
  48  * RSA is named by its inventors (Ron Rivest, Adi Shamir, and Leonard
  49  * Adleman) (published in 1977), patented expired in 21 September 2000.
  50  *
  51  *
  52  * Speed for RSA in seconds
  53  *   no key blinding
  54  *   1000 iteration,
  55  *   same rsa keys (1024 and 2048)
  56  *   operation performed each eteration sign, verify, encrypt, decrypt on a random bit pattern
  57  *
  58  * name         1024    2048    4098
  59  * =================================
  60  * gmp:          0.73     6.60   44.80
  61  * tfm:          2.45       --      --
  62  * ltm:          3.79    20.74  105.41  (default in hcrypto)
  63  * openssl:      4.04    11.90   82.59
  64  * cdsa:        15.89   102.89  721.40
  65  * imath:       40.62       --      --
  66  *
  67  * See the library functions here: @ref hcrypto_rsa
  68  */
  69
  70 /**
  71  * Same as RSA_new_method() using NULL as engine.
  72  *
  73  * @return a newly allocated RSA object. Free with RSA_free().
  74  *
  75  * @ingroup hcrypto_rsa
  76  */
  77
  78 RSA *
  79 RSA_new(void)
  80 {
  81     return RSA_new_method(NULL);
  82 }
  83
  84 /**
  85  * Allocate a new RSA object using the engine, if NULL is specified as
  86  * the engine, use the default RSA engine as returned by
  87  * ENGINE_get_default_RSA().
  88  *
  89  * @param engine Specific what ENGINE RSA provider should be used.
  90  *
  91  * @return a newly allocated RSA object. Free with RSA_free().
  92  *
  93  * @ingroup hcrypto_rsa
  94  */
  95
  96 RSA *
  97 RSA_new_method(ENGINE *engine)
  98 {
  99     RSA *rsa;
 100
 101     rsa = calloc(1, sizeof(*rsa));
 102     if (rsa == NULL)
 103         return NULL;
 104
 105     rsa->references = 1;
 106
 107     if (engine) {
 108         ENGINE_up_ref(engine);
 109         rsa->engine = engine;
 110     } else {
 111         rsa->engine = ENGINE_get_default_RSA();
 112     }
 113
 114     if (rsa->engine) {
 115         rsa->meth = ENGINE_get_RSA(rsa->engine);
 116         if (rsa->meth == NULL) {
 117             ENGINE_finish(engine);
 118             free(rsa);
 119             return 0;
 120         }
 121     }
 122
 123     if (rsa->meth == NULL)
 124         rsa->meth = rk_UNCONST(RSA_get_default_method());
 125
 126     (*rsa->meth->init)(rsa);
 127
 128     return rsa;
 129 }
 130
 131 /**
 132  * Free an allocation RSA object.
 133  *
 134  * @param rsa the RSA object to free.
 135  * @ingroup hcrypto_rsa
 136  */
 137
 138 void
 139 RSA_free(RSA *rsa)
 140 {
 141     if (rsa->references <= 0)
 142         abort();
 143
 144     if (--rsa->references > 0)
 145         return;
 146
 147     (*rsa->meth->finish)(rsa);
 148
 149     if (rsa->engine)
 150         ENGINE_finish(rsa->engine);
 151
 152 #define free_if(f) if (f) { BN_free(f); }
 153     free_if(rsa->n);
 154     free_if(rsa->e);
 155     free_if(rsa->d);
 156     free_if(rsa->p);
 157     free_if(rsa->q);
 158     free_if(rsa->dmp1);
 159     free_if(rsa->dmq1);
 160     free_if(rsa->iqmp);
 161 #undef free_if
 162
 163     memset(rsa, 0, sizeof(*rsa));
 164     free(rsa);
 165 }
 166
 167 /**
 168  * Add an extra reference to the RSA object. The object should be free
 169  * with RSA_free() to drop the reference.
 170  *
 171  * @param rsa the object to add reference counting too.
 172  *
 173  * @return the current reference count, can't safely be used except
 174  * for debug printing.
 175  *
 176  * @ingroup hcrypto_rsa
 177  */
 178
 179 int
 180 RSA_up_ref(RSA *rsa)
 181 {
 182     return ++rsa->references;
 183 }
 184
 185 /**
 186  * Return the RSA_METHOD used for this RSA object.
 187  *
 188  * @param rsa the object to get the method from.
 189  *
 190  * @return the method used for this RSA object.
 191  *
 192  * @ingroup hcrypto_rsa
 193  */
 194
 195 const RSA_METHOD *
 196 RSA_get_method(const RSA *rsa)
 197 {
 198     return rsa->meth;
 199 }
 200
 201 /**
 202  * Set a new method for the RSA keypair.
 203  *
 204  * @param rsa rsa parameter.
 205  * @param method the new method for the RSA parameter.
 206  *
 207  * @return 1 on success.
 208  *
 209  * @ingroup hcrypto_rsa
 210  */
 211
 212 int
 213 RSA_set_method(RSA *rsa, const RSA_METHOD *method)
 214 {
 215     (*rsa->meth->finish)(rsa);
 216
 217     if (rsa->engine) {
 218         ENGINE_finish(rsa->engine);
 219         rsa->engine = NULL;
 220     }
 221
 222     rsa->meth = method;
 223     (*rsa->meth->init)(rsa);
 224     return 1;
 225 }
 226
 227 /**
 228  * Set the application data for the RSA object.
 229  *
 230  * @param rsa the rsa object to set the parameter for
 231  * @param arg the data object to store
 232  *
 233  * @return 1 on success.
 234  *
 235  * @ingroup hcrypto_rsa
 236  */
 237
 238 int
 239 RSA_set_app_data(RSA *rsa, void *arg)
 240 {
 241     rsa->ex_data.sk = arg;
 242     return 1;
 243 }
 244
 245 /**
 246  * Get the application data for the RSA object.
 247  *
 248  * @param rsa the rsa object to get the parameter for
 249  *
 250  * @return the data object
 251  *
 252  * @ingroup hcrypto_rsa
 253  */
 254
 255 void *
 256 RSA_get_app_data(const RSA *rsa)
 257 {
 258     return rsa->ex_data.sk;
 259 }
 260
 261 int
 262 RSA_check_key(const RSA *key)
 263 {
 264     static const unsigned char inbuf[] = "hello, world!";
 265     RSA *rsa = rk_UNCONST(key);
 266     void *buffer;
 267     int ret;
 268
 269     /*
 270      * XXX I have no clue how to implement this w/o a bignum library.
 271      * Well, when we have a RSA key pair, we can try to encrypt/sign
 272      * and then decrypt/verify.
 273      */
 274
 275     if ((rsa->d == NULL || rsa->n == NULL) &&
 276         (rsa->p == NULL || rsa->q || rsa->dmp1 == NULL || rsa->dmq1 == NULL || rsa->iqmp == NULL))
 277         return 0;
 278
 279     buffer = malloc(RSA_size(rsa));
 280     if (buffer == NULL)
 281         return 0;
 282
 283     ret = RSA_private_encrypt(sizeof(inbuf), inbuf, buffer,
 284                              rsa, RSA_PKCS1_PADDING);
 285     if (ret == -1) {
 286         free(buffer);
 287         return 0;
 288     }
 289
 290     ret = RSA_public_decrypt(ret, buffer, buffer,
 291                               rsa, RSA_PKCS1_PADDING);
 292     if (ret == -1) {
 293         free(buffer);
 294         return 0;
 295     }
 296
 297     if (ret == sizeof(inbuf) && ct_memcmp(buffer, inbuf, sizeof(inbuf)) == 0) {
 298         free(buffer);
 299         return 1;
 300     }
 301     free(buffer);
 302     return 0;
 303 }
 304
 305 int
 306 RSA_size(const RSA *rsa)
 307 {
 308     return BN_num_bytes(rsa->n);
 309 }
 310
 311 #define RSAFUNC(name, body) \
 312 int \
 313 name(int flen,const unsigned char* f, unsigned char* t, RSA* r, int p){\
 314     return body; \
 315 }
 316
 317 RSAFUNC(RSA_public_encrypt, (r)->meth->rsa_pub_enc(flen, f, t, r, p))
 318 RSAFUNC(RSA_public_decrypt, (r)->meth->rsa_pub_dec(flen, f, t, r, p))
 319 RSAFUNC(RSA_private_encrypt, (r)->meth->rsa_priv_enc(flen, f, t, r, p))
 320 RSAFUNC(RSA_private_decrypt, (r)->meth->rsa_priv_dec(flen, f, t, r, p))
 321
 322 static const heim_octet_string null_entry_oid = { 2, rk_UNCONST("\x05\x00") };
 323
 324 static const unsigned sha1_oid_tree[] = { 1, 3, 14, 3, 2, 26 };
 325 static const AlgorithmIdentifier _signature_sha1_data = {
 326     { 6, rk_UNCONST(sha1_oid_tree) }, rk_UNCONST(&null_entry_oid)
 327 };
 328 static const unsigned sha256_oid_tree[] = { 2, 16, 840, 1, 101, 3, 4, 2, 1 };
 329 static const AlgorithmIdentifier _signature_sha256_data = {
 330     { 9, rk_UNCONST(sha256_oid_tree) }, rk_UNCONST(&null_entry_oid)
 331 };
 332 static const unsigned md5_oid_tree[] = { 1, 2, 840, 113549, 2, 5 };
 333 static const AlgorithmIdentifier _signature_md5_data = {
 334     { 6, rk_UNCONST(md5_oid_tree) }, rk_UNCONST(&null_entry_oid)
 335 };
 336
 337
 338 int
 339 RSA_sign(int type, const unsigned char *from, unsigned int flen,
 340          unsigned char *to, unsigned int *tlen, RSA *rsa)
 341 {
 342     if (rsa->meth->rsa_sign)
 343         return rsa->meth->rsa_sign(type, from, flen, to, tlen, rsa);
 344
 345     if (rsa->meth->rsa_priv_enc) {
 346         heim_octet_string indata;
 347         DigestInfo di;
 348         size_t size;
 349         int ret;
 350
 351         memset(&di, 0, sizeof(di));
 352
 353         if (type == NID_sha1) {
 354             di.digestAlgorithm = _signature_sha1_data;
 355         } else if (type == NID_md5) {
 356             di.digestAlgorithm = _signature_md5_data;
 357         } else if (type == NID_sha256) {
 358             di.digestAlgorithm = _signature_sha256_data;
 359         } else
 360             return -1;
 361
 362         di.digest.data = rk_UNCONST(from);
 363         di.digest.length = flen;
 364
 365         ASN1_MALLOC_ENCODE(DigestInfo,
 366                            indata.data,
 367                            indata.length,
 368                            &di,
 369                            &size,
 370                            ret);
 371         if (ret)
 372             return ret;
 373         if (indata.length != size)
 374             abort();
 375
 376         ret = rsa->meth->rsa_priv_enc(indata.length, indata.data, to,
 377                                       rsa, RSA_PKCS1_PADDING);
 378         free(indata.data);
 379         if (ret > 0) {
 380             *tlen = ret;
 381             ret = 1;
 382         } else
 383             ret = 0;
 384
 385         return ret;
 386     }
 387
 388     return 0;
 389 }
 390
 391 int
 392 RSA_verify(int type, const unsigned char *from, unsigned int flen,
 393            unsigned char *sigbuf, unsigned int siglen, RSA *rsa)
 394 {
 395     if (rsa->meth->rsa_verify)
 396         return rsa->meth->rsa_verify(type, from, flen, sigbuf, siglen, rsa);
 397
 398     if (rsa->meth->rsa_pub_dec) {
 399         const AlgorithmIdentifier *digest_alg;
 400         void *data;
 401         DigestInfo di;
 402         size_t size;
 403         int ret, ret2;
 404
 405         data = malloc(RSA_size(rsa));
 406         if (data == NULL)
 407             return -1;
 408
 409         memset(&di, 0, sizeof(di));
 410
 411         ret = rsa->meth->rsa_pub_dec(siglen, sigbuf, data, rsa, RSA_PKCS1_PADDING);
 412         if (ret <= 0) {
 413             free(data);
 414             return -2;
 415         }
 416
 417         ret2 = decode_DigestInfo(data, ret, &di, &size);
 418         free(data);
 419         if (ret2 != 0)
 420             return -3;
 421         if (ret != size) {
 422             free_DigestInfo(&di);
 423             return -4;
 424         }
 425
 426         if (flen != di.digest.length || memcmp(di.digest.data, from, flen) != 0) {
 427             free_DigestInfo(&di);
 428             return -5;
 429         }
 430
 431         if (type == NID_sha1) {
 432             digest_alg = &_signature_sha1_data;
 433         } else if (type == NID_md5) {
 434             digest_alg = &_signature_md5_data;
 435         } else if (type == NID_sha256) {
 436             digest_alg = &_signature_sha256_data;
 437         } else {
 438             free_DigestInfo(&di);
 439             return -1;
 440         }
 441
 442         ret = der_heim_oid_cmp(&digest_alg->algorithm,
 443                                &di.digestAlgorithm.algorithm);
 444         free_DigestInfo(&di);
 445
 446         if (ret != 0)
 447             return 0;
 448         return 1;
 449     }
 450
 451     return 0;
 452 }
 453
 454 /*
 455  * A NULL RSA_METHOD that returns failure for all operations. This is
 456  * used as the default RSA method if we don't have any native
 457  * support.
 458  */
 459
 460 static RSAFUNC(null_rsa_public_encrypt, -1)
 461 static RSAFUNC(null_rsa_public_decrypt, -1)
 462 static RSAFUNC(null_rsa_private_encrypt, -1)
 463 static RSAFUNC(null_rsa_private_decrypt, -1)
 464
 465 /*
 466  *
 467  */
 468
 469 int
 470 RSA_generate_key_ex(RSA *r, int bits, BIGNUM *e, BN_GENCB *cb)
 471 {
 472     if (r->meth->rsa_keygen)
 473         return (*r->meth->rsa_keygen)(r, bits, e, cb);
 474     return 0;
 475 }
 476
 477
 478 /*
 479  *
 480  */
 481
 482 static int
 483 null_rsa_init(RSA *rsa)
 484 {
 485     return 1;
 486 }
 487
 488 static int
 489 null_rsa_finish(RSA *rsa)
 490 {
 491     return 1;
 492 }
 493
 494 static const RSA_METHOD rsa_null_method = {
 495     "hcrypto null RSA",
 496     null_rsa_public_encrypt,
 497     null_rsa_public_decrypt,
 498     null_rsa_private_encrypt,
 499     null_rsa_private_decrypt,
 500     NULL,
 501     NULL,
 502     null_rsa_init,
 503     null_rsa_finish,
 504     0,
 505     NULL,
 506     NULL,
 507     NULL,
 508     NULL
 509 };
 510
 511 const RSA_METHOD *
 512 RSA_null_method(void)
 513 {
 514     return &rsa_null_method;
 515 }
 516
 517 extern const RSA_METHOD hc_rsa_gmp_method;
 518 extern const RSA_METHOD hc_rsa_tfm_method;
 519 extern const RSA_METHOD hc_rsa_ltm_method;
 520 static const RSA_METHOD *default_rsa_method = &hc_rsa_ltm_method;
 521
 522
 523 const RSA_METHOD *
 524 RSA_get_default_method(void)
 525 {
 526     return default_rsa_method;
 527 }
 528
 529 void
 530 RSA_set_default_method(const RSA_METHOD *meth)
 531 {
 532     default_rsa_method = meth;
 533 }
 534
 535 /*
 536  *
 537  */
 538
 539 RSA *
 540 d2i_RSAPrivateKey(RSA *rsa, const unsigned char **pp, size_t len)
 541 {
 542     RSAPrivateKey data;
 543     RSA *k = rsa;
 544     size_t size;
 545     int ret;
 546
 547     ret = decode_RSAPrivateKey(*pp, len, &data, &size);
 548     if (ret)
 549         return NULL;
 550
 551     *pp += size;
 552
 553     if (k == NULL) {
 554         k = RSA_new();
 555         if (k == NULL) {
 556             free_RSAPrivateKey(&data);
 557             return NULL;
 558         }
 559     }
 560
 561     k->n = _hc_integer_to_BN(&data.modulus, NULL);
 562     k->e = _hc_integer_to_BN(&data.publicExponent, NULL);
 563     k->d = _hc_integer_to_BN(&data.privateExponent, NULL);
 564     k->p = _hc_integer_to_BN(&data.prime1, NULL);
 565     k->q = _hc_integer_to_BN(&data.prime2, NULL);
 566     k->dmp1 = _hc_integer_to_BN(&data.exponent1, NULL);
 567     k->dmq1 = _hc_integer_to_BN(&data.exponent2, NULL);
 568     k->iqmp = _hc_integer_to_BN(&data.coefficient, NULL);
 569     free_RSAPrivateKey(&data);
 570
 571     if (k->n == NULL || k->e == NULL || k->d == NULL || k->p == NULL ||
 572         k->q == NULL || k->dmp1 == NULL || k->dmq1 == NULL || k->iqmp == NULL)
 573     {
 574         RSA_free(k);
 575         return NULL;
 576     }
 577
 578     return k;
 579 }
 580
 581 int
 582 i2d_RSAPrivateKey(RSA *rsa, unsigned char **pp)
 583 {
 584     RSAPrivateKey data;
 585     size_t size;
 586     int ret;
 587
 588     if (rsa->n == NULL || rsa->e == NULL || rsa->d == NULL || rsa->p == NULL ||
 589         rsa->q == NULL || rsa->dmp1 == NULL || rsa->dmq1 == NULL ||
 590         rsa->iqmp == NULL)
 591         return -1;
 592
 593     memset(&data, 0, sizeof(data));
 594
 595     ret  = _hc_BN_to_integer(rsa->n, &data.modulus);
 596     ret |= _hc_BN_to_integer(rsa->e, &data.publicExponent);
 597     ret |= _hc_BN_to_integer(rsa->d, &data.privateExponent);
 598     ret |= _hc_BN_to_integer(rsa->p, &data.prime1);
 599     ret |= _hc_BN_to_integer(rsa->q, &data.prime2);
 600     ret |= _hc_BN_to_integer(rsa->dmp1, &data.exponent1);
 601     ret |= _hc_BN_to_integer(rsa->dmq1, &data.exponent2);
 602     ret |= _hc_BN_to_integer(rsa->iqmp, &data.coefficient);
 603     if (ret) {
 604         free_RSAPrivateKey(&data);
 605         return -1;
 606     }
 607
 608     if (pp == NULL) {
 609         size = length_RSAPrivateKey(&data);
 610         free_RSAPrivateKey(&data);
 611     } else {
 612         void *p;
 613         size_t len;
 614
 615         ASN1_MALLOC_ENCODE(RSAPrivateKey, p, len, &data, &size, ret);
 616         free_RSAPrivateKey(&data);
 617         if (ret)
 618             return -1;
 619         if (len != size)
 620             abort();
 621
 622         memcpy(*pp, p, size);
 623         free(p);
 624
 625         *pp += size;
 626
 627     }
 628     return size;
 629 }
 630
 631 int
 632 i2d_RSAPublicKey(RSA *rsa, unsigned char **pp)
 633 {
 634     RSAPublicKey data;
 635     size_t size;
 636     int ret;
 637
 638     memset(&data, 0, sizeof(data));
 639
 640     if (_hc_BN_to_integer(rsa->n, &data.modulus) ||
 641         _hc_BN_to_integer(rsa->e, &data.publicExponent))
 642     {
 643         free_RSAPublicKey(&data);
 644         return -1;
 645     }
 646
 647     if (pp == NULL) {
 648         size = length_RSAPublicKey(&data);
 649         free_RSAPublicKey(&data);
 650     } else {
 651         void *p;
 652         size_t len;
 653
 654         ASN1_MALLOC_ENCODE(RSAPublicKey, p, len, &data, &size, ret);
 655         free_RSAPublicKey(&data);
 656         if (ret)
 657             return -1;
 658         if (len != size)
 659             abort();
 660
 661         memcpy(*pp, p, size);
 662         free(p);
 663
 664         *pp += size;
 665     }
 666
 667     return size;
 668 }
 669
 670 RSA *
 671 d2i_RSAPublicKey(RSA *rsa, const unsigned char **pp, size_t len)
 672 {
 673     RSAPublicKey data;
 674     RSA *k = rsa;
 675     size_t size;
 676     int ret;
 677
 678     ret = decode_RSAPublicKey(*pp, len, &data, &size);
 679     if (ret)
 680         return NULL;
 681
 682     *pp += size;
 683
 684     if (k == NULL) {
 685         k = RSA_new();
 686         if (k == NULL) {
 687             free_RSAPublicKey(&data);
 688             return NULL;
 689         }
 690     }
 691
 692     k->n = _hc_integer_to_BN(&data.modulus, NULL);
 693     k->e = _hc_integer_to_BN(&data.publicExponent, NULL);
 694
 695     free_RSAPublicKey(&data);
 696
 697     if (k->n == NULL || k->e == NULL) {
 698         RSA_free(k);
 699         return NULL;
 700     }
 701
 702     return k;
 703 }