RSA "NoPadding" encryption is considered not secure but required by conscrypt to support TLS RSA-PSS signing algorithm

[adams-y-chen]

Describe the issue:

TLS handshake fails if client certificate keypair is created in Android Keystore which specifies OEAP encryption padding. setEncryptionPaddings(KeyProperties.ENCRYPTION_PADDING_OEAP)

This happens when the server requests RSA-PSS signature algorithms in Certificate Request.
In order for the keypair to work with RSA-PSS signature, client needs to set 'RSA NoPadding' by setEncryptionPaddings(KeyProperties.ENCRYPTION_PADDING_NONE).

Refs:
https://developer.android.com/reference/android/security/keystore/KeyGenParameterSpec.Builder#setEncryptionPaddings(java.lang.String[])
https://developer.android.com/reference/android/security/keystore/KeyProperties#ENCRYPTION_PADDING_NONE

There are articles saying that RSA NoPadding shall not be used for encryption as it's not considered sure. Company SDL also forbids using RSA NoPadding encryption. Is there any way that we can explain why RSA NoPadding encryption is needed for TLS RSA-PSS signature and it's secure?

Sample code to reproduce the issue:
Please find the steps to create keypair in Android keystore in previously reported issue: SSL Handshake failure in Android 10 #718

[prbprbprb]

You're absolutely correct that RSA with no padding is incredibly insecure.

However in this case, what is happening is that PSS padding has already been added by BoringSSL, so the "raw" payload that is passed to Android Keystore for encryption is the message digest plus PSS padding, which is equivalent to passing only the message digest and asking Keystore to do the padding.

The TLS signing process in Conscrypt is somewhat complex, especially when the private key is "foreign" (i.e. belongs to some other security Provider than Conscrypt - Android Keystore in your example) as it involves calling back into Java, finding the correct Provider for the key etc. Currently this uses the BoringSSL ENGINE APIs which entails doing the padding in BoringSSL, because reasons.

We have an open bug to improve this to what Chromium uses, because it breaks at least one other hardware-based keystore which assumes a really-raw payload and adds PKCS#1 padding, but it's currently not high on the list.

[prbprbprb]

Also, we should document this better, so please don't close out this issue just yet!

[prbprbprb]

Is there any way that we can explain why RSA NoPadding encryption is needed for TLS RSA-PSS signature and it's secure?

Whilst pointing at the code would be a bit hand-wavey, if you need to explain this claim to auditors or similar, you can point out that unless the payload being encrypted was already padded correctly, then verification on the peer would fail and thus the TLS handshake would fail.

[adams-y-chen]

A follow up question is why conscrypt calls encryption operation into keystore provider instead of signature operation when it performs rsa_pss_ signature.

When creating the keypair on Android, user can specify both encryption padding and signature padding.
See: https://developer.android.com/reference/android/security/keystore/KeyGenParameterSpec.Builder

Since we are trying to support rsa_pss_ signature algorithms in addition to the old rsa_pkcs1_ signature, I would specify both signature padding like below.
setSignaturePaddings(KeyProperties.SIGNATURE_PADDING_RSA_PKCS1, KeyProperties.SIGNATURE_PADDING_RSA_PSS)

This however doesn't have impact and the app still can't handle rsa_pss_ in TLS.

The issue is resolved only after adding KeyProperties.ENCRYPTION_PADDING_NONE to setEncryptionPadding.

  KeyProperties.ENCRYPTION_PADDING_RSA_OAEP,
  KeyProperties.ENCRYPTION_PADDING_RSA_PKCS1,
  KeyProperties.ENCRYPTION_PADDING_NONE
)
setRandomizedEncryptionRequired(false)

Would appreciate if I can learn more context about it.

[adams-y-chen]

Summarize and share my findings here. The padding part has already been explained by Pete above (thanks, Pete). Please keep me honest.

The signature is break into two steps by conscrypt:

1. conscrypt calculates the message digest (i.e., hash) and padded the digest using PSS padding.
2. conscrypt calls Cipher to "encrypt" the digest to produce a signature. This works because creating an RSA signature of some data is mathematically equivalent to "encrypting" the padded hash of that data using the private key.

Since conscrypt has already padded the digest, thus it invokes the RSA "NoPadding" encryption for step 2. This calls into Keystore encryption operation which requires keypair to support KeyProperties.ENCRYPTION_PADDING_NONE.

[adams-y-chen]

Looks like this the PR that implements RSA PSS signature algorithm in conscrypt.

rsaSignDigestWithPrivateKey code confirms the implementation.

See: https://github.com/google/conscrypt/blob/master/common/src/main/java/org/conscrypt/CryptoUpcalls.java

[adams-y-chen]

@prbprbprb, would you please share me the bug link you mentioned in
#1201 (comment) ?

I would like to monitor it and also review to ensure it aligns with my understanding.

My understanding is that the improvement will involve two repos:

1. A change in BoringSSL (https://github.com/google/boringssl) in terms of the way how TLS handshake digest is produced.
2. The change in Conscrypt to call provider RSA signing operation using PSS padding instead of calling the RSA encryption (Java Cipher class) to perform the signing of the diget.

[davidben]

No, no BoringSSL change is need. BoringSSL's SSL_PRIVATE_KEY_METHOD APIs already pass the unhashed input to the caller.