rsa_ossl.c@ 97878

Last change on this file since 97878 was 94404, checked in by vboxsync, 3 years ago
libs/openssl: Update to 3.0.2 and switch to it, bugref:10128
File size: 29.4 KB

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

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/openssl-3.0.7/crypto/rsa/rsa_ossl.c@ 97878

Download in other formats: