6 ms·

"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 securit

"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?

tptacek 11y ago
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.
- dadrian 11y ago
  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.
  - schoen 11y ago
    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 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-ff-dhe/ 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.
    - dadrian 11y ago
      My totally unscientific estimates tend to be about 1 minute for 2048-bit primes and 20 minutes for 4096-bit primes.
      - schoen 11y ago
        So maybe we can do on-the-fly 2048-bit DH primes for securing access to a single-line dial-up BBS! :-)
    - daveloyall 11y ago
      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?
      - daveloyall 11y ago
        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...
        schoen 11y ago
        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.
- dredmorbius 11y ago
  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.
- vacri 11y ago
  Do we need to upgrade that software to use an eliptic-curve fuckload?
dogma1138 11y ago
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..
- misiti3780 11y ago
  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
  - tptacek 11y ago
    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.
    - misiti3780 11y ago
      ok that makes sense ... thank you
    - BinaryIdiot 11y ago
      Thanks for that explanation; I had thought similar to the parent until I read this and it just "clicked".
    - azinman2 11y ago
      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.
Buge 11y ago
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.
amluto 11y ago
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.
- phicoh 11y ago
  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.
  - schoen 11y ago
    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-hash-01.txt 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.
aidenn0 11y ago
FWIW, SSLLabs has recommended either not using 1024-bit DH, or using a non-standard prime for a while now.

tptacek 11y ago

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.

dadrian 11y ago
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.
- schoen 11y ago
  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 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-ff-dhe/ 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.
  - dadrian 11y ago
    My totally unscientific estimates tend to be about 1 minute for 2048-bit primes and 20 minutes for 4096-bit primes.
    - schoen 11y ago
      So maybe we can do on-the-fly 2048-bit DH primes for securing access to a single-line dial-up BBS! :-)
  - daveloyall 11y ago
    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?
    - daveloyall 11y ago
      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...
      - schoen 11y ago
        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.
dredmorbius 11y ago
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.
vacri 11y ago
Do we need to upgrade that software to use an eliptic-curve fuckload?

dogma1138 11y ago

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

misiti3780 11y ago
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
- tptacek 11y ago
  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.
  - misiti3780 11y ago
    ok that makes sense ... thank you
  - BinaryIdiot 11y ago
    Thanks for that explanation; I had thought similar to the parent until I read this and it just "clicked".
  - azinman2 11y ago
    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.

Buge 11y ago

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.

amluto 11y ago

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.

phicoh 11y ago
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.
- schoen 11y ago
  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-hash-01.txt 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.

aidenn0 11y ago

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