Left-pad messages when doing "unpadded" RSA operations.

When RSA messages that are shorter than the key size, and padding is not
applied, BoringSSL (sensbibly) refuses, because odds are very high that
the caller is doing something dumb.  However, this causes some (dumb)
things that used to work to no longer work.

This CL also fixes the error code returned when a message is signed or
encrypted which is the same length as the public modulus but is
numerically larger than or equal to the public modulus.  Rather than
KM_ERROR_UNKNOWN_ERROR, it now returns KM_ERROR_INVALID_ARGUMENT.

Bug: 22599805
Change-Id: I99aca5516b092f3676ffdc6c5de39f2777e3d275

3 files changed, 125 insertions, 34 deletions

diff --git a/android_keymaster_test.cpp b/android_keymaster_test.cpp
index 479a2e6..af829e6 100644
--- a/android_keymaster_test.cpp
+++ b/android_keymaster_test.cpp
@@ -26,6 +26,7 @@
 
 #include "android_keymaster_test_utils.h"
 #include "keymaster0_engine.h"
+#include "openssl_utils.h"
 
 using std::ifstream;
 using std::istreambuf_iterator;
@@ -701,24 +702,12 @@ TEST_P(SigningOperationsTest, RsaTooShortMessage) {
                                            .RsaSigningKey(256, 3)
                                            .Digest(KM_DIGEST_NONE)
                                            .Padding(KM_PAD_NONE)));
-    AuthorizationSet begin_params(client_params());
-    begin_params.push_back(TAG_DIGEST, KM_DIGEST_NONE);
-    begin_params.push_back(TAG_PADDING, KM_PAD_NONE);
-    ASSERT_EQ(KM_ERROR_OK, BeginOperation(KM_PURPOSE_SIGN, begin_params));
-
     string message = "1234567890123456789012345678901";
-    string result;
-    size_t input_consumed;
-    ASSERT_EQ(KM_ERROR_OK, UpdateOperation(message, &result, &input_consumed));
-    EXPECT_EQ(0U, result.size());
-    EXPECT_EQ(31U, input_consumed);
-
     string signature;
-    ASSERT_EQ(KM_ERROR_INVALID_INPUT_LENGTH, FinishOperation(&signature));
-    EXPECT_EQ(0U, signature.length());
+    SignMessage(message, &signature, KM_DIGEST_NONE, KM_PAD_NONE);
 
     if (GetParam()->algorithm_in_hardware(KM_ALGORITHM_RSA))
