1 /*
2 * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the OpenSSL license (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include "internal/cryptlib.h"
11 #include "crypto/bn.h"
12 #include "rsa_local.h"
13 #include "internal/constant_time.h"
14
15 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
16 unsigned char *to, RSA *rsa, int padding);
17 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
18 unsigned char *to, RSA *rsa, int padding);
19 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
20 unsigned char *to, RSA *rsa, int padding);
21 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
22 unsigned char *to, RSA *rsa, int padding);
23 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
24 BN_CTX *ctx);
25 static int rsa_ossl_init(RSA *rsa);
26 static int rsa_ossl_finish(RSA *rsa);
27 static RSA_METHOD rsa_pkcs1_ossl_meth = {
28 "OpenSSL PKCS#1 RSA",
29 rsa_ossl_public_encrypt,
30 rsa_ossl_public_decrypt, /* signature verification */
31 rsa_ossl_private_encrypt, /* signing */
32 rsa_ossl_private_decrypt,
33 rsa_ossl_mod_exp,
34 BN_mod_exp_mont, /* XXX probably we should not use Montgomery
35 * if e == 3 */
36 rsa_ossl_init,
37 rsa_ossl_finish,
38 RSA_FLAG_FIPS_METHOD, /* flags */
39 NULL,
40 0, /* rsa_sign */
41 0, /* rsa_verify */
42 NULL, /* rsa_keygen */
43 NULL /* rsa_multi_prime_keygen */
44 };
45
46 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth;
47
RSA_set_default_method(const RSA_METHOD * meth)48 void RSA_set_default_method(const RSA_METHOD *meth)
49 {
50 default_RSA_meth = meth;
51 }
52
RSA_get_default_method(void)53 const RSA_METHOD *RSA_get_default_method(void)
54 {
55 return default_RSA_meth;
56 }
57
RSA_PKCS1_OpenSSL(void)58 const RSA_METHOD *RSA_PKCS1_OpenSSL(void)
59 {
60 return &rsa_pkcs1_ossl_meth;
61 }
62
RSA_null_method(void)63 const RSA_METHOD *RSA_null_method(void)
64 {
65 return NULL;
66 }
67
rsa_ossl_public_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)68 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
69 unsigned char *to, RSA *rsa, int padding)
70 {
71 BIGNUM *f, *ret;
72 int i, num = 0, r = -1;
73 unsigned char *buf = NULL;
74 BN_CTX *ctx = NULL;
75
76 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
77 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_MODULUS_TOO_LARGE);
78 return -1;
79 }
80
81 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
82 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
83 return -1;
84 }
85
86 /* for large moduli, enforce exponent limit */
87 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
88 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
89 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
90 return -1;
91 }
92 }
93
94 if ((ctx = BN_CTX_new()) == NULL)
95 goto err;
96 BN_CTX_start(ctx);
97 f = BN_CTX_get(ctx);
98 ret = BN_CTX_get(ctx);
99 num = BN_num_bytes(rsa->n);
100 buf = OPENSSL_malloc(num);
101 if (ret == NULL || buf == NULL) {
102 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE);
103 goto err;
104 }
105
106 switch (padding) {
107 case RSA_PKCS1_PADDING:
108 i = RSA_padding_add_PKCS1_type_2(buf, num, from, flen);
109 break;
110 case RSA_PKCS1_OAEP_PADDING:
111 i = RSA_padding_add_PKCS1_OAEP(buf, num, from, flen, NULL, 0);
112 break;
113 case RSA_SSLV23_PADDING:
114 i = RSA_padding_add_SSLv23(buf, num, from, flen);
115 break;
116 case RSA_NO_PADDING:
117 i = RSA_padding_add_none(buf, num, from, flen);
118 break;
119 default:
120 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
121 goto err;
122 }
123 if (i <= 0)
124 goto err;
125
126 if (BN_bin2bn(buf, num, f) == NULL)
127 goto err;
128
129 if (BN_ucmp(f, rsa->n) >= 0) {
130 /* usually the padding functions would catch this */
131 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT,
132 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
133 goto err;
134 }
135
136 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
137 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
138 rsa->n, ctx))
139 goto err;
140
141 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
142 rsa->_method_mod_n))
143 goto err;
144
145 /*
146 * BN_bn2binpad puts in leading 0 bytes if the number is less than
147 * the length of the modulus.
148 */
149 r = BN_bn2binpad(ret, to, num);
150 err:
151 BN_CTX_end(ctx);
152 BN_CTX_free(ctx);
153 OPENSSL_clear_free(buf, num);
154 return r;
155 }
156
rsa_get_blinding(RSA * rsa,int * local,BN_CTX * ctx)157 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
158 {
159 BN_BLINDING *ret;
160
161 CRYPTO_THREAD_write_lock(rsa->lock);
162
163 if (rsa->blinding == NULL) {
164 rsa->blinding = RSA_setup_blinding(rsa, ctx);
165 }
166
167 ret = rsa->blinding;
168 if (ret == NULL)
169 goto err;
170
171 if (BN_BLINDING_is_current_thread(ret)) {
172 /* rsa->blinding is ours! */
173
174 *local = 1;
175 } else {
176 /* resort to rsa->mt_blinding instead */
177
178 /*
179 * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
180 * BN_BLINDING is shared, meaning that accesses require locks, and
181 * that the blinding factor must be stored outside the BN_BLINDING
182 */
183 *local = 0;
184
185 if (rsa->mt_blinding == NULL) {
186 rsa->mt_blinding = RSA_setup_blinding(rsa, ctx);
187 }
188 ret = rsa->mt_blinding;
189 }
190
191 err:
192 CRYPTO_THREAD_unlock(rsa->lock);
193 return ret;
194 }
195
rsa_blinding_convert(BN_BLINDING * b,BIGNUM * f,BIGNUM * unblind,BN_CTX * ctx)196 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
197 BN_CTX *ctx)
198 {
199 if (unblind == NULL) {
200 /*
201 * Local blinding: store the unblinding factor in BN_BLINDING.
202 */
203 return BN_BLINDING_convert_ex(f, NULL, b, ctx);
204 } else {
205 /*
206 * Shared blinding: store the unblinding factor outside BN_BLINDING.
207 */
208 int ret;
209
210 BN_BLINDING_lock(b);
211 ret = BN_BLINDING_convert_ex(f, unblind, b, ctx);
212 BN_BLINDING_unlock(b);
213
214 return ret;
215 }
216 }
217
rsa_blinding_invert(BN_BLINDING * b,BIGNUM * f,BIGNUM * unblind,BN_CTX * ctx)218 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
219 BN_CTX *ctx)
220 {
221 /*
222 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
223 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
224 * is shared between threads, unblind must be non-null:
225 * BN_BLINDING_invert_ex will then use the local unblinding factor, and
226 * will only read the modulus from BN_BLINDING. In both cases it's safe
227 * to access the blinding without a lock.
228 */
229 return BN_BLINDING_invert_ex(f, unblind, b, ctx);
230 }
231
232 /* signing */
rsa_ossl_private_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)233 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
234 unsigned char *to, RSA *rsa, int padding)
235 {
236 BIGNUM *f, *ret, *res;
237 int i, num = 0, r = -1;
238 unsigned char *buf = NULL;
239 BN_CTX *ctx = NULL;
240 int local_blinding = 0;
241 /*
242 * Used only if the blinding structure is shared. A non-NULL unblind
243 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
244 * the unblinding factor outside the blinding structure.
245 */
246 BIGNUM *unblind = NULL;
247 BN_BLINDING *blinding = NULL;
248
249 if ((ctx = BN_CTX_new()) == NULL)
250 goto err;
251 BN_CTX_start(ctx);
252 f = BN_CTX_get(ctx);
253 ret = BN_CTX_get(ctx);
254 num = BN_num_bytes(rsa->n);
255 buf = OPENSSL_malloc(num);
256 if (ret == NULL || buf == NULL) {
257 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
258 goto err;
259 }
260
261 switch (padding) {
262 case RSA_PKCS1_PADDING:
263 i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
264 break;
265 case RSA_X931_PADDING:
266 i = RSA_padding_add_X931(buf, num, from, flen);
267 break;
268 case RSA_NO_PADDING:
269 i = RSA_padding_add_none(buf, num, from, flen);
270 break;
271 case RSA_SSLV23_PADDING:
272 default:
273 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
274 goto err;
275 }
276 if (i <= 0)
277 goto err;
278
279 if (BN_bin2bn(buf, num, f) == NULL)
280 goto err;
281
282 if (BN_ucmp(f, rsa->n) >= 0) {
283 /* usually the padding functions would catch this */
284 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT,
285 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
286 goto err;
287 }
288
289 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
290 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
291 rsa->n, ctx))
292 goto err;
293
294 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
295 blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
296 if (blinding == NULL) {
297 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_INTERNAL_ERROR);
298 goto err;
299 }
300 }
301
302 if (blinding != NULL) {
303 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
304 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
305 goto err;
306 }
307 if (!rsa_blinding_convert(blinding, f, unblind, ctx))
308 goto err;
309 }
310
311 if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
312 (rsa->version == RSA_ASN1_VERSION_MULTI) ||
313 ((rsa->p != NULL) &&
314 (rsa->q != NULL) &&
315 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
316 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
317 goto err;
318 } else {
319 BIGNUM *d = BN_new();
320 if (d == NULL) {
321 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
322 goto err;
323 }
324 if (rsa->d == NULL) {
325 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_MISSING_PRIVATE_KEY);
326 BN_free(d);
327 goto err;
328 }
329 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
330
331 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
332 rsa->_method_mod_n)) {
333 BN_free(d);
334 goto err;
335 }
336 /* We MUST free d before any further use of rsa->d */
337 BN_free(d);
338 }
339
340 if (blinding)
341 if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
342 goto err;
343
344 if (padding == RSA_X931_PADDING) {
345 if (!BN_sub(f, rsa->n, ret))
346 goto err;
347 if (BN_cmp(ret, f) > 0)
348 res = f;
349 else
350 res = ret;
351 } else {
352 res = ret;
353 }
354
355 /*
356 * BN_bn2binpad puts in leading 0 bytes if the number is less than
357 * the length of the modulus.
358 */
359 r = BN_bn2binpad(res, to, num);
360 err:
361 BN_CTX_end(ctx);
362 BN_CTX_free(ctx);
363 OPENSSL_clear_free(buf, num);
364 return r;
365 }
366
rsa_ossl_private_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)367 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
368 unsigned char *to, RSA *rsa, int padding)
369 {
370 BIGNUM *f, *ret;
371 int j, num = 0, r = -1;
372 unsigned char *buf = NULL;
373 BN_CTX *ctx = NULL;
374 int local_blinding = 0;
375 /*
376 * Used only if the blinding structure is shared. A non-NULL unblind
377 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
378 * the unblinding factor outside the blinding structure.
379 */
380 BIGNUM *unblind = NULL;
381 BN_BLINDING *blinding = NULL;
382
383 if ((ctx = BN_CTX_new()) == NULL)
384 goto err;
385 BN_CTX_start(ctx);
386 f = BN_CTX_get(ctx);
387 ret = BN_CTX_get(ctx);
388 num = BN_num_bytes(rsa->n);
389 buf = OPENSSL_malloc(num);
390 if (ret == NULL || buf == NULL) {
391 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
392 goto err;
393 }
394
395 /*
396 * This check was for equality but PGP does evil things and chops off the
397 * top '0' bytes
398 */
399 if (flen > num) {
400 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT,
401 RSA_R_DATA_GREATER_THAN_MOD_LEN);
402 goto err;
403 }
404
405 /* make data into a big number */
406 if (BN_bin2bn(from, (int)flen, f) == NULL)
407 goto err;
408
409 if (BN_ucmp(f, rsa->n) >= 0) {
410 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT,
411 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
412 goto err;
413 }
414
415 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
416 blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
417 if (blinding == NULL) {
418 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR);
419 goto err;
420 }
421 }
422
423 if (blinding != NULL) {
424 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
425 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
426 goto err;
427 }
428 if (!rsa_blinding_convert(blinding, f, unblind, ctx))
429 goto err;
430 }
431
432 /* do the decrypt */
433 if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
434 (rsa->version == RSA_ASN1_VERSION_MULTI) ||
435 ((rsa->p != NULL) &&
436 (rsa->q != NULL) &&
437 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
438 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
439 goto err;
440 } else {
441 BIGNUM *d = BN_new();
442 if (d == NULL) {
443 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
444 goto err;
445 }
446 if (rsa->d == NULL) {
447 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_MISSING_PRIVATE_KEY);
448 BN_free(d);
449 goto err;
450 }
451 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
452
453 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
454 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
455 rsa->n, ctx)) {
456 BN_free(d);
457 goto err;
458 }
459 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
460 rsa->_method_mod_n)) {
461 BN_free(d);
462 goto err;
463 }
464 /* We MUST free d before any further use of rsa->d */
465 BN_free(d);
466 }
467
468 if (blinding) {
469 /*
470 * ossl_bn_rsa_do_unblind() combines blinding inversion and
471 * 0-padded BN BE serialization
472 */
473 j = ossl_bn_rsa_do_unblind(ret, blinding, unblind, rsa->n, ctx,
474 buf, num);
475 if (j == 0)
476 goto err;
477 } else {
478 j = BN_bn2binpad(ret, buf, num);
479 if (j < 0)
480 goto err;
481 }
482
483 switch (padding) {
484 case RSA_PKCS1_PADDING:
485 r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num);
486 break;
487 case RSA_PKCS1_OAEP_PADDING:
488 r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0);
489 break;
490 case RSA_SSLV23_PADDING:
491 r = RSA_padding_check_SSLv23(to, num, buf, j, num);
492 break;
493 case RSA_NO_PADDING:
494 memcpy(to, buf, (r = j));
495 break;
496 default:
497 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
498 goto err;
499 }
500 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
501 err_clear_last_constant_time(1 & ~constant_time_msb(r));
502
503 err:
504 BN_CTX_end(ctx);
505 BN_CTX_free(ctx);
506 OPENSSL_clear_free(buf, num);
507 return r;
508 }
509
510 /* signature verification */
rsa_ossl_public_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)511 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
512 unsigned char *to, RSA *rsa, int padding)
513 {
514 BIGNUM *f, *ret;
515 int i, num = 0, r = -1;
516 unsigned char *buf = NULL;
517 BN_CTX *ctx = NULL;
518
519 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
520 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE);
521 return -1;
522 }
523
524 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
525 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
526 return -1;
527 }
528
529 /* for large moduli, enforce exponent limit */
530 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
531 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
532 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
533 return -1;
534 }
535 }
536
537 if ((ctx = BN_CTX_new()) == NULL)
538 goto err;
539 BN_CTX_start(ctx);
540 f = BN_CTX_get(ctx);
541 ret = BN_CTX_get(ctx);
542 num = BN_num_bytes(rsa->n);
543 buf = OPENSSL_malloc(num);
544 if (ret == NULL || buf == NULL) {
545 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE);
546 goto err;
547 }
548
549 /*
550 * This check was for equality but PGP does evil things and chops off the
551 * top '0' bytes
552 */
553 if (flen > num) {
554 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN);
555 goto err;
556 }
557
558 if (BN_bin2bn(from, flen, f) == NULL)
559 goto err;
560
561 if (BN_ucmp(f, rsa->n) >= 0) {
562 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT,
563 RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
564 goto err;
565 }
566
567 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
568 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
569 rsa->n, ctx))
570 goto err;
571
572 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
573 rsa->_method_mod_n))
574 goto err;
575
576 if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12))
577 if (!BN_sub(ret, rsa->n, ret))
578 goto err;
579
580 i = BN_bn2binpad(ret, buf, num);
581
582 switch (padding) {
583 case RSA_PKCS1_PADDING:
584 r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
585 break;
586 case RSA_X931_PADDING:
587 r = RSA_padding_check_X931(to, num, buf, i, num);
588 break;
589 case RSA_NO_PADDING:
590 memcpy(to, buf, (r = i));
591 break;
592 default:
593 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
594 goto err;
595 }
596 if (r < 0)
597 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
598
599 err:
600 BN_CTX_end(ctx);
601 BN_CTX_free(ctx);
602 OPENSSL_clear_free(buf, num);
603 return r;
604 }
605
rsa_ossl_mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)606 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
607 {
608 BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2];
609 int ret = 0, i, ex_primes = 0, smooth = 0;
610 RSA_PRIME_INFO *pinfo;
611
612 BN_CTX_start(ctx);
613
614 r1 = BN_CTX_get(ctx);
615 r2 = BN_CTX_get(ctx);
616 m1 = BN_CTX_get(ctx);
617 vrfy = BN_CTX_get(ctx);
618 if (vrfy == NULL)
619 goto err;
620
621 if (rsa->version == RSA_ASN1_VERSION_MULTI
622 && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0
623 || ex_primes > RSA_MAX_PRIME_NUM - 2))
624 goto err;
625
626 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
627 BIGNUM *factor = BN_new();
628
629 if (factor == NULL)
630 goto err;
631
632 /*
633 * Make sure BN_mod_inverse in Montgomery initialization uses the
634 * BN_FLG_CONSTTIME flag
635 */
636 if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME),
637 BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock,
638 factor, ctx))
639 || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME),
640 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock,
641 factor, ctx))) {
642 BN_free(factor);
643 goto err;
644 }
645 for (i = 0; i < ex_primes; i++) {
646 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
647 BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME);
648 if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) {
649 BN_free(factor);
650 goto err;
651 }
652 }
653 /*
654 * We MUST free |factor| before any further use of the prime factors
655 */
656 BN_free(factor);
657
658 smooth = (ex_primes == 0)
659 && (rsa->meth->bn_mod_exp == BN_mod_exp_mont)
660 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p));
661 }
662
663 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
664 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
665 rsa->n, ctx))
666 goto err;
667
668 if (smooth) {
669 /*
670 * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
671 * accepts values in [0-m*2^w) range. w is m's bit width rounded up
672 * to limb width. So that at the very least if |I| is fully reduced,
673 * i.e. less than p*q, we can count on from-to round to perform
674 * below modulo operations on |I|. Unlike BN_mod it's constant time.
675 */
676 if (/* m1 = I moq q */
677 !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)
678 || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)
679 /* m1 = m1^dmq1 mod q */
680 || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx,
681 rsa->_method_mod_q)
682 /* r1 = I mod p */
683 || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)
684 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
685 /* r1 = r1^dmp1 mod p */
686 || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx,
687 rsa->_method_mod_p)
688 /* r1 = (r1 - m1) mod p */
689 /*
690 * bn_mod_sub_fixed_top is not regular modular subtraction,
691 * it can tolerate subtrahend to be larger than modulus, but
692 * not bit-wise wider. This makes up for uncommon q>p case,
693 * when |m1| can be larger than |rsa->p|.
694 */
695 || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)
696
697 /* r1 = r1 * iqmp mod p */
698 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
699 || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,
700 ctx)
701 /* r0 = r1 * q + m1 */
702 || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)
703 || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))
704 goto err;
705
706 goto tail;
707 }
708
709 /* compute I mod q */
710 {
711 BIGNUM *c = BN_new();
712 if (c == NULL)
713 goto err;
714 BN_with_flags(c, I, BN_FLG_CONSTTIME);
715
716 if (!BN_mod(r1, c, rsa->q, ctx)) {
717 BN_free(c);
718 goto err;
719 }
720
721 {
722 BIGNUM *dmq1 = BN_new();
723 if (dmq1 == NULL) {
724 BN_free(c);
725 goto err;
726 }
727 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
728
729 /* compute r1^dmq1 mod q */
730 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
731 rsa->_method_mod_q)) {
732 BN_free(c);
733 BN_free(dmq1);
734 goto err;
735 }
736 /* We MUST free dmq1 before any further use of rsa->dmq1 */
737 BN_free(dmq1);
738 }
739
740 /* compute I mod p */
741 if (!BN_mod(r1, c, rsa->p, ctx)) {
742 BN_free(c);
743 goto err;
744 }
745 /* We MUST free c before any further use of I */
746 BN_free(c);
747 }
748
749 {
750 BIGNUM *dmp1 = BN_new();
751 if (dmp1 == NULL)
752 goto err;
753 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
754
755 /* compute r1^dmp1 mod p */
756 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
757 rsa->_method_mod_p)) {
758 BN_free(dmp1);
759 goto err;
760 }
761 /* We MUST free dmp1 before any further use of rsa->dmp1 */
762 BN_free(dmp1);
763 }
764
765 /*
766 * calculate m_i in multi-prime case
767 *
768 * TODO:
769 * 1. squash the following two loops and calculate |m_i| there.
770 * 2. remove cc and reuse |c|.
771 * 3. remove |dmq1| and |dmp1| in previous block and use |di|.
772 *
773 * If these things are done, the code will be more readable.
774 */
775 if (ex_primes > 0) {
776 BIGNUM *di = BN_new(), *cc = BN_new();
777
778 if (cc == NULL || di == NULL) {
779 BN_free(cc);
780 BN_free(di);
781 goto err;
782 }
783
784 for (i = 0; i < ex_primes; i++) {
785 /* prepare m_i */
786 if ((m[i] = BN_CTX_get(ctx)) == NULL) {
787 BN_free(cc);
788 BN_free(di);
789 goto err;
790 }
791
792 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
793
794 /* prepare c and d_i */
795 BN_with_flags(cc, I, BN_FLG_CONSTTIME);
796 BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
797
798 if (!BN_mod(r1, cc, pinfo->r, ctx)) {
799 BN_free(cc);
800 BN_free(di);
801 goto err;
802 }
803 /* compute r1 ^ d_i mod r_i */
804 if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
805 BN_free(cc);
806 BN_free(di);
807 goto err;
808 }
809 }
810
811 BN_free(cc);
812 BN_free(di);
813 }
814
815 if (!BN_sub(r0, r0, m1))
816 goto err;
817 /*
818 * This will help stop the size of r0 increasing, which does affect the
819 * multiply if it optimised for a power of 2 size
820 */
821 if (BN_is_negative(r0))
822 if (!BN_add(r0, r0, rsa->p))
823 goto err;
824
825 if (!BN_mul(r1, r0, rsa->iqmp, ctx))
826 goto err;
827
828 {
829 BIGNUM *pr1 = BN_new();
830 if (pr1 == NULL)
831 goto err;
832 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
833
834 if (!BN_mod(r0, pr1, rsa->p, ctx)) {
835 BN_free(pr1);
836 goto err;
837 }
838 /* We MUST free pr1 before any further use of r1 */
839 BN_free(pr1);
840 }
841
842 /*
843 * If p < q it is occasionally possible for the correction of adding 'p'
844 * if r0 is negative above to leave the result still negative. This can
845 * break the private key operations: the following second correction
846 * should *always* correct this rare occurrence. This will *never* happen
847 * with OpenSSL generated keys because they ensure p > q [steve]
848 */
849 if (BN_is_negative(r0))
850 if (!BN_add(r0, r0, rsa->p))
851 goto err;
852 if (!BN_mul(r1, r0, rsa->q, ctx))
853 goto err;
854 if (!BN_add(r0, r1, m1))
855 goto err;
856
857 /* add m_i to m in multi-prime case */
858 if (ex_primes > 0) {
859 BIGNUM *pr2 = BN_new();
860
861 if (pr2 == NULL)
862 goto err;
863
864 for (i = 0; i < ex_primes; i++) {
865 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
866 if (!BN_sub(r1, m[i], r0)) {
867 BN_free(pr2);
868 goto err;
869 }
870
871 if (!BN_mul(r2, r1, pinfo->t, ctx)) {
872 BN_free(pr2);
873 goto err;
874 }
875
876 BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
877
878 if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
879 BN_free(pr2);
880 goto err;
881 }
882
883 if (BN_is_negative(r1))
884 if (!BN_add(r1, r1, pinfo->r)) {
885 BN_free(pr2);
886 goto err;
887 }
888 if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
889 BN_free(pr2);
890 goto err;
891 }
892 if (!BN_add(r0, r0, r1)) {
893 BN_free(pr2);
894 goto err;
895 }
896 }
897 BN_free(pr2);
898 }
899
900 tail:
901 if (rsa->e && rsa->n) {
902 if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
903 if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
904 rsa->_method_mod_n))
905 goto err;
906 } else {
907 bn_correct_top(r0);
908 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
909 rsa->_method_mod_n))
910 goto err;
911 }
912 /*
913 * If 'I' was greater than (or equal to) rsa->n, the operation will
914 * be equivalent to using 'I mod n'. However, the result of the
915 * verify will *always* be less than 'n' so we don't check for
916 * absolute equality, just congruency.
917 */
918 if (!BN_sub(vrfy, vrfy, I))
919 goto err;
920 if (BN_is_zero(vrfy)) {
921 bn_correct_top(r0);
922 ret = 1;
923 goto err; /* not actually error */
924 }
925 if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
926 goto err;
927 if (BN_is_negative(vrfy))
928 if (!BN_add(vrfy, vrfy, rsa->n))
929 goto err;
930 if (!BN_is_zero(vrfy)) {
931 /*
932 * 'I' and 'vrfy' aren't congruent mod n. Don't leak
933 * miscalculated CRT output, just do a raw (slower) mod_exp and
934 * return that instead.
935 */
936
937 BIGNUM *d = BN_new();
938 if (d == NULL)
939 goto err;
940 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
941
942 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
943 rsa->_method_mod_n)) {
944 BN_free(d);
945 goto err;
946 }
947 /* We MUST free d before any further use of rsa->d */
948 BN_free(d);
949 }
950 }
951 /*
952 * It's unfortunate that we have to bn_correct_top(r0). What hopefully
953 * saves the day is that correction is highly unlike, and private key
954 * operations are customarily performed on blinded message. Which means
955 * that attacker won't observe correlation with chosen plaintext.
956 * Secondly, remaining code would still handle it in same computational
957 * time and even conceal memory access pattern around corrected top.
958 */
959 bn_correct_top(r0);
960 ret = 1;
961 err:
962 BN_CTX_end(ctx);
963 return ret;
964 }
965
rsa_ossl_init(RSA * rsa)966 static int rsa_ossl_init(RSA *rsa)
967 {
968 rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
969 return 1;
970 }
971
rsa_ossl_finish(RSA * rsa)972 static int rsa_ossl_finish(RSA *rsa)
973 {
974 int i;
975 RSA_PRIME_INFO *pinfo;
976
977 BN_MONT_CTX_free(rsa->_method_mod_n);
978 BN_MONT_CTX_free(rsa->_method_mod_p);
979 BN_MONT_CTX_free(rsa->_method_mod_q);
980 for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
981 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
982 BN_MONT_CTX_free(pinfo->m);
983 }
984 return 1;
985 }
986