rsa_ossl.c 34 KB

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