How to Backdoor Diffie-Hellman
eprint.iacr.org
eprint.iacr.org
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.
Unless they've read this :)
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.
[0]https://en.wikipedia.org/wiki/Dual_EC_DRBG [1]https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
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.
[0]https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
exploring how DH can be mathematically attacked (but still computationally infeasible, just much easier), and,
ways that a library implementing DH could be backdoored/weakened to make one of those attacks computationally feasible to a well-equipped adversary.
EDIT: if you like code more than math, the paper links to this repo for some examples: https://github.com/mimoo/Diffie-Hellman_Backdoor
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_.
http://noiseprotocol.org/noise.html
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.
Thank you for posting it.
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."
That's what I assume is happening on a large scale - there is a reason why Bluffdale came to live.
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.
is that the same as "constructions using something-up-my-sleeve numbers?"
However, there is no reference. Anyone got any sources cause I'd like to check this out.
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.