Plan to address RSA attacks of eprint.iacr.org/2020/055?

[jack-fortanix]

https://eprint.iacr.org/2020/055.pdf describes side channel attacks affecting mbedtls ECDSA signing and RSA key loading. It appears the ECDSA signing was already resolved in 247c4d3 but as best I can determine the RSA side channel has not yet been resolved since mbedtls_rsa_deduce_crt (https://github.com/ARMmbed/mbed-crypto/blob/development/library/rsa_internal.c#L480) invokes mbedtls_mpi_inv_mod (https://github.com/ARMmbed/mbed-crypto/blob/development/library/bignum.c#L2345) which is implemented using an extended binary GCD which leaks information due to conditional branching and which additional invokes binary GCD which is also leaky (https://github.com/ARMmbed/mbed-crypto/blob/development/library/bignum.c#L2252), the second being the attack implemented in 2020/055 though they note that the BEEA implementation can also be used as a source of information.

I wanted to know if you have plans to address these issues and/or would be willing to accept patches addressing them.

For computing Q^-1 mod P following the papers suggested remediation of using a side-channel secured mod-exp and computing Q^(P-2) mod P seems good to me, albeit with some probable runtime overhead.

The paper https://gcd.cr.yp.to/safegcd-20190413.pdf proposes various constant-time algorithms for GCD and extended GCD. In particular the plain GCD algorithm (Figure 1.2 in the paper) is quite easy to implement.

Another option for inversion is the algorithm given in the appendix of https://hal.inria.fr/hal-01506572/document (Algorithm 5) which works for any odd modulus and is quite easily implemented in const time.

[ciarmcom]

Internal Jira reference: https://jira.arm.com/browse/IOTCRYPT-1040

[yanesca]

@jack-fortanix thank you for reporting this issue!

I wanted to know if you have plans to address these issues and/or would be willing to accept patches addressing them.

Yes, we would like to fix this issue as soon as possible. We would be very grateful for contributions addressing this issue! If you would like to submit a PR, please let us know in advance, so that we can avoid double work!

Regarding the nature of the fix, I think we should take the performance penalty, the issue only happens on private key import, which usually does not happen very frequently.

[jack-fortanix]

@yanesca Glad to hear.

I spent some time examining the right way to fix this. The paper recommends computing the modular inverse Q^-1 mod P by taking advantage of Fermat's little theorem - Q^(P-2) mod P. Unfortunately my read on the modular exponentiation in mbedtls_mpi_exp_mod is that it is not safe to use with a secret exponent without blinding because it uses sliding windows and so leaks information about the exponent both though control flow and via cache effects due to the variable lookup in W[wbits]. That suggests using blinding - computing instead Q^k*(P-1)+(P-2) mod P for some random k. But mbedtls_rsa_deduce_crt is not set up for blinding - it doesn't take parameters for a RNG. And it doesn't seem possible to add it without breaking public API since mbedtls_rsa_export_crt uses this function, and that function also doesn't have access to a RNG. So this doesn't seem to be an effective resolution.

Making GCD, mod-exp and modular inverse all constant time seems like it solves the problem, and is one thing we'd like to see on our end anyway since it neatly closes many possible avenues for side channels, including ones which have not yet been identified or analyzed. I will not be able to work on these until next month, and I will check in to make sure we are not duplicating work there but you can expect PRs here.

But what to do in the short term? I remembered that Q^-1 mod P is already included in PKCS1 private keys. But currently pk_parse_key_pkcs1_der just ignores those entries:
https://github.com/ARMmbed/mbed-crypto/blob/development/library/pkparse.c#L776 with a comment "Check optional parameters". But per PKCS1 these params are not optional https://tools.ietf.org/html/rfc2313#section-7.2 and in implementations I checked they are always used. So I think all that is required to fix at least the case of key load would be to parse out DP, DQ and QP and, in mbedtls_rsa_complete and skip the call to mbedtls_rsa_deduce_crt if all three are already set. What do you think?

[yanesca]

And it doesn't seem possible to add it without breaking public API since mbedtls_rsa_export_crt uses this function, and that function also doesn't have access to a RNG.

In cases like this we usually introduce a new API with the additional parameter and deprecate the old one. In this case we could take a similar approach. The difference would be that we don't deprecate the old API function. The intention here would be that if or when the GCD and mod-exp functions are fixed and resistant to microarchitectural SCA we deprecate the API that takes the RNG parameter.

So I think all that is required to fix at least the case of key load would be to parse out DP, DQ and QP and, in mbedtls_rsa_complete and skip the call to mbedtls_rsa_deduce_crt if all three are already set.

I think that is a brilliant idea! Although the fix does not cover every use case, it protects the majority of existing applications without them having to change their code.

But what to do in the short term?

I think we should do both of these fixes. This way we can provide full protection for those who can change their application code and severely limit the impacted use cases for those who can't.

[jack-fortanix]

@yanesca Initial patch to parse the parameters from the private key in #352

I will prepare a separate PR adding blinding during CRT recomputation using a new API as you suggested, since that can also be used to protect key generation which is still vulnerable with #352

[yanesca]

Thank you very much!

[yanesca]

Thank you very much for submitting the fix!

Would you like to contribute the second fix too?

[jack-fortanix]

@yanesca Yes I'm going to create a PR adding the alternative version of CRT recomputation using blinding, probably will have that next week. I also would like to contribute changes to const-time gcd, modular inversion, and possibly also modular exponentiation, which would prevent a range of these vulnerabilities for good. But I probably will not have time for the const time work until end of Feb.

[yanesca]

@jack-fortanix Thank you very much!

The alternative CRT recomputation fix is very important and urgent for us, we are very grateful for your fix and we would like to integrate it as soon as possible.

Eventually we would like to have a bignum implementation in Mbed TLS that is constant time, but we haven't got plans about the timeline or the exact approach yet. Meanwhile we are very happy to take incremental improvements in this direction like the one you are suggesting.

[yanesca]

@jack-fortanix Although we would like to avoid duplicating work as much as possible, as I mentioned, the alternative CRT recomputation fix is very important and urgent for us. Because of this, we need to start working on it on Monday.

That being said, we are very grateful for your efforts and we are still going to favour your contribution if it arrives before our version of the fix is ready.

[jack-fortanix]

@yanesca Indeed I have been pulled away by other high priority projects and have not been able to work on this, nor will I be able to begin until at least week after next, so your efforts will likely be available faster. Glad this is being addressed and I would like continue to coordinate in this area (const time gcd etc) to avoid any duplicated efforts on either side.

[yanesca]

@jack-fortanix In the end we decided to go with a different temporary fix, so it is not necessary to implement the alternative CRT recomputation anymore.