1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2  * All rights reserved.
3  *
4  * This package is an SSL implementation written
5  * by Eric Young (eay@cryptsoft.com).
6  * The implementation was written so as to conform with Netscapes SSL.
7  *
8  * This library is free for commercial and non-commercial use as long as
9  * the following conditions are aheared to.  The following conditions
10  * apply to all code found in this distribution, be it the RC4, RSA,
11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
12  * included with this distribution is covered by the same copyright terms
13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14  *
15  * Copyright remains Eric Young's, and as such any Copyright notices in
16  * the code are not to be removed.
17  * If this package is used in a product, Eric Young should be given attribution
18  * as the author of the parts of the library used.
19  * This can be in the form of a textual message at program startup or
20  * in documentation (online or textual) provided with the package.
21  *
22  * Redistribution and use in source and binary forms, with or without
23  * modification, are permitted provided that the following conditions
24  * are met:
25  * 1. Redistributions of source code must retain the copyright
26  *    notice, this list of conditions and the following disclaimer.
27  * 2. Redistributions in binary form must reproduce the above copyright
28  *    notice, this list of conditions and the following disclaimer in the
29  *    documentation and/or other materials provided with the distribution.
30  * 3. All advertising materials mentioning features or use of this software
31  *    must display the following acknowledgement:
32  *    "This product includes cryptographic software written by
33  *     Eric Young (eay@cryptsoft.com)"
34  *    The word 'cryptographic' can be left out if the rouines from the library
35  *    being used are not cryptographic related :-).
36  * 4. If you include any Windows specific code (or a derivative thereof) from
37  *    the apps directory (application code) you must include an acknowledgement:
38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39  *
40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50  * SUCH DAMAGE.
51  *
52  * The licence and distribution terms for any publically available version or
53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
54  * copied and put under another distribution licence
55  * [including the GNU Public Licence.] */
56 
57 #include <openssl/rsa.h>
58 
59 #include <string.h>
60 
61 #include <openssl/bn.h>
62 #include <openssl/err.h>
63 #include <openssl/mem.h>
64 #include <openssl/thread.h>
65 
66 #include "internal.h"
67 #include "../internal.h"
68 
69 
70 #define OPENSSL_RSA_MAX_MODULUS_BITS 16384
71 #define OPENSSL_RSA_SMALL_MODULUS_BITS 3072
72 #define OPENSSL_RSA_MAX_PUBEXP_BITS \
73   64 /* exponent limit enforced for "large" modulus only */
74 
75 
rsa_default_size(const RSA * rsa)76 size_t rsa_default_size(const RSA *rsa) {
77   return BN_num_bytes(rsa->n);
78 }
79 
rsa_default_encrypt(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)80 int rsa_default_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
81                         const uint8_t *in, size_t in_len, int padding) {
82   const unsigned rsa_size = RSA_size(rsa);
83   BIGNUM *f, *result;
84   uint8_t *buf = NULL;
85   BN_CTX *ctx = NULL;
86   int i, ret = 0;
87 
88   if (rsa_size > OPENSSL_RSA_MAX_MODULUS_BITS) {
89     OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
90     return 0;
91   }
92 
93   if (max_out < rsa_size) {
94     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
95     return 0;
96   }
97 
98   if (BN_ucmp(rsa->n, rsa->e) <= 0) {
99     OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
100     return 0;
101   }
102 
103   /* for large moduli, enforce exponent limit */
104   if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
105       BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
106     OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
107     return 0;
108   }
109 
110   ctx = BN_CTX_new();
111   if (ctx == NULL) {
112     goto err;
113   }
114 
115   BN_CTX_start(ctx);
116   f = BN_CTX_get(ctx);
117   result = BN_CTX_get(ctx);
118   buf = OPENSSL_malloc(rsa_size);
119   if (!f || !result || !buf) {
120     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
121     goto err;
122   }
123 
124   switch (padding) {
125     case RSA_PKCS1_PADDING:
126       i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
127       break;
128     case RSA_PKCS1_OAEP_PADDING:
129       /* Use the default parameters: SHA-1 for both hashes and no label. */
130       i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
131                                           NULL, 0, NULL, NULL);
132       break;
133     case RSA_NO_PADDING:
134       i = RSA_padding_add_none(buf, rsa_size, in, in_len);
135       break;
136     default:
137       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
138       goto err;
139   }
140 
141   if (i <= 0) {
142     goto err;
143   }
144 
145   if (BN_bin2bn(buf, rsa_size, f) == NULL) {
146     goto err;
147   }
148 
149   if (BN_ucmp(f, rsa->n) >= 0) {
150     /* usually the padding functions would catch this */
151     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
152     goto err;
153   }
154 
155   if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
156     if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) == NULL) {
157       goto err;
158     }
159   }
160 
161   if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
162     goto err;
163   }
164 
165   /* put in leading 0 bytes if the number is less than the length of the
166    * modulus */
167   if (!BN_bn2bin_padded(out, rsa_size, result)) {
168     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
169     goto err;
170   }
171 
172   *out_len = rsa_size;
173   ret = 1;
174 
175 err:
176   if (ctx != NULL) {
177     BN_CTX_end(ctx);
178     BN_CTX_free(ctx);
179   }
180   if (buf != NULL) {
181     OPENSSL_cleanse(buf, rsa_size);
182     OPENSSL_free(buf);
183   }
184 
185   return ret;
186 }
187 
188 /* MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
189  * RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
190  * destroyed as needed. */
191 #define MAX_BLINDINGS_PER_RSA 1024
192 
193 /* rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
194  * allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
195  * none are free, the cache will be extended by a extra element and the new
196  * BN_BLINDING is returned.
197  *
198  * On success, the index of the assigned BN_BLINDING is written to
199  * |*index_used| and must be passed to |rsa_blinding_release| when finished. */
rsa_blinding_get(RSA * rsa,unsigned * index_used,BN_CTX * ctx)200 static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
201                                      BN_CTX *ctx) {
202   BN_BLINDING *ret = NULL;
203   BN_BLINDING **new_blindings;
204   uint8_t *new_blindings_inuse;
205   char overflow = 0;
206 
207   CRYPTO_MUTEX_lock_write(&rsa->lock);
208 
209   unsigned i;
210   for (i = 0; i < rsa->num_blindings; i++) {
211     if (rsa->blindings_inuse[i] == 0) {
212       rsa->blindings_inuse[i] = 1;
213       ret = rsa->blindings[i];
214       *index_used = i;
215       break;
216     }
217   }
218 
219   if (ret != NULL) {
220     CRYPTO_MUTEX_unlock(&rsa->lock);
221     return ret;
222   }
223 
224   overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
225 
226   /* We didn't find a free BN_BLINDING to use so increase the length of
227    * the arrays by one and use the newly created element. */
228 
229   CRYPTO_MUTEX_unlock(&rsa->lock);
230   ret = rsa_setup_blinding(rsa, ctx);
231   if (ret == NULL) {
232     return NULL;
233   }
234 
235   if (overflow) {
236     /* We cannot add any more cached BN_BLINDINGs so we use |ret|
237      * and mark it for destruction in |rsa_blinding_release|. */
238     *index_used = MAX_BLINDINGS_PER_RSA;
239     return ret;
240   }
241 
242   CRYPTO_MUTEX_lock_write(&rsa->lock);
243 
244   new_blindings =
245       OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
246   if (new_blindings == NULL) {
247     goto err1;
248   }
249   memcpy(new_blindings, rsa->blindings,
250          sizeof(BN_BLINDING *) * rsa->num_blindings);
251   new_blindings[rsa->num_blindings] = ret;
252 
253   new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
254   if (new_blindings_inuse == NULL) {
255     goto err2;
256   }
257   memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
258   new_blindings_inuse[rsa->num_blindings] = 1;
259   *index_used = rsa->num_blindings;
260 
261   OPENSSL_free(rsa->blindings);
262   rsa->blindings = new_blindings;
263   OPENSSL_free(rsa->blindings_inuse);
264   rsa->blindings_inuse = new_blindings_inuse;
265   rsa->num_blindings++;
266 
267   CRYPTO_MUTEX_unlock(&rsa->lock);
268   return ret;
269 
270 err2:
271   OPENSSL_free(new_blindings);
272 
273 err1:
274   CRYPTO_MUTEX_unlock(&rsa->lock);
275   BN_BLINDING_free(ret);
276   return NULL;
277 }
278 
279 /* rsa_blinding_release marks the cached BN_BLINDING at the given index as free
280  * for other threads to use. */
rsa_blinding_release(RSA * rsa,BN_BLINDING * blinding,unsigned blinding_index)281 static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
282                                  unsigned blinding_index) {
283   if (blinding_index == MAX_BLINDINGS_PER_RSA) {
284     /* This blinding wasn't cached. */
285     BN_BLINDING_free(blinding);
286     return;
287   }
288 
289   CRYPTO_MUTEX_lock_write(&rsa->lock);
290   rsa->blindings_inuse[blinding_index] = 0;
291   CRYPTO_MUTEX_unlock(&rsa->lock);
292 }
293 
294 /* signing */
rsa_default_sign_raw(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)295 int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out,
296                          size_t max_out, const uint8_t *in, size_t in_len,
297                          int padding) {
298   const unsigned rsa_size = RSA_size(rsa);
299   uint8_t *buf = NULL;
300   int i, ret = 0;
301 
302   if (max_out < rsa_size) {
303     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
304     return 0;
305   }
306 
307   buf = OPENSSL_malloc(rsa_size);
308   if (buf == NULL) {
309     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
310     goto err;
311   }
312 
313   switch (padding) {
314     case RSA_PKCS1_PADDING:
315       i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
316       break;
317     case RSA_NO_PADDING:
318       i = RSA_padding_add_none(buf, rsa_size, in, in_len);
319       break;
320     default:
321       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
322       goto err;
323   }
324 
325   if (i <= 0) {
326     goto err;
327   }
328 
329   if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
330     goto err;
331   }
332 
333   *out_len = rsa_size;
334   ret = 1;
335 
336 err:
337   if (buf != NULL) {
338     OPENSSL_cleanse(buf, rsa_size);
339     OPENSSL_free(buf);
340   }
341 
342   return ret;
343 }
344 
rsa_default_decrypt(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)345 int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
346                         const uint8_t *in, size_t in_len, int padding) {
347   const unsigned rsa_size = RSA_size(rsa);
348   int r = -1;
349   uint8_t *buf = NULL;
350   int ret = 0;
351 
352   if (max_out < rsa_size) {
353     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
354     return 0;
355   }
356 
357   if (padding == RSA_NO_PADDING) {
358     buf = out;
359   } else {
360     /* Allocate a temporary buffer to hold the padded plaintext. */
361     buf = OPENSSL_malloc(rsa_size);
362     if (buf == NULL) {
363       OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
364       goto err;
365     }
366   }
367 
368   if (in_len != rsa_size) {
369     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
370     goto err;
371   }
372 
373   if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
374     goto err;
375   }
376 
377   switch (padding) {
378     case RSA_PKCS1_PADDING:
379       r = RSA_padding_check_PKCS1_type_2(out, rsa_size, buf, rsa_size);
380       break;
381     case RSA_PKCS1_OAEP_PADDING:
382       /* Use the default parameters: SHA-1 for both hashes and no label. */
383       r = RSA_padding_check_PKCS1_OAEP_mgf1(out, rsa_size, buf, rsa_size,
384                                             NULL, 0, NULL, NULL);
385       break;
386     case RSA_NO_PADDING:
387       r = rsa_size;
388       break;
389     default:
390       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
391       goto err;
392   }
393 
394   if (r < 0) {
395     OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
396   } else {
397     *out_len = r;
398     ret = 1;
399   }
400 
401 err:
402   if (padding != RSA_NO_PADDING && buf != NULL) {
403     OPENSSL_cleanse(buf, rsa_size);
404     OPENSSL_free(buf);
405   }
406 
407   return ret;
408 }
409 
rsa_default_verify_raw(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)410 int rsa_default_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out,
411                            size_t max_out, const uint8_t *in, size_t in_len,
412                            int padding) {
413   const unsigned rsa_size = RSA_size(rsa);
414   BIGNUM *f, *result;
415   int ret = 0;
416   int r = -1;
417   uint8_t *buf = NULL;
418   BN_CTX *ctx = NULL;
419 
420   if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
421     OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
422     return 0;
423   }
424 
425   if (BN_ucmp(rsa->n, rsa->e) <= 0) {
426     OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
427     return 0;
428   }
429 
430   if (max_out < rsa_size) {
431     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
432     return 0;
433   }
434 
435   /* for large moduli, enforce exponent limit */
436   if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
437       BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
438     OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
439     return 0;
440   }
441 
442   ctx = BN_CTX_new();
443   if (ctx == NULL) {
444     goto err;
445   }
446 
447   BN_CTX_start(ctx);
448   f = BN_CTX_get(ctx);
449   result = BN_CTX_get(ctx);
450   if (padding == RSA_NO_PADDING) {
451     buf = out;
452   } else {
453     /* Allocate a temporary buffer to hold the padded plaintext. */
454     buf = OPENSSL_malloc(rsa_size);
455     if (buf == NULL) {
456       OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
457       goto err;
458     }
459   }
460   if (!f || !result) {
461     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
462     goto err;
463   }
464 
465   if (in_len != rsa_size) {
466     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
467     goto err;
468   }
469 
470   if (BN_bin2bn(in, in_len, f) == NULL) {
471     goto err;
472   }
473 
474   if (BN_ucmp(f, rsa->n) >= 0) {
475     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
476     goto err;
477   }
478 
479   if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
480     if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) == NULL) {
481       goto err;
482     }
483   }
484 
485   if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
486     goto err;
487   }
488 
489   if (!BN_bn2bin_padded(buf, rsa_size, result)) {
490     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
491     goto err;
492   }
493 
494   switch (padding) {
495     case RSA_PKCS1_PADDING:
496       r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);
497       break;
498     case RSA_NO_PADDING:
499       r = rsa_size;
500       break;
501     default:
502       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
503       goto err;
504   }
505 
506   if (r < 0) {
507     OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
508   } else {
509     *out_len = r;
510     ret = 1;
511   }
512 
513 err:
514   if (ctx != NULL) {
515     BN_CTX_end(ctx);
516     BN_CTX_free(ctx);
517   }
518   if (padding != RSA_NO_PADDING && buf != NULL) {
519     OPENSSL_cleanse(buf, rsa_size);
520     OPENSSL_free(buf);
521   }
522   return ret;
523 }
524 
rsa_default_private_transform(RSA * rsa,uint8_t * out,const uint8_t * in,size_t len)525 int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
526                                   size_t len) {
527   BIGNUM *f, *result;
528   BN_CTX *ctx = NULL;
529   unsigned blinding_index = 0;
530   BN_BLINDING *blinding = NULL;
531   int ret = 0;
532 
533   ctx = BN_CTX_new();
534   if (ctx == NULL) {
535     goto err;
536   }
537   BN_CTX_start(ctx);
538   f = BN_CTX_get(ctx);
539   result = BN_CTX_get(ctx);
540 
541   if (f == NULL || result == NULL) {
542     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
543     goto err;
544   }
545 
546   if (BN_bin2bn(in, len, f) == NULL) {
547     goto err;
548   }
549 
550   if (BN_ucmp(f, rsa->n) >= 0) {
551     /* Usually the padding functions would catch this. */
552     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
553     goto err;
554   }
555 
556   if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
557     blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
558     if (blinding == NULL) {
559       OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
560       goto err;
561     }
562     if (!BN_BLINDING_convert_ex(f, NULL, blinding, ctx)) {
563       goto err;
564     }
565   }
566 
567   if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
568       ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) &&
569        (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
570     if (!rsa->meth->mod_exp(result, f, rsa, ctx)) {
571       goto err;
572     }
573   } else {
574     BIGNUM local_d;
575     BIGNUM *d = NULL;
576 
577     BN_init(&local_d);
578     d = &local_d;
579     BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
580 
581     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
582       if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ==
583           NULL) {
584         goto err;
585       }
586     }
587 
588     if (!rsa->meth->bn_mod_exp(result, f, d, rsa->n, ctx, rsa->mont_n)) {
589       goto err;
590     }
591   }
592 
593   if (blinding) {
594     if (!BN_BLINDING_invert_ex(result, NULL, blinding, ctx)) {
595       goto err;
596     }
597   }
598 
599   if (!BN_bn2bin_padded(out, len, result)) {
600     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
601     goto err;
602   }
603 
604   ret = 1;
605 
606 err:
607   if (ctx != NULL) {
608     BN_CTX_end(ctx);
609     BN_CTX_free(ctx);
610   }
611   if (blinding != NULL) {
612     rsa_blinding_release(rsa, blinding, blinding_index);
613   }
614 
615   return ret;
616 }
617 
mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)618 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
619   BIGNUM *r1, *m1, *vrfy;
620   BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
621   BIGNUM *dmp1, *dmq1, *c, *pr1;
622   int ret = 0;
623   size_t i, num_additional_primes = 0;
624 
625   if (rsa->additional_primes != NULL) {
626     num_additional_primes = sk_RSA_additional_prime_num(rsa->additional_primes);
627   }
628 
629   BN_CTX_start(ctx);
630   r1 = BN_CTX_get(ctx);
631   m1 = BN_CTX_get(ctx);
632   vrfy = BN_CTX_get(ctx);
633 
634   {
635     BIGNUM local_p, local_q;
636     BIGNUM *p = NULL, *q = NULL;
637 
638     /* Make sure BN_mod_inverse in Montgomery intialization uses the
639      * BN_FLG_CONSTTIME flag. */
640     BN_init(&local_p);
641     p = &local_p;
642     BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
643 
644     BN_init(&local_q);
645     q = &local_q;
646     BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
647 
648     if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
649       if (BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, p, ctx) == NULL) {
650         goto err;
651       }
652       if (BN_MONT_CTX_set_locked(&rsa->mont_q, &rsa->lock, q, ctx) == NULL) {
653         goto err;
654       }
655     }
656   }
657 
658   if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
659     if (BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) == NULL) {
660       goto err;
661     }
662   }
663 
664   /* compute I mod q */
665   c = &local_c;
666   BN_with_flags(c, I, BN_FLG_CONSTTIME);
667   if (!BN_mod(r1, c, rsa->q, ctx)) {
668     goto err;
669   }
670 
671   /* compute r1^dmq1 mod q */
672   dmq1 = &local_dmq1;
673   BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
674   if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, rsa->mont_q)) {
675     goto err;
676   }
677 
678   /* compute I mod p */
679   c = &local_c;
680   BN_with_flags(c, I, BN_FLG_CONSTTIME);
681   if (!BN_mod(r1, c, rsa->p, ctx)) {
682     goto err;
683   }
684 
685   /* compute r1^dmp1 mod p */
686   dmp1 = &local_dmp1;
687   BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
688   if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, rsa->mont_p)) {
689     goto err;
690   }
691 
692   if (!BN_sub(r0, r0, m1)) {
693     goto err;
694   }
695   /* This will help stop the size of r0 increasing, which does
696    * affect the multiply if it optimised for a power of 2 size */
697   if (BN_is_negative(r0)) {
698     if (!BN_add(r0, r0, rsa->p)) {
699       goto err;
700     }
701   }
702 
703   if (!BN_mul(r1, r0, rsa->iqmp, ctx)) {
704     goto err;
705   }
706 
707   /* Turn BN_FLG_CONSTTIME flag on before division operation */
708   pr1 = &local_r1;
709   BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
710 
711   if (!BN_mod(r0, pr1, rsa->p, ctx)) {
712     goto err;
713   }
714 
715   /* If p < q it is occasionally possible for the correction of
716    * adding 'p' if r0 is negative above to leave the result still
717    * negative. This can break the private key operations: the following
718    * second correction should *always* correct this rare occurrence.
719    * This will *never* happen with OpenSSL generated keys because
720    * they ensure p > q [steve] */
721   if (BN_is_negative(r0)) {
722     if (!BN_add(r0, r0, rsa->p)) {
723       goto err;
724     }
725   }
726   if (!BN_mul(r1, r0, rsa->q, ctx)) {
727     goto err;
728   }
729   if (!BN_add(r0, r1, m1)) {
730     goto err;
731   }
732 
733   for (i = 0; i < num_additional_primes; i++) {
734     /* multi-prime RSA. */
735     BIGNUM local_exp, local_prime;
736     BIGNUM *exp = &local_exp, *prime = &local_prime;
737     RSA_additional_prime *ap =
738         sk_RSA_additional_prime_value(rsa->additional_primes, i);
739 
740     BN_with_flags(exp, ap->exp, BN_FLG_CONSTTIME);
741     BN_with_flags(prime, ap->prime, BN_FLG_CONSTTIME);
742 
743     /* c will already point to a BIGNUM with the correct flags. */
744     if (!BN_mod(r1, c, prime, ctx)) {
745       goto err;
746     }
747 
748     if ((rsa->flags & RSA_FLAG_CACHE_PRIVATE) &&
749         !BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, prime, ctx)) {
750       goto err;
751     }
752 
753     if (!rsa->meth->bn_mod_exp(m1, r1, exp, prime, ctx, ap->mont)) {
754       goto err;
755     }
756 
757     BN_set_flags(m1, BN_FLG_CONSTTIME);
758 
759     if (!BN_sub(m1, m1, r0) ||
760         !BN_mul(m1, m1, ap->coeff, ctx) ||
761         !BN_mod(m1, m1, prime, ctx) ||
762         (BN_is_negative(m1) && !BN_add(m1, m1, prime)) ||
763         !BN_mul(m1, m1, ap->r, ctx) ||
764         !BN_add(r0, r0, m1)) {
765       goto err;
766     }
767   }
768 
769   if (rsa->e && rsa->n) {
770     if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, rsa->mont_n)) {
771       goto err;
772     }
773     /* If 'I' was greater than (or equal to) rsa->n, the operation
774      * will be equivalent to using 'I mod n'. However, the result of
775      * the verify will *always* be less than 'n' so we don't check
776      * for absolute equality, just congruency. */
777     if (!BN_sub(vrfy, vrfy, I)) {
778       goto err;
779     }
780     if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) {
781       goto err;
782     }
783     if (BN_is_negative(vrfy)) {
784       if (!BN_add(vrfy, vrfy, rsa->n)) {
785         goto err;
786       }
787     }
788     if (!BN_is_zero(vrfy)) {
789       /* 'I' and 'vrfy' aren't congruent mod n. Don't leak
790        * miscalculated CRT output, just do a raw (slower)
791        * mod_exp and return that instead. */
792 
793       BIGNUM local_d;
794       BIGNUM *d = NULL;
795 
796       d = &local_d;
797       BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
798       if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, rsa->mont_n)) {
799         goto err;
800       }
801     }
802   }
803   ret = 1;
804 
805 err:
806   BN_CTX_end(ctx);
807   return ret;
808 }
809 
rsa_default_multi_prime_keygen(RSA * rsa,int bits,int num_primes,BIGNUM * e_value,BN_GENCB * cb)810 int rsa_default_multi_prime_keygen(RSA *rsa, int bits, int num_primes,
811                                    BIGNUM *e_value, BN_GENCB *cb) {
812   BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
813   BIGNUM local_r0, local_d, local_p;
814   BIGNUM *pr0, *d, *p;
815   int prime_bits, ok = -1, n = 0, i, j;
816   BN_CTX *ctx = NULL;
817   STACK_OF(RSA_additional_prime) *additional_primes = NULL;
818 
819   if (num_primes < 2) {
820     ok = 0; /* we set our own err */
821     OPENSSL_PUT_ERROR(RSA, RSA_R_MUST_HAVE_AT_LEAST_TWO_PRIMES);
822     goto err;
823   }
824 
825   ctx = BN_CTX_new();
826   if (ctx == NULL) {
827     goto err;
828   }
829   BN_CTX_start(ctx);
830   r0 = BN_CTX_get(ctx);
831   r1 = BN_CTX_get(ctx);
832   r2 = BN_CTX_get(ctx);
833   r3 = BN_CTX_get(ctx);
834   if (r0 == NULL || r1 == NULL || r2 == NULL || r3 == NULL) {
835     goto err;
836   }
837 
838   if (num_primes > 2) {
839     additional_primes = sk_RSA_additional_prime_new_null();
840     if (additional_primes == NULL) {
841       goto err;
842     }
843   }
844 
845   for (i = 2; i < num_primes; i++) {
846     RSA_additional_prime *ap = OPENSSL_malloc(sizeof(RSA_additional_prime));
847     if (ap == NULL) {
848       goto err;
849     }
850     memset(ap, 0, sizeof(RSA_additional_prime));
851     ap->prime = BN_new();
852     ap->exp = BN_new();
853     ap->coeff = BN_new();
854     ap->r = BN_new();
855     if (ap->prime == NULL ||
856         ap->exp == NULL ||
857         ap->coeff == NULL ||
858         ap->r == NULL ||
859         !sk_RSA_additional_prime_push(additional_primes, ap)) {
860       RSA_additional_prime_free(ap);
861       goto err;
862     }
863   }
864 
865   /* We need the RSA components non-NULL */
866   if (!rsa->n && ((rsa->n = BN_new()) == NULL)) {
867     goto err;
868   }
869   if (!rsa->d && ((rsa->d = BN_new()) == NULL)) {
870     goto err;
871   }
872   if (!rsa->e && ((rsa->e = BN_new()) == NULL)) {
873     goto err;
874   }
875   if (!rsa->p && ((rsa->p = BN_new()) == NULL)) {
876     goto err;
877   }
878   if (!rsa->q && ((rsa->q = BN_new()) == NULL)) {
879     goto err;
880   }
881   if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL)) {
882     goto err;
883   }
884   if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL)) {
885     goto err;
886   }
887   if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL)) {
888     goto err;
889   }
890 
891   if (!BN_copy(rsa->e, e_value)) {
892     goto err;
893   }
894 
895   /* generate p and q */
896   prime_bits = (bits + (num_primes - 1)) / num_primes;
897   for (;;) {
898     if (!BN_generate_prime_ex(rsa->p, prime_bits, 0, NULL, NULL, cb) ||
899         !BN_sub(r2, rsa->p, BN_value_one()) ||
900         !BN_gcd(r1, r2, rsa->e, ctx)) {
901       goto err;
902     }
903     if (BN_is_one(r1)) {
904       break;
905     }
906     if (!BN_GENCB_call(cb, 2, n++)) {
907       goto err;
908     }
909   }
910   if (!BN_GENCB_call(cb, 3, 0)) {
911     goto err;
912   }
913   prime_bits = ((bits - prime_bits) + (num_primes - 2)) / (num_primes - 1);
914   for (;;) {
915     /* When generating ridiculously small keys, we can get stuck
916      * continually regenerating the same prime values. Check for
917      * this and bail if it happens 3 times. */
918     unsigned int degenerate = 0;
919     do {
920       if (!BN_generate_prime_ex(rsa->q, prime_bits, 0, NULL, NULL, cb)) {
921         goto err;
922       }
923     } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
924     if (degenerate == 3) {
925       ok = 0; /* we set our own err */
926       OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
927       goto err;
928     }
929     if (!BN_sub(r2, rsa->q, BN_value_one()) ||
930         !BN_gcd(r1, r2, rsa->e, ctx)) {
931       goto err;
932     }
933     if (BN_is_one(r1)) {
934       break;
935     }
936     if (!BN_GENCB_call(cb, 2, n++)) {
937       goto err;
938     }
939   }
940 
941   if (!BN_GENCB_call(cb, 3, 1) ||
942       !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) {
943     goto err;
944   }
945 
946   for (i = 2; i < num_primes; i++) {
947     RSA_additional_prime *ap =
948         sk_RSA_additional_prime_value(additional_primes, i - 2);
949     prime_bits = ((bits - BN_num_bits(rsa->n)) + (num_primes - (i + 1))) /
950                  (num_primes - i);
951 
952     for (;;) {
953       if (!BN_generate_prime_ex(ap->prime, prime_bits, 0, NULL, NULL, cb)) {
954         goto err;
955       }
956       if (BN_cmp(rsa->p, ap->prime) == 0 ||
957           BN_cmp(rsa->q, ap->prime) == 0) {
958         continue;
959       }
960 
961       for (j = 0; j < i - 2; j++) {
962         if (BN_cmp(sk_RSA_additional_prime_value(additional_primes, j)->prime,
963                    ap->prime) == 0) {
964           break;
965         }
966       }
967       if (j != i - 2) {
968         continue;
969       }
970 
971       if (!BN_sub(r2, ap->prime, BN_value_one()) ||
972           !BN_gcd(r1, r2, rsa->e, ctx)) {
973         goto err;
974       }
975 
976       if (!BN_is_one(r1)) {
977         continue;
978       }
979       if (i != num_primes - 1) {
980         break;
981       }
982 
983       /* For the last prime we'll check that it makes n large enough. In the
984        * two prime case this isn't a problem because we generate primes with
985        * the top two bits set and so the product is always of the expected
986        * size. In the multi prime case, this doesn't follow. */
987       if (!BN_mul(r1, rsa->n, ap->prime, ctx)) {
988         goto err;
989       }
990       if (BN_num_bits(r1) == (unsigned) bits) {
991         break;
992       }
993 
994       if (!BN_GENCB_call(cb, 2, n++)) {
995         goto err;
996       }
997     }
998 
999     /* ap->r is is the product of all the primes prior to the current one
1000      * (including p and q). */
1001     if (!BN_copy(ap->r, rsa->n)) {
1002       goto err;
1003     }
1004     if (i == num_primes - 1) {
1005       /* In the case of the last prime, we calculated n as |r1| in the loop
1006        * above. */
1007       if (!BN_copy(rsa->n, r1)) {
1008         goto err;
1009       }
1010     } else if (!BN_mul(rsa->n, rsa->n, ap->prime, ctx)) {
1011       goto err;
1012     }
1013 
1014     if (!BN_GENCB_call(cb, 3, 1)) {
1015       goto err;
1016     }
1017   }
1018 
1019   if (BN_cmp(rsa->p, rsa->q) < 0) {
1020     tmp = rsa->p;
1021     rsa->p = rsa->q;
1022     rsa->q = tmp;
1023   }
1024 
1025   /* calculate d */
1026   if (!BN_sub(r1, rsa->p, BN_value_one())) {
1027     goto err; /* p-1 */
1028   }
1029   if (!BN_sub(r2, rsa->q, BN_value_one())) {
1030     goto err; /* q-1 */
1031   }
1032   if (!BN_mul(r0, r1, r2, ctx)) {
1033     goto err; /* (p-1)(q-1) */
1034   }
1035   for (i = 2; i < num_primes; i++) {
1036     RSA_additional_prime *ap =
1037         sk_RSA_additional_prime_value(additional_primes, i - 2);
1038     if (!BN_sub(r3, ap->prime, BN_value_one()) ||
1039         !BN_mul(r0, r0, r3, ctx)) {
1040       goto err;
1041     }
1042   }
1043   pr0 = &local_r0;
1044   BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
1045   if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx)) {
1046     goto err; /* d */
1047   }
1048 
1049   /* set up d for correct BN_FLG_CONSTTIME flag */
1050   d = &local_d;
1051   BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
1052 
1053   /* calculate d mod (p-1) */
1054   if (!BN_mod(rsa->dmp1, d, r1, ctx)) {
1055     goto err;
1056   }
1057 
1058   /* calculate d mod (q-1) */
1059   if (!BN_mod(rsa->dmq1, d, r2, ctx)) {
1060     goto err;
1061   }
1062 
1063   /* calculate inverse of q mod p */
1064   p = &local_p;
1065   BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
1066 
1067   if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx)) {
1068     goto err;
1069   }
1070 
1071   for (i = 2; i < num_primes; i++) {
1072     RSA_additional_prime *ap =
1073         sk_RSA_additional_prime_value(additional_primes, i - 2);
1074     if (!BN_sub(ap->exp, ap->prime, BN_value_one()) ||
1075         !BN_mod(ap->exp, rsa->d, ap->exp, ctx) ||
1076         !BN_mod_inverse(ap->coeff, ap->r, ap->prime, ctx)) {
1077       goto err;
1078     }
1079   }
1080 
1081   ok = 1;
1082   rsa->additional_primes = additional_primes;
1083   additional_primes = NULL;
1084 
1085 err:
1086   if (ok == -1) {
1087     OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
1088     ok = 0;
1089   }
1090   if (ctx != NULL) {
1091     BN_CTX_end(ctx);
1092     BN_CTX_free(ctx);
1093   }
1094   sk_RSA_additional_prime_pop_free(additional_primes,
1095                                    RSA_additional_prime_free);
1096   return ok;
1097 }
1098 
rsa_default_keygen(RSA * rsa,int bits,BIGNUM * e_value,BN_GENCB * cb)1099 int rsa_default_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
1100   return rsa_default_multi_prime_keygen(rsa, bits, 2 /* num primes */, e_value,
1101                                         cb);
1102 }
1103 
1104 /* Many of these methods are NULL to more easily drop unused functions. The
1105  * wrapper functions will select the appropriate |rsa_default_*| for all
1106  * methods. */
1107 const RSA_METHOD RSA_default_method = {
1108   {
1109     0 /* references */,
1110     1 /* is_static */,
1111   },
1112   NULL /* app_data */,
1113 
1114   NULL /* init */,
1115   NULL /* finish (defaults to rsa_default_finish) */,
1116 
1117   NULL /* size (defaults to rsa_default_size) */,
1118 
1119   NULL /* sign */,
1120   NULL /* verify */,
1121 
1122   NULL /* encrypt (defaults to rsa_default_encrypt) */,
1123   NULL /* sign_raw (defaults to rsa_default_sign_raw) */,
1124   NULL /* decrypt (defaults to rsa_default_decrypt) */,
1125   NULL /* verify_raw (defaults to rsa_default_verify_raw) */,
1126 
1127   NULL /* private_transform (defaults to rsa_default_private_transform) */,
1128 
1129   mod_exp,
1130   BN_mod_exp_mont /* bn_mod_exp */,
1131 
1132   RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
1133 
1134   NULL /* keygen (defaults to rsa_default_keygen) */,
1135   NULL /* multi_prime_keygen (defaults to rsa_default_multi_prime_keygen) */,
1136 
1137   NULL /* supports_digest */,
1138 };
1139