blog.intothesymmetry.com Open in urlscan Pro
2a00:1450:400d:804::2013 Public Scan

Back to summary

Submitted URL:
http://intothesymmetry.blogspot.com/2016/01/openssl-key-recovery-attack-on-dh-small.html
Effective URL:
http://blog.intothesymmetry.com/2016/01/openssl-key-recovery-attack-on-dh-small.html
Submission: On January 22 via api (January 22nd 2023, 11:08:59 am UTC) from FR — Scanned from FR

Form analysis
1 forms found in the DOM

http://blog.intothesymmetry.com/search

<form action="http://blog.intothesymmetry.com/search" target="_top">
  <div class="search-input">
    <input aria-label="Search this blog" autocomplete="off" name="q" placeholder="Search this blog" value="">
  </div>
  <label class="search-submit">
    <input type="submit">
    <div class="flat-icon-button ripple">
      <svg class="svg-icon-24 search-icon">
        <use xlink:href="/responsive/sprite_v1_6.css.svg#ic_search_black_24dp" xmlns:xlink="http://www.w3.org/1999/xlink"></use>
      </svg>
    </div>
  </label>
</form>

Text Content

INTO THE SYMMETRY

SEARCH THIS BLOG

OPENSSL KEY RECOVERY ATTACK ON DH SMALL SUBGROUPS (CVE-2016-0701)

January 28, 2016
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.

INTRODUCTION

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.

and

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:
* Why the generators g (defined in this spec) are so big ? Often the generator
is 2. Now I am aware that the generator g=2 leaks one bit but AFAIK this is
still considered safe.
* Why (p-1)/2 (defined in this spec) are not a safe prime?

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 ATTACK

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

* p as the prime number
* g the generator with order
* q the size of the prime-order subgroup generate by g
* y public key
* x private key

In order for the attack to succeed it needs to have two prerequisites:

1. requires that the attacker complete multiple handshakes in which the peer
(OpenSSL in this case) uses the same private DH exponent. And this is true
for the default configuration of OpenSSL for the DHE ciphersuites (namely
SSL_OP_SINGLE_DH_USE is not set) and is always true for Static DH
ciphersuites. As mentioned above, 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.
2. requires DH configured with parameters based on primes that are not "safe"
or not Lim-Lee. This is well the case of RFC 5114 where p-1 = 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). But the problem it is not limited to RFC 5114 (while this
is a perfect example). Note in order to generate the RFC 5114 parameter file
in X9.42 style using openssl just do:

openssl genpkey -genparam -algorithm DH -pkeyopt dh_rfc5114:2

This will generate something like

-----BEGIN X9.42 DH PARAMETERS-----
MIICKQKCAQEArRB+
HpEjqdDWYPqnlVnFH6INZOVoO5/RtUsVl7YdCnXm+hQd+VpW
26+aPEB7od8V6z1oijCcGA4d5rhaEnSgpm0/gVKtasISkDfJ7e/aTfjZHo/vVbc5
S3rVt9C2wSIHyfmNEe002/bGugssi7wnvmoA4KC5xJcIs7+KMXCRiDaBKGEwvImF
2xYC5xRBXZMwJ4Jzx94x79xzEPcSH9WgdBWYfZrcCkhtzfk6zEQyg4cxXXXhmMZB
pIDNhqG55YfovmDmnMkosrnFIXLkEwQumyPxCw4W55djybU9z0uoCinj+3PBa451
uX7zY+L/ox9xz53lOE5xuBwKxN/+DBDmTwKCAQEArEAy708tmuOd8wtcj/2sUGze
vnuJmYyvdIZqCM/k/+OmgkpOELmm8N2SHwGnDEr6q3OddwDCn1LFfbF8YgqGUr5e
kAGo1mrXwXZpEBmZAkr00CcnWsE0i7inYtBSG8mK4kcVBCLqHtQJk51U2nRgzbX2
xrJQcXy+8YDrNBGOmNEZUppF1vg0Vm4wJeMWozDvu3eobwwasVsFGuPUKMj4rLcK
gTcVC47rEOGD7dGZY93Z4mPkdwWJ72qiHn9fL/OBtTnM40CdE81Wavu0jWwBkYHh
vP6UswJp7f5y/ptqpL17Wg8ccc//TBnEGOH27AF5gbwIfypwZbOEuJDTGR8r+gId
AIAcDTTFjZP+mXF3EB+AU1pHOM68vziambNjces=
-----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:

