Usual Mandatory Disclaimer: IANAC (I am not a cryptographer) so I might likely end up writing a bunch of mistakes in this blog post...
tl;dr The OpenSSL 1.0.2 releases suffer from a Key Recovery Attack on DH small subgroups. This issue got assigned CVE-2016-0701 with a severity of High and OpenSSL 1.0.2 users should upgrade to 1.0.2f. If an application is using DH configured with parameters based on primes that are not "safe" or not Lim-Lee (as the one in RFC 5114) and either Static DH ciphersuites are used or DHE ciphersuites with the default OpenSSL configuration (in particular SSL_OP_SINGLE_DH_USE is not set) then is vulnerable to this attack. It is believed that many popular applications (e.g. Apache mod_ssl) do set the SSL_OP_SINGLE_DH_USE option and would therefore not be at risk (for DHE ciphersuites), they still might be for Static DH ciphersuites.
So if you are still here it means you wanna know more. And here is the thing. In my last blog post I was literally wondering: What the heck is RFC 5114? In a nutshell RFC-5114 was described here (emphasis mine) as
_...a semi-mysterious RFC 5114 – Additional Diffie-Hellman Groups document. It introduces new MODP groups not with higher sizes, but just with different primes. _
_the odd thing is that when I talked to people in the IPsec community, no one really knew why this document was started. Nothing triggered this document, no one really wanted these, but no one really objected to it either, so the document (originating from Defense contractor BBN) made it to RFC status. _
The thing that caught my attention back then and I was trying to get an answer were:
I posted those questions in my blog post and other places in the web (including randombit) hoping for an answer. Well it turned out I got a pretty decent one (thanks again Paul Wouters BTW!!). This answer was pointing to an old IETF mailing thread that contained a really interesting part (emphasis mine) :
Longer answer: FIPS 186-3 was written about generating values for DSA, not DH. Now, for DSA, there is a known weakness if the exponents you use are biased; these algorithms used in FIPS 186-3 were designed to make sure that the exponents are unbiased (or close enough not to matter). DH doesn't have similar issues, and so these steps aren't required (although they wouldn't hurt either). [...] For these new groups, (p-1)/q is quite large, and in all three cases, has a number of small factors (now, NIST could have defined groups where (p-1)/q has 2 as the only small factor; they declined to do so). **For example, for group 23 (which is the worse of the three), (p-1)/q == 2 * 3 * 3 * 5 * 43 * 73 * 157 * 387493 * 605921 * 5213881177 * 3528910760717 * 83501807020473429349 * C489 (where C489 is a 489 digit composite number with no small factors). ** The attacker could use this (again, if you don't validate the peer value) to effective cut your exponent size by about 137 bits with using only O(2**42) time); **if you used 224 bit exponents, then the attacker would cut the work used to find the rest of the exponent to about O(2**44) time.** Obviously, this is not acceptable.
Reading this answer and knowing that OpenSSL does use RFC 5114 my immediate though was, I gonna try this to OpenSSL. And you know what? I actually did...
The actual attack I performed is literally a verbatim application of a classical paper published in 1997: A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup. The attack is as beautiful as simple. Here I will try to sketch it. For details please refer to the original paper. For the record, this attack is not the type where the other party merely forces the shared secret value to be "weak" (i.e. from a small set of possible values) without attempting to compromise the private key (like the one I previously reported for Mozilla NSS).
I would refer to the classic Diffie Hellman nomenclature
In order for the attack to succeed it needs to have two prerequisites:
openssl genpkey -genparam -algorithm DH -pkeyopt dh_rfc5114:2
This will generate something like
-----BEGIN X9.42 DH PARAMETERS-----
-----END X9.42 DH PARAMETERS-----
that defines the following hexadecimals numbers:
p = AD107E1E 9123A9D0 D660FAA7 9559C51F A20D64E5 683B9FD1 B54B1597 B61D0A75 E6FA141D F95A56DB AF9A3C40 7BA1DF15 EB3D688A 309C180E 1DE6B85A 1274A0A6 6D3F8152 AD6AC212 9037C9ED EFDA4DF8 D91E8FEF 55B7394B 7AD5B7D0 B6C12207 C9F98D11 ED34DBF6 C6BA0B2C 8BBC27BE 6A00E0A0 B9C49708 B3BF8A31 70918836 81286130 BC8985DB 1602E714 415D9330 278273C7 DE31EFDC 7310F712 1FD5A074 15987D9A DC0A486D CDF93ACC 44328387 315D75E1 98C641A4 80CD86A1 B9E587E8 BE60E69C C928B2B9 C52172E4 13042E9B 23F10B0E 16E79763 C9B53DCF 4BA80A29 E3FB73C1 6B8E75B9 7EF363E2 FFA31F71 CF9DE538 4E71B81C 0AC4DFFE 0C10E64F g = AC4032EF 4F2D9AE3 9DF30B5C 8FFDAC50 6CDEBE7B 89998CAF 74866A08 CFE4FFE3 A6824A4E 10B9A6F0 DD921F01 A70C4AFA AB739D77 00C29F52 C57DB17C 620A8652 BE5E9001 A8D66AD7 C1766910 1999024A F4D02727 5AC1348B B8A762D0 521BC98A E2471504 22EA1ED4 09939D54 DA7460CD B5F6C6B2 50717CBE F180EB34 118E98D1 19529A45 D6F83456 6E3025E3 16A330EF BB77A86F 0C1AB15B 051AE3D4 28C8F8AC B70A8137 150B8EEB 10E183ED D19963DD D9E263E4 770589EF 6AA21E7F 5F2FF381 B539CCE3 409D13CD 566AFBB4 8D6C0191 81E1BCFE 94B30269 EDFE72FE 9B6AA4BD 7B5A0F1C 71CFFF4C 19C418E1 F6EC0179 81BC087F 2A7065B3 84B890D3 191F2BFA q = 801C0D34 C58D93FE 99717710 1F80535A 4738CEBC BF389A99 B36371EB
As mentioned above the thing that the peers need to take in consideration is the fact that for this particular group (p-1)/2 has many small factors hence a validation of the peer public value (we will see how this can be done later) is required. Well it turns out that OpenSSL did not do this extra step probably for a couple of reason (historically OpenSSL only ever generated DH parameters based on "safe" primes, while this changed lately and the validation has a certain cost in terms of performance). So here how the attack looks like:
Then transmits yb = g ^ xb (mod p) Then the attacker
choose B where ord(B) is small (and is equal to one of the small factors of p-1, (e.g. for RFC 5114 ord(B) = 2 or or 3 or 5 or 43 or 73 or 157 or 387493... )
Again, for details please refer to the original paper. But to be more ground on Earth this would means that for RFC 5114 group 23 (the one shown in this blog post) that has 2048-bit MODP Group with 256-bit Prime Order Subgroup the attacker would cut the work used to find the rest of the exponent to about O(2**44) time. Now this is for sure not feasible work for many common PCs (isn't it :S?) but it is for sure not a safe.
As mentioned before in order for work safely with DH parameters as the one in RFC 5114 two options are possible:
12-01-2016 - Reported to OpenSSL security team.
13-01-2016 - Vendor confirmation, CVE-2016-0701 assigned.
15-01-2016 - Disclosure scheduled.
25-01-2016 - Release publicly announced.
28-01-2016 - Public release and disclosure.
I would like to thank the OpenSSL team for the constant and quick support. Same as the LibreSSL team.
That's all folks. For more, follow me on twitter.