rsa_oaep.c revision 344604
1/* crypto/rsa/rsa_oaep.c */ 2/* 3 * Written by Ulf Moeller. This software is distributed on an "AS IS" basis, 4 * WITHOUT WARRANTY OF ANY KIND, either express or implied. 5 */ 6 7/* EME-OAEP as defined in RFC 2437 (PKCS #1 v2.0) */ 8 9/* 10 * See Victor Shoup, "OAEP reconsidered," Nov. 2000, <URL: 11 * http://www.shoup.net/papers/oaep.ps.Z> for problems with the security 12 * proof for the original OAEP scheme, which EME-OAEP is based on. A new 13 * proof can be found in E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern, 14 * "RSA-OEAP is Still Alive!", Dec. 2000, <URL: 15 * http://eprint.iacr.org/2000/061/>. The new proof has stronger requirements 16 * for the underlying permutation: "partial-one-wayness" instead of 17 * one-wayness. For the RSA function, this is an equivalent notion. 18 */ 19 20#include "constant_time_locl.h" 21 22#if !defined(OPENSSL_NO_SHA) && !defined(OPENSSL_NO_SHA1) 23# include <stdio.h> 24# include "cryptlib.h" 25# include <openssl/bn.h> 26# include <openssl/rsa.h> 27# include <openssl/evp.h> 28# include <openssl/rand.h> 29# include <openssl/sha.h> 30 31int RSA_padding_add_PKCS1_OAEP(unsigned char *to, int tlen, 32 const unsigned char *from, int flen, 33 const unsigned char *param, int plen) 34{ 35 return RSA_padding_add_PKCS1_OAEP_mgf1(to, tlen, from, flen, 36 param, plen, NULL, NULL); 37} 38 39int RSA_padding_add_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 40 const unsigned char *from, int flen, 41 const unsigned char *param, int plen, 42 const EVP_MD *md, const EVP_MD *mgf1md) 43{ 44 int i, emlen = tlen - 1; 45 unsigned char *db, *seed; 46 unsigned char *dbmask, seedmask[EVP_MAX_MD_SIZE]; 47 int mdlen; 48 49 if (md == NULL) 50 md = EVP_sha1(); 51 if (mgf1md == NULL) 52 mgf1md = md; 53 54 mdlen = EVP_MD_size(md); 55 56 if (flen > emlen - 2 * mdlen - 1) { 57 RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP_MGF1, 58 RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 59 return 0; 60 } 61 62 if (emlen < 2 * mdlen + 1) { 63 RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP_MGF1, 64 RSA_R_KEY_SIZE_TOO_SMALL); 65 return 0; 66 } 67 68 to[0] = 0; 69 seed = to + 1; 70 db = to + mdlen + 1; 71 72 if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL)) 73 return 0; 74 memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1); 75 db[emlen - flen - mdlen - 1] = 0x01; 76 memcpy(db + emlen - flen - mdlen, from, (unsigned int)flen); 77 if (RAND_bytes(seed, mdlen) <= 0) 78 return 0; 79# ifdef PKCS_TESTVECT 80 memcpy(seed, 81 "\xaa\xfd\x12\xf6\x59\xca\xe6\x34\x89\xb4\x79\xe5\x07\x6d\xde\xc2\xf0\x6c\xb5\x8f", 82 20); 83# endif 84 85 dbmask = OPENSSL_malloc(emlen - mdlen); 86 if (dbmask == NULL) { 87 RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP_MGF1, ERR_R_MALLOC_FAILURE); 88 return 0; 89 } 90 91 if (PKCS1_MGF1(dbmask, emlen - mdlen, seed, mdlen, mgf1md) < 0) 92 goto err; 93 for (i = 0; i < emlen - mdlen; i++) 94 db[i] ^= dbmask[i]; 95 96 if (PKCS1_MGF1(seedmask, mdlen, db, emlen - mdlen, mgf1md) < 0) 97 goto err; 98 for (i = 0; i < mdlen; i++) 99 seed[i] ^= seedmask[i]; 100 101 OPENSSL_free(dbmask); 102 return 1; 103 104 err: 105 OPENSSL_free(dbmask); 106 return 0; 107} 108 109int RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen, 110 const unsigned char *from, int flen, int num, 111 const unsigned char *param, int plen) 112{ 113 return RSA_padding_check_PKCS1_OAEP_mgf1(to, tlen, from, flen, num, 114 param, plen, NULL, NULL); 115} 116 117int RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen, 118 const unsigned char *from, int flen, 119 int num, const unsigned char *param, 120 int plen, const EVP_MD *md, 121 const EVP_MD *mgf1md) 122{ 123 int i, dblen = 0, mlen = -1, one_index = 0, msg_index; 124 unsigned int good = 0, found_one_byte, mask; 125 const unsigned char *maskedseed, *maskeddb; 126 /* 127 * |em| is the encoded message, zero-padded to exactly |num| bytes: em = 128 * Y || maskedSeed || maskedDB 129 */ 130 unsigned char *db = NULL, *em = NULL, seed[EVP_MAX_MD_SIZE], 131 phash[EVP_MAX_MD_SIZE]; 132 int mdlen; 133 134 if (md == NULL) 135 md = EVP_sha1(); 136 if (mgf1md == NULL) 137 mgf1md = md; 138 139 mdlen = EVP_MD_size(md); 140 141 if (tlen <= 0 || flen <= 0) 142 return -1; 143 /* 144 * |num| is the length of the modulus; |flen| is the length of the 145 * encoded message. Therefore, for any |from| that was obtained by 146 * decrypting a ciphertext, we must have |flen| <= |num|. Similarly, 147 * num < 2 * mdlen + 2 must hold for the modulus irrespective of 148 * the ciphertext, see PKCS #1 v2.2, section 7.1.2. 149 * This does not leak any side-channel information. 150 */ 151 if (num < flen || num < 2 * mdlen + 2) { 152 RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, 153 RSA_R_OAEP_DECODING_ERROR); 154 return -1; 155 } 156 157 dblen = num - mdlen - 1; 158 db = OPENSSL_malloc(dblen); 159 if (db == NULL) { 160 RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, ERR_R_MALLOC_FAILURE); 161 goto cleanup; 162 } 163 164 em = OPENSSL_malloc(num); 165 if (em == NULL) { 166 RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, 167 ERR_R_MALLOC_FAILURE); 168 goto cleanup; 169 } 170 171 /* 172 * Caller is encouraged to pass zero-padded message created with 173 * BN_bn2binpad. Trouble is that since we can't read out of |from|'s 174 * bounds, it's impossible to have an invariant memory access pattern 175 * in case |from| was not zero-padded in advance. 176 */ 177 for (from += flen, em += num, i = 0; i < num; i++) { 178 mask = ~constant_time_is_zero(flen); 179 flen -= 1 & mask; 180 from -= 1 & mask; 181 *--em = *from & mask; 182 } 183 from = em; 184 185 /* 186 * The first byte must be zero, however we must not leak if this is 187 * true. See James H. Manger, "A Chosen Ciphertext Attack on RSA 188 * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001). 189 */ 190 good = constant_time_is_zero(from[0]); 191 192 maskedseed = from + 1; 193 maskeddb = from + 1 + mdlen; 194 195 if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md)) 196 goto cleanup; 197 for (i = 0; i < mdlen; i++) 198 seed[i] ^= maskedseed[i]; 199 200 if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md)) 201 goto cleanup; 202 for (i = 0; i < dblen; i++) 203 db[i] ^= maskeddb[i]; 204 205 if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL)) 206 goto cleanup; 207 208 good &= constant_time_is_zero(CRYPTO_memcmp(db, phash, mdlen)); 209 210 found_one_byte = 0; 211 for (i = mdlen; i < dblen; i++) { 212 /* 213 * Padding consists of a number of 0-bytes, followed by a 1. 214 */ 215 unsigned int equals1 = constant_time_eq(db[i], 1); 216 unsigned int equals0 = constant_time_is_zero(db[i]); 217 one_index = constant_time_select_int(~found_one_byte & equals1, 218 i, one_index); 219 found_one_byte |= equals1; 220 good &= (found_one_byte | equals0); 221 } 222 223 good &= found_one_byte; 224 225 /* 226 * At this point |good| is zero unless the plaintext was valid, 227 * so plaintext-awareness ensures timing side-channels are no longer a 228 * concern. 229 */ 230 msg_index = one_index + 1; 231 mlen = dblen - msg_index; 232 233 /* 234 * For good measure, do this check in constant tine as well. 235 */ 236 good &= constant_time_ge(tlen, mlen); 237 238 /* 239 * Even though we can't fake result's length, we can pretend copying 240 * |tlen| bytes where |mlen| bytes would be real. Last |tlen| of |dblen| 241 * bytes are viewed as circular buffer with start at |tlen|-|mlen'|, 242 * where |mlen'| is "saturated" |mlen| value. Deducing information 243 * about failure or |mlen| would take attacker's ability to observe 244 * memory access pattern with byte granularity *as it occurs*. It 245 * should be noted that failure is indistinguishable from normal 246 * operation if |tlen| is fixed by protocol. 247 */ 248 tlen = constant_time_select_int(constant_time_lt(dblen, tlen), dblen, tlen); 249 msg_index = constant_time_select_int(good, msg_index, dblen - tlen); 250 mlen = dblen - msg_index; 251 for (from = db + msg_index, mask = good, i = 0; i < tlen; i++) { 252 unsigned int equals = constant_time_eq(i, mlen); 253 254 from -= dblen & equals; /* if (i == dblen) rewind */ 255 mask &= mask ^ equals; /* if (i == dblen) mask = 0 */ 256 to[i] = constant_time_select_8(mask, from[i], to[i]); 257 } 258 259 /* 260 * To avoid chosen ciphertext attacks, the error message should not 261 * reveal which kind of decoding error happened. 262 */ 263 RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, 264 RSA_R_OAEP_DECODING_ERROR); 265 err_clear_last_constant_time(1 & good); 266 cleanup: 267 OPENSSL_cleanse(seed, sizeof(seed)); 268 OPENSSL_cleanse(db, dblen); 269 OPENSSL_free(db); 270 OPENSSL_cleanse(em, num); 271 OPENSSL_free(em); 272 273 return constant_time_select_int(good, mlen, -1); 274} 275 276int PKCS1_MGF1(unsigned char *mask, long len, 277 const unsigned char *seed, long seedlen, const EVP_MD *dgst) 278{ 279 long i, outlen = 0; 280 unsigned char cnt[4]; 281 EVP_MD_CTX c; 282 unsigned char md[EVP_MAX_MD_SIZE]; 283 int mdlen; 284 int rv = -1; 285 286 EVP_MD_CTX_init(&c); 287 mdlen = EVP_MD_size(dgst); 288 if (mdlen < 0) 289 goto err; 290 for (i = 0; outlen < len; i++) { 291 cnt[0] = (unsigned char)((i >> 24) & 255); 292 cnt[1] = (unsigned char)((i >> 16) & 255); 293 cnt[2] = (unsigned char)((i >> 8)) & 255; 294 cnt[3] = (unsigned char)(i & 255); 295 if (!EVP_DigestInit_ex(&c, dgst, NULL) 296 || !EVP_DigestUpdate(&c, seed, seedlen) 297 || !EVP_DigestUpdate(&c, cnt, 4)) 298 goto err; 299 if (outlen + mdlen <= len) { 300 if (!EVP_DigestFinal_ex(&c, mask + outlen, NULL)) 301 goto err; 302 outlen += mdlen; 303 } else { 304 if (!EVP_DigestFinal_ex(&c, md, NULL)) 305 goto err; 306 memcpy(mask + outlen, md, len - outlen); 307 outlen = len; 308 } 309 } 310 rv = 0; 311 err: 312 EVP_MD_CTX_cleanup(&c); 313 return rv; 314} 315 316#endif 317