Does PKCS 1.5 padding make it possible for an attacker to extract the private key or not? Is PKCS 1.5 safe to use in authentication context?

Question

Im currently writing a authentication app based on RSA, for Android that should be impossible to copy, even if you have physical access to a phone without lockscreen/PIN.

However, the HSM inside the phone, that ensures the private key can never leave the storage, only be "used", does only support PKCS 1.5 padding due to a bug in the bouncycastle implementation.

The encrypted messages, will be different every time (nonce) so theres no possibility to observe that two encrypted messages are identical over the wire.

A attacker or adversiary, while not having access to the phone, does not have access to a padding oracle. The app works by having the user scan a encrypted QR and this encrypted QR decrypts into a OTP code. Yes, the attacker can display, on a phishing page or hijacked connection, a QR code containing padding errors, and observe if the user proceeds with authentication (enters a valid OTP) or not, but what I read on some pages, a padding oracle attack requires millions of "tests" against the padding.

When the attacker or adversiary do have access to the phone, the attacker can use the phone itself as padding oracle, but also, when having access to the phone, the attacker is able to decrypt arbitary messages using the app anyways.

The security goals that must be met, is that:

• While the attacker does not have access to the phone, the attacker should not be able to authenticate.

• If the attacker does have access to the phone, even for a long time, he should be able to authenticate, but not extract the private key.

• When attacker does no longer have access to the phone, for example if the attacker is a previous employee that have been fired and then have turned in the phone, the attacker should no longer be able to authenticate, even if he previously did have access to the phone, and even if the keypair inside the secure hardware, has not been changed.

On this page, the answer mentions its possible to extract the private key, by mounting a padding oracle attack: What specific padding weakness does OAEP address in RSA?

However, the wikipedia page, mentions no reveal of private keys: https://en.wikipedia.org/wiki/Padding_oracle_attack

But the wikipedia page mentions, using the padding oracle, a attacker is able to decrypt arbitary messages, by just checking the padding oracle replies, without having access to the either the key nor the plaintext output of the decryption engine. However, in this case, when a attacker does have access to the padding oracle, the attacker also have access to the plaintext output and vice versa, which means that decryption of arbitary messages is already possible when the attacker does have access to the decryption engine, without having to resort to a padding oracle attack.

The 2 things are completely different, because with the private key, the attacker is able to do decryption while he no longer have access to the padding oracle, but if the padding oracle can only be used to decrypt messages, the padding oracle effectively becomes useless to the attacker in this case, because when the attacker no longer have padding oracle access, he can no longer do decryption, and the security goal is met.

The questions I have is:

1: Is it safe to use PKCS 1.5 in this case?

2: Is it really possible to extract the private key using a padding oracle, or does the padding oracle just allow arbitary message decryption? The 2 linked articles are ambigious in that regard.

Answer 1

Is it safe to use PKCS 1.5 in this case?

I cannot answer "no" here. But it is recommended to avoid "safe in this case" for any practical purposes. E.g., why would you use RSA encryption if all you care for is protecting the private key (but not the confidentiality of the messages themselves)? Also, if BouncyCastle hasn't fixed that bug already - it's likely to get it fixed soon (have you reported it, by the way?).

Is it really possible to extract the private key using a padding oracle, or does the padding oracle just allow arbitary message decryption?

No, RSA Padding Oracle just allows arbitrary message decryption (we are not talking about timing attacks, etc.). So the RSA private key is safe in the phone's HSM.

The CRYPTO'12 paper was about applying Padding Oracle to Key Wrapping - a key is "wrapped" (aka RSA-encrypted), passed to the token, and "unwrapped" there (aka decrypted and made ready for use in this token). It doesn't make sense to apply this attack to normal encryption/decryption, because if you have the device (your phone, your cryptographic token) and the PIN - you can tell the device to decrypt whatever ciphertext you got in one request, no need to pry it bit by bit.

Also, would you consider an authentication scheme based on signature rather than decryption?

Update

The reason I selected a auth scheme based on decryption instead of signatures, is because signatures get huge, as long as the key.

For the RSA encryption the ciphertext is as big as the key (modulus), just like in RSA signature (and for the same reason - that's what padding is for). But I guess it doesn't matter, because it's passed to the phone as a QR scan...?

But also the system needs to work without any network connectivity for the device, so I have based the system on encrypted QR codes, that decrypt to a simple OTP string, that is entered on server

Based on your comments, you mean that the phone itself may not be connected, i.e., it cannot react to what it QR-scanned. It just displays the result (presumably something fairly short that the user can type easily).

In the use case you describe, I guess it's OK. And your private key is not exposed anyway. Although I wonder how your public key is going to get from the phone to the server that would use it to encrypt that OTP for this specific client (so your phone would need some connectivity at some point in time).