So ... explain like I'm five. :) How can Diffie-Hellman, which has been taught ad infinitum as a safe method for key exchange, be discussed like it has a loophole?
Diffie-Hellman implemented very carefully can be a one component of a sound crypto protocol that does key exchange.
Both italicized phrases are important:
* It is extremely easy to implement textbook Diffie-Hellman in ways that are gravely insecure. In addition to domain-specific software implementation concerns that you must known about to safely implement number-theoretic crypto, you also have to carefully select parameters. It's parameter selection weaknesses David's paper takes advantage of.
* Diffie-Hellman by itself produces trivially breakable cryptosystems. DH is a building block. To build a safe protocol that uses DH, you need a higher-level construction --- usually, an authenticated key exchange. Check out the Noise protocol framework for more details on what this looks like. As you skim it, try to think about how relaxing or altering any of the constructions in an instantiation of Noise might produce a crypto vulnerability. This stuff is _hard_.
The basic idea of the paper is to explore the different species of [p,g] DH parameter tuples you can come up with to produce a version of DH whose key exchanges are cryptographically difficult for randos to break, but easy for their authors to break. For instance, you can set p = pq for p and q sharing a bad generator g.
A true cryptographic "NOBUS" DH backdoor is an interesting thing to have: you can deploy it across the Internet and it will chug along executing key exchanges that only you, as the author of the parameters for the backdoor, can break.
To be pedantic, I don't think the Diffie-Hellman is the weak link as it doesn't specify the group or generator. It just requires that given g^a and g^b it's hard to determine g^ab. And obviously if your generator is poor the preconditions to the algorithm don't work. And then as what the post-conditions for what DHKE provides. It just establishes a shared secret with the person on the other end of a connection. You have no idea who that other person is, but you can communicate securely with them (which is why you need authenticated encryption).
I guess a better wording would be "It's extremely easy to implement textbook Diffie-Hellman Key Exchange in was that don't satisfy the preconditions of Diffie-Hellman, and this are gravely insecure."
Not specifying the group/generator is a weak link, which is what David is taking advantage of. Curve25519 is a good counterexample of a DH function that leaves nothing to the imagination.
> A true cryptographic "NOBUS" DH backdoor is an interesting thing to have: you can deploy it across the Internet and it will chug along executing key exchanges that only you, as the author of the parameters for the backdoor, can break.
That's what I assume is happening on a large scale - there is a reason why Bluffdale came to live.
You can think of it as a magic trick. The magician is convincing you the he's computing a totally legit action X, all the while abusing your trust (or your cognitive biases) to perform action Y instead right under your nose.
In this case, the abuse is to have you believe the modulus---which defines the core mathematical structure you're working on---is a prime, when it is not. Once you manage to sell this, and clearly not everyone checks the primality of their moduli, the rest become implementation details.
I think this is a rather about building a backdoor into a library which implements Diffie-Hellman, if I understand this correctly. The method itself is not flawed.
Just to make it slightly clearer this is about a "mathematical backdoor" not a software one.
This isn't about making a backdoor that looks like this:
for each (user.session.ip_addr in nsa_addrs[])
{
user.session.isauth = true;
}
This is about weakening the mathematical constructs of a DH implementation in a way that would not be noticeable even in a code review conducted by software security experts.
Only if they have both the capability and knowledge of reviewing how certain cryptographic parameters / initial states were chosen this isn't something you can easily detect unless you know very specifically what you are looking for.
This isn't that much different than the ECC "NSA" NIST presumed backdoor in the Dual-EC module of RSA[0].
The Dual-EC backdoor was pretty much identical to a one that 2 cryptographers presented in 1997 however it took about 15 years for this to be "discovered" and even now we don't have decisive proof that the NSA or any other entity had selected those specific values because it pre-computed (or potentially knew it could compute it within X amount of years) the relationship between them.
There aren't that many security experts that can audit such systems in the first place, and the few that can will most likely not have the same resources that a state actor level adversary would to select values that could be used for a NBOUS backdoor, even if you know what you are looking for when testing initial values some one with 10 times the computing power you have can select better values that would both serve as a backdoor and would be resistant to reversing by outsiders.
My personal projection for the next 10 years or so is that there will be a huge push towards dumping any cryptographic system that is based on some initial seed values and/or a lot of work needs to be done to be able to generate or prove NUMS[1] in regards to those values.
I believe both attacks described here require the modulus to be composite not prime. Wouldn't then the only necessary review necessary be to check the primality of the modulus used in DH?
Primality tests are effectively brute force computations, if your adversary has considerably more compute power than you they could calculate values that you would not be able to identify as being composite.
For example SSH-Keygen uses the Miller-Rabin[0] test on the moduli and depending on the bit size if your number and the number of rounds you get a probability of how likely it is that the number is prime or not, but effectively there is never a guarantee because of the size of the numbers in question.
The likelihood of an adversary being able to compute a value that you would consider to be prime but infact it would not be is directly tied to the size of the number, the method of verification you are using, and how much resources you are spending to evaluate that number.
Given an adversary that in all likelihood completely outclasses you in computational capacity, and is also likely to be able to develop more efficient algorithms than those available to you there is a pretty good chance that they will able to backdoor you every time without you having an effective counter measure or the ability to detect it if they choose to do so.
Recall not that long ago that the default DH group in SSH may have been defeated by NSA or someone similar. So now, during key agreement in SSH, the server and the client agree on the DH group that they will proceed to use, and I believe that the server provides the group. If the client trusts the server without verifying the DH modulus is appropriate (of the form 2p + 1 with p prime), then a malicious server could weaken the connection by providing one of these weaker composite numbers.
Haven't read the paper but the abstract suggests it is describing how to weaken or compromise an otherwise correct implementation of DH. Not a fatal flaw in the DH itself that would exist in all implementations.
Because there's a big difference between theory and practice. There are sneaky ways of hiding subtle weaknesses in real DH code that aren't readily apparent. This is actually a more general problem than just DH. How do you know that the supposedly secure chat app that you downloaded as a binary isn't using steganography to expose your keys?
The title is suggestive of a vulnerability in the DH key exchange protocol, which is misleading. Plus the technique described can be used against many crypto primitives that depend on trustworthy random number generators. Please consider changing the title to something less click-baity
Not necessarily. If you can show that you're using nothing-up-my-sleeve numbers, everyone knows (that part of) your construction is safe. But if you can't show that you're using them, it doesn't necessarily mean you've backdoored it.
It is mentioned in the article that:
"Note that the concept of “ephemeral”
is not defined the same by everyone: the default
behavior of OpenSSL, up until recent versions,
has been to generate the ephemeral DH
key at boot time and cache it until reboot,
unless specified not to do so."
However, there is no reference. Anyone got any sources cause I'd like to check this out.
For someone whose almost exclusively studied cryptography in cyclic curve groups rather than cyclic integer groups (coming from an algebraic geometry background). Maybe someone can explain to me why the modulus isn't always chosen to be prime for DH? Is there some reason you would ever want to allow composite modulus in DH?
As far as I know, using a composite modulus is bad. It means that some of the integers (besides the obvious case of 0) no longer exhibit the group properties. That said, it only makes it a bit more difficult to find a generator. I am not sure about the overall security implications.
However, the plan here is too get someone to use your chosen modulus which is weaker. I'd suppose they are banking on no one checking that the modulus actually is prime.
I see - I searched for a while and it seems (if I'm reading correctly) that right in the RFC from 1999 it says to use / check prime-ness of the modulus: http://tools.ietf.org/html/rfc2631 so I'm still a bit confused - maybe the point is that it's commonly not done?
