RT3066: rewrite RSA padding checks to be slightly more constant time.

[openssl.git] / crypto / rsa / rsa_oaep.c

diff --git a/crypto/rsa/rsa_oaep.c b/crypto/rsa/rsa_oaep.c
index 882c7c582e9ff80c87f1428886e512bb912e2eda..18ee6f4b88ef0e9820451132314b00662e0a6ee2 100644 (file)
--- a/crypto/rsa/rsa_oaep.c
+++ b/crypto/rsa/rsa_oaep.c
@@ -20,6 +20,7 @@
 
 #define OPENSSL_FIPSAPI
 
 
 #define OPENSSL_FIPSAPI
 

+#include "../constant_time_locl.h"

 
 #if !defined(OPENSSL_NO_SHA) && !defined(OPENSSL_NO_SHA1)
 #include <stdio.h>
 
 #if !defined(OPENSSL_NO_SHA) && !defined(OPENSSL_NO_SHA1)
 #include <stdio.h>


@@ -121,12 +122,13 @@ int RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen,
        const unsigned char *param, int plen,
        const EVP_MD *md, const EVP_MD *mgf1md)
        {
        const unsigned char *param, int plen,
        const EVP_MD *md, const EVP_MD *mgf1md)
        {

-       int i, dblen, mlen = -1;
-       const unsigned char *maskeddb;
-       int lzero;
-       unsigned char *db = NULL, seed[EVP_MAX_MD_SIZE], phash[EVP_MAX_MD_SIZE];
-       unsigned char *padded_from;
-       int bad = 0;
+       int i, dblen, mlen = -1, one_index = 0, msg_index;
+       unsigned int good, found_one_byte;
+       const unsigned char *maskedseed, *maskeddb;
+       /* |em| is the encoded message, zero-padded to exactly |num| bytes:
+        * em = Y || maskedSeed || maskedDB */
+       unsigned char *db = NULL, *em = NULL, seed[EVP_MAX_MD_SIZE],
+               phash[EVP_MAX_MD_SIZE];

        int mdlen;
 
        if (md == NULL)
        int mdlen;
 
        if (md == NULL)


@@ -136,85 +138,108 @@ int RSA_padding_check_PKCS1_OAEP_mgf1(unsigned char *to, int tlen,
 
        mdlen = EVP_MD_size(md);
 
 
        mdlen = EVP_MD_size(md);
 

-       if (--num < 2 * mdlen + 1)
-               /* 'num' is the length of the modulus, i.e. does not depend on the
-                * particular ciphertext. */
+        if (tlen <= 0 || flen <= 0)
+               return -1;
+       /*
+        * |num| is the length of the modulus; |flen| is the length of the
+        * encoded message. Therefore, for any |from| that was obtained by
+        * decrypting a ciphertext, we must have |flen| <= |num|. Similarly,
+        * num < 2 * mdlen + 2 must hold for the modulus irrespective of
+        * the ciphertext, see PKCS #1 v2.2, section 7.1.2.
+        * This does not leak any side-channel information.
+        */
+       if (num < flen || num < 2 * mdlen + 2)

                goto decoding_err;
 
                goto decoding_err;
 

-       lzero = num - flen;
-       if (lzero < 0)
-               {
-               /* signalling this error immediately after detection might allow
-                * for side-channel attacks (e.g. timing if 'plen' is huge
-                * -- cf. James H. Manger, "A Chosen Ciphertext Attack on RSA Optimal
-                * Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001),
-                * so we use a 'bad' flag */
-               bad = 1;
-               lzero = 0;
-               flen = num; /* don't overflow the memcpy to padded_from */
-               }
-
-       dblen = num - mdlen;
-       db = OPENSSL_malloc(dblen + num);
-       if (db == NULL)
+       dblen = num - mdlen - 1;
+       db = OPENSSL_malloc(dblen);
+       em = OPENSSL_malloc(num);
+       if (db == NULL || em == NULL)

                {
                RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, ERR_R_MALLOC_FAILURE);
                {
                RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, ERR_R_MALLOC_FAILURE);

-               return -1;
+               goto cleanup;

                }
 
                }
 

