crypto/rsa/rsa_oaep.c

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