crypto/rsa/rsa_oaep.c

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