1 | /* |
2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License 2.0 (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 | |
48 | void RSA_set_default_method(const RSA_METHOD *meth) |
49 | { |
50 | default_RSA_meth = meth; |
51 | } |
52 | |
53 | const RSA_METHOD *RSA_get_default_method(void) |
54 | { |
55 | return default_RSA_meth; |
56 | } |
57 | |
58 | const RSA_METHOD *RSA_PKCS1_OpenSSL(void) |
59 | { |
60 | return &rsa_pkcs1_ossl_meth; |
61 | } |
62 | |
63 | const RSA_METHOD *RSA_null_method(void) |
64 | { |
65 | return NULL; |
66 | } |
67 | |
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 | |
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 | |
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 | |
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 */ |
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 | |
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 | if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) |
470 | goto err; |
471 | |
472 | j = BN_bn2binpad(ret, buf, num); |
473 | if (j < 0) |
474 | goto err; |
475 | |
476 | switch (padding) { |
477 | case RSA_PKCS1_PADDING: |
478 | r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num); |
479 | break; |
480 | case RSA_PKCS1_OAEP_PADDING: |
481 | r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0); |
482 | break; |
483 | case RSA_SSLV23_PADDING: |
484 | r = RSA_padding_check_SSLv23(to, num, buf, j, num); |
485 | break; |
486 | case RSA_NO_PADDING: |
487 | memcpy(to, buf, (r = j)); |
488 | break; |
489 | default: |
490 | RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); |
491 | goto err; |
492 | } |
493 | RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED); |
494 | err_clear_last_constant_time(1 & ~constant_time_msb(r)); |
495 | |
496 | err: |
497 | BN_CTX_end(ctx); |
498 | BN_CTX_free(ctx); |
499 | OPENSSL_clear_free(buf, num); |
500 | return r; |
501 | } |
502 | |
503 | /* signature verification */ |
504 | static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, |
505 | unsigned char *to, RSA *rsa, int padding) |
506 | { |
507 | BIGNUM *f, *ret; |
508 | int i, num = 0, r = -1; |
509 | unsigned char *buf = NULL; |
510 | BN_CTX *ctx = NULL; |
511 | |
512 | if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) { |
513 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE); |
514 | return -1; |
515 | } |
516 | |
517 | if (BN_ucmp(rsa->n, rsa->e) <= 0) { |
518 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); |
519 | return -1; |
520 | } |
521 | |
522 | /* for large moduli, enforce exponent limit */ |
523 | if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { |
524 | if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { |
525 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); |
526 | return -1; |
527 | } |
528 | } |
529 | |
530 | if ((ctx = BN_CTX_new()) == NULL) |
531 | goto err; |
532 | BN_CTX_start(ctx); |
533 | f = BN_CTX_get(ctx); |
534 | ret = BN_CTX_get(ctx); |
535 | num = BN_num_bytes(rsa->n); |
536 | buf = OPENSSL_malloc(num); |
537 | if (ret == NULL || buf == NULL) { |
538 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE); |
539 | goto err; |
540 | } |
541 | |
542 | /* |
543 | * This check was for equality but PGP does evil things and chops off the |
544 | * top '0' bytes |
545 | */ |
546 | if (flen > num) { |
547 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN); |
548 | goto err; |
549 | } |
550 | |
551 | if (BN_bin2bn(from, flen, f) == NULL) |
552 | goto err; |
553 | |
554 | if (BN_ucmp(f, rsa->n) >= 0) { |
555 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, |
556 | RSA_R_DATA_TOO_LARGE_FOR_MODULUS); |
557 | goto err; |
558 | } |
559 | |
560 | if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) |
561 | if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, |
562 | rsa->n, ctx)) |
563 | goto err; |
564 | |
565 | if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, |
566 | rsa->_method_mod_n)) |
567 | goto err; |
568 | |
569 | if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12)) |
570 | if (!BN_sub(ret, rsa->n, ret)) |
571 | goto err; |
572 | |
573 | i = BN_bn2binpad(ret, buf, num); |
574 | if (i < 0) |
575 | goto err; |
576 | |
577 | switch (padding) { |
578 | case RSA_PKCS1_PADDING: |
579 | r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num); |
580 | break; |
581 | case RSA_X931_PADDING: |
582 | r = RSA_padding_check_X931(to, num, buf, i, num); |
583 | break; |
584 | case RSA_NO_PADDING: |
585 | memcpy(to, buf, (r = i)); |
586 | break; |
587 | default: |
588 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); |
589 | goto err; |
590 | } |
591 | if (r < 0) |
592 | RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED); |
593 | |
594 | err: |
595 | BN_CTX_end(ctx); |
596 | BN_CTX_free(ctx); |
597 | OPENSSL_clear_free(buf, num); |
598 | return r; |
599 | } |
600 | |
601 | static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) |
602 | { |
603 | BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2]; |
604 | int ret = 0, i, ex_primes = 0, smooth = 0; |
605 | RSA_PRIME_INFO *pinfo; |
606 | |
607 | BN_CTX_start(ctx); |
608 | |
609 | r1 = BN_CTX_get(ctx); |
610 | r2 = BN_CTX_get(ctx); |
611 | m1 = BN_CTX_get(ctx); |
612 | vrfy = BN_CTX_get(ctx); |
613 | if (vrfy == NULL) |
614 | goto err; |
615 | |
616 | if (rsa->version == RSA_ASN1_VERSION_MULTI |
617 | && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0 |
618 | || ex_primes > RSA_MAX_PRIME_NUM - 2)) |
619 | goto err; |
620 | |
621 | if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { |
622 | BIGNUM *factor = BN_new(); |
623 | |
624 | if (factor == NULL) |
625 | goto err; |
626 | |
627 | /* |
628 | * Make sure BN_mod_inverse in Montgomery initialization uses the |
629 | * BN_FLG_CONSTTIME flag |
630 | */ |
631 | if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME), |
632 | BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock, |
633 | factor, ctx)) |
634 | || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME), |
635 | BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock, |
636 | factor, ctx))) { |
637 | BN_free(factor); |
638 | goto err; |
639 | } |
640 | for (i = 0; i < ex_primes; i++) { |
641 | pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); |
642 | BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME); |
643 | if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) { |
644 | BN_free(factor); |
645 | goto err; |
646 | } |
647 | } |
648 | /* |
649 | * We MUST free |factor| before any further use of the prime factors |
650 | */ |
651 | BN_free(factor); |
652 | |
653 | smooth = (ex_primes == 0) |
654 | && (rsa->meth->bn_mod_exp == BN_mod_exp_mont) |
655 | && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p)); |
656 | } |
657 | |
658 | if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) |
659 | if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, |
660 | rsa->n, ctx)) |
661 | goto err; |
662 | |
663 | if (smooth) { |
664 | /* |
665 | * Conversion from Montgomery domain, a.k.a. Montgomery reduction, |
666 | * accepts values in [0-m*2^w) range. w is m's bit width rounded up |
667 | * to limb width. So that at the very least if |I| is fully reduced, |
668 | * i.e. less than p*q, we can count on from-to round to perform |
669 | * below modulo operations on |I|. Unlike BN_mod it's constant time. |
670 | */ |
671 | if (/* m1 = I moq q */ |
672 | !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx) |
673 | || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx) |
674 | /* m1 = m1^dmq1 mod q */ |
675 | || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx, |
676 | rsa->_method_mod_q) |
677 | /* r1 = I mod p */ |
678 | || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx) |
679 | || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) |
680 | /* r1 = r1^dmp1 mod p */ |
681 | || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx, |
682 | rsa->_method_mod_p) |
683 | /* r1 = (r1 - m1) mod p */ |
684 | /* |
685 | * bn_mod_sub_fixed_top is not regular modular subtraction, |
686 | * it can tolerate subtrahend to be larger than modulus, but |
687 | * not bit-wise wider. This makes up for uncommon q>p case, |
688 | * when |m1| can be larger than |rsa->p|. |
689 | */ |
690 | || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p) |
691 | |
692 | /* r1 = r1 * iqmp mod p */ |
693 | || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) |
694 | || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p, |
695 | ctx) |
696 | /* r0 = r1 * q + m1 */ |
697 | || !bn_mul_fixed_top(r0, r1, rsa->q, ctx) |
698 | || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n)) |
699 | goto err; |
700 | |
701 | goto tail; |
702 | } |
703 | |
704 | /* compute I mod q */ |
705 | { |
706 | BIGNUM *c = BN_new(); |
707 | if (c == NULL) |
708 | goto err; |
709 | BN_with_flags(c, I, BN_FLG_CONSTTIME); |
710 | |
711 | if (!BN_mod(r1, c, rsa->q, ctx)) { |
712 | BN_free(c); |
713 | goto err; |
714 | } |
715 | |
716 | { |
717 | BIGNUM *dmq1 = BN_new(); |
718 | if (dmq1 == NULL) { |
719 | BN_free(c); |
720 | goto err; |
721 | } |
722 | BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); |
723 | |
724 | /* compute r1^dmq1 mod q */ |
725 | if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, |
726 | rsa->_method_mod_q)) { |
727 | BN_free(c); |
728 | BN_free(dmq1); |
729 | goto err; |
730 | } |
731 | /* We MUST free dmq1 before any further use of rsa->dmq1 */ |
732 | BN_free(dmq1); |
733 | } |
734 | |
735 | /* compute I mod p */ |
736 | if (!BN_mod(r1, c, rsa->p, ctx)) { |
737 | BN_free(c); |
738 | goto err; |
739 | } |
740 | /* We MUST free c before any further use of I */ |
741 | BN_free(c); |
742 | } |
743 | |
744 | { |
745 | BIGNUM *dmp1 = BN_new(); |
746 | if (dmp1 == NULL) |
747 | goto err; |
748 | BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); |
749 | |
750 | /* compute r1^dmp1 mod p */ |
751 | if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, |
752 | rsa->_method_mod_p)) { |
753 | BN_free(dmp1); |
754 | goto err; |
755 | } |
756 | /* We MUST free dmp1 before any further use of rsa->dmp1 */ |
757 | BN_free(dmp1); |
758 | } |
759 | |
760 | /* |
761 | * calculate m_i in multi-prime case |
762 | * |
763 | * TODO: |
764 | * 1. squash the following two loops and calculate |m_i| there. |
765 | * 2. remove cc and reuse |c|. |
766 | * 3. remove |dmq1| and |dmp1| in previous block and use |di|. |
767 | * |
768 | * If these things are done, the code will be more readable. |
769 | */ |
770 | if (ex_primes > 0) { |
771 | BIGNUM *di = BN_new(), *cc = BN_new(); |
772 | |
773 | if (cc == NULL || di == NULL) { |
774 | BN_free(cc); |
775 | BN_free(di); |
776 | goto err; |
777 | } |
778 | |
779 | for (i = 0; i < ex_primes; i++) { |
780 | /* prepare m_i */ |
781 | if ((m[i] = BN_CTX_get(ctx)) == NULL) { |
782 | BN_free(cc); |
783 | BN_free(di); |
784 | goto err; |
785 | } |
786 | |
787 | pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); |
788 | |
789 | /* prepare c and d_i */ |
790 | BN_with_flags(cc, I, BN_FLG_CONSTTIME); |
791 | BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME); |
792 | |
793 | if (!BN_mod(r1, cc, pinfo->r, ctx)) { |
794 | BN_free(cc); |
795 | BN_free(di); |
796 | goto err; |
797 | } |
798 | /* compute r1 ^ d_i mod r_i */ |
799 | if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) { |
800 | BN_free(cc); |
801 | BN_free(di); |
802 | goto err; |
803 | } |
804 | } |
805 | |
806 | BN_free(cc); |
807 | BN_free(di); |
808 | } |
809 | |
810 | if (!BN_sub(r0, r0, m1)) |
811 | goto err; |
812 | /* |
813 | * This will help stop the size of r0 increasing, which does affect the |
814 | * multiply if it optimised for a power of 2 size |
815 | */ |
816 | if (BN_is_negative(r0)) |
817 | if (!BN_add(r0, r0, rsa->p)) |
818 | goto err; |
819 | |
820 | if (!BN_mul(r1, r0, rsa->iqmp, ctx)) |
821 | goto err; |
822 | |
823 | { |
824 | BIGNUM *pr1 = BN_new(); |
825 | if (pr1 == NULL) |
826 | goto err; |
827 | BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); |
828 | |
829 | if (!BN_mod(r0, pr1, rsa->p, ctx)) { |
830 | BN_free(pr1); |
831 | goto err; |
832 | } |
833 | /* We MUST free pr1 before any further use of r1 */ |
834 | BN_free(pr1); |
835 | } |
836 | |
837 | /* |
838 | * If p < q it is occasionally possible for the correction of adding 'p' |
839 | * if r0 is negative above to leave the result still negative. This can |
840 | * break the private key operations: the following second correction |
841 | * should *always* correct this rare occurrence. This will *never* happen |
842 | * with OpenSSL generated keys because they ensure p > q [steve] |
843 | */ |
844 | if (BN_is_negative(r0)) |
845 | if (!BN_add(r0, r0, rsa->p)) |
846 | goto err; |
847 | if (!BN_mul(r1, r0, rsa->q, ctx)) |
848 | goto err; |
849 | if (!BN_add(r0, r1, m1)) |
850 | goto err; |
851 | |
852 | /* add m_i to m in multi-prime case */ |
853 | if (ex_primes > 0) { |
854 | BIGNUM *pr2 = BN_new(); |
855 | |
856 | if (pr2 == NULL) |
857 | goto err; |
858 | |
859 | for (i = 0; i < ex_primes; i++) { |
860 | pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); |
861 | if (!BN_sub(r1, m[i], r0)) { |
862 | BN_free(pr2); |
863 | goto err; |
864 | } |
865 | |
866 | if (!BN_mul(r2, r1, pinfo->t, ctx)) { |
867 | BN_free(pr2); |
868 | goto err; |
869 | } |
870 | |
871 | BN_with_flags(pr2, r2, BN_FLG_CONSTTIME); |
872 | |
873 | if (!BN_mod(r1, pr2, pinfo->r, ctx)) { |
874 | BN_free(pr2); |
875 | goto err; |
876 | } |
877 | |
878 | if (BN_is_negative(r1)) |
879 | if (!BN_add(r1, r1, pinfo->r)) { |
880 | BN_free(pr2); |
881 | goto err; |
882 | } |
883 | if (!BN_mul(r1, r1, pinfo->pp, ctx)) { |
884 | BN_free(pr2); |
885 | goto err; |
886 | } |
887 | if (!BN_add(r0, r0, r1)) { |
888 | BN_free(pr2); |
889 | goto err; |
890 | } |
891 | } |
892 | BN_free(pr2); |
893 | } |
894 | |
895 | tail: |
896 | if (rsa->e && rsa->n) { |
897 | if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) { |
898 | if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx, |
899 | rsa->_method_mod_n)) |
900 | goto err; |
901 | } else { |
902 | bn_correct_top(r0); |
903 | if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, |
904 | rsa->_method_mod_n)) |
905 | goto err; |
906 | } |
907 | /* |
908 | * If 'I' was greater than (or equal to) rsa->n, the operation will |
909 | * be equivalent to using 'I mod n'. However, the result of the |
910 | * verify will *always* be less than 'n' so we don't check for |
911 | * absolute equality, just congruency. |
912 | */ |
913 | if (!BN_sub(vrfy, vrfy, I)) |
914 | goto err; |
915 | if (BN_is_zero(vrfy)) { |
916 | bn_correct_top(r0); |
917 | ret = 1; |
918 | goto err; /* not actually error */ |
919 | } |
920 | if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) |
921 | goto err; |
922 | if (BN_is_negative(vrfy)) |
923 | if (!BN_add(vrfy, vrfy, rsa->n)) |
924 | goto err; |
925 | if (!BN_is_zero(vrfy)) { |
926 | /* |
927 | * 'I' and 'vrfy' aren't congruent mod n. Don't leak |
928 | * miscalculated CRT output, just do a raw (slower) mod_exp and |
929 | * return that instead. |
930 | */ |
931 | |
932 | BIGNUM *d = BN_new(); |
933 | if (d == NULL) |
934 | goto err; |
935 | BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); |
936 | |
937 | if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, |
938 | rsa->_method_mod_n)) { |
939 | BN_free(d); |
940 | goto err; |
941 | } |
942 | /* We MUST free d before any further use of rsa->d */ |
943 | BN_free(d); |
944 | } |
945 | } |
946 | /* |
947 | * It's unfortunate that we have to bn_correct_top(r0). What hopefully |
948 | * saves the day is that correction is highly unlike, and private key |
949 | * operations are customarily performed on blinded message. Which means |
950 | * that attacker won't observe correlation with chosen plaintext. |
951 | * Secondly, remaining code would still handle it in same computational |
952 | * time and even conceal memory access pattern around corrected top. |
953 | */ |
954 | bn_correct_top(r0); |
955 | ret = 1; |
956 | err: |
957 | BN_CTX_end(ctx); |
958 | return ret; |
959 | } |
960 | |
961 | static int rsa_ossl_init(RSA *rsa) |
962 | { |
963 | rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE; |
964 | return 1; |
965 | } |
966 | |
967 | static int rsa_ossl_finish(RSA *rsa) |
968 | { |
969 | int i; |
970 | RSA_PRIME_INFO *pinfo; |
971 | |
972 | BN_MONT_CTX_free(rsa->_method_mod_n); |
973 | BN_MONT_CTX_free(rsa->_method_mod_p); |
974 | BN_MONT_CTX_free(rsa->_method_mod_q); |
975 | for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) { |
976 | pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); |
977 | BN_MONT_CTX_free(pinfo->m); |
978 | } |
979 | return 1; |
980 | } |
981 | |