1 /* $OpenBSD: rsa_oaep.c,v 1.33 2019/10/17 14:31:56 jsing 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 "rsa_locl.h" 84 85 int 86 RSA_padding_add_PKCS1_OAEP(unsigned char *to, int tlen, 87 const unsigned char *from, int flen, const unsigned char *param, int plen) 88 { 89 return RSA_padding_add_PKCS1_OAEP_mgf1(to, tlen, from, flen, param, 90 plen, NULL, NULL); 91 } 92 93 int 94 RSA_padding_add_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 95 const unsigned char *from, int flen, const unsigned char *param, int plen, 96 const EVP_MD *md, const EVP_MD *mgf1md) 97 { 98 int i, emlen = tlen - 1; 99 unsigned char *db, *seed; 100 unsigned char *dbmask = NULL; 101 unsigned char seedmask[EVP_MAX_MD_SIZE]; 102 int mdlen, dbmask_len = 0; 103 int rv = 0; 104 105 if (md == NULL) 106 md = EVP_sha1(); 107 if (mgf1md == NULL) 108 mgf1md = md; 109 110 if ((mdlen = EVP_MD_size(md)) <= 0) 111 goto err; 112 113 if (flen > emlen - 2 * mdlen - 1) { 114 RSAerror(RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 115 goto err; 116 } 117 118 if (emlen < 2 * mdlen + 1) { 119 RSAerror(RSA_R_KEY_SIZE_TOO_SMALL); 120 goto err; 121 } 122 123 to[0] = 0; 124 seed = to + 1; 125 db = to + mdlen + 1; 126 127 if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL)) 128 goto err; 129 130 memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1); 131 db[emlen - flen - mdlen - 1] = 0x01; 132 memcpy(db + emlen - flen - mdlen, from, flen); 133 arc4random_buf(seed, mdlen); 134 135 dbmask_len = emlen - mdlen; 136 if ((dbmask = malloc(dbmask_len)) == NULL) { 137 RSAerror(ERR_R_MALLOC_FAILURE); 138 goto err; 139 } 140 141 if (PKCS1_MGF1(dbmask, dbmask_len, seed, mdlen, mgf1md) < 0) 142 goto err; 143 for (i = 0; i < dbmask_len; i++) 144 db[i] ^= dbmask[i]; 145 if (PKCS1_MGF1(seedmask, mdlen, db, dbmask_len, mgf1md) < 0) 146 goto err; 147 for (i = 0; i < mdlen; i++) 148 seed[i] ^= seedmask[i]; 149 150 rv = 1; 151 152 err: 153 explicit_bzero(seedmask, sizeof(seedmask)); 154 freezero(dbmask, dbmask_len); 155 156 return rv; 157 } 158 159 int 160 RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen, 161 const unsigned char *from, int flen, int num, const unsigned char *param, 162 int plen) 163 { 164 return RSA_padding_check_PKCS1_OAEP_mgf1(to, tlen, from, flen, num, 165 param, plen, NULL, NULL); 166 } 167 168 int 169 RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 170 const unsigned char *from, int flen, int num, const unsigned char *param, 171 int plen, const EVP_MD *md, const EVP_MD *mgf1md) 172 { 173 int i, dblen = 0, mlen = -1, one_index = 0, msg_index; 174 unsigned int good = 0, found_one_byte, mask; 175 const unsigned char *maskedseed, *maskeddb; 176 unsigned char seed[EVP_MAX_MD_SIZE], phash[EVP_MAX_MD_SIZE]; 177 unsigned char *db = NULL, *em = NULL; 178 int mdlen; 179 180 if (md == NULL) 181 md = EVP_sha1(); 182 if (mgf1md == NULL) 183 mgf1md = md; 184 185 if ((mdlen = EVP_MD_size(md)) <= 0) 186 return -1; 187 188 if (tlen <= 0 || flen <= 0) 189 return -1; 190 191 /* 192 * |num| is the length of the modulus; |flen| is the length of the 193 * encoded message. Therefore, for any |from| that was obtained by 194 * decrypting a ciphertext, we must have |flen| <= |num|. Similarly, 195 * |num| >= 2 * |mdlen| + 2 must hold for the modulus irrespective 196 * of the ciphertext, see PKCS #1 v2.2, section 7.1.2. 197 * This does not leak any side-channel information. 198 */ 199 if (num < flen || num < 2 * mdlen + 2) { 200 RSAerror(RSA_R_OAEP_DECODING_ERROR); 201 return -1; 202 } 203 204 dblen = num - mdlen - 1; 205 if ((db = malloc(dblen)) == NULL) { 206 RSAerror(ERR_R_MALLOC_FAILURE); 207 goto cleanup; 208 } 209 if ((em = malloc(num)) == NULL) { 210 RSAerror(ERR_R_MALLOC_FAILURE); 211 goto cleanup; 212 } 213 214 /* 215 * Caller is encouraged to pass zero-padded message created with 216 * BN_bn2binpad. Trouble is that since we can't read out of |from|'s 217 * bounds, it's impossible to have an invariant memory access pattern 218 * in case |from| was not zero-padded in advance. 219 */ 220 for (from += flen, em += num, i = 0; i < num; i++) { 221 mask = ~constant_time_is_zero(flen); 222 flen -= 1 & mask; 223 from -= 1 & mask; 224 *--em = *from & mask; 225 } 226 from = em; 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(from[0]); 234 235 maskedseed = from + 1; 236 maskeddb = from + 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, tlen), dblen, tlen); 293 msg_index = constant_time_select_int(good, msg_index, dblen - tlen); 294 mlen = dblen - msg_index; 295 for (from = db + msg_index, mask = good, i = 0; i < tlen; i++) { 296 unsigned int equals = constant_time_eq(i, mlen); 297 298 from -= dblen & equals; /* if (i == mlen) rewind */ 299 mask &= mask ^ equals; /* if (i == mlen) mask = 0 */ 300 to[i] = constant_time_select_8(mask, from[i], to[i]); 301 } 302 303 /* 304 * To avoid chosen ciphertext attacks, the error message should not 305 * reveal which kind of decoding error happened. 306 */ 307 RSAerror(RSA_R_OAEP_DECODING_ERROR); 308 err_clear_last_constant_time(1 & good); 309 310 cleanup: 311 explicit_bzero(seed, sizeof(seed)); 312 freezero(db, dblen); 313 freezero(em, num); 314 315 return constant_time_select_int(good, mlen, -1); 316 } 317 318 int 319 PKCS1_MGF1(unsigned char *mask, long len, const unsigned char *seed, 320 long seedlen, const EVP_MD *dgst) 321 { 322 long i, outlen = 0; 323 unsigned char cnt[4]; 324 EVP_MD_CTX c; 325 unsigned char md[EVP_MAX_MD_SIZE]; 326 int mdlen; 327 int rv = -1; 328 329 EVP_MD_CTX_init(&c); 330 mdlen = EVP_MD_size(dgst); 331 if (mdlen < 0) 332 goto err; 333 for (i = 0; outlen < len; i++) { 334 cnt[0] = (unsigned char)((i >> 24) & 255); 335 cnt[1] = (unsigned char)((i >> 16) & 255); 336 cnt[2] = (unsigned char)((i >> 8)) & 255; 337 cnt[3] = (unsigned char)(i & 255); 338 if (!EVP_DigestInit_ex(&c, dgst, NULL) || 339 !EVP_DigestUpdate(&c, seed, seedlen) || 340 !EVP_DigestUpdate(&c, cnt, 4)) 341 goto err; 342 if (outlen + mdlen <= len) { 343 if (!EVP_DigestFinal_ex(&c, mask + outlen, NULL)) 344 goto err; 345 outlen += mdlen; 346 } else { 347 if (!EVP_DigestFinal_ex(&c, md, NULL)) 348 goto err; 349 memcpy(mask + outlen, md, len - outlen); 350 outlen = len; 351 } 352 } 353 rv = 0; 354 err: 355 EVP_MD_CTX_cleanup(&c); 356 return rv; 357 } 358