-       /* Always do this zero-padding copy (even when lzero == 0)
-        * to avoid leaking timing info about the value of lzero. */
-       padded_from = db + dblen;
-       memset(padded_from, 0, lzero);
-       memcpy(padded_from + lzero, from, flen);
-
-       maskeddb = padded_from + mdlen;
+       /*
+        * Always do this zero-padding copy (even when num == flen) to avoid
+        * leaking that information. The copy still leaks some side-channel
+        * information, but it's impossible to have a fixed  memory access
+        * pattern since we can't read out of the bounds of |from|.
+        *
+        * TODO(emilia): Consider porting BN_bn2bin_padded from BoringSSL.
+        */
+       memset(em, 0, num);
+       memcpy(em + num - flen, from, flen);
+
+       /*
+        * The first byte must be zero, however we must not leak if this is
+        * true. See James H. Manger, "A Chosen Ciphertext  Attack on RSA
+        * Optimal Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001).
+        */
+       good = constant_time_is_zero(em[0]);
+
+       maskedseed = em + 1;
+       maskeddb = em + 1 + mdlen;

 
        if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md))
 
        if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md))

-               return -1;
+               goto cleanup;

        for (i = 0; i < mdlen; i++)
        for (i = 0; i < mdlen; i++)

-               seed[i] ^= padded_from[i];
-  
+               seed[i] ^= maskedseed[i];
+

        if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md))
        if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md))

-               return -1;
+               goto cleanup;

        for (i = 0; i < dblen; i++)
                db[i] ^= maskeddb[i];
 
        if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL))
        for (i = 0; i < dblen; i++)
                db[i] ^= maskeddb[i];
 
        if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL))

-               return -1;
+               goto cleanup;
+
+       good &= constant_time_is_zero(CRYPTO_memcmp(db, phash, mdlen));
+
+       found_one_byte = 0;
+       for (i = mdlen; i < dblen; i++)
+               {
+               /* Padding consists of a number of 0-bytes, followed by a 1. */
+               unsigned int equals1 = constant_time_eq(db[i], 1);
+               unsigned int equals0 = constant_time_is_zero(db[i]);
+               one_index = constant_time_select_int(~found_one_byte & equals1,
+                       i, one_index);
+               found_one_byte |= equals1;
+               good &= (found_one_byte | equals0);
+               }
+
+       good &= found_one_byte;

 
 

-       if (CRYPTO_memcmp(db, phash, mdlen) != 0 || bad)
+       /*
+        * At this point |good| is zero unless the plaintext was valid,
+        * so plaintext-awareness ensures timing side-channels are no longer a
+        * concern.
+        */
+       if (!good)

                goto decoding_err;
                goto decoding_err;

+
+       msg_index = one_index + 1;
+       mlen = dblen - msg_index;
+
+       if (tlen < mlen)
+               {
+               RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, RSA_R_DATA_TOO_LARGE);
+               mlen = -1;
+               }

        else
                {
        else
                {

-               for (i = mdlen; i < dblen; i++)
-                       if (db[i] != 0x00)
-                               break;
-               if (i == dblen || db[i] != 0x01)
-                       goto decoding_err;
-               else
-                       {
-                       /* everything looks OK */
-
-                       mlen = dblen - ++i;
-                       if (tlen < mlen)
-                               {
-                               RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, RSA_R_DATA_TOO_LARGE);
-                               mlen = -1;
-                               }
-                       else
-                               memcpy(to, db + i, mlen);
-                       }
+               memcpy(to, db + msg_index, mlen);
+               goto cleanup;

                }
                }

-       OPENSSL_free(db);
-       return mlen;

 
 decoding_err:
 
 decoding_err:

-       /* to avoid chosen ciphertext attacks, the error message should not reveal
-        * which kind of decoding error happened */
+       /* To avoid chosen ciphertext attacks, the error message should not reveal
+        * which kind of decoding error happened. */

        RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, RSA_R_OAEP_DECODING_ERROR);
        RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_OAEP_MGF1, RSA_R_OAEP_DECODING_ERROR);

+cleanup:

        if (db != NULL) OPENSSL_free(db);
        if (db != NULL) OPENSSL_free(db);

-       return -1;
+       if (em != NULL) OPENSSL_free(em);
+       return mlen;

        }
 
 int PKCS1_MGF1(unsigned char *mask, long len,
        }
 
 int PKCS1_MGF1(unsigned char *mask, long len,