2
0

rsa_oaep.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369
  1. /*
  2. * Copyright 1999-2021 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. /* EME-OAEP as defined in RFC 2437 (PKCS #1 v2.0) */
  10. /*
  11. * See Victor Shoup, "OAEP reconsidered," Nov. 2000, <URL:
  12. * http://www.shoup.net/papers/oaep.ps.Z> for problems with the security
  13. * proof for the original OAEP scheme, which EME-OAEP is based on. A new
  14. * proof can be found in E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern,
  15. * "RSA-OEAP is Still Alive!", Dec. 2000, <URL:
  16. * http://eprint.iacr.org/2000/061/>. The new proof has stronger requirements
  17. * for the underlying permutation: "partial-one-wayness" instead of
  18. * one-wayness. For the RSA function, this is an equivalent notion.
  19. */
  20. /*
  21. * RSA low level APIs are deprecated for public use, but still ok for
  22. * internal use.
  23. */
  24. #include "internal/deprecated.h"
  25. #include "internal/constant_time.h"
  26. #include <stdio.h>
  27. #include "internal/cryptlib.h"
  28. #include <openssl/bn.h>
  29. #include <openssl/evp.h>
  30. #include <openssl/rand.h>
  31. #include <openssl/sha.h>
  32. #include "rsa_local.h"
  33. int RSA_padding_add_PKCS1_OAEP(unsigned char *to, int tlen,
  34. const unsigned char *from, int flen,
  35. const unsigned char *param, int plen)
  36. {
  37. return ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(NULL, to, tlen, from, flen,
  38. param, plen, NULL, NULL);
  39. }
  40. /*
  41. * Perform the padding as per NIST 800-56B 7.2.2.3
  42. * from (K) is the key material.
  43. * param (A) is the additional input.
  44. * Step numbers are included here but not in the constant time inverse below
  45. * to avoid complicating an already difficult enough function.
  46. */
  47. int ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(OSSL_LIB_CTX *libctx,
  48. unsigned char *to, int tlen,
  49. const unsigned char *from, int flen,
  50. const unsigned char *param,
  51. int plen, const EVP_MD *md,
  52. const EVP_MD *mgf1md)
  53. {
  54. int rv = 0;
  55. int i, emlen = tlen - 1;
  56. unsigned char *db, *seed;
  57. unsigned char *dbmask = NULL;
  58. unsigned char seedmask[EVP_MAX_MD_SIZE];
  59. int mdlen, dbmask_len = 0;
  60. if (md == NULL) {
  61. #ifndef FIPS_MODULE
  62. md = EVP_sha1();
  63. #else
  64. ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
  65. return 0;
  66. #endif
  67. }
  68. if (mgf1md == NULL)
  69. mgf1md = md;
  70. mdlen = EVP_MD_get_size(md);
  71. if (mdlen <= 0) {
  72. ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_LENGTH);
  73. return 0;
  74. }
  75. /* step 2b: check KLen > nLen - 2 HLen - 2 */
  76. if (flen > emlen - 2 * mdlen - 1) {
  77. ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
  78. return 0;
  79. }
  80. if (emlen < 2 * mdlen + 1) {
  81. ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
  82. return 0;
  83. }
  84. /* step 3i: EM = 00000000 || maskedMGF || maskedDB */
  85. to[0] = 0;
  86. seed = to + 1;
  87. db = to + mdlen + 1;
  88. /* step 3a: hash the additional input */
  89. if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL))
  90. goto err;
  91. /* step 3b: zero bytes array of length nLen - KLen - 2 HLen -2 */
  92. memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1);
  93. /* step 3c: DB = HA || PS || 00000001 || K */
  94. db[emlen - flen - mdlen - 1] = 0x01;
  95. memcpy(db + emlen - flen - mdlen, from, (unsigned int)flen);
  96. /* step 3d: generate random byte string */
  97. if (RAND_bytes_ex(libctx, seed, mdlen, 0) <= 0)
  98. goto err;
  99. dbmask_len = emlen - mdlen;
  100. dbmask = OPENSSL_malloc(dbmask_len);
  101. if (dbmask == NULL)
  102. goto err;
  103. /* step 3e: dbMask = MGF(mgfSeed, nLen - HLen - 1) */
  104. if (PKCS1_MGF1(dbmask, dbmask_len, seed, mdlen, mgf1md) < 0)
  105. goto err;
  106. /* step 3f: maskedDB = DB XOR dbMask */
  107. for (i = 0; i < dbmask_len; i++)
  108. db[i] ^= dbmask[i];
  109. /* step 3g: mgfSeed = MGF(maskedDB, HLen) */
  110. if (PKCS1_MGF1(seedmask, mdlen, db, dbmask_len, mgf1md) < 0)
  111. goto err;
  112. /* stepo 3h: maskedMGFSeed = mgfSeed XOR mgfSeedMask */
  113. for (i = 0; i < mdlen; i++)
  114. seed[i] ^= seedmask[i];
  115. rv = 1;
  116. err:
  117. OPENSSL_cleanse(seedmask, sizeof(seedmask));
  118. OPENSSL_clear_free(dbmask, dbmask_len);
  119. return rv;
  120. }
  121. int RSA_padding_add_PKCS1_OAEP_mgf1(unsigned char *to, int tlen,
  122. const unsigned char *from, int flen,
  123. const unsigned char *param, int plen,
  124. const EVP_MD *md, const EVP_MD *mgf1md)
  125. {
  126. return ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(NULL, to, tlen, from, flen,
  127. param, plen, md, mgf1md);
  128. }
  129. int RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen,
  130. const unsigned char *from, int flen, int num,
  131. const unsigned char *param, int plen)
  132. {
  133. return RSA_padding_check_PKCS1_OAEP_mgf1(to, tlen, from, flen, num,
  134. param, plen, NULL, NULL);
  135. }
  136. int RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen,
  137. const unsigned char *from, int flen,
  138. int num, const unsigned char *param,
  139. int plen, const EVP_MD *md,
  140. const EVP_MD *mgf1md)
  141. {
  142. int i, dblen = 0, mlen = -1, one_index = 0, msg_index;
  143. unsigned int good = 0, found_one_byte, mask;
  144. const unsigned char *maskedseed, *maskeddb;
  145. /*
  146. * |em| is the encoded message, zero-padded to exactly |num| bytes: em =
  147. * Y || maskedSeed || maskedDB
  148. */
  149. unsigned char *db = NULL, *em = NULL, seed[EVP_MAX_MD_SIZE],
  150. phash[EVP_MAX_MD_SIZE];
  151. int mdlen;
  152. if (md == NULL) {
  153. #ifndef FIPS_MODULE
  154. md = EVP_sha1();
  155. #else
  156. ERR_raise(ERR_LIB_RSA, ERR_R_PASSED_NULL_PARAMETER);
  157. return -1;
  158. #endif
  159. }
  160. if (mgf1md == NULL)
  161. mgf1md = md;
  162. mdlen = EVP_MD_get_size(md);
  163. if (tlen <= 0 || flen <= 0)
  164. return -1;
  165. /*
  166. * |num| is the length of the modulus; |flen| is the length of the
  167. * encoded message. Therefore, for any |from| that was obtained by
  168. * decrypting a ciphertext, we must have |flen| <= |num|. Similarly,
  169. * |num| >= 2 * |mdlen| + 2 must hold for the modulus irrespective of
  170. * the ciphertext, see PKCS #1 v2.2, section 7.1.2.
  171. * This does not leak any side-channel information.
  172. */
  173. if (num < flen || num < 2 * mdlen + 2) {
  174. ERR_raise(ERR_LIB_RSA, RSA_R_OAEP_DECODING_ERROR);
  175. return -1;
  176. }
  177. dblen = num - mdlen - 1;
  178. db = OPENSSL_malloc(dblen);
  179. if (db == NULL)
  180. goto cleanup;
  181. em = OPENSSL_malloc(num);
  182. if (em == NULL)
  183. goto cleanup;
  184. /*
  185. * Caller is encouraged to pass zero-padded message created with
  186. * BN_bn2binpad. Trouble is that since we can't read out of |from|'s
  187. * bounds, it's impossible to have an invariant memory access pattern
  188. * in case |from| was not zero-padded in advance.
  189. */
  190. for (from += flen, em += num, i = 0; i < num; i++) {
  191. mask = ~constant_time_is_zero(flen);
  192. flen -= 1 & mask;
  193. from -= 1 & mask;
  194. *--em = *from & mask;
  195. }
  196. /*
  197. * The first byte must be zero, however we must not leak if this is
  198. * true. See James H. Manger, "A Chosen Ciphertext Attack on RSA
  199. * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001).
  200. */
  201. good = constant_time_is_zero(em[0]);
  202. maskedseed = em + 1;
  203. maskeddb = em + 1 + mdlen;
  204. if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md))
  205. goto cleanup;
  206. for (i = 0; i < mdlen; i++)
  207. seed[i] ^= maskedseed[i];
  208. if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md))
  209. goto cleanup;
  210. for (i = 0; i < dblen; i++)
  211. db[i] ^= maskeddb[i];
  212. if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL))
  213. goto cleanup;
  214. good &= constant_time_is_zero(CRYPTO_memcmp(db, phash, mdlen));
  215. found_one_byte = 0;
  216. for (i = mdlen; i < dblen; i++) {
  217. /*
  218. * Padding consists of a number of 0-bytes, followed by a 1.
  219. */
  220. unsigned int equals1 = constant_time_eq(db[i], 1);
  221. unsigned int equals0 = constant_time_is_zero(db[i]);
  222. one_index = constant_time_select_int(~found_one_byte & equals1,
  223. i, one_index);
  224. found_one_byte |= equals1;
  225. good &= (found_one_byte | equals0);
  226. }
  227. good &= found_one_byte;
  228. /*
  229. * At this point |good| is zero unless the plaintext was valid,
  230. * so plaintext-awareness ensures timing side-channels are no longer a
  231. * concern.
  232. */
  233. msg_index = one_index + 1;
  234. mlen = dblen - msg_index;
  235. /*
  236. * For good measure, do this check in constant time as well.
  237. */
  238. good &= constant_time_ge(tlen, mlen);
  239. /*
  240. * Move the result in-place by |dblen|-|mdlen|-1-|mlen| bytes to the left.
  241. * Then if |good| move |mlen| bytes from |db|+|mdlen|+1 to |to|.
  242. * Otherwise leave |to| unchanged.
  243. * Copy the memory back in a way that does not reveal the size of
  244. * the data being copied via a timing side channel. This requires copying
  245. * parts of the buffer multiple times based on the bits set in the real
  246. * length. Clear bits do a non-copy with identical access pattern.
  247. * The loop below has overall complexity of O(N*log(N)).
  248. */
  249. tlen = constant_time_select_int(constant_time_lt(dblen - mdlen - 1, tlen),
  250. dblen - mdlen - 1, tlen);
  251. for (msg_index = 1; msg_index < dblen - mdlen - 1; msg_index <<= 1) {
  252. mask = ~constant_time_eq(msg_index & (dblen - mdlen - 1 - mlen), 0);
  253. for (i = mdlen + 1; i < dblen - msg_index; i++)
  254. db[i] = constant_time_select_8(mask, db[i + msg_index], db[i]);
  255. }
  256. for (i = 0; i < tlen; i++) {
  257. mask = good & constant_time_lt(i, mlen);
  258. to[i] = constant_time_select_8(mask, db[i + mdlen + 1], to[i]);
  259. }
  260. #ifndef FIPS_MODULE
  261. /*
  262. * To avoid chosen ciphertext attacks, the error message should not
  263. * reveal which kind of decoding error happened.
  264. *
  265. * This trick doesn't work in the FIPS provider because libcrypto manages
  266. * the error stack. Instead we opt not to put an error on the stack at all
  267. * in case of padding failure in the FIPS provider.
  268. */
  269. ERR_raise(ERR_LIB_RSA, RSA_R_OAEP_DECODING_ERROR);
  270. err_clear_last_constant_time(1 & good);
  271. #endif
  272. cleanup:
  273. OPENSSL_cleanse(seed, sizeof(seed));
  274. OPENSSL_clear_free(db, dblen);
  275. OPENSSL_clear_free(em, num);
  276. return constant_time_select_int(good, mlen, -1);
  277. }
  278. /*
  279. * Mask Generation Function corresponding to section 7.2.2.2 of NIST SP 800-56B.
  280. * The variables are named differently to NIST:
  281. * mask (T) and len (maskLen)are the returned mask.
  282. * seed (mgfSeed).
  283. * The range checking steps inm the process are performed outside.
  284. */
  285. int PKCS1_MGF1(unsigned char *mask, long len,
  286. const unsigned char *seed, long seedlen, const EVP_MD *dgst)
  287. {
  288. long i, outlen = 0;
  289. unsigned char cnt[4];
  290. EVP_MD_CTX *c = EVP_MD_CTX_new();
  291. unsigned char md[EVP_MAX_MD_SIZE];
  292. int mdlen;
  293. int rv = -1;
  294. if (c == NULL)
  295. goto err;
  296. mdlen = EVP_MD_get_size(dgst);
  297. if (mdlen < 0)
  298. goto err;
  299. /* step 4 */
  300. for (i = 0; outlen < len; i++) {
  301. /* step 4a: D = I2BS(counter, 4) */
  302. cnt[0] = (unsigned char)((i >> 24) & 255);
  303. cnt[1] = (unsigned char)((i >> 16) & 255);
  304. cnt[2] = (unsigned char)((i >> 8)) & 255;
  305. cnt[3] = (unsigned char)(i & 255);
  306. /* step 4b: T =T || hash(mgfSeed || D) */
  307. if (!EVP_DigestInit_ex(c, dgst, NULL)
  308. || !EVP_DigestUpdate(c, seed, seedlen)
  309. || !EVP_DigestUpdate(c, cnt, 4))
  310. goto err;
  311. if (outlen + mdlen <= len) {
  312. if (!EVP_DigestFinal_ex(c, mask + outlen, NULL))
  313. goto err;
  314. outlen += mdlen;
  315. } else {
  316. if (!EVP_DigestFinal_ex(c, md, NULL))
  317. goto err;
  318. memcpy(mask + outlen, md, len - outlen);
  319. outlen = len;
  320. }
  321. }
  322. rv = 0;
  323. err:
  324. OPENSSL_cleanse(md, sizeof(md));
  325. EVP_MD_CTX_free(c);
  326. return rv;
  327. }