crypto/rsa/rsa_oaep.c

   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 "internal/constant_time_locl.h"
  21
  22 #include <stdio.h>
  23 #include "internal/cryptlib.h"
  24 #include <openssl/bn.h>
  25 #include <openssl/rsa.h>
  26 #include <openssl/evp.h>
  27 #include <openssl/rand.h>
  28 #include <openssl/sha.h>
  29
  30 int RSA_padding_add_PKCS1_OAEP(unsigned char *to, int tlen,
  31                                const unsigned char *from, int flen,
  32                                const unsigned char *param, int plen)
  33 {
  34     return RSA_padding_add_PKCS1_OAEP_mgf1(to, tlen, from, flen,
  35                                            param, plen, NULL, NULL);
  36 }
  37
  38 int RSA_padding_add_PKCS1_OAEP_mgf1(unsigned char *to, int tlen,
  39                                     const unsigned char *from, int flen,
  40                                     const unsigned char *param, int plen,
  41                                     const EVP_MD *md, const EVP_MD *mgf1md)
  42 {
  43     int i, emlen = tlen - 1;
  44     unsigned char *db, *seed;
  45     unsigned char *dbmask, seedmask[EVP_MAX_MD_SIZE];
  46     int mdlen;
  47
  48     if (md == NULL)
  49         md = EVP_sha1();
  50     if (mgf1md == NULL)
  51         mgf1md = md;
  52
  53     mdlen = EVP_MD_size(md);
  54
  55     if (flen > emlen - 2 * mdlen - 1) {
  56         RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP_MGF1,
  57                RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
  58         return 0;
  59     }
  60
  61     if (emlen < 2 * mdlen + 1) {
  62         RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP_MGF1,
  63                RSA_R_KEY_SIZE_TOO_SMALL);
  64         return 0;
  65     }
  66
  67     to[0] = 0;
  68     seed = to + 1;
  69     db = to + mdlen + 1;
  70
  71     if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL))
  72         return 0;
  73     memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1);
  74     db[emlen - flen - mdlen - 1] = 0x01;
  75     memcpy(db + emlen - flen - mdlen, from, (unsigned int)flen);
  76     if (RAND_bytes(seed, mdlen) <= 0)
  77         return 0;
  78 #ifdef PKCS_TESTVECT
  79     memcpy(seed,
  80            "\xaa\xfd\x12\xf6\x59\xca\xe6\x34\x89\xb4\x79\xe5\x07\x6d\xde\xc2\xf0\x6c\xb5\x8f",
  81            20);
  82 #endif
  83
  84     dbmask = OPENSSL_malloc(emlen - mdlen);
  85     if (dbmask == NULL) {
  86         RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_OAEP_MGF1, ERR_R_MALLOC_FAILURE);
  87         return 0;
  88     }
  89
  90     if (PKCS1_MGF1(dbmask, emlen - mdlen, seed, mdlen, mgf1md) < 0)
  91         return 0;
  92     for (i = 0; i < emlen - mdlen; i++)
  93         db[i] ^= dbmask[i];
  94
  95     if (PKCS1_MGF1(seedmask, mdlen, db, emlen - mdlen, mgf1md) < 0)
  96         return 0;
  97     for (i = 0; i < mdlen; i++)
  98         seed[i] ^= seedmask[i];
  99
 100     OPENSSL_free(dbmask);
 101     return 1;
 102 }
 103
 104 int RSA_padding_check_PKCS1_OAEP(unsigned char *to, int tlen,
 105                                  const unsigned char *from, int flen, int num,
 106                                  const unsigned char *param, int plen)
 107 {
 108     return RSA_padding_check_PKCS1_OAEP_mgf1(to, tlen, from, flen, num,
 109                                              param, plen, NULL, NULL);
 110 }
 111
 112 int RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen,
 113                                       const unsigned char *from, int flen,
 114                                       int num, const unsigned char *param,
 115                                       int plen, const EVP_MD *md,
 116                                       const EVP_MD *mgf1md)
 117 {
 118     int i, dblen, mlen = -1, one_index = 0, msg_index;
 119     unsigned int good, found_one_byte;
 120     const unsigned char *maskedseed, *maskeddb;
 121     /*
 122      * |em| is the encoded message, zero-padded to exactly |num| bytes: em =
 123      * Y || maskedSeed || maskedDB
 124      */
 125     unsigned char *db = NULL, *em = NULL, seed[EVP_MAX_MD_SIZE],
 126         phash[EVP_MAX_MD_SIZE];
 127     int mdlen;
 128
 129     if (md == NULL)
 130         md = EVP_sha1();
 131     if (mgf1md == NULL)
 132         mgf1md = md;
 133
 134     mdlen = EVP_MD_size(md);
 135
 136     if (tlen <= 0 || flen <= 0)
 137         return -1;
 138     /*
 139      * |num| is the length of the modulus; |flen| is the length of the
 140      * encoded message. Therefore, for any |from| that was obtained by
 141      * decrypting a ciphertext, we must have |flen| <= |num|. Similarly,
 142      * num < 2 * mdlen + 2 must hold for the modulus irrespective of
 143      * the ciphertext, see PKCS #1 v2.2, section 7.1.2.
 144      * This does not leak any side-channel information.
 145      */
 146     if (num < flen || num < 2 * mdlen + 2)
 147         goto decoding_err;
 148
 149     dblen = num - mdlen - 1;
 150     db = OPENSSL_malloc(dblen);
 151     em = OPENSSL_malloc(num);
 152     if (db == NULL || em == NULL) {
 153         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, ERR_R_MALLOC_FAILURE);
 154         goto cleanup;
 155     }
 156
 157     /*
 158      * Always do this zero-padding copy (even when num == flen) to avoid
 159      * leaking that information. The copy still leaks some side-channel
 160      * information, but it's impossible to have a fixed  memory access
 161      * pattern since we can't read out of the bounds of |from|.
 162      *
 163      * TODO(emilia): Consider porting BN_bn2bin_padded from BoringSSL.
 164      */
 165     memset(em, 0, num);
 166     memcpy(em + num - flen, from, flen);
 167
 168     /*
 169      * The first byte must be zero, however we must not leak if this is
 170      * true. See James H. Manger, "A Chosen Ciphertext  Attack on RSA
 171      * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001).
 172      */
 173     good = constant_time_is_zero(em[0]);
 174
 175     maskedseed = em + 1;
 176     maskeddb = em + 1 + mdlen;
 177
 178     if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md))
 179         goto cleanup;
 180     for (i = 0; i < mdlen; i++)
 181         seed[i] ^= maskedseed[i];
 182
 183     if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md))
 184         goto cleanup;
 185     for (i = 0; i < dblen; i++)
 186         db[i] ^= maskeddb[i];
 187
 188     if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL))
 189         goto cleanup;
 190
 191     good &= constant_time_is_zero(CRYPTO_memcmp(db, phash, mdlen));
 192
 193     found_one_byte = 0;
 194     for (i = mdlen; i < dblen; i++) {
 195         /*
 196          * Padding consists of a number of 0-bytes, followed by a 1.
 197          */
 198         unsigned int equals1 = constant_time_eq(db[i], 1);
 199         unsigned int equals0 = constant_time_is_zero(db[i]);
 200         one_index = constant_time_select_int(~found_one_byte & equals1,
 201                                              i, one_index);
 202         found_one_byte |= equals1;
 203         good &= (found_one_byte | equals0);
 204     }
 205
 206     good &= found_one_byte;
 207
 208     /*
 209      * At this point |good| is zero unless the plaintext was valid,
 210      * so plaintext-awareness ensures timing side-channels are no longer a
 211      * concern.
 212      */
 213     if (!good)
 214         goto decoding_err;
 215
 216     msg_index = one_index + 1;
 217     mlen = dblen - msg_index;
 218
 219     if (tlen < mlen) {
 220         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, RSA_R_DATA_TOO_LARGE);
 221         mlen = -1;
 222     } else {
 223         memcpy(to, db + msg_index, mlen);
 224         goto cleanup;
 225     }
 226
 227  decoding_err:
 228     /*
 229      * To avoid chosen ciphertext attacks, the error message should not
 230      * reveal which kind of decoding error happened.
 231      */
 232     RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1,
 233            RSA_R_OAEP_DECODING_ERROR);
 234  cleanup:
 235     OPENSSL_free(db);
 236     OPENSSL_free(em);
 237     return mlen;
 238 }
 239
 240 int PKCS1_MGF1(unsigned char *mask, long len,
 241                const unsigned char *seed, long seedlen, const EVP_MD *dgst)
 242 {
 243     long i, outlen = 0;
 244     unsigned char cnt[4];
 245     EVP_MD_CTX c;
 246     unsigned char md[EVP_MAX_MD_SIZE];
 247     int mdlen;
 248     int rv = -1;
 249
 250     EVP_MD_CTX_init(&c);
 251     mdlen = M_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_cleanup(&c);
 277     return rv;
 278 }