* Assuming the server (OpenSSL in this case) chooses his DH private key to be
xb
* 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... )
* choose xa
* calculate ya = g^xa (mod p) * B
* with the received yb the attacker by exhaustive search (for TLS these means
try to handshake many sessions) tries yb^xa * B^j (mod p). It does it j-times
where 0< j <ord (B).
* At this point the attacker found j = xb (mod ord(B))
* Once this is done the attacker may repeat the same steps above with a
different computational feasible B' where ord(B')) is small.
* The resulting partial secrets can then be combined using the Chinese
Remainder Theorem .
* And for the yet remaining bits Shanks's method Pollard's lambda methods can
be used.

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.

THE FIX

As mentioned before in order for work safely with DH parameters as the one in
RFC 5114 two options are possible:

1. Never reuse the key for DHE ciphers suites. And this has been fixed in
OpenSSL in
https://git.openssl.org/?p=openssl.git;a=commit;h=ffaef3f1526ed87a46f82fa4924d5b08f2a2e631.
Curiously enough when I reported the issue to OpenSSL (12-01-2016) this
particular fix was already committed (indeed was done 23-12-2015) but was
not yet in the release branches.
2. Validate the peer value. This can be easily done just checking that ya^q
(mod p) = 1. The fix done by OpenSSL for this issue adds an additional check
where a "q" parameter is available (as is the case in X9.42 based
parameters). This detects the only known attack, and is the only possible
defense for static DH ciphersuites. This could have some performance impact.

FORK STATUS

* BoringSSL got rid of SSL_OP_SINGLE_DH_USE support some months ago. I am not
sure about the Static DH ciphersuites situation.

* I gave an heads up to the LibreSSL folks as well. I know they also assigned a
CVE and deprecated SSL_OP_SINGLE_DH_USE this week. Again, I am not sure about
the Static DH ciphersuites situation.

DISCLOSURE TIMELINE

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.

ACKNOWLEDGEMENT

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.

Share
* Get link
* Facebook
* Twitter
* Pinterest
* Email
* Other Apps

LABELS

bounty crypto openssl tls
Labels: bounty crypto openssl tls

Share
* Get link
* Facebook
* Twitter
* Pinterest
* Email
* Other Apps

COMMENTS

Anonymous said…
Great work to all involved in raising and fixing this issue and thank you
Antonio for documenting this so thoroughly.
28 January 2016 at 09:25
Anonymous said…
Ditto. Great find and blog post. Thanks!
28 January 2016 at 16:18
Anonymous said…
The link to Paul Wouters reply is wrong and instead points to the openssl
announcement. Thanks!
28 January 2016 at 16:23
ll said…
thanks. I did update the link!
28 January 2016 at 21:19
Anonymous said…
Thanks a lot.. Got most of stuff.
28 January 2016 at 21:32
Dominique said…
Great job, Antonio!
29 January 2016 at 01:25
Anonymous said…
CVE is different on OpenSSL advisory, they're listing CVE-2016-0701 as the ID fr
this.
29 January 2016 at 05:40
ll said…
isn't the same CVE listed here or am I missing something? :)
29 January 2016 at 07:34
Anonymous said…
Antonio, in the Disclosure Timeline area you list a CVE that doesn't match the
title of the article. Both CVE-2015-1788 and CVE-2016-0701 are mentioned.
29 January 2016 at 10:02
ll said…
ooops :) thanks !! updated
29 January 2016 at 10:08
Anonymous said…

