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