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 <assert.h>
60 #include <string.h>
61 
62 #include <openssl/bn.h>
63 #include <openssl/err.h>
64 #include <openssl/mem.h>
65 #include <openssl/thread.h>
66 
67 #include "internal.h"
68 #include "../bn/internal.h"
69 #include "../internal.h"
70 
71 
check_modulus_and_exponent_sizes(const RSA * rsa)72 static int check_modulus_and_exponent_sizes(const RSA *rsa) {
73   unsigned rsa_bits = BN_num_bits(rsa->n);
74 
75   if (rsa_bits > 16 * 1024) {
76     OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
77     return 0;
78   }
79 
80   /* Mitigate DoS attacks by limiting the exponent size. 33 bits was chosen as
81    * the limit based on the recommendations in [1] and [2]. Windows CryptoAPI
82    * doesn't support values larger than 32 bits [3], so it is unlikely that
83    * exponents larger than 32 bits are being used for anything Windows commonly
84    * does.
85    *
86    * [1] https://www.imperialviolet.org/2012/03/16/rsae.html
87    * [2] https://www.imperialviolet.org/2012/03/17/rsados.html
88    * [3] https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx */
89   static const unsigned kMaxExponentBits = 33;
90 
91   if (BN_num_bits(rsa->e) > kMaxExponentBits) {
92     OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
93     return 0;
94   }
95 
96   /* Verify |n > e|. Comparing |rsa_bits| to |kMaxExponentBits| is a small
97    * shortcut to comparing |n| and |e| directly. In reality, |kMaxExponentBits|
98    * is much smaller than the minimum RSA key size that any application should
99    * accept. */
100   if (rsa_bits <= kMaxExponentBits) {
101     OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
102     return 0;
103   }
104   assert(BN_ucmp(rsa->n, rsa->e) > 0);
105 
106   return 1;
107 }
108 
rsa_default_size(const RSA * rsa)109 size_t rsa_default_size(const RSA *rsa) {
110   return BN_num_bytes(rsa->n);
111 }
112 
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)113 int rsa_default_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
114                         const uint8_t *in, size_t in_len, int padding) {
115   const unsigned rsa_size = RSA_size(rsa);
116   BIGNUM *f, *result;
117   uint8_t *buf = NULL;
118   BN_CTX *ctx = NULL;
119   int i, ret = 0;
120 
121   if (max_out < rsa_size) {
122     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
123     return 0;
124   }
125 
126   if (!check_modulus_and_exponent_sizes(rsa)) {
127     return 0;
128   }
129 
130   ctx = BN_CTX_new();
131   if (ctx == NULL) {
132     goto err;
133   }
134 
135   BN_CTX_start(ctx);
136   f = BN_CTX_get(ctx);
137   result = BN_CTX_get(ctx);
138   buf = OPENSSL_malloc(rsa_size);
139   if (!f || !result || !buf) {
140     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
141     goto err;
142   }
143 
144   switch (padding) {
145     case RSA_PKCS1_PADDING:
146       i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
147       break;
148     case RSA_PKCS1_OAEP_PADDING:
149       /* Use the default parameters: SHA-1 for both hashes and no label. */
150       i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
151                                           NULL, 0, NULL, NULL);
152       break;
153     case RSA_NO_PADDING:
154       i = RSA_padding_add_none(buf, rsa_size, in, in_len);
155       break;
156     default:
157       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
158       goto err;
159   }
160 
161   if (i <= 0) {
162     goto err;
163   }
164 
165   if (BN_bin2bn(buf, rsa_size, f) == NULL) {
166     goto err;
167   }
168 
169   if (BN_ucmp(f, rsa->n) >= 0) {
170     /* usually the padding functions would catch this */
171     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
172     goto err;
173   }
174 
175   if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
176       !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
177     goto err;
178   }
179 
180   /* put in leading 0 bytes if the number is less than the length of the
181    * modulus */
182   if (!BN_bn2bin_padded(out, rsa_size, result)) {
183     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
184     goto err;
185   }
186 
187   *out_len = rsa_size;
188   ret = 1;
189 
190 err:
191   if (ctx != NULL) {
192     BN_CTX_end(ctx);
193     BN_CTX_free(ctx);
194   }
195   if (buf != NULL) {
196     OPENSSL_cleanse(buf, rsa_size);
197     OPENSSL_free(buf);
198   }
199 
200   return ret;
201 }
202 
203 /* MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
204  * RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
205  * destroyed as needed. */
206 #define MAX_BLINDINGS_PER_RSA 1024
207 
208 /* rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
209  * allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
210  * none are free, the cache will be extended by a extra element and the new
211  * BN_BLINDING is returned.
212  *
213  * On success, the index of the assigned BN_BLINDING is written to
214  * |*index_used| and must be passed to |rsa_blinding_release| when finished. */
rsa_blinding_get(RSA * rsa,unsigned * index_used,BN_CTX * ctx)215 static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
216                                      BN_CTX *ctx) {
217   assert(ctx != NULL);
218   assert(rsa->mont_n != NULL);
219 
220   BN_BLINDING *ret = NULL;
221   BN_BLINDING **new_blindings;
222   uint8_t *new_blindings_inuse;
223   char overflow = 0;
224 
225   CRYPTO_MUTEX_lock_write(&rsa->lock);
226 
227   unsigned i;
228   for (i = 0; i < rsa->num_blindings; i++) {
229     if (rsa->blindings_inuse[i] == 0) {
230       rsa->blindings_inuse[i] = 1;
231       ret = rsa->blindings[i];
232       *index_used = i;
233       break;
234     }
235   }
236 
237   if (ret != NULL) {
238     CRYPTO_MUTEX_unlock_write(&rsa->lock);
239     return ret;
240   }
241 
242   overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
243 
244   /* We didn't find a free BN_BLINDING to use so increase the length of
245    * the arrays by one and use the newly created element. */
246 
247   CRYPTO_MUTEX_unlock_write(&rsa->lock);
248   ret = BN_BLINDING_new();
249   if (ret == NULL) {
250     return NULL;
251   }
252 
253   if (overflow) {
254     /* We cannot add any more cached BN_BLINDINGs so we use |ret|
255      * and mark it for destruction in |rsa_blinding_release|. */
256     *index_used = MAX_BLINDINGS_PER_RSA;
257     return ret;
258   }
259 
260   CRYPTO_MUTEX_lock_write(&rsa->lock);
261 
262   new_blindings =
263       OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
264   if (new_blindings == NULL) {
265     goto err1;
266   }
267   OPENSSL_memcpy(new_blindings, rsa->blindings,
268          sizeof(BN_BLINDING *) * rsa->num_blindings);
269   new_blindings[rsa->num_blindings] = ret;
270 
271   new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
272   if (new_blindings_inuse == NULL) {
273     goto err2;
274   }
275   OPENSSL_memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
276   new_blindings_inuse[rsa->num_blindings] = 1;
277   *index_used = rsa->num_blindings;
278 
279   OPENSSL_free(rsa->blindings);
280   rsa->blindings = new_blindings;
281   OPENSSL_free(rsa->blindings_inuse);
282   rsa->blindings_inuse = new_blindings_inuse;
283   rsa->num_blindings++;
284 
285   CRYPTO_MUTEX_unlock_write(&rsa->lock);
286   return ret;
287 
288 err2:
289   OPENSSL_free(new_blindings);
290 
291 err1:
292   CRYPTO_MUTEX_unlock_write(&rsa->lock);
293   BN_BLINDING_free(ret);
294   return NULL;
295 }
296 
297 /* rsa_blinding_release marks the cached BN_BLINDING at the given index as free
298  * for other threads to use. */
rsa_blinding_release(RSA * rsa,BN_BLINDING * blinding,unsigned blinding_index)299 static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
300                                  unsigned blinding_index) {
301   if (blinding_index == MAX_BLINDINGS_PER_RSA) {
302     /* This blinding wasn't cached. */
303     BN_BLINDING_free(blinding);
304     return;
305   }
306 
307   CRYPTO_MUTEX_lock_write(&rsa->lock);
308   rsa->blindings_inuse[blinding_index] = 0;
309   CRYPTO_MUTEX_unlock_write(&rsa->lock);
310 }
311 
312 /* 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)313 int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out,
314                          size_t max_out, const uint8_t *in, size_t in_len,
315                          int padding) {
316   const unsigned rsa_size = RSA_size(rsa);
317   uint8_t *buf = NULL;
318   int i, ret = 0;
319 
320   if (max_out < rsa_size) {
321     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
322     return 0;
323   }
324 
325   buf = OPENSSL_malloc(rsa_size);
326   if (buf == NULL) {
327     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
328     goto err;
329   }
330 
331   switch (padding) {
332     case RSA_PKCS1_PADDING:
333       i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
334       break;
335     case RSA_NO_PADDING:
336       i = RSA_padding_add_none(buf, rsa_size, in, in_len);
337       break;
338     default:
339       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
340       goto err;
341   }
342 
343   if (i <= 0) {
344     goto err;
345   }
346 
347   if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
348     goto err;
349   }
350 
351   *out_len = rsa_size;
352   ret = 1;
353 
354 err:
355   if (buf != NULL) {
356     OPENSSL_cleanse(buf, rsa_size);
357     OPENSSL_free(buf);
358   }
359 
360   return ret;
361 }
362 
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)363 int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
364                         const uint8_t *in, size_t in_len, int padding) {
365   const unsigned rsa_size = RSA_size(rsa);
366   int r = -1;
367   uint8_t *buf = NULL;
368   int ret = 0;
369 
370   if (max_out < rsa_size) {
371     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
372     return 0;
373   }
374 
375   if (padding == RSA_NO_PADDING) {
376     buf = out;
377   } else {
378     /* Allocate a temporary buffer to hold the padded plaintext. */
379     buf = OPENSSL_malloc(rsa_size);
380     if (buf == NULL) {
381       OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
382       goto err;
383     }
384   }
385 
386   if (in_len != rsa_size) {
387     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
388     goto err;
389   }
390 
391   if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
392     goto err;
393   }
394 
395   switch (padding) {
396     case RSA_PKCS1_PADDING:
397       r = RSA_padding_check_PKCS1_type_2(out, rsa_size, buf, rsa_size);
398       break;
399     case RSA_PKCS1_OAEP_PADDING:
400       /* Use the default parameters: SHA-1 for both hashes and no label. */
401       r = RSA_padding_check_PKCS1_OAEP_mgf1(out, rsa_size, buf, rsa_size,
402                                             NULL, 0, NULL, NULL);
403       break;
404     case RSA_NO_PADDING:
405       r = rsa_size;
406       break;
407     default:
408       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
409       goto err;
410   }
411 
412   if (r < 0) {
413     OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
414   } else {
415     *out_len = r;
416     ret = 1;
417   }
418 
419 err:
420   if (padding != RSA_NO_PADDING && buf != NULL) {
421     OPENSSL_cleanse(buf, rsa_size);
422     OPENSSL_free(buf);
423   }
424 
425   return ret;
426 }
427 
428 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx);
429 
RSA_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)430 int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
431                    const uint8_t *in, size_t in_len, int padding) {
432   if (rsa->n == NULL || rsa->e == NULL) {
433     OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
434     return 0;
435   }
436 
437   const unsigned rsa_size = RSA_size(rsa);
438   BIGNUM *f, *result;
439   int r = -1;
440 
441   if (max_out < rsa_size) {
442     OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
443     return 0;
444   }
445 
446   if (in_len != rsa_size) {
447     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
448     return 0;
449   }
450 
451   if (!check_modulus_and_exponent_sizes(rsa)) {
452     return 0;
453   }
454 
455   BN_CTX *ctx = BN_CTX_new();
456   if (ctx == NULL) {
457     return 0;
458   }
459 
460   int ret = 0;
461   uint8_t *buf = NULL;
462 
463   BN_CTX_start(ctx);
464   f = BN_CTX_get(ctx);
465   result = BN_CTX_get(ctx);
466   if (f == NULL || result == NULL) {
467     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
468     goto err;
469   }
470 
471   if (padding == RSA_NO_PADDING) {
472     buf = out;
473   } else {
474     /* Allocate a temporary buffer to hold the padded plaintext. */
475     buf = OPENSSL_malloc(rsa_size);
476     if (buf == NULL) {
477       OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
478       goto err;
479     }
480   }
481 
482   if (BN_bin2bn(in, in_len, f) == NULL) {
483     goto err;
484   }
485 
486   if (BN_ucmp(f, rsa->n) >= 0) {
487     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
488     goto err;
489   }
490 
491   if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
492       !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {
493     goto err;
494   }
495 
496   if (!BN_bn2bin_padded(buf, rsa_size, result)) {
497     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
498     goto err;
499   }
500 
501   switch (padding) {
502     case RSA_PKCS1_PADDING:
503       r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);
504       break;
505     case RSA_NO_PADDING:
506       r = rsa_size;
507       break;
508     default:
509       OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
510       goto err;
511   }
512 
513   if (r < 0) {
514     OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
515   } else {
516     *out_len = r;
517     ret = 1;
518   }
519 
520 err:
521   BN_CTX_end(ctx);
522   BN_CTX_free(ctx);
523   if (buf != out) {
524     OPENSSL_free(buf);
525   }
526   return ret;
527 }
528 
rsa_default_private_transform(RSA * rsa,uint8_t * out,const uint8_t * in,size_t len)529 int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
530                                   size_t len) {
531   BIGNUM *f, *result;
532   BN_CTX *ctx = NULL;
533   unsigned blinding_index = 0;
534   BN_BLINDING *blinding = NULL;
535   int ret = 0;
536 
537   ctx = BN_CTX_new();
538   if (ctx == NULL) {
539     goto err;
540   }
541   BN_CTX_start(ctx);
542   f = BN_CTX_get(ctx);
543   result = BN_CTX_get(ctx);
544 
545   if (f == NULL || result == NULL) {
546     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
547     goto err;
548   }
549 
550   if (BN_bin2bn(in, len, f) == NULL) {
551     goto err;
552   }
553 
554   if (BN_ucmp(f, rsa->n) >= 0) {
555     /* Usually the padding functions would catch this. */
556     OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
557     goto err;
558   }
559 
560   if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {
561     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
562     goto err;
563   }
564 
565   /* We cannot do blinding or verification without |e|, and continuing without
566    * those countermeasures is dangerous. However, the Java/Android RSA API
567    * requires support for keys where only |d| and |n| (and not |e|) are known.
568    * The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|. */
569   int disable_security = (rsa->flags & RSA_FLAG_NO_BLINDING) && rsa->e == NULL;
570 
571   if (!disable_security) {
572     /* Keys without public exponents must have blinding explicitly disabled to
573      * be used. */
574     if (rsa->e == NULL) {
575       OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);
576       goto err;
577     }
578 
579     blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
580     if (blinding == NULL) {
581       OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
582       goto err;
583     }
584     if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {
585       goto err;
586     }
587   }
588 
589   if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&
590       rsa->dmq1 != NULL && rsa->iqmp != NULL) {
591     if (!mod_exp(result, f, rsa, ctx)) {
592       goto err;
593     }
594   } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d, rsa->n, ctx,
595                                         rsa->mont_n)) {
596     goto err;
597   }
598 
599   /* Verify the result to protect against fault attacks as described in the
600    * 1997 paper "On the Importance of Checking Cryptographic Protocols for
601    * Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some
602    * implementations do this only when the CRT is used, but we do it in all
603    * cases. Section 6 of the aforementioned paper describes an attack that
604    * works when the CRT isn't used. That attack is much less likely to succeed
605    * than the CRT attack, but there have likely been improvements since 1997.
606    *
607    * This check is cheap assuming |e| is small; it almost always is. */
608   if (!disable_security) {
609     BIGNUM *vrfy = BN_CTX_get(ctx);
610     if (vrfy == NULL ||
611         !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||
612         !BN_equal_consttime(vrfy, f)) {
613       OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
614       goto err;
615     }
616 
617     if (!BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {
618       goto err;
619     }
620   }
621 
622   if (!BN_bn2bin_padded(out, len, result)) {
623     OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
624     goto err;
625   }
626 
627   ret = 1;
628 
629 err:
630   if (ctx != NULL) {
631     BN_CTX_end(ctx);
632     BN_CTX_free(ctx);
633   }
634   if (blinding != NULL) {
635     rsa_blinding_release(rsa, blinding, blinding_index);
636   }
637 
638   return ret;
639 }
640 
mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)641 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
642   assert(ctx != NULL);
643 
644   assert(rsa->n != NULL);
645   assert(rsa->e != NULL);
646   assert(rsa->d != NULL);
647   assert(rsa->p != NULL);
648   assert(rsa->q != NULL);
649   assert(rsa->dmp1 != NULL);
650   assert(rsa->dmq1 != NULL);
651   assert(rsa->iqmp != NULL);
652 
653   BIGNUM *r1, *m1, *vrfy;
654   int ret = 0;
655   size_t i, num_additional_primes = 0;
656 
657   if (rsa->additional_primes != NULL) {
658     num_additional_primes = sk_RSA_additional_prime_num(rsa->additional_primes);
659   }
660 
661   BN_CTX_start(ctx);
662   r1 = BN_CTX_get(ctx);
663   m1 = BN_CTX_get(ctx);
664   vrfy = BN_CTX_get(ctx);
665   if (r1 == NULL ||
666       m1 == NULL ||
667       vrfy == NULL) {
668     goto err;
669   }
670 
671   if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, rsa->p, ctx) ||
672       !BN_MONT_CTX_set_locked(&rsa->mont_q, &rsa->lock, rsa->q, ctx)) {
673     goto err;
674   }
675 
676   if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {
677     goto err;
678   }
679 
680   /* compute I mod q */
681   if (!BN_mod(r1, I, rsa->q, ctx)) {
682     goto err;
683   }
684 
685   /* compute r1^dmq1 mod q */
686   if (!BN_mod_exp_mont_consttime(m1, r1, rsa->dmq1, rsa->q, ctx, rsa->mont_q)) {
687     goto err;
688   }
689 
690   /* compute I mod p */
691   if (!BN_mod(r1, I, rsa->p, ctx)) {
692     goto err;
693   }
694 
695   /* compute r1^dmp1 mod p */
696   if (!BN_mod_exp_mont_consttime(r0, r1, rsa->dmp1, rsa->p, ctx, rsa->mont_p)) {
697     goto err;
698   }
699 
700   if (!BN_sub(r0, r0, m1)) {
701     goto err;
702   }
703   /* This will help stop the size of r0 increasing, which does
704    * affect the multiply if it optimised for a power of 2 size */
705   if (BN_is_negative(r0)) {
706     if (!BN_add(r0, r0, rsa->p)) {
707       goto err;
708     }
709   }
710 
711   if (!BN_mul(r1, r0, rsa->iqmp, ctx)) {
712     goto err;
713   }
714 
715   if (!BN_mod(r0, r1, rsa->p, ctx)) {
716     goto err;
717   }
718 
719   /* If p < q it is occasionally possible for the correction of
720    * adding 'p' if r0 is negative above to leave the result still
721    * negative. This can break the private key operations: the following
722    * second correction should *always* correct this rare occurrence.
723    * This will *never* happen with OpenSSL generated keys because
724    * they ensure p > q [steve] */
725   if (BN_is_negative(r0)) {
726     if (!BN_add(r0, r0, rsa->p)) {
727       goto err;
728     }
729   }
730   if (!BN_mul(r1, r0, rsa->q, ctx)) {
731     goto err;
732   }
733   if (!BN_add(r0, r1, m1)) {
734     goto err;
735   }
736 
737   for (i = 0; i < num_additional_primes; i++) {
738     /* multi-prime RSA. */
739     RSA_additional_prime *ap =
740         sk_RSA_additional_prime_value(rsa->additional_primes, i);
741 
742     /* c will already point to a BIGNUM with the correct flags. */
743     if (!BN_mod(r1, I, ap->prime, ctx)) {
744       goto err;
745     }
746 
747     if (!BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, ap->prime, ctx) ||
748         !BN_mod_exp_mont_consttime(m1, r1, ap->exp, ap->prime, ctx, ap->mont)) {
749       goto err;
750     }
751 
752     if (!BN_sub(m1, m1, r0) ||
753         !BN_mul(m1, m1, ap->coeff, ctx) ||
754         !BN_mod(m1, m1, ap->prime, ctx) ||
755         (BN_is_negative(m1) && !BN_add(m1, m1, ap->prime)) ||
756         !BN_mul(m1, m1, ap->r, ctx) ||
757         !BN_add(r0, r0, m1)) {
758       goto err;
759     }
760   }
761 
762   ret = 1;
763 
764 err:
765   BN_CTX_end(ctx);
766   return ret;
767 }
768 
rsa_default_multi_prime_keygen(RSA * rsa,int bits,int num_primes,BIGNUM * e_value,BN_GENCB * cb)769 int rsa_default_multi_prime_keygen(RSA *rsa, int bits, int num_primes,
770                                    BIGNUM *e_value, BN_GENCB *cb) {
771   BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
772   int prime_bits, ok = -1, n = 0, i, j;
773   BN_CTX *ctx = NULL;
774   STACK_OF(RSA_additional_prime) *additional_primes = NULL;
775 
776   if (num_primes < 2) {
777     ok = 0; /* we set our own err */
778     OPENSSL_PUT_ERROR(RSA, RSA_R_MUST_HAVE_AT_LEAST_TWO_PRIMES);
779     goto err;
780   }
781 
782   ctx = BN_CTX_new();
783   if (ctx == NULL) {
784     goto err;
785   }
786   BN_CTX_start(ctx);
787   r0 = BN_CTX_get(ctx);
788   r1 = BN_CTX_get(ctx);
789   r2 = BN_CTX_get(ctx);
790   r3 = BN_CTX_get(ctx);
791   if (r0 == NULL || r1 == NULL || r2 == NULL || r3 == NULL) {
792     goto err;
793   }
794 
795   if (num_primes > 2) {
796     additional_primes = sk_RSA_additional_prime_new_null();
797     if (additional_primes == NULL) {
798       goto err;
799     }
800   }
801 
802   for (i = 2; i < num_primes; i++) {
803     RSA_additional_prime *ap = OPENSSL_malloc(sizeof(RSA_additional_prime));
804     if (ap == NULL) {
805       goto err;
806     }
807     OPENSSL_memset(ap, 0, sizeof(RSA_additional_prime));
808     ap->prime = BN_new();
809     ap->exp = BN_new();
810     ap->coeff = BN_new();
811     ap->r = BN_new();
812     if (ap->prime == NULL ||
813         ap->exp == NULL ||
814         ap->coeff == NULL ||
815         ap->r == NULL ||
816         !sk_RSA_additional_prime_push(additional_primes, ap)) {
817       RSA_additional_prime_free(ap);
818       goto err;
819     }
820   }
821 
822   /* We need the RSA components non-NULL */
823   if (!rsa->n && ((rsa->n = BN_new()) == NULL)) {
824     goto err;
825   }
826   if (!rsa->d && ((rsa->d = BN_new()) == NULL)) {
827     goto err;
828   }
829   if (!rsa->e && ((rsa->e = BN_new()) == NULL)) {
830     goto err;
831   }
832   if (!rsa->p && ((rsa->p = BN_new()) == NULL)) {
833     goto err;
834   }
835   if (!rsa->q && ((rsa->q = BN_new()) == NULL)) {
836     goto err;
837   }
838   if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL)) {
839     goto err;
840   }
841   if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL)) {
842     goto err;
843   }
844   if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL)) {
845     goto err;
846   }
847 
848   if (!BN_copy(rsa->e, e_value)) {
849     goto err;
850   }
851 
852   /* generate p and q */
853   prime_bits = (bits + (num_primes - 1)) / num_primes;
854   for (;;) {
855     if (!BN_generate_prime_ex(rsa->p, prime_bits, 0, NULL, NULL, cb) ||
856         !BN_sub(r2, rsa->p, BN_value_one()) ||
857         !BN_gcd(r1, r2, rsa->e, ctx)) {
858       goto err;
859     }
860     if (BN_is_one(r1)) {
861       break;
862     }
863     if (!BN_GENCB_call(cb, 2, n++)) {
864       goto err;
865     }
866   }
867   if (!BN_GENCB_call(cb, 3, 0)) {
868     goto err;
869   }
870   prime_bits = ((bits - prime_bits) + (num_primes - 2)) / (num_primes - 1);
871   for (;;) {
872     /* When generating ridiculously small keys, we can get stuck
873      * continually regenerating the same prime values. Check for
874      * this and bail if it happens 3 times. */
875     unsigned int degenerate = 0;
876     do {
877       if (!BN_generate_prime_ex(rsa->q, prime_bits, 0, NULL, NULL, cb)) {
878         goto err;
879       }
880     } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
881     if (degenerate == 3) {
882       ok = 0; /* we set our own err */
883       OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
884       goto err;
885     }
886     if (!BN_sub(r2, rsa->q, BN_value_one()) ||
887         !BN_gcd(r1, r2, rsa->e, ctx)) {
888       goto err;
889     }
890     if (BN_is_one(r1)) {
891       break;
892     }
893     if (!BN_GENCB_call(cb, 2, n++)) {
894       goto err;
895     }
896   }
897 
898   if (!BN_GENCB_call(cb, 3, 1) ||
899       !BN_mul(rsa->n, rsa->p, rsa->q, ctx)) {
900     goto err;
901   }
902 
903   for (i = 2; i < num_primes; i++) {
904     RSA_additional_prime *ap =
905         sk_RSA_additional_prime_value(additional_primes, i - 2);
906     prime_bits = ((bits - BN_num_bits(rsa->n)) + (num_primes - (i + 1))) /
907                  (num_primes - i);
908 
909     for (;;) {
910       if (!BN_generate_prime_ex(ap->prime, prime_bits, 0, NULL, NULL, cb)) {
911         goto err;
912       }
913       if (BN_cmp(rsa->p, ap->prime) == 0 ||
914           BN_cmp(rsa->q, ap->prime) == 0) {
915         continue;
916       }
917 
918       for (j = 0; j < i - 2; j++) {
919         if (BN_cmp(sk_RSA_additional_prime_value(additional_primes, j)->prime,
920                    ap->prime) == 0) {
921           break;
922         }
923       }
924       if (j != i - 2) {
925         continue;
926       }
927 
928       if (!BN_sub(r2, ap->prime, BN_value_one()) ||
929           !BN_gcd(r1, r2, rsa->e, ctx)) {
930         goto err;
931       }
932 
933       if (!BN_is_one(r1)) {
934         continue;
935       }
936       if (i != num_primes - 1) {
937         break;
938       }
939 
940       /* For the last prime we'll check that it makes n large enough. In the
941        * two prime case this isn't a problem because we generate primes with
942        * the top two bits set and so the product is always of the expected
943        * size. In the multi prime case, this doesn't follow. */
944       if (!BN_mul(r1, rsa->n, ap->prime, ctx)) {
945         goto err;
946       }
947       if (BN_num_bits(r1) == (unsigned) bits) {
948         break;
949       }
950 
951       if (!BN_GENCB_call(cb, 2, n++)) {
952         goto err;
953       }
954     }
955 
956     /* ap->r is is the product of all the primes prior to the current one
957      * (including p and q). */
958     if (!BN_copy(ap->r, rsa->n)) {
959       goto err;
960     }
961     if (i == num_primes - 1) {
962       /* In the case of the last prime, we calculated n as |r1| in the loop
963        * above. */
964       if (!BN_copy(rsa->n, r1)) {
965         goto err;
966       }
967     } else if (!BN_mul(rsa->n, rsa->n, ap->prime, ctx)) {
968       goto err;
969     }
970 
971     if (!BN_GENCB_call(cb, 3, 1)) {
972       goto err;
973     }
974   }
975 
976   if (BN_cmp(rsa->p, rsa->q) < 0) {
977     tmp = rsa->p;
978     rsa->p = rsa->q;
979     rsa->q = tmp;
980   }
981 
982   /* calculate d */
983   if (!BN_sub(r1, rsa->p, BN_value_one())) {
984     goto err; /* p-1 */
985   }
986   if (!BN_sub(r2, rsa->q, BN_value_one())) {
987     goto err; /* q-1 */
988   }
989   if (!BN_mul(r0, r1, r2, ctx)) {
990     goto err; /* (p-1)(q-1) */
991   }
992   for (i = 2; i < num_primes; i++) {
993     RSA_additional_prime *ap =
994         sk_RSA_additional_prime_value(additional_primes, i - 2);
995     if (!BN_sub(r3, ap->prime, BN_value_one()) ||
996         !BN_mul(r0, r0, r3, ctx)) {
997       goto err;
998     }
999   }
1000   if (!BN_mod_inverse(rsa->d, rsa->e, r0, ctx)) {
1001     goto err; /* d */
1002   }
1003 
1004   /* calculate d mod (p-1) */
1005   if (!BN_mod(rsa->dmp1, rsa->d, r1, ctx)) {
1006     goto err;
1007   }
1008 
1009   /* calculate d mod (q-1) */
1010   if (!BN_mod(rsa->dmq1, rsa->d, r2, ctx)) {
1011     goto err;
1012   }
1013 
1014   /* Calculate inverse of q mod p. Note that although RSA key generation is far
1015    * from constant-time, |bn_mod_inverse_secret_prime| uses the same modular
1016    * exponentation logic as in RSA private key operations and, if the RSAZ-1024
1017    * code is enabled, will be optimized for common RSA prime sizes. */
1018   if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, rsa->p, ctx) ||
1019       !bn_mod_inverse_secret_prime(rsa->iqmp, rsa->q, rsa->p, ctx,
1020                                    rsa->mont_p)) {
1021     goto err;
1022   }
1023 
1024   for (i = 2; i < num_primes; i++) {
1025     RSA_additional_prime *ap =
1026         sk_RSA_additional_prime_value(additional_primes, i - 2);
1027     if (!BN_sub(ap->exp, ap->prime, BN_value_one()) ||
1028         !BN_mod(ap->exp, rsa->d, ap->exp, ctx) ||
1029         !BN_MONT_CTX_set_locked(&ap->mont, &rsa->lock, ap->prime, ctx) ||
1030         !bn_mod_inverse_secret_prime(ap->coeff, ap->r, ap->prime, ctx,
1031                                      ap->mont)) {
1032       goto err;
1033     }
1034   }
1035 
1036   rsa->additional_primes = additional_primes;
1037   additional_primes = NULL;
1038 
1039   /* The key generation process is complex and thus error-prone. It could be
1040    * disastrous to generate and then use a bad key so double-check that the key
1041    * makes sense. */
1042   ok = RSA_check_key(rsa);
1043   if (!ok) {
1044     OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR);
1045   }
1046 
1047 err:
1048   if (ok == -1) {
1049     OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
1050     ok = 0;
1051   }
1052   if (ctx != NULL) {
1053     BN_CTX_end(ctx);
1054     BN_CTX_free(ctx);
1055   }
1056   sk_RSA_additional_prime_pop_free(additional_primes,
1057                                    RSA_additional_prime_free);
1058   return ok;
1059 }
1060 
rsa_default_keygen(RSA * rsa,int bits,BIGNUM * e_value,BN_GENCB * cb)1061 int rsa_default_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
1062   return rsa_default_multi_prime_keygen(rsa, bits, 2 /* num primes */, e_value,
1063                                         cb);
1064 }
1065 
1066 /* All of the methods are NULL to make it easier for the compiler/linker to drop
1067  * unused functions. The wrapper functions will select the appropriate
1068  * |rsa_default_*| implementation. */
1069 const RSA_METHOD RSA_default_method = {
1070   {
1071     0 /* references */,
1072     1 /* is_static */,
1073   },
1074   NULL /* app_data */,
1075 
1076   NULL /* init */,
1077   NULL /* finish (defaults to rsa_default_finish) */,
1078 
1079   NULL /* size (defaults to rsa_default_size) */,
1080 
1081   NULL /* sign */,
1082   NULL /* verify */,
1083 
1084   NULL /* encrypt (defaults to rsa_default_encrypt) */,
1085   NULL /* sign_raw (defaults to rsa_default_sign_raw) */,
1086   NULL /* decrypt (defaults to rsa_default_decrypt) */,
1087   NULL /* verify_raw (defaults to rsa_default_verify_raw) */,
1088 
1089   NULL /* private_transform (defaults to rsa_default_private_transform) */,
1090 
1091   NULL /* mod_exp (ignored) */,
1092   NULL /* bn_mod_exp (ignored) */,
1093 
1094   RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
1095 
1096   NULL /* keygen (defaults to rsa_default_keygen) */,
1097   NULL /* multi_prime_keygen (defaults to rsa_default_multi_prime_keygen) */,
1098 
1099   NULL /* supports_digest */,
1100 };
1101