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