are you sure the fix is ya^q (mod p) = 1? This holds for any ya according to
Fermat little theorem. If p is not a safe prime, it means order of group (since
p is prime, = p-1 = q) has small prime factors, say q = q0 q1 ... qn. Assuming
one of them is big (call it qi), then you ought to check that ya^qi = 1 mod p.
That would ensure that your group order is big, and an attacker cannot trick u
into using a small subgroup attack.
Can you point out the file where the supposedly fix is done?
29 January 2016 at 13:48
Anonymous said…
The answer to why RFC 5114 exists is simple. The NIST standard for
Diffie-Hellman key exchanges is NIST Special Publication 800-56A. If you read
page 28 of the 2007 version of this standard you will find that NIST explicitly
requires that primes for use in Finite Field Diffie-Hellman have the same form
as the primes they require for DSA.

As far as I know NIST has always accepted primes (p) of a forms such that
(p-1)/2 is prime - thus not conforming to their standard. The writers of RFC
5114 were just supplying some primes that actually met NIST's own standard.

Regarding the question of why 2 wasn't used as a generator I think the answer is
also simple. Given a prime modulus p such that there's another prime q that
divides (p-1)/2 you want the generator to be an element of order q. The
probability that the integer "2" happens to be of order q is very, very, small.
The NIST standard for DSA has several complex processes to generate the
generator given the primes p and q.
29 January 2016 at 16:48
ll said…
AFAIK ya^q (mod p) = 1 is the right validation. This is the OpenSSL commit
https://git.openssl.org/?p=openssl.git;a=commit;h=b128abc3437600c3143cb2145185ab87ba3156a2
(For the record I update the blog post to include it now )
30 January 2016 at 05:11
ll said…
About RFC 5114 : true but but why making those factors sooooo small and soooo
many ?
30 January 2016 at 05:12
daidai said…
Great work!
BTW 83501807020473429349 may not be a prime...Please try 742327609 *
112486462861.
I guess the attack complexity slightly decreases.
1 February 2016 at 07:03
ll said…
@daidai you are actually right. As you can see this was just a quote of somebody
else work though :)
1 February 2016 at 08:43
Unknown said…
Great Find Antonio.

Is there a commit record for the fix.
1 February 2016 at 14:01
ll said…
@Anamitra. The commit records are a both listed in this blog post :)
1 February 2016 at 23:24
Anonymous said…
Great work! But I don't quite understand the step "calculate yb = g*xa (mod p) *
B"... In my understanding, it should be ya = g^xa (mod p) * B , and ya is sent
to the server. yb in yb^xa * B^j (mod p) is the one received from server, which
is yb = g ^ xb (mod p). Please correct me if I am wrong.
5 February 2016 at 22:18
ll said…
you are completely right. there were indeed few typos. Corrected :)
8 February 2016 at 00:56
Anonymous said…
Thanks for the elaborate post...

Is there a way to check if the server supports static DH ciphersuites?
12 February 2016 at 01:17
ll said…
yes, try to negotiate it....
15 February 2016 at 21:48
Unknown said…
Great blog! i actually love however it's straightforward on my eyes and
therefore the info area unit well written. I'm curious however I'd be notified
whenever a brand new post has been created. I actually have signed to your rss
feed that extremely ought to do the trick! Have a pleasant day!

Clay Anderson
college essay writing service
20 April 2016 at 22:07
Post a Comment

blog.intothesymmetry.com Open in urlscan Pro 2a00:1450:400d:804::2013 Public Scan

Form analysis 1 forms found in the DOM

http://blog.intothesymmetry.com/search

Text Content

blog.intothesymmetry.com Open in urlscan Pro
2a00:1450:400d:804::2013 Public Scan

Form analysis
1 forms found in the DOM