-        EXPECT_EQ(2, GetParam()->keymaster0_calls());
+        EXPECT_EQ(3, GetParam()->keymaster0_calls());
 }
 
 TEST_P(SigningOperationsTest, RsaSignWithEncryptionKey) {
@@ -1897,7 +1886,25 @@ TEST_P(EncryptionOperationsTest, RsaNoPaddingTooShort) {
     ASSERT_EQ(KM_ERROR_OK,
               GenerateKey(AuthorizationSetBuilder().RsaEncryptionKey(256, 3).Padding(KM_PAD_NONE)));
 
-    string message = "1234567890123456789012345678901";
+    string message = "1";
+
+    string ciphertext = EncryptMessage(message, KM_PAD_NONE);
+    EXPECT_EQ(256U / 8, ciphertext.size());
+
+    string expected_plaintext = string(256 / 8 - 1, 0) + message;
+    string plaintext = DecryptMessage(ciphertext, KM_PAD_NONE);
+
+    EXPECT_EQ(expected_plaintext, plaintext);
+
+    if (GetParam()->algorithm_in_hardware(KM_ALGORITHM_RSA))
+        EXPECT_EQ(4, GetParam()->keymaster0_calls());
+}
+
+TEST_P(EncryptionOperationsTest, RsaNoPaddingTooLong) {
+    ASSERT_EQ(KM_ERROR_OK,
+              GenerateKey(AuthorizationSetBuilder().RsaEncryptionKey(256, 3).Padding(KM_PAD_NONE)));
+
+    string message = "123456789012345678901234567890123";
 
     AuthorizationSet begin_params(client_params());
     begin_params.push_back(TAG_PADDING, KM_PAD_NONE);
@@ -1905,19 +1912,31 @@ TEST_P(EncryptionOperationsTest, RsaNoPaddingTooShort) {
 
     string result;
     size_t input_consumed;
-    EXPECT_EQ(KM_ERROR_OK, UpdateOperation(message, &result, &input_consumed));
-    EXPECT_EQ(KM_ERROR_INVALID_INPUT_LENGTH, FinishOperation(&result));
-    EXPECT_EQ(0U, result.size());
+    EXPECT_EQ(KM_ERROR_INVALID_INPUT_LENGTH, UpdateOperation(message, &result, &input_consumed));
 
     if (GetParam()->algorithm_in_hardware(KM_ALGORITHM_RSA))
         EXPECT_EQ(2, GetParam()->keymaster0_calls());
 }
 
-TEST_P(EncryptionOperationsTest, RsaNoPaddingTooLong) {
+TEST_P(EncryptionOperationsTest, RsaNoPaddingLargerThanModulus) {
     ASSERT_EQ(KM_ERROR_OK,
               GenerateKey(AuthorizationSetBuilder().RsaEncryptionKey(256, 3).Padding(KM_PAD_NONE)));
 
-    string message = "123456789012345678901234567890123";
+    string exported;
+    ASSERT_EQ(KM_ERROR_OK, ExportKey(KM_KEY_FORMAT_X509, &exported));
+
+    const uint8_t* p = reinterpret_cast<const uint8_t*>(exported.data());
+    unique_ptr<EVP_PKEY, EVP_PKEY_Delete> pkey(
+        d2i_PUBKEY(nullptr /* alloc new */, &p, exported.size()));
+    unique_ptr<RSA, RSA_Delete> rsa(EVP_PKEY_get1_RSA(pkey.get()));
+
+    size_t modulus_len = BN_num_bytes(rsa->n);
+    ASSERT_EQ(256U / 8, modulus_len);
+    unique_ptr<uint8_t> modulus_buf(new uint8_t[modulus_len]);
+    BN_bn2bin(rsa->n, modulus_buf.get());
+
+    // The modulus is too big to encrypt.
+    string message(reinterpret_cast<const char*>(modulus_buf.get()), modulus_len);
 
     AuthorizationSet begin_params(client_params());
     begin_params.push_back(TAG_PADDING, KM_PAD_NONE);
@@ -1925,10 +1944,21 @@ TEST_P(EncryptionOperationsTest, RsaNoPaddingTooLong) {
 
     string result;
     size_t input_consumed;
-    EXPECT_EQ(KM_ERROR_INVALID_INPUT_LENGTH, UpdateOperation(message, &result, &input_consumed));
+    EXPECT_EQ(KM_ERROR_OK, UpdateOperation(message, &result, &input_consumed));
+    EXPECT_EQ(KM_ERROR_INVALID_ARGUMENT, FinishOperation(&result));
+
+    // One smaller than the modulus is okay.
+    BN_sub(rsa->n, rsa->n, BN_value_one());
+    modulus_len = BN_num_bytes(rsa->n);
+    ASSERT_EQ(256U / 8, modulus_len);
+    BN_bn2bin(rsa->n, modulus_buf.get());
+    message = string(reinterpret_cast<const char*>(modulus_buf.get()), modulus_len);
+    EXPECT_EQ(KM_ERROR_OK, BeginOperation(KM_PURPOSE_ENCRYPT, begin_params));
+    EXPECT_EQ(KM_ERROR_OK, UpdateOperation(message, &result, &input_consumed));
+    EXPECT_EQ(KM_ERROR_OK, FinishOperation(&result));
 
     if (GetParam()->algorithm_in_hardware(KM_ALGORITHM_RSA))
-        EXPECT_EQ(2, GetParam()->keymaster0_calls());
+        EXPECT_EQ(4, GetParam()->keymaster0_calls());
 }
 
 TEST_P(EncryptionOperationsTest, RsaOaepSuccess) {
diff --git a/openssl_err.cpp b/openssl_err.cpp
index 2548d5c..51a29d9 100644
--- a/openssl_err.cpp
+++ b/openssl_err.cpp
@@ -151,6 +151,8 @@ keymaster_error_t TranslateRsaError(int reason) {
     case RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE:
     case RSA_R_DATA_TOO_SMALL_FOR_KEY_SIZE:
         return KM_ERROR_INVALID_INPUT_LENGTH;
+    case RSA_R_DATA_TOO_LARGE_FOR_MODULUS:
+        return KM_ERROR_INVALID_ARGUMENT;
     default:
         return KM_ERROR_UNKNOWN_ERROR;
     };
diff --git a/rsa_operation.cpp b/rsa_operation.cpp
index 20ef45f..076f333 100644
--- a/rsa_operation.cpp
+++ b/rsa_operation.cpp
@@ -297,6 +297,21 @@ keymaster_error_t RsaSignOperation::Finish(const AuthorizationSet& /* additional
         return SignDigested(output);
 }
 
+static keymaster_error_t zero_pad_left(UniquePtr<uint8_t[]>* dest, size_t padded_len, Buffer& src) {
+    assert(padded_len > src.available_read());
+
+    dest->reset(new uint8_t[padded_len]);
+    if (!dest->get())
+        return KM_ERROR_MEMORY_ALLOCATION_FAILED;
+
+    size_t padding_len = padded_len - src.available_read();
+    memset(dest->get(), 0, padding_len);
+    if (!src.read(dest->get() + padding_len, src.available_read()))
+        return KM_ERROR_UNKNOWN_ERROR;
+
+    return KM_ERROR_OK;
+}
+
 keymaster_error_t RsaSignOperation::SignUndigested(Buffer* output) {
     UniquePtr<RSA, RSA_Delete> rsa(EVP_PKEY_get1_RSA(const_cast<EVP_PKEY*>(rsa_key_)));
     if (!rsa.get())
@@ -305,16 +320,27 @@ keymaster_error_t RsaSignOperation::SignUndigested(Buffer* output) {
     if (!output->Reinitialize(RSA_size(rsa.get())))
         return KM_ERROR_MEMORY_ALLOCATION_FAILED;
 
+    size_t key_len = EVP_PKEY_size(rsa_key_);
     int bytes_encrypted;
     switch (padding_) {
-    case KM_PAD_NONE:
-        bytes_encrypted = RSA_private_encrypt(data_.available_read(), data_.peek_read(),
-                                              output->peek_write(), rsa.get(), RSA_NO_PADDING);
+    case KM_PAD_NONE: {
+        const uint8_t* to_encrypt = data_.peek_read();
+        UniquePtr<uint8_t[]> zero_padded;
+        if (data_.available_read() > key_len) {
+            return KM_ERROR_INVALID_INPUT_LENGTH;
+        } else if (data_.available_read() < key_len) {
+            keymaster_error_t error = zero_pad_left(&zero_padded, key_len, data_);
+            if (error != KM_ERROR_OK)
+                return error;
+            to_encrypt = zero_padded.get();
+        }
+        bytes_encrypted = RSA_private_encrypt(key_len, to_encrypt, output->peek_write(), rsa.get(),
+                                              RSA_NO_PADDING);
         break;
+    }
     case KM_PAD_RSA_PKCS1_1_5_SIGN:
         // Does PKCS1 padding without digesting even make sense?  Dunno.  We'll support it.
-        if (data_.available_read() + kPkcs1UndigestedSignaturePaddingOverhead >
-            static_cast<size_t>(EVP_PKEY_size(rsa_key_))) {
+        if (data_.available_read() + kPkcs1UndigestedSignaturePaddingOverhead > key_len) {
             LOG_E("Input too long: cannot sign %u-byte message with PKCS1 padding with %u-bit key",
                   data_.available_read(), EVP_PKEY_size(rsa_key_) * 8);
             return KM_ERROR_INVALID_INPUT_LENGTH;
@@ -322,6 +348,7 @@ keymaster_error_t RsaSignOperation::SignUndigested(Buffer* output) {
         bytes_encrypted = RSA_private_encrypt(data_.available_read(), data_.peek_read(),
                                               output->peek_write(), rsa.get(), RSA_PKCS1_PADDING);
         break;
+
     default:
         return KM_ERROR_UNSUPPORTED_PADDING_MODE;
     }
@@ -397,9 +424,9 @@ keymaster_error_t RsaVerifyOperation::VerifyUndigested(const Buffer& signature)
     int openssl_padding;
     switch (padding_) {
     case KM_PAD_NONE:
-        if (data_.available_read() != key_len)
+        if (data_.available_read() > key_len)
             return KM_ERROR_INVALID_INPUT_LENGTH;
-        if (data_.available_read() != signature.available_read())
+        if (key_len != signature.available_read())
             return KM_ERROR_VERIFICATION_FAILED;
         openssl_padding = RSA_NO_PADDING;
         break;
@@ -423,7 +450,19 @@ keymaster_error_t RsaVerifyOperation::VerifyUndigested(const Buffer& signature)
     if (bytes_decrypted < 0)
         return KM_ERROR_VERIFICATION_FAILED;
 
-    if (memcmp_s(decrypted_data.get(), data_.peek_read(), data_.available_read()) != 0)
+    const uint8_t* compare_pos = decrypted_data.get();
+    size_t bytes_to_compare = bytes_decrypted;
+    uint8_t zero_check_result = 0;
+    if (padding_ == KM_PAD_NONE && data_.available_read() < bytes_to_compare) {
+        // If the data is short, for "unpadded" signing we zero-pad to the left.  So during
+        // verification we should have zeros on the left of the decrypted data.  Do a constant-time
+        // check.
+        const uint8_t* zero_end = compare_pos + bytes_to_compare - data_.available_read();
+        while (compare_pos < zero_end)
+            zero_check_result |= *compare_pos++;
+        bytes_to_compare = data_.available_read();
+    }
+    if (memcmp_s(compare_pos, data_.peek_read(), bytes_to_compare) != 0 || zero_check_result != 0)
         return KM_ERROR_VERIFICATION_FAILED;
     return KM_ERROR_OK;
 }
@@ -496,8 +535,18 @@ keymaster_error_t RsaEncryptOperation::Finish(const AuthorizationSet& /* additio
     if (!output->Reinitialize(outlen))
         return KM_ERROR_MEMORY_ALLOCATION_FAILED;
 
-    if (EVP_PKEY_encrypt(ctx.get(), output->peek_write(), &outlen, data_.peek_read(),
-                         data_.available_read()) <= 0)
+    const uint8_t* to_encrypt = data_.peek_read();
+    size_t to_encrypt_len = data_.available_read();
+    UniquePtr<uint8_t[]> zero_padded;
+    if (padding_ == KM_PAD_NONE && to_encrypt_len < outlen) {
+        keymaster_error_t error = zero_pad_left(&zero_padded, outlen, data_);
+        if (error != KM_ERROR_OK)
+            return error;
+        to_encrypt = zero_padded.get();
+        to_encrypt_len = outlen;
+    }
+
+    if (EVP_PKEY_encrypt(ctx.get(), output->peek_write(), &outlen, to_encrypt, to_encrypt_len) <= 0)
         return TranslateLastOpenSslError();
     if (!output->advance_write(outlen))
         return KM_ERROR_UNKNOWN_ERROR;
@@ -534,8 +583,18 @@ keymaster_error_t RsaDecryptOperation::Finish(const AuthorizationSet& /* additio
     if (!output->Reinitialize(outlen))
         return KM_ERROR_MEMORY_ALLOCATION_FAILED;
 
-    if (EVP_PKEY_decrypt(ctx.get(), output->peek_write(), &outlen, data_.peek_read(),
-                         data_.available_read()) <= 0)
+    const uint8_t* to_decrypt = data_.peek_read();
+    size_t to_decrypt_len = data_.available_read();
+    UniquePtr<uint8_t[]> zero_padded;
+    if (padding_ == KM_PAD_NONE && to_decrypt_len < outlen) {
+        keymaster_error_t error = zero_pad_left(&zero_padded, outlen, data_);
+        if (error != KM_ERROR_OK)
+            return error;
+        to_decrypt = zero_padded.get();
+        to_decrypt_len = outlen;
+    }
+
+    if (EVP_PKEY_decrypt(ctx.get(), output->peek_write(), &outlen, to_decrypt, to_decrypt_len) <= 0)
         return TranslateLastOpenSslError();
     if (!output->advance_write(outlen))
         return KM_ERROR_UNKNOWN_ERROR;