Bug 1651411 New tlsfuzzer code can still detect timing issues in RSA operations.

This patch defeats Bleichenbacher by not trying to hide the size of the
decrypted text, but to hide if the text succeeded for failed. This is done
by generating a fake returned text that's based on the key and the cipher text,
so the fake data is always the same for the same key and cipher text. Both the
length and the plain text are generated with a prf.

Here's the proposed spec the patch codes to:

    1. Use SHA-256 to hash the private exponent encoded as a big-endian integer to a string the same length as the public modulus. Keep this value secret. (this is just an optimisation so that the implementation doesn't have to serialise the key over and over again)
    2. Check the length of input according to step one of https://tools.ietf.org/html/rfc8017#section-7.2.2
    3. When provided with a ciphertext, use SHA-256 HMAC(key=hash_from_step1, text=ciphertext) to generate the key derivation key
    4. Use SHA-256 HMAC with key derivation key as the key and a two-byte big-endian iterator concatenated with byte string "length" with the big-endian representation of 2048 (0x0800) as the bit length of the generated string.
      - Iterate this PRF 8 times to generate a 256 byte string
    5. initialise the length of synthetic message to 0
    6. split the PRF output into 2 byte strings, convert into big-endian integers, zero-out high-order bits so that they have the same bit length as the octet length of the maximum acceptable message size (k-11), select the last integer that is no larger than (k-11) or remain at 0 if no integer is smaller than (k-11); this selection needs to be performed using a side-channel free operators
    7. Use SHA-256 HMAC with key derivation key as the key and a two-byte big-endian iterator concatenated with byte string "message" with the big-endian representation of k*8
      - use this PRF to generate k bytes of output (right-truncate last HMAC call if the number of generated bytes is not a multiple of SHA-256 output size)
    8. perform the RSA decryption as described in step 2 of section 7.2.2 of rfc8017
    9. Verify the EM message padding as described in step 3 of section 7.2.2 of rfc8017, but instead of outputting "decryption error", return the last l bytes of the "message" PRF, when l is the selected synthetic message length using the "length" PRF, make this decision and copy using side-channel free operation

Differential Revision: https://phabricator.services.mozilla.com/D99843

2 files changed, 30 insertions, 11 deletions

diff --git a/gtests/pk11_gtest/pk11_rsaencrypt_unittest.cc b/gtests/pk11_gtest/pk11_rsaencrypt_unittest.cc
index ea31c48cb..1b312027f 100644
--- a/gtests/pk11_gtest/pk11_rsaencrypt_unittest.cc
+++ b/gtests/pk11_gtest/pk11_rsaencrypt_unittest.cc
@@ -13,6 +13,7 @@
 #include "nss.h"
 #include "nss_scoped_ptrs.h"
 #include "pk11pub.h"
+#include "databuffer.h"
 
 #include "testvectors/rsa_pkcs1_2048_test-vectors.h"
 #include "testvectors/rsa_pkcs1_3072_test-vectors.h"
@@ -44,13 +45,15 @@ class RsaDecryptWycheproofTest
     rv = PK11_PrivDecryptPKCS1(priv_key.get(), decrypted.data(), &decrypted_len,
                                decrypted.size(), vec.ct.data(), vec.ct.size());
 
-    // RSA_DecryptBlock returns SECFailure with an empty message.
-    if (vec.valid && vec.msg.size()) {
+    if (vec.valid) {
       EXPECT_EQ(SECSuccess, rv);
       decrypted.resize(decrypted_len);
       EXPECT_EQ(vec.msg, decrypted);
     } else {
-      EXPECT_EQ(SECFailure, rv);
+      DataBuffer::SetLogLimit(512);
+      decrypted.resize(decrypted_len);
+      EXPECT_EQ(SECFailure, rv)
+          << "Returned:" << DataBuffer(decrypted.data(), decrypted.size());
     }
   };
 };
diff --git a/gtests/pk11_gtest/pk11_rsaoaep_unittest.cc b/gtests/pk11_gtest/pk11_rsaoaep_unittest.cc
index 9d329aaaf..2e80e6a38 100644
--- a/gtests/pk11_gtest/pk11_rsaoaep_unittest.cc
+++ b/gtests/pk11_gtest/pk11_rsaoaep_unittest.cc
@@ -157,11 +157,32 @@ TEST(Pkcs11RsaOaepTest, TestOaepWrapUnwrap) {
 
   PK11SymKey* p_unwrapped_tmp = nullptr;
 
-  // This fails because this method is broken and assumes CKM_RSA_PKCS and
-  // doesn't understand OAEP.
+  // Extract key's value in order to validate decryption worked.
+  rv = PK11_ExtractKeyValue(to_wrap.get());
+  ASSERT_EQ(rv, SECSuccess);
+
+  // References owned by PKCS#11 layer; no need to scope and free.
+  SECItem* expectedItem = PK11_GetKeyData(to_wrap.get());
+
+  // This assumes CKM_RSA_PKCS and doesn't understand OAEP.
+  // CKM_RSA_PKCS cannot safely return errors, however, as it can lead
+  // to Blecheinbaucher-like attacks. To solve this there's a new definition
+  // that generates fake key material based on the message and private key.
+  // This returned key material will not be the key we were expecting, so
+  // make sure that's the case:
   p_unwrapped_tmp = PK11_PubUnwrapSymKey(priv.get(), wrapped.get(), CKM_AES_CBC,
                                          CKA_DECRYPT, 16);
-  ASSERT_EQ(p_unwrapped_tmp, nullptr);
+  // as long as the wrapped data is legal RSA length of the key
+  // (which is should be), then CKM_RSA_PKCS should not fail.
+  ASSERT_NE(p_unwrapped_tmp, nullptr);
+  ScopedPK11SymKey fakeUnwrapped;
+  fakeUnwrapped.reset(p_unwrapped_tmp);
+  rv = PK11_ExtractKeyValue(fakeUnwrapped.get());
+  ASSERT_EQ(rv, SECSuccess);
+
+  // References owned by PKCS#11 layer; no need to scope and free.
+  SECItem* fakeItem = PK11_GetKeyData(fakeUnwrapped.get());
+  ASSERT_NE(SECITEM_CompareItem(fakeItem, expectedItem), 0);
 
   ScopedPK11SymKey unwrapped;
   p_unwrapped_tmp = PK11_PubUnwrapSymKeyWithMechanism(
@@ -171,15 +192,10 @@ TEST(Pkcs11RsaOaepTest, TestOaepWrapUnwrap) {
 
   unwrapped.reset(p_unwrapped_tmp);
 
-  // Extract key's value in order to validate decryption worked.
-  rv = PK11_ExtractKeyValue(to_wrap.get());
-  ASSERT_EQ(rv, SECSuccess);
-
   rv = PK11_ExtractKeyValue(unwrapped.get());
   ASSERT_EQ(rv, SECSuccess);
 
   // References owned by PKCS#11 layer; no need to scope and free.
-  SECItem* expectedItem = PK11_GetKeyData(to_wrap.get());
   SECItem* actualItem = PK11_GetKeyData(unwrapped.get());
 
   ASSERT_EQ(SECITEM_CompareItem(actualItem, expectedItem), 0);