1121982Sjhb/* crypto/rsa/rsa_oaep.c */ 2121982Sjhb/* 3121982Sjhb * Written by Ulf Moeller. This software is distributed on an "AS IS" basis, 4121982Sjhb * WITHOUT WARRANTY OF ANY KIND, either express or implied. 5121982Sjhb */ 6121982Sjhb 7121982Sjhb/* EME-OAEP as defined in RFC 2437 (PKCS #1 v2.0) */ 8121982Sjhb 9121982Sjhb/* 10121982Sjhb * See Victor Shoup, "OAEP reconsidered," Nov. 2000, <URL: 11121982Sjhb * http://www.shoup.net/papers/oaep.ps.Z> for problems with the security 12121982Sjhb * proof for the original OAEP scheme, which EME-OAEP is based on. A new 13121982Sjhb * proof can be found in E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern, 14121982Sjhb * "RSA-OEAP is Still Alive!", Dec. 2000, <URL: 15121982Sjhb * http://eprint.iacr.org/2000/061/>. The new proof has stronger requirements 16121982Sjhb * for the underlying permutation: "partial-one-wayness" instead of 17121982Sjhb * one-wayness. For the RSA function, this is an equivalent notion. 18121982Sjhb */ 19121982Sjhb 20121982Sjhb#include "constant_time_locl.h" 21121982Sjhb 22121982Sjhb#if !defined(OPENSSL_NO_SHA) && !defined(OPENSSL_NO_SHA1) 23121982Sjhb# include <stdio.h> 24121982Sjhb# include "cryptlib.h" 25121982Sjhb# include <openssl/bn.h> 26121982Sjhb# include <openssl/rsa.h> 27121982Sjhb# include <openssl/evp.h> 28121982Sjhb# include <openssl/rand.h> 29121982Sjhb# include <openssl/sha.h> 30121982Sjhb 31121982Sjhbstatic int MGF1(unsigned char *mask, long len, 32121982Sjhb const unsigned char *seed, long seedlen); 33232747Sjhb 34121982Sjhbint RSA_padding_add_PKCS1_OAEP(unsigned char *to, int tlen, 35121982Sjhb const unsigned char *from, int flen, 36121982Sjhb const unsigned char *param, int plen) 37121982Sjhb{ 38121982Sjhb int i, emlen = tlen - 1; 39121982Sjhb unsigned char *db, *seed; 40232744Sjhb unsigned char *dbmask, seedmask[SHA_DIGEST_LENGTH]; 41121982Sjhb 42121982Sjhb if (flen > emlen - 2 * SHA_DIGEST_LENGTH - 1) { 43121982Sjhb RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP, 44121982Sjhb RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 45121982Sjhb return 0; 46121982Sjhb } 47121982Sjhb 48169391Sjhb if (emlen < 2 * SHA_DIGEST_LENGTH + 1) { 49121982Sjhb RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP, RSA_R_KEY_SIZE_TOO_SMALL); 50121982Sjhb return 0; 51177160Sjhb } 52121982Sjhb 53121982Sjhb to[0] = 0; 54122572Sjhb seed = to + 1; 55121982Sjhb db = to + SHA_DIGEST_LENGTH + 1; 56167273Sjhb 57121982Sjhb if (!EVP_Digest((void *)param, plen, db, NULL, EVP_sha1(), NULL)) 58121982Sjhb return 0; 59121982Sjhb memset(db + SHA_DIGEST_LENGTH, 0, 60121982Sjhb emlen - flen - 2 * SHA_DIGEST_LENGTH - 1); 61232744Sjhb db[emlen - flen - SHA_DIGEST_LENGTH - 1] = 0x01; 62232744Sjhb memcpy(db + emlen - flen - SHA_DIGEST_LENGTH, from, (unsigned int)flen); 63232744Sjhb if (RAND_bytes(seed, SHA_DIGEST_LENGTH) <= 0) 64232744Sjhb return 0; 65232744Sjhb# ifdef PKCS_TESTVECT 66233031Snyan memcpy(seed, 67233031Snyan "\xaa\xfd\x12\xf6\x59\xca\xe6\x34\x89\xb4\x79\xe5\x07\x6d\xde\xc2\xf0\x6c\xb5\x8f", 68233031Snyan 20); 69232744Sjhb# endif 70232744Sjhb 71233031Snyan dbmask = OPENSSL_malloc(emlen - SHA_DIGEST_LENGTH); 72232744Sjhb if (dbmask == NULL) { 73121982Sjhb RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP, ERR_R_MALLOC_FAILURE); 74121982Sjhb return 0; 75151658Sjhb } 76121982Sjhb 77121982Sjhb if (MGF1(dbmask, emlen - SHA_DIGEST_LENGTH, seed, SHA_DIGEST_LENGTH) < 0) 78121982Sjhb return 0; 79194985Sjhb for (i = 0; i < emlen - SHA_DIGEST_LENGTH; i++) 80169391Sjhb db[i] ^= dbmask[i]; 81246247Savg 82121982Sjhb if (MGF1(seedmask, SHA_DIGEST_LENGTH, db, emlen - SHA_DIGEST_LENGTH) < 0) 83156124Sjhb return 0; 84156124Sjhb for (i = 0; i < SHA_DIGEST_LENGTH; i++) 85156124Sjhb seed[i] ^= seedmask[i]; 86156124Sjhb 87224187Sattilio OPENSSL_free(dbmask); 88224187Sattilio return 1; 89224187Sattilio} 90224187Sattilio 91224187Sattilioint RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen, 92177181Sjhb const unsigned char *from, int flen, int num, 93177325Sjhb const unsigned char *param, int plen) 94121982Sjhb{ 95163219Sjhb int i, dblen, mlen = -1, one_index = 0, msg_index; 96121982Sjhb unsigned int good, found_one_byte; 97121982Sjhb const unsigned char *maskedseed, *maskeddb; 98121982Sjhb /* 99121982Sjhb * |em| is the encoded message, zero-padded to exactly |num| bytes: em = 100163219Sjhb * Y || maskedSeed || maskedDB 101163219Sjhb */ 102163219Sjhb unsigned char *db = NULL, *em = NULL, seed[EVP_MAX_MD_SIZE], 103163219Sjhb phash[EVP_MAX_MD_SIZE]; 104163219Sjhb 105246247Savg if (tlen <= 0 || flen <= 0) 106163219Sjhb return -1; 107163219Sjhb 108163219Sjhb /* 109163219Sjhb * |num| is the length of the modulus; |flen| is the length of the 110163219Sjhb * encoded message. Therefore, for any |from| that was obtained by 111163219Sjhb * decrypting a ciphertext, we must have |flen| <= |num|. Similarly, 112121982Sjhb * num < 2 * SHA_DIGEST_LENGTH + 2 must hold for the modulus 113163219Sjhb * irrespective of the ciphertext, see PKCS #1 v2.2, section 7.1.2. 114163219Sjhb * This does not leak any side-channel information. 115163219Sjhb */ 116163219Sjhb if (num < flen || num < 2 * SHA_DIGEST_LENGTH + 2) 117163219Sjhb goto decoding_err; 118163219Sjhb 119163219Sjhb dblen = num - SHA_DIGEST_LENGTH - 1; 120163219Sjhb db = OPENSSL_malloc(dblen); 121163219Sjhb em = OPENSSL_malloc(num); 122163219Sjhb if (db == NULL || em == NULL) { 123194985Sjhb RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP, ERR_R_MALLOC_FAILURE); 124163219Sjhb goto cleanup; 125163219Sjhb } 126163219Sjhb 127246247Savg /* 128163219Sjhb * Always do this zero-padding copy (even when num == flen) to avoid 129163219Sjhb * leaking that information. The copy still leaks some side-channel 130194985Sjhb * information, but it's impossible to have a fixed memory access 131163219Sjhb * pattern since we can't read out of the bounds of |from|. 132163219Sjhb * 133163219Sjhb * TODO(emilia): Consider porting BN_bn2bin_padded from BoringSSL. 134163219Sjhb */ 135121982Sjhb memset(em, 0, num); 136121982Sjhb memcpy(em + num - flen, from, flen); 137121982Sjhb 138121982Sjhb /* 139121982Sjhb * The first byte must be zero, however we must not leak if this is 140121982Sjhb * true. See James H. Manger, "A Chosen Ciphertext Attack on RSA 141121982Sjhb * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001). 142121982Sjhb */ 143121982Sjhb good = constant_time_is_zero(em[0]); 144163219Sjhb 145121982Sjhb maskedseed = em + 1; 146121982Sjhb maskeddb = em + 1 + SHA_DIGEST_LENGTH; 147121982Sjhb 148178092Sjeff if (MGF1(seed, SHA_DIGEST_LENGTH, maskeddb, dblen)) 149177325Sjhb goto cleanup; 150177325Sjhb for (i = 0; i < SHA_DIGEST_LENGTH; i++) 151177181Sjhb seed[i] ^= maskedseed[i]; 152121982Sjhb 153121982Sjhb if (MGF1(db, dblen, seed, SHA_DIGEST_LENGTH)) 154194985Sjhb goto cleanup; 155121982Sjhb for (i = 0; i < dblen; i++) 156194985Sjhb db[i] ^= maskeddb[i]; 157151658Sjhb 158121982Sjhb if (!EVP_Digest((void *)param, plen, phash, NULL, EVP_sha1(), NULL)) 159121982Sjhb goto cleanup; 160121982Sjhb 161121982Sjhb good &= 162169391Sjhb constant_time_is_zero(CRYPTO_memcmp(db, phash, SHA_DIGEST_LENGTH)); 163194985Sjhb 164121982Sjhb found_one_byte = 0; 165121982Sjhb for (i = SHA_DIGEST_LENGTH; i < dblen; i++) { 166121982Sjhb /* 167121982Sjhb * Padding consists of a number of 0-bytes, followed by a 1. 168121982Sjhb */ 169121982Sjhb unsigned int equals1 = constant_time_eq(db[i], 1); 170121982Sjhb unsigned int equals0 = constant_time_is_zero(db[i]); 171121982Sjhb one_index = constant_time_select_int(~found_one_byte & equals1, 172121982Sjhb i, one_index); 173121982Sjhb found_one_byte |= equals1; 174121982Sjhb good &= (found_one_byte | equals0); 175166901Spiso } 176166901Spiso 177121982Sjhb good &= found_one_byte; 178121982Sjhb 179121982Sjhb /* 180121982Sjhb * At this point |good| is zero unless the plaintext was valid, 181121982Sjhb * so plaintext-awareness ensures timing side-channels are no longer a 182121982Sjhb * concern. 183121982Sjhb */ 184166901Spiso if (!good) 185169320Spiso goto decoding_err; 186121982Sjhb 187194985Sjhb msg_index = one_index + 1; 188121982Sjhb mlen = dblen - msg_index; 189169391Sjhb 190169391Sjhb if (tlen < mlen) { 191156124Sjhb RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP, RSA_R_DATA_TOO_LARGE); 192169391Sjhb mlen = -1; 193169391Sjhb } else { 194194985Sjhb memcpy(to, db + msg_index, mlen); 195121982Sjhb goto cleanup; 196121982Sjhb } 197121982Sjhb 198121982Sjhb decoding_err: 199121982Sjhb /* 200121982Sjhb * To avoid chosen ciphertext attacks, the error message should not 201121982Sjhb * reveal which kind of decoding error happened. 202165125Sjhb */ 203121982Sjhb RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP, RSA_R_OAEP_DECODING_ERROR); 204121982Sjhb cleanup: 205165125Sjhb if (db != NULL) 206151658Sjhb OPENSSL_free(db); 207169391Sjhb if (em != NULL) 208194985Sjhb OPENSSL_free(em); 209169391Sjhb return mlen; 210169391Sjhb} 211169391Sjhb 212169391Sjhbint PKCS1_MGF1(unsigned char *mask, long len, 213169391Sjhb const unsigned char *seed, long seedlen, const EVP_MD *dgst) 214165125Sjhb{ 215194985Sjhb long i, outlen = 0; 216169391Sjhb unsigned char cnt[4]; 217121982Sjhb EVP_MD_CTX c; 218121982Sjhb unsigned char md[EVP_MAX_MD_SIZE]; 219121982Sjhb int mdlen; 220128931Sjhb int rv = -1; 221128931Sjhb 222128931Sjhb EVP_MD_CTX_init(&c); 223128931Sjhb mdlen = EVP_MD_size(dgst); 224128931Sjhb if (mdlen < 0) 225128931Sjhb goto err; 226128931Sjhb for (i = 0; outlen < len; i++) { 227128931Sjhb cnt[0] = (unsigned char)((i >> 24) & 255); 228128931Sjhb cnt[1] = (unsigned char)((i >> 16) & 255); 229128931Sjhb cnt[2] = (unsigned char)((i >> 8)) & 255; 230128931Sjhb cnt[3] = (unsigned char)(i & 255); 231177325Sjhb if (!EVP_DigestInit_ex(&c, dgst, NULL) 232177325Sjhb || !EVP_DigestUpdate(&c, seed, seedlen) 233177325Sjhb || !EVP_DigestUpdate(&c, cnt, 4)) 234177325Sjhb goto err; 235177325Sjhb if (outlen + mdlen <= len) { 236177325Sjhb if (!EVP_DigestFinal_ex(&c, mask + outlen, NULL)) 237177325Sjhb goto err; 238177325Sjhb outlen += mdlen; 239177325Sjhb } else { 240121982Sjhb if (!EVP_DigestFinal_ex(&c, md, NULL)) 241153146Sjhb goto err; 242121982Sjhb memcpy(mask + outlen, md, len - outlen); 243177940Sjhb outlen = len; 244169320Spiso } 245169320Spiso } 246169320Spiso rv = 0; 247169320Spiso err: 248169320Spiso EVP_MD_CTX_cleanup(&c); 249169320Spiso return rv; 250169320Spiso} 251169320Spiso 252169320Spisostatic int MGF1(unsigned char *mask, long len, const unsigned char *seed, 253170291Sattilio long seedlen) 254169320Spiso{ 255169320Spiso return PKCS1_MGF1(mask, len, seed, seedlen, EVP_sha1()); 256169320Spiso} 257169320Spiso#endif 258169320Spiso