Hacker News new | comments | ask | show | jobs | submit login

"Since weak use of Diffie-Hellman is widespread in standards and implementations, it will be many years before the problems go away, even given existing security recommendations and our new findings. In the meantime, other large governments potentially can implement similar attacks, if they haven’t already. "

can someone explain to me why this cant be fixed over night. im no crypto expert, but

" If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. "

why can't you just switch the large prime number and then continue on sending encrypted data?




It turns out that verifying whether a given prime is appropriate for Diffie-Hellman is rather slow. This means that, if you accept a prime supplied by someone else (e.g. whoever you're communicating with), and you don't carefully verify the prime, then you're at risk of ending up with a maliciously chosen weak group and/or generator.

For some protocols, this is fine. For other protocols, it's a problem. IIRC one variant of the triple-handshake attach on TLS involved tricking the client into using a weak group.

From memory (too lazy to look up all the details right now), the issue is that the order of the multiplicative group mod p is p-1. If p is a prime greater than 3 (which it is in standard Diffie-Hellman), then p-1 is certainly not prime, which means that the multiplicative group will have subgroups of varying sizes. Some subgroups might be small. If one party sends a public share in a small subgroup, then bad things can happen.

Unfortunately, validating the DH parameters is too slow to do with each handshake. So either you carefully design the protocol to avoid this problem (which is certainly doable in many case), you use a well-known group (which should be fine as long as the group is large enough), or you use something like ECDH. ECDH is nice because the index calculus attacks don't work and you can have a nice group structure.

Aside: While it's possible for an EC group to have a prime order, for various tricky reasons, the better modern EC curves deliberately have an order that's h*p for some small h (h is called the "cofactor" and h=4 or h=8 are common) and a large prime p. This gives some nifty benefits, but it requires a bit of care under some circumstances.


Well, the lazy way to do this is for everyone to use the same prime, but to pick a safe prime so large it is out of reach of the NSA.

Isn't the all promise of cryptography predicated on the idea that you can impose exponential effort by merely incurring polynomial effort?


Validating EC is even harder. Accepting arbitrary curves is a bad practice. The draft of TLS 1.3 uses named curves and named primes for both DH and ECDH. And it starts with 2048 bits, because the possibility of NSA cracking 1024 primes was mentioned in the logjam paper.

See https://tools.ietf.org/html/draft-ietf-tls-tls13-09#page-49


There is an easy way to solve this at the protocol level: maintain a hash of everything that was said and sign it during authentication. Any downgrade attack will show up and cause the wrong hash to be signed.


As I understand it, this fix has already been proposed for TLS by the developers of the triple-handshake attack, but it may take some time to be implemented and may never be implemented everywhere.

https://www.ietf.org/archive/id/draft-bhargavan-tls-session-...

I'm not quite sure why this Internet-Draft expired without a replacement or if this work is still continuing somewhere in the TLS WG.


> I'm not quite sure why this Internet-Draft expired without a replacement

Oh, because it was issued as an RFC!

https://www.rfc-editor.org/rfc/rfc7627.txt


If the entity you are communicating with is out to subvert the encryption you are using with them, couldn't they just plain-text transmit everything in your communication to other channels?

What you are saying seems to only make sense for MITM attacks?


That seems right intuitively, but in existing TLS, there is a way that this can also be used to attack your communications with a third-party site. It is described in papers that were published at

https://secure-resumption.com/

although that site seems to be down right now.

While people can agree that this is ultimately a flaw in the design of the TLS protocol, in some contexts, it's still a reason that it matters whether your connection with an arbitrary site is using a safe Diffie-Hellman group or not.


Because there is not magic switch to deploy software on millions of servers?

Getting rid of old software is hard, people don't know, then there isn't enough incentive to upgrade, then you need to support legacy clients so you still keep old crypto support (which now means that you can attack clients which support stronger crypto through various downgrade/fallback attacks) etc..


i understand not every piece of software can be updated, but when something like heart bleed was release - correct me if i am wrong here - but millions of machines were updated.

if i read this article correctly, if we could update millions of computers in a short period of time with a new prime number that would be enough to solve this problem in the short term - long term all we need to do is change the prime number every X number of months, were X would require billions (as opposed to hundreds of millions) of dollars to solve


That was one specific piece of software, the overwhelming majority of deployments of which were on machines that could be updated easily. Weak DH parameters for TLS are deployed in tens of thousands of middleboxes that are not easily updated.


That and you could be attacked by anyone easily. Most ordinary people don't have the NSA as a problem in their treat model compared to the Internet at large.


Thanks for that explanation; I had thought similar to the parent until I read this and it just "clicked".


Well, that is sounds plausible but hard to prove. And I don't know what you mean by "middle boxes", especially that would be involved with DH. Most boxes other than endpoint and client are only doing TCP. And if I'm wrong I desperately want to know!


You're right, except that every "middle box" has both endpoint s and clients. HTTPS, FTP, SSH, IRC, all sorts of databases, caches, queue servers, task runners, announce servers, everything. DH is used any time you're leaving your box.


Middlebox = proxy.


ok that makes sense ... thank you


> but millions of machines were updated.

Millions more weren't. Shitty routers (did you know WEMO devices still run an old Linux 2.6 series kernel? How about Cisco firewall appliances? Yup). Home automation systems. Boxes people have half forgotten about. Systems running software from vendors who won't support you if you run anything more than half a decade old.


There are still millions of machines that affected with HB. And HB was different it was 1 single software and only limited versions, so if you haven't updated OpenSSL for about 2 years there was a good chance you weren't affected in the first place.

There are probably 1000's of various DH implementations that are utter crap, it's not like you can release a single advisory and make big news about it.



Note that the findings referenced by your first link are total B.S.: http://blog.erratasec.com/2015/04/no-75-are-not-vulnerable-t...


I think that may be the link I wanted, actually, but I took what I found after a quick search. Anyway, Heartbleed wasn't quite fixed overnight, or even in a week or more.


You can, but there's a cubic fuckload of software deployed using the old parameters, and a whole lot of it doesn't know how to update itself.


Beyond that, generating prime numbers >= to 2048 bits takes a non-trivial amount of time, sometimes close to a minute. This isn't feasible for servers to do on launch, and might not even be feasible to generate during install---which brings us back to predistributed parameters.


I think "close to a minute" is far too optimistic for the time required :-( -- note that the prime for DH is supposed to be a safe prime.

https://en.wikipedia.org/wiki/Safe_prime

You can contrast

  openssl dhparam -5 2048
which generates 2048-bit Diffie-Hellman parameters, to

  openssl genrsa 4096
which generates a 4096-bit RSA key (containing two 2048-bit primes) and note that the second is dramatically faster than the first. On-the-fly DH parameter generation is really slow.

However, generating 1024-bit parameters is probably fast enough to do on launch or install. Under the authors' estimates this might be fairly safe today because the adversary will have to spend many millions of dollars to attack your individual service (and you could change the parameters once a day or something if you wanted). But I think the authors agreed that large predistributed parameters make a better tradeoff for most cases.

There is an RFC about to issue listing such parameters

https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-f...

Edit: I possibly shouldn't refer to "the authors" in the third person here, because you are the lead author.

Further edit: "Close to a minute" is actually not a bad estimate, but the variance is very high! So it can easily be considerably worse.


    hobbes@namagiri:~$ time openssl dhparam -5 2048
    Generating DH parameters, 2048 bit long safe prime, generator 5
    This is going to take a long time
    ............[snip]......++*++*
    -----BEGIN DH PARAMETERS-----
    MIIBCAKCAQEAzshMWp3IBjMW5Aia2wJOvA2EBY32Mn2fMXzlyFDklnRUg8ff/19A
    YWbRA4RAXrBMxoXEH1LVVpm5l89PGZ3DzjDafuNzNskgUhcAewUXXMQdkOFnPHYc
    5F7+3DS8981Q0Q05qscBb26YGb2XaoJygyVj+B87NTvdAPzNU4fW5DyCuxhf5eov
    ZeZwcC4KZ31Lr7enFcFBjTjxQxW88pP4YhiNYQ1fsFARGJT0X7ksOlRVWFrODu6b
    nq0Ye/UWe0WB1zzmxz66ZujAwRwAgfmQZd7rILJqg68sxBeg88FlXJUeKfPL/bIT
    KOl1LhiHr/HkUBfgZRahK0MGcthwiLdFZwIBBQ==
    -----END DH PARAMETERS-----
    
    real	0m37.073s
    user	0m33.464s
    sys	0m2.924s
    hobbes@namagiri:~$
Edit: second run:

    real	0m35.362s
    user	0m31.992s
    sys	0m2.880s

Would somebody post the steps I should use to make my own OpenSSH sshd(s) use non-standard DH parameters? Do I need to do anything to my clients?


Bit late to the party here, but this is why I wrote https://2ton.com.au/dhtool/ ... I have 48 CPU cores still dedicated to constantly generating safe primes and generators (have amassed a huge number of 2k, 3k, 4k and 8k DH parameters if anyone's interested)

Any of the sizes' most recent 128 parameters can be downloaded in SSH moduli format, e.g. https://2ton.com.au/dhparam/4096/ssh


If you wanted, you could start a small business selling CDs with those DH parameters. Be of public service and make some money at the same time.


Very interesting. Any chance you'll be attending the Ruxcon security conference in Melbourne?


The EFF addressed this today. For SSH, they suggested this guide.

https://stribika.github.io/2015/01/04/secure-secure-shell.ht...

Indeed, the guide recommends generating new contents for the /etc/ssh/moduli file (IFF you keep `diffie-hellman-group-exchange-sha256` enabled).


Apparently `/etc/ssh/moduli` is where I should store newly generated DH parameters.

See the manpage moduli(5).

Hm, the format of the existing file does not match the format of what `openssl dhparam` generated. I'll research...


The dhparam command has mostly been used with Apache, as far as I know; ssh provides its own commands as part of ssh-keygen, which are described in the man page you just mentioned.

However, the paper authors say

"If you use SSH, you should upgrade both your server and client installations to the most recent version of OpenSSH, which prefers Elliptic-Curve Diffie-Hellman Key Exchange."

That might ultimately be a simpler and safer course unless you have to deal with old clients that you don't have the ability to upgrade.


I ran that command:

    Generating DH parameters, 2048 bit long safe prime, generator 5
    This is going to take a long time
Haha! It also made my CPU sweat nicely. I Ctrl+C^d after it ran for nearly 10 minutes with no sign of stopping though :( I see what you mean when you guys say it isn't feasible on every install of everything and why these are reused. I do think software maintainers should make an effort to do this regularly when new patches are released.

This actually opens up a new question in my mind: how does Open Source Software manage to keep these keys secret? Off to google...


The DH parameters created by "dhparam" don't contain any secrets; they're entirely public.

The secrets used in Diffie-Hellman are chosen by the participants in the key exchange at the moment that it's used.

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exc...

Here, the dhparam command is creating g and p (well, you're supplying g as a command-line argument, and the command is choosing p); those are the public parameters which can be published anywhere, can be given to anyone, and can be re-used by multiple sites and services (although the last case makes life easier for attackers if the p value is too small, as the researchers indicate it is for some popular Internet standards and software configurations).

When a Diffie-Hellman key exchange happens, the two sites agree (not necessarily in a secret way, indeed normally not in a secret way) on what g and p to use, and then one site secretly chooses a, the other side secretly chooses b, and they do the math that results in both sides knowing the same combined secret without other parties being able to determine it. Only a, b, and the resulting combined secret g^ab mod p are confidential; g and p aren't.

Diffie-Hellman can also provide forward secrecy because you can deliberately forget what values of a and b you used on a particular occasion, and then you can't reconstruct them (unless you can compute discrete logarithms, which is supposed to be difficult). That's not true for key exchange using RSA for confidentiality, where, if you still have the private key, you can still read your messages that were sent to you in the past using that private key.

Ciphersuites in TLS that use Diffie-Hellman in an ephemeral way ("DHE") will still use RSA, but for identifying the server (and optionally the client) and confirming that no man-in-the-middle attack has happened. So, they only use RSA for signatures, not for confidentiality, and they still get forward secrecy if they forget the DH private values associated with individual sessions. (Some servers use the same b value for multiple incoming connections, which reduces the degree of forward secrecy they get: if someone hacked them or seized their server while it still contained a particular b value, that person could decrypt previously recorded TLS sessions with that server that used the same b value.)


... thank you for trying to explain. I am still too thick to get it on first read. I have saved this in Evernote and will keep coming back to it after researching terms etc., until I understand in full.


I'm sure you'll want to keep reading about this, but let me just set out:

Diffie-Hellman involves four numbers, which are called g, p, a, and b (and which are used to calculate other numbers).

g and p are public, and are often used "for the long term" (including sharing g and p values between different Internet sites and services). The researchers found that the problem is that a lot of sites use the same p values, and the ones they use are too small, so that there is a single calculation that a government can do which allows them to break DH that uses those particular p values. Although this calculation is phenomenally expensive, it seems likely that NSA did it several years ago.

a and b are private and must remain secret. Commonly a different a and b are chosen each time Diffie-Hellman is used (like for each new connection or session with an Internet service).

Diffie-Hellman provides a property called forward secrecy because it allows two ends of a connection to derive a session key (which gets calculated using information derived from g, p, a, and b, and gets then used as a key for some other cryptosystem, normally some form of AES today, but in theory it could be anything) but then later "forget" what the session key was and how it was derived. Unlike other ways of doing key exchange, when the parties choose to "forget" their session key and associated information this way, they no longer have a way to recover or reconstruct it!

This is useful because, for example, if someone hacks the computer of someone who was using protocols with ephemeral DH, the computer likely won't contain information that could be used to reconstruct the session key and decrypt old communications. (That's assuming that the software scrubs key material from memory when it's no longer needed... which might not always be true.)


My totally unscientific estimates tend to be about 1 minute for 2048-bit primes and 20 minutes for 4096-bit primes.


So maybe we can do on-the-fly 2048-bit DH primes for securing access to a single-line dial-up BBS! :-)


Or worse, it knows how to update itself but those ways don't work any more.

Change is a bitch. As are proprietary and one-off updating schemes.


Do we need to upgrade that software to use an eliptic-curve fuckload?


Specific protocols might even specify that you have to use a particular prime.

Then the protocol would have to be rewritten and the change would not be backwards compatible.


FWIW, SSLLabs has recommended either not using 1024-bit DH, or using a non-standard prime for a while now.




Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: