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

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAFeDd5bgmNV4=u0GNwpuszCv-k+ZeOJv=uF+z3MZybf+thG+fg@mail.gmail.com>
Date: Mon, 16 Apr 2018 19:46:03 +0300
From: Billy Brumley <bbrumley@...il.com>
To: oss-security@...ts.openwall.com
Subject: CVE-2018-0737 OpenSSL: RSA key generation follows several non
 constant time code paths

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

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.