4 ms·
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
by 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 agoThere 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 agoAs 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.
- schoen 11y ago> 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 https://www.rfc-editor.org/rfc/rfc7627.txt
- murbard2 11y agoWell, 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?
- Peaker 11y agoIf 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?
- schoen 11y agoThat 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/ 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.
- epimenov 11y agoValidating 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 https://tools.ietf.org/html/draft-ietf-tls-tls13-09#page-49