Re: CVE-2018-0737 OpenSSL: RSA key generation follows several non constant time code paths

[Billy Brumley <bbrumley () gmail com>]

This note is mostly for package maintainers.

One might interpret this security advisory

https://www.openssl.org/news/secadv/20180416.txt

as suggesting the one referenced commit solves this issue. But it doesn't.

Please note our original recommendation points at four commits. (To
distros list on 11 Apr, it was 3 commits and attached patches for both
1.1.0 and 1.0.2.)

Preprint describing our work is already in IACR eprint moderation
queue, so it'll show up soon and when it does I'll follow up as
promised with the URL.

BBB

On Mon, Apr 16, 2018 at 7:46 PM, Billy Brumley <bbrumley () gmail com> wrote:
> Hey Folks,
>
> We discovered 3 vulnerabilities in OpenSSL that allow cache-timing
> enabled attackers to recover RSA private keys during key generation.
>
> 1. BN_gcd gets called to check that _e_ and _p-1_ are relatively
> prime. This function is not constant time, and leaks critical GCD
> state leading to information on _p_.
>
> 2. During primality testing, BN_mod_inverse gets called without the
> BN_FLG_CONSTTIME set during Montgomery arithmetic setup. The resulting
> code path is not constant time, and leaks critical GCD state leading
> to information on _p_.
>
> 3. During primality testing, BN_mod_exp_mont gets called without the
> BN_FLG_CONSTTIME set during modular exponentiation, with an exponent
> _x_ satisfying _p - 1 = 2**k * x_ hence recovering _x_ gives you most
> of _p_. The resulting code path is not constant time, and leaks
> critical exponentiation state leading to information on _x_ and hence
> _p_.
>
> OpenSSL issued CVE-2018-0737 to track this issue.
>
> # Affected software
>
> LibreSSL fixed these issues (nice!) way back when this was reported in
> Jan 2017. Looks like commits
>
> 5a1bc054398ec4d2c33e5bdc3a16eece01c8901d
> 952c1252f58f5f57227f5efaeec0169759c77d72
>
> We verified that with a debugger.
>
> OTOH, OpenSSL wanted concrete evidence of exploitability. That's what
> we did over the past year and a half or so.We ran with bug (1) and
> recover RSA keys with cache-timings, achieving roughly 30% success
> rate in over 10K trials on a cluster.
>
> Affects 1.1.0, 1.0.2, and presumably all the EOL lines.
>
> ## Fixes
>
> Recently, it looks like (1) was independently discovered, and some
> code changes happened. Nothing for (2) and (3).
>
> ### 1.0.2-stable
>
> Part of the fix (1) is in commits
>
> 0d6710289307d277ebc3354105c965b6e8ba8eb0
> 64eb614ccc7ccf30cc412b736f509f1d82bbf897
> 0b199a883e9170cdfe8e61c150bbaf8d8951f3e7
>
> In combination with our contributed patch in
>
> 349a41da1ad88ad87825414752a8ff5fdd6a6c3f
>
> we verified with a debugger they cumulatively solve (1) (2) and (3).
>
> ### 1.1.0-stable
>
> Part of the fix (1) is in commits
>
> 7150a4720af7913cae16f2e4eaf768b578c0b298
> 011f82e66f4bf131c733fd41a8390039859aafb2
> 9db724cfede4ba7a3668bff533973ee70145ec07
>
> In combination with our contributed patch in
>
> 6939eab03a6e23d2bd2c3f5e34fe1d48e542e787
>
> we verified with a debugger they cumulatively solve (1) (2) and (3).
>
> Look for our preprint on http://eprint.iacr.org/ soon -- working title
> is "One Shot, One Trace, One Key: Cache-Timing Attacks on RSA Key
> Generation". We'll update the list with the full URL once it's posted.
>
> # Timeline
>
> Jan 2017: Notified OpenSSL, LibreSSL, BoringSSL
> 4 Apr 2018: Notified OpenSSL again, with PoC and 16 Apr, 15:00 UTC embargo
> 11 Apr 2018: Notified distros list
> 16 Apr 2018: Notified oss-security list
>
> Thanks for reading!
>
> Alejandro Cabrera Aldaya
> Cesar Pereida Garcia
> Luis Manuel Alvarez Tapia
> Billy Brumley