1 /* $OpenBSD: rsa_oaep.c,v 1.38 2024/02/18 15:45:42 tb Exp $ */ 2 /* 3 * Copyright 1999-2018 The OpenSSL Project Authors. All Rights Reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * 17 * 3. All advertising materials mentioning features or use of this 18 * software must display the following acknowledgment: 19 * "This product includes software developed by the OpenSSL Project 20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21 * 22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23 * endorse or promote products derived from this software without 24 * prior written permission. For written permission, please contact 25 * openssl-core@openssl.org. 26 * 27 * 5. Products derived from this software may not be called "OpenSSL" 28 * nor may "OpenSSL" appear in their names without prior written 29 * permission of the OpenSSL Project. 30 * 31 * 6. Redistributions of any form whatsoever must retain the following 32 * acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47 * OF THE POSSIBILITY OF SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This product includes cryptographic software written by Eric Young 51 * (eay@cryptsoft.com). This product includes software written by Tim 52 * Hudson (tjh@cryptsoft.com). 53 * 54 */ 55 56 /* EME-OAEP as defined in RFC 2437 (PKCS #1 v2.0) */ 57 58 /* See Victor Shoup, "OAEP reconsidered," Nov. 2000, 59 * <URL: http://www.shoup.net/papers/oaep.ps.Z> 60 * for problems with the security proof for the 61 * original OAEP scheme, which EME-OAEP is based on. 62 * 63 * A new proof can be found in E. Fujisaki, T. Okamoto, 64 * D. Pointcheval, J. Stern, "RSA-OEAP is Still Alive!", 65 * Dec. 2000, <URL: http://eprint.iacr.org/2000/061/>. 66 * The new proof has stronger requirements for the 67 * underlying permutation: "partial-one-wayness" instead 68 * of one-wayness. For the RSA function, this is 69 * an equivalent notion. 70 */ 71 72 #include <stdio.h> 73 #include <stdlib.h> 74 #include <string.h> 75 76 #include <openssl/bn.h> 77 #include <openssl/err.h> 78 #include <openssl/evp.h> 79 #include <openssl/rsa.h> 80 #include <openssl/sha.h> 81 82 #include "constant_time.h" 83 #include "evp_local.h" 84 #include "rsa_local.h" 85 86 int 87 RSA_padding_add_PKCS1_OAEP(unsigned char *to, int tlen, 88 const unsigned char *from, int flen, const unsigned char *param, int plen) 89 { 90 return RSA_padding_add_PKCS1_OAEP_mgf1(to, tlen, from, flen, param, 91 plen, NULL, NULL); 92 } 93 LCRYPTO_ALIAS(RSA_padding_add_PKCS1_OAEP); 94 95 int 96 RSA_padding_add_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 97 const unsigned char *from, int flen, const unsigned char *param, int plen, 98 const EVP_MD *md, const EVP_MD *mgf1md) 99 { 100 int i, emlen = tlen - 1; 101 unsigned char *db, *seed; 102 unsigned char *dbmask = NULL; 103 unsigned char seedmask[EVP_MAX_MD_SIZE]; 104 int mdlen, dbmask_len = 0; 105 int rv = 0; 106 107 if (md == NULL) 108 md = EVP_sha1(); 109 if (mgf1md == NULL) 110 mgf1md = md; 111 112 if ((mdlen = EVP_MD_size(md)) <= 0) 113 goto err; 114 115 if (flen > emlen - 2 * mdlen - 1) { 116 RSAerror(RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 117 goto err; 118 } 119 120 if (emlen < 2 * mdlen + 1) { 121 RSAerror(RSA_R_KEY_SIZE_TOO_SMALL); 122 goto err; 123 } 124 125 to[0] = 0; 126 seed = to + 1; 127 db = to + mdlen + 1; 128 129 if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL)) 130 goto err; 131 132 memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1); 133 db[emlen - flen - mdlen - 1] = 0x01; 134 memcpy(db + emlen - flen - mdlen, from, flen); 135 arc4random_buf(seed, mdlen); 136 137 dbmask_len = emlen - mdlen; 138 if ((dbmask = malloc(dbmask_len)) == NULL) { 139 RSAerror(ERR_R_MALLOC_FAILURE); 140 goto err; 141 } 142 143 if (PKCS1_MGF1(dbmask, dbmask_len, seed, mdlen, mgf1md) < 0) 144 goto err; 145 for (i = 0; i < dbmask_len; i++) 146 db[i] ^= dbmask[i]; 147 if (PKCS1_MGF1(seedmask, mdlen, db, dbmask_len, mgf1md) < 0) 148 goto err; 149 for (i = 0; i < mdlen; i++) 150 seed[i] ^= seedmask[i]; 151 152 rv = 1; 153 154 err: 155 explicit_bzero(seedmask, sizeof(seedmask)); 156 freezero(dbmask, dbmask_len); 157 158 return rv; 159 } 160 LCRYPTO_ALIAS(RSA_padding_add_PKCS1_OAEP_mgf1); 161 162 int 163 RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen, 164 const unsigned char *from, int flen, int num, const unsigned char *param, 165 int plen) 166 { 167 return RSA_padding_check_PKCS1_OAEP_mgf1(to, tlen, from, flen, num, 168 param, plen, NULL, NULL); 169 } 170 LCRYPTO_ALIAS(RSA_padding_check_PKCS1_OAEP); 171 172 int 173 RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 174 const unsigned char *from, int flen, int num, const unsigned char *param, 175 int plen, const EVP_MD *md, const EVP_MD *mgf1md) 176 { 177 int i, dblen = 0, mlen = -1, one_index = 0, msg_index; 178 unsigned int good = 0, found_one_byte, mask; 179 const unsigned char *maskedseed, *maskeddb; 180 unsigned char seed[EVP_MAX_MD_SIZE], phash[EVP_MAX_MD_SIZE]; 181 unsigned char *db = NULL, *em = NULL; 182 int mdlen; 183 184 if (md == NULL) 185 md = EVP_sha1(); 186 if (mgf1md == NULL) 187 mgf1md = md; 188 189 if ((mdlen = EVP_MD_size(md)) <= 0) 190 return -1; 191 192 if (tlen <= 0 || flen <= 0) 193 return -1; 194 195 /* 196 * |num| is the length of the modulus; |flen| is the length of the 197 * encoded message. Therefore, for any |from| that was obtained by 198 * decrypting a ciphertext, we must have |flen| <= |num|. Similarly, 199 * |num| >= 2 * |mdlen| + 2 must hold for the modulus irrespective 200 * of the ciphertext, see PKCS #1 v2.2, section 7.1.2. 201 * This does not leak any side-channel information. 202 */ 203 if (num < flen || num < 2 * mdlen + 2) { 204 RSAerror(RSA_R_OAEP_DECODING_ERROR); 205 return -1; 206 } 207 208 dblen = num - mdlen - 1; 209 if ((db = malloc(dblen)) == NULL) { 210 RSAerror(ERR_R_MALLOC_FAILURE); 211 goto cleanup; 212 } 213 if ((em = malloc(num)) == NULL) { 214 RSAerror(ERR_R_MALLOC_FAILURE); 215 goto cleanup; 216 } 217 218 /* 219 * Caller is encouraged to pass zero-padded message created with 220 * BN_bn2binpad. Trouble is that since we can't read out of |from|'s 221 * bounds, it's impossible to have an invariant memory access pattern 222 * in case |from| was not zero-padded in advance. 223 */ 224 for (from += flen, em += num, i = 0; i < num; i++) { 225 mask = ~constant_time_is_zero(flen); 226 flen -= 1 & mask; 227 from -= 1 & mask; 228 *--em = *from & mask; 229 } 230 231 /* 232 * The first byte must be zero, however we must not leak if this is 233 * true. See James H. Manger, "A Chosen Ciphertext Attack on RSA 234 * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001). 235 */ 236 good = constant_time_is_zero(em[0]); 237 238 maskedseed = em + 1; 239 maskeddb = em + 1 + mdlen; 240 241 if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md)) 242 goto cleanup; 243 for (i = 0; i < mdlen; i++) 244 seed[i] ^= maskedseed[i]; 245 246 if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md)) 247 goto cleanup; 248 for (i = 0; i < dblen; i++) 249 db[i] ^= maskeddb[i]; 250 251 if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL)) 252 goto cleanup; 253 254 good &= constant_time_is_zero(timingsafe_memcmp(db, phash, mdlen)); 255 256 found_one_byte = 0; 257 for (i = mdlen; i < dblen; i++) { 258 /* 259 * Padding consists of a number of 0-bytes, followed by a 1. 260 */ 261 unsigned int equals1 = constant_time_eq(db[i], 1); 262 unsigned int equals0 = constant_time_is_zero(db[i]); 263 264 one_index = constant_time_select_int(~found_one_byte & equals1, 265 i, one_index); 266 found_one_byte |= equals1; 267 good &= (found_one_byte | equals0); 268 } 269 270 good &= found_one_byte; 271 272 /* 273 * At this point |good| is zero unless the plaintext was valid, 274 * so plaintext-awareness ensures timing side-channels are no longer a 275 * concern. 276 */ 277 msg_index = one_index + 1; 278 mlen = dblen - msg_index; 279 280 /* 281 * For good measure, do this check in constant time as well. 282 */ 283 good &= constant_time_ge(tlen, mlen); 284 285 /* 286 * Even though we can't fake result's length, we can pretend copying 287 * |tlen| bytes where |mlen| bytes would be real. The last |tlen| of 288 * |dblen| bytes are viewed as a circular buffer starting at |tlen|-|mlen'|, 289 * where |mlen'| is the "saturated" |mlen| value. Deducing information 290 * about failure or |mlen| would require an attacker to observe 291 * memory access patterns with byte granularity *as it occurs*. It 292 * should be noted that failure is indistinguishable from normal 293 * operation if |tlen| is fixed by protocol. 294 */ 295 tlen = constant_time_select_int(constant_time_lt(dblen - mdlen - 1, tlen), 296 dblen - mdlen - 1, tlen); 297 msg_index = constant_time_select_int(good, msg_index, dblen - tlen); 298 mlen = dblen - msg_index; 299 for (mask = good, i = 0; i < tlen; i++) { 300 unsigned int equals = constant_time_eq(msg_index, dblen); 301 302 msg_index -= tlen & equals; /* rewind at EOF */ 303 mask &= ~equals; /* mask = 0 at EOF */ 304 to[i] = constant_time_select_8(mask, db[msg_index++], to[i]); 305 } 306 307 /* 308 * To avoid chosen ciphertext attacks, the error message should not 309 * reveal which kind of decoding error happened. 310 */ 311 RSAerror(RSA_R_OAEP_DECODING_ERROR); 312 err_clear_last_constant_time(1 & good); 313 314 cleanup: 315 explicit_bzero(seed, sizeof(seed)); 316 freezero(db, dblen); 317 freezero(em, num); 318 319 return constant_time_select_int(good, mlen, -1); 320 } 321 LCRYPTO_ALIAS(RSA_padding_check_PKCS1_OAEP_mgf1); 322 323 int 324 PKCS1_MGF1(unsigned char *mask, long len, const unsigned char *seed, 325 long seedlen, const EVP_MD *dgst) 326 { 327 long i, outlen = 0; 328 unsigned char cnt[4]; 329 EVP_MD_CTX c; 330 unsigned char md[EVP_MAX_MD_SIZE]; 331 int mdlen; 332 int rv = -1; 333 334 EVP_MD_CTX_legacy_clear(&c); 335 mdlen = EVP_MD_size(dgst); 336 if (mdlen < 0) 337 goto err; 338 for (i = 0; outlen < len; i++) { 339 cnt[0] = (unsigned char)((i >> 24) & 255); 340 cnt[1] = (unsigned char)((i >> 16) & 255); 341 cnt[2] = (unsigned char)((i >> 8)) & 255; 342 cnt[3] = (unsigned char)(i & 255); 343 if (!EVP_DigestInit_ex(&c, dgst, NULL) || 344 !EVP_DigestUpdate(&c, seed, seedlen) || 345 !EVP_DigestUpdate(&c, cnt, 4)) 346 goto err; 347 if (outlen + mdlen <= len) { 348 if (!EVP_DigestFinal_ex(&c, mask + outlen, NULL)) 349 goto err; 350 outlen += mdlen; 351 } else { 352 if (!EVP_DigestFinal_ex(&c, md, NULL)) 353 goto err; 354 memcpy(mask + outlen, md, len - outlen); 355 outlen = len; 356 } 357 } 358 rv = 0; 359 err: 360 EVP_MD_CTX_cleanup(&c); 361 return rv; 362 } 363 LCRYPTO_ALIAS(PKCS1_MGF1); 364