1 /* $OpenBSD: rsa_oaep.c,v 1.35 2022/02/20 19:16:34 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_locl.h" 83 #include "evp_locl.h" 84 #include "rsa_locl.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 94 int 95 RSA_padding_add_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 96 const unsigned char *from, int flen, const unsigned char *param, int plen, 97 const EVP_MD *md, const EVP_MD *mgf1md) 98 { 99 int i, emlen = tlen - 1; 100 unsigned char *db, *seed; 101 unsigned char *dbmask = NULL; 102 unsigned char seedmask[EVP_MAX_MD_SIZE]; 103 int mdlen, dbmask_len = 0; 104 int rv = 0; 105 106 if (md == NULL) 107 md = EVP_sha1(); 108 if (mgf1md == NULL) 109 mgf1md = md; 110 111 if ((mdlen = EVP_MD_size(md)) <= 0) 112 goto err; 113 114 if (flen > emlen - 2 * mdlen - 1) { 115 RSAerror(RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 116 goto err; 117 } 118 119 if (emlen < 2 * mdlen + 1) { 120 RSAerror(RSA_R_KEY_SIZE_TOO_SMALL); 121 goto err; 122 } 123 124 to[0] = 0; 125 seed = to + 1; 126 db = to + mdlen + 1; 127 128 if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL)) 129 goto err; 130 131 memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1); 132 db[emlen - flen - mdlen - 1] = 0x01; 133 memcpy(db + emlen - flen - mdlen, from, flen); 134 arc4random_buf(seed, mdlen); 135 136 dbmask_len = emlen - mdlen; 137 if ((dbmask = malloc(dbmask_len)) == NULL) { 138 RSAerror(ERR_R_MALLOC_FAILURE); 139 goto err; 140 } 141 142 if (PKCS1_MGF1(dbmask, dbmask_len, seed, mdlen, mgf1md) < 0) 143 goto err; 144 for (i = 0; i < dbmask_len; i++) 145 db[i] ^= dbmask[i]; 146 if (PKCS1_MGF1(seedmask, mdlen, db, dbmask_len, mgf1md) < 0) 147 goto err; 148 for (i = 0; i < mdlen; i++) 149 seed[i] ^= seedmask[i]; 150 151 rv = 1; 152 153 err: 154 explicit_bzero(seedmask, sizeof(seedmask)); 155 freezero(dbmask, dbmask_len); 156 157 return rv; 158 } 159 160 int 161 RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen, 162 const unsigned char *from, int flen, int num, const unsigned char *param, 163 int plen) 164 { 165 return RSA_padding_check_PKCS1_OAEP_mgf1(to, tlen, from, flen, num, 166 param, plen, NULL, NULL); 167 } 168 169 int 170 RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 171 const unsigned char *from, int flen, int num, const unsigned char *param, 172 int plen, const EVP_MD *md, const EVP_MD *mgf1md) 173 { 174 int i, dblen = 0, mlen = -1, one_index = 0, msg_index; 175 unsigned int good = 0, found_one_byte, mask; 176 const unsigned char *maskedseed, *maskeddb; 177 unsigned char seed[EVP_MAX_MD_SIZE], phash[EVP_MAX_MD_SIZE]; 178 unsigned char *db = NULL, *em = NULL; 179 int mdlen; 180 181 if (md == NULL) 182 md = EVP_sha1(); 183 if (mgf1md == NULL) 184 mgf1md = md; 185 186 if ((mdlen = EVP_MD_size(md)) <= 0) 187 return -1; 188 189 if (tlen <= 0 || flen <= 0) 190 return -1; 191 192 /* 193 * |num| is the length of the modulus; |flen| is the length of the 194 * encoded message. Therefore, for any |from| that was obtained by 195 * decrypting a ciphertext, we must have |flen| <= |num|. Similarly, 196 * |num| >= 2 * |mdlen| + 2 must hold for the modulus irrespective 197 * of the ciphertext, see PKCS #1 v2.2, section 7.1.2. 198 * This does not leak any side-channel information. 199 */ 200 if (num < flen || num < 2 * mdlen + 2) { 201 RSAerror(RSA_R_OAEP_DECODING_ERROR); 202 return -1; 203 } 204 205 dblen = num - mdlen - 1; 206 if ((db = malloc(dblen)) == NULL) { 207 RSAerror(ERR_R_MALLOC_FAILURE); 208 goto cleanup; 209 } 210 if ((em = malloc(num)) == NULL) { 211 RSAerror(ERR_R_MALLOC_FAILURE); 212 goto cleanup; 213 } 214 215 /* 216 * Caller is encouraged to pass zero-padded message created with 217 * BN_bn2binpad. Trouble is that since we can't read out of |from|'s 218 * bounds, it's impossible to have an invariant memory access pattern 219 * in case |from| was not zero-padded in advance. 220 */ 221 for (from += flen, em += num, i = 0; i < num; i++) { 222 mask = ~constant_time_is_zero(flen); 223 flen -= 1 & mask; 224 from -= 1 & mask; 225 *--em = *from & mask; 226 } 227 228 /* 229 * The first byte must be zero, however we must not leak if this is 230 * true. See James H. Manger, "A Chosen Ciphertext Attack on RSA 231 * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001). 232 */ 233 good = constant_time_is_zero(em[0]); 234 235 maskedseed = em + 1; 236 maskeddb = em + 1 + mdlen; 237 238 if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md)) 239 goto cleanup; 240 for (i = 0; i < mdlen; i++) 241 seed[i] ^= maskedseed[i]; 242 243 if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md)) 244 goto cleanup; 245 for (i = 0; i < dblen; i++) 246 db[i] ^= maskeddb[i]; 247 248 if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL)) 249 goto cleanup; 250 251 good &= constant_time_is_zero(timingsafe_memcmp(db, phash, mdlen)); 252 253 found_one_byte = 0; 254 for (i = mdlen; i < dblen; i++) { 255 /* 256 * Padding consists of a number of 0-bytes, followed by a 1. 257 */ 258 unsigned int equals1 = constant_time_eq(db[i], 1); 259 unsigned int equals0 = constant_time_is_zero(db[i]); 260 261 one_index = constant_time_select_int(~found_one_byte & equals1, 262 i, one_index); 263 found_one_byte |= equals1; 264 good &= (found_one_byte | equals0); 265 } 266 267 good &= found_one_byte; 268 269 /* 270 * At this point |good| is zero unless the plaintext was valid, 271 * so plaintext-awareness ensures timing side-channels are no longer a 272 * concern. 273 */ 274 msg_index = one_index + 1; 275 mlen = dblen - msg_index; 276 277 /* 278 * For good measure, do this check in constant time as well. 279 */ 280 good &= constant_time_ge(tlen, mlen); 281 282 /* 283 * Even though we can't fake result's length, we can pretend copying 284 * |tlen| bytes where |mlen| bytes would be real. The last |tlen| of 285 * |dblen| bytes are viewed as a circular buffer starting at |tlen|-|mlen'|, 286 * where |mlen'| is the "saturated" |mlen| value. Deducing information 287 * about failure or |mlen| would require an attacker to observe 288 * memory access patterns with byte granularity *as it occurs*. It 289 * should be noted that failure is indistinguishable from normal 290 * operation if |tlen| is fixed by protocol. 291 */ 292 tlen = constant_time_select_int(constant_time_lt(dblen - mdlen - 1, tlen), 293 dblen - mdlen - 1, tlen); 294 msg_index = constant_time_select_int(good, msg_index, dblen - tlen); 295 mlen = dblen - msg_index; 296 for (mask = good, i = 0; i < tlen; i++) { 297 unsigned int equals = constant_time_eq(msg_index, dblen); 298 299 msg_index -= tlen & equals; /* rewind at EOF */ 300 mask &= ~equals; /* mask = 0 at EOF */ 301 to[i] = constant_time_select_8(mask, db[msg_index++], to[i]); 302 } 303 304 /* 305 * To avoid chosen ciphertext attacks, the error message should not 306 * reveal which kind of decoding error happened. 307 */ 308 RSAerror(RSA_R_OAEP_DECODING_ERROR); 309 err_clear_last_constant_time(1 & good); 310 311 cleanup: 312 explicit_bzero(seed, sizeof(seed)); 313 freezero(db, dblen); 314 freezero(em, num); 315 316 return constant_time_select_int(good, mlen, -1); 317 } 318 319 int 320 PKCS1_MGF1(unsigned char *mask, long len, const unsigned char *seed, 321 long seedlen, const EVP_MD *dgst) 322 { 323 long i, outlen = 0; 324 unsigned char cnt[4]; 325 EVP_MD_CTX c; 326 unsigned char md[EVP_MAX_MD_SIZE]; 327 int mdlen; 328 int rv = -1; 329 330 EVP_MD_CTX_init(&c); 331 mdlen = EVP_MD_size(dgst); 332 if (mdlen < 0) 333 goto err; 334 for (i = 0; outlen < len; i++) { 335 cnt[0] = (unsigned char)((i >> 24) & 255); 336 cnt[1] = (unsigned char)((i >> 16) & 255); 337 cnt[2] = (unsigned char)((i >> 8)) & 255; 338 cnt[3] = (unsigned char)(i & 255); 339 if (!EVP_DigestInit_ex(&c, dgst, NULL) || 340 !EVP_DigestUpdate(&c, seed, seedlen) || 341 !EVP_DigestUpdate(&c, cnt, 4)) 342 goto err; 343 if (outlen + mdlen <= len) { 344 if (!EVP_DigestFinal_ex(&c, mask + outlen, NULL)) 345 goto err; 346 outlen += mdlen; 347 } else { 348 if (!EVP_DigestFinal_ex(&c, md, NULL)) 349 goto err; 350 memcpy(mask + outlen, md, len - outlen); 351 outlen = len; 352 } 353 } 354 rv = 0; 355 err: 356 EVP_MD_CTX_cleanup(&c); 357 return rv; 358 } 359