Skip to main content

The RFC 5114 saga

Back in January I posed a question "to the Internet": What the heck is RFC 5114?
It looks like a lot happened since then around it. I would like to use this post to recollect some of the stuff around RFC5114 .

Chapter 0: October 2007


RFC5114 draft was submitted to the IETF .

Chapter I: January 2016


In short RFC5114 is an IETF Informational RTC that "describes eight Diffie-Hellman groups that can be used in conjunction with IETF protocols to provide security for Internet communications." .
One of the thing about this RTC that attracted the attention of many (and also mine) is that violates the Nothing up my sleeve principle.
The other peculiar thing about this RTC (that caught my attention) was that the Ps specified for groups 22/23/24 were not safe primes but were indeed DSA primes adapted to Diffie Hellman. So far so good. Except that all the p-1 specified for those groups factored in a really nice way! So I decided to intensify a bit my research and found something  here (emphasis mine):

...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. 

It was than that  I posted this question 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.

NOTE:  it turned out that this factorization listed here is actually wrong (more about it below).

At this point we started to look for some usage of the specification in the wild and with surprisingly we found was kind of commonly used!! In turn it was:
  • the default choice for Bouncy Castle and Exim
  • OpenSSL has built-in support for RFC5114 in OpenSSL 1.0.2 
  • and much more...
One of the outcome of this analysis was  OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701) (easy explanation in this ArsTechnica article). In turn we had:

Interlude: February 2016- June 2016

In the meantime another news came into the game. It was indeed discovered that Socat (a versatile command line utility that builds bi-directional communication) contained an hard-coded Diffie-Hellman 1024-bit prime number that was NOT prime!! This story is covered here. All this brought David Wong to write "How to Backdoor Diffie-Hellman"

Chapter II: October 2016


All this happened toward the first half of the year and the situation was kind of quiet until really recently when Fried et al. released "A kilobit hidden SNFS discrete logarithm computation" that made some people wake up. What is so special about this paper you might ask? An easy explanation can be found in this article. In a nutshell the authors of the paper were able to reuse some theory from the '90s and introduce a backdoor into a 1024 prime such that:

  1. it would be feasible for the creator of the backdoor to calculate discrete log 
  2. it would be impossible for anybody else to prove that this particular number was actually backdoored!
As we said at the begin of the post, RFC5114 violates the Nothing up my sleeve principle making it a possible backdoor candidate (but here is where the speculations start). Anyway this paper did not pass unobserved by the crypto  community and led to some actions:

At this point you might actually wonder how much is actually used this RFC5114 in the end ? If you are curious you can find a pretty decent answer in the paper we just released: "Measuring small subgroup attacks against Diffie-Hellman".
The paper contains a detailed usage of  RFC5114 in various protocols: HTTPS, POP3S, IKE. etc and analyzes over 20 open-source cryptographic libraries. For the sake of correctness the paper doesn't focus only on RFC5114 but includes also analysis of non-safe primes usage in the wild. For example Amazon ELB was also found to be partially vulnerable while it was not using RFC5114 : "...We  were  able  to  use  a small-subgroup  key  recovery  attack  to  compute  17  bits  of our load balancer’s private Diffie-Hellman exponent..." .

Another thing present in the paper is a complete factorization of group 22 and improved factorization for the other groups:


Chapter III:  ...What's next? and When ?

Funnily enough one of the author of RFC5114 was invited to express his point of view and here is his answer! So what is going on with RFC5114 ? Well is still unknown. So far there are only speculations and no facts but we all know what has happened with the Dual_EC_DRBG right?

That's all folks. For more, follow me on twitter.

Comments

Unknown said…
I also brought it up on crypto-dev of the BC folk and reminded them about this post again:

https://www.bouncycastle.org/devmailarchive/msg14882.html

Gruss
Bernd

Popular posts from this blog

Slack SAML authentication bypass

tl;dr  I found a severe issue in the Slack's SAML implementation that allowed me to bypass the authentication. This has now been solved by Slack.
Introduction IMHO the rule #1 of any bug hunter (note I do not consider myself one of them since I do this really sporadically) is to have a good RSS feed list.  In the course of the last years I built a pretty decent one and I try to follow other security experts trying to "steal" some useful tricks. There are many experts in different fields of the security panorama and too many to quote them here (maybe another post). But one of the leading expert (that I follow) on SAML is by far Ioannis Kakavas. Indeed he was able in the last years to find serious vulnerability in the SAML implementation of Microsoft and Github. Usually I am more an "OAuth guy" but since both, SAML and OAuth, are nothing else that grandchildren of Kerberos learning SAML has been in my todo list for long time. The Github incident gave me the final…

Bug bounty left over (and rant) Part III (Google and Twitter)

tl;dr in this blog post I am going to talk about some bug bounty left over with a little rant.

Here you can find bug bounty left over part I and II
Here you can find bug bounty rant part I and II
Introduction In one of my previous post I was saying that: 

"The rule #1 of any bug hunter... is to have a good RSS feed list."
Well well well allow me in this post to state rule #2 (IMHO)

"The rule #2 of any bug hunter is to DO NOT be to fussy with 'food' specifically with left over"

aka even if the most experience bug hunter was there (and it definitely was my case here, given the fact we are talking about no one less than filedescriptor) do not assume that all the vulnerabilities have been found! So if you want some examples here we go.
Part I - GoogleI have the privilege to receive from time to time Google Vulnerability Research Grant. One of the last I received had many target options to choose from, but one in particular caught my attention, namely Google Issue T…

OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701)

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 …