Based on Diffie-Hellman's negotiation of key exchange, why would it turn out that only a few primes are commonly used? What and who determines the prime?
Would it not be safer to use a safe prime? (example: p = 2q + 1)
*The question is based on this article:
Edit #2 (11/09/15) - I read through a few articles and a paper. See down at bottom for more comments.
I read the article, although I have no direct data on the following, so guess work on my part.
There are a combination of factors going on here.
The exchange requires that the two parties have the Base Prime. It ought to be a Safe Prime (or Sophie-Germain Prime). If the client doesn't have it, the server will send it over. Both parties should use secure random number generators to create their exponents. Computations should be structured such that successes and failures take the same amount of wall clock time.
Generating large Primes is not hard, but it is for the uninitiated. Having a piece of software that does it for you is best. That software must use a secure random number generator. Most people will just use whatever keys (primes) that have been pre-provisioned out of habit, ignorance or laziness.
It's entirely likely that much of the software in question wasn't engineered to allow a Prime number change. Engineers who author the software are often as ignorant of proper security methodology as the users. I don't mean that pejoratively; ignorant as in "lack knowledge".
Where to start!
A shorter key (768) was well within the ability for a couple of graduate students to compute partial discrete log matrices and attack Sun's network password authentication scheme a couple of decades ago. See reference at end of this Answer. I wouldn't be surprised if the NSA (or anyone) has the ability to compute partials for known 1024 bit keys, today.
The protocol can be attacked by replacing the Prime in transit to the client if the client doesn't have the Prime and requests it from the server.
Even better, DH is subject to man-in-the-middle attacks, especially with a client that requests the Prime from the server, but even if it doesn't. The DH algorithm relies on secure exponents being computed. However, it doesn't rely on any other data - server and client need not prove each other to establish a secure session. If somehow the client's password (or a hash of it) were mixed into the DH key negotiations without any information leakage and retaining perfect forward secrecy, then the client could be assured the server was legitimate. Look up the SPEKE and DHEKE algorithms for a start on this. In any event, NSA as MITM creates two DH sessions, one with the client and the other with the server and records all data while piping between the two. Easy peasy.
The article states that NSA relied on well known Primes to attack the sessions. I refer back to the paper I mentioned about computing discrete log partial matrices. If possible now with h/w advances, 1024 bit keys wouldn't provide secrecy from observer attacks.
Who's to say the machines running the DH algorithms weren't compromised in some other way? Perhaps, they leaked key data or gave it up when queried in the right way? There has been so much information published about how every piece of computational h/w can be compromised by the NSA, perhaps they didn't bother breaking the algorithm unless they needed to, and instead broke into the machines and got the session encryption keys directly?
Edit
Other DH attacks:
g^(A*B)%P should map 1:1 or 2:1 over the field of P; a bad P can map large swaths of numbers to a computationally feasible small set.I read an article linked through and the twelve author paper posted.
As suspected above, here's the gist of it. At the end I'll add a little bit more on TLS+DH+RSA cipher suite, just to show another vulnerability.
First off, it appears likely that the NSA has broken a number of the commonly used DH Groups (Safe Prime P + Generator g) used for Diffie-Hellman key exchange. As I indicated above, at least a decade or so ago, this attack was completed by a couple of graduate students (still don't have reference) on Sun's 768 DH key used for network password authentication. The attack is an observer attack, so no man-in-the-middle needed. The work required to break any particular Group is quite large. However, once broken, all exchanges using that can now be compromised.
Theoretically, DH key exchange provides Perfect Forward Secrecy (vs. RSA which does not). Once the a DH group is broken, any exchange using that group not is compromised going forward, it's also compromised going backward (ie. recorded exchanges can be broken), so no more perfect forward secrecy for that group. It also means that a dedicated attacker could break uncommon DH keys. This is assumed to be possible for 1024 bit keys, so up your key lengths to 2048 for DH. You should already be using larger key lengths for RSA.
Next, the researchers make a number of notable points. The paper covers Logjam, which I won't explain in detail except to say it's a MITM, cipher suite downgrade attack. Clever, but not algorithmically complex.
I strongly urge anyone interested to read the paper. It's fantastic. Here's the second paragraph of the Abstract.
We go on to consider Diffie-Hellman with 768- and 1024-bit groups. We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources. A small number of fixed or standardized groups are used by millions of servers; performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers. A close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break. We conclude that moving to stronger key exchange methods should be a priority for the Internet community.
That pretty much says it all. Fixed keys, broken by the NSA allows observer (passive) breaking of many of the secure networking protocols. So, don't use pre-provisioned or common keys (if possible) and/or up your key lengths.
As for the TLS+DH+RSA cipher suite, is this safe at higher key lengths?
I would hazard that it is safe from an observer attack, however, it's still subject to man-in-the-middle attacks and here is how.
In this mode, the Server signs its DH ephemeral with its RSA key (Sign((g^B)%P,RSA_Key_Server)). That means, the server's portion of the DH exchange is authenticated. Assuming the signature is valid when it reaches the client and the Server certificate has not been revoked, the client can proceed safely with the DH exchange knowing only the server can complete it.
How, then, is a MITM possible? Two ways, one more likely than the other. Both rely on the client failing to do a proper signature check.
First, the client has too many root certificate authorities in its key store (many browsers have over 100). Some of these root CAs are not trustworthy. MITM gets a server cert for the remote site in question, sits in the middle and signs with its own cert (Sign((g^B2)%P,RSA_Key_Middle_Server)). The client will validate the signature, assume the server is authentic and complete the DH exchange with the server. Meanwhile, the middle server can run its own client side of the exchange with the real server and watch all data in between.
Second, I think this is less likely. The client fails to check for a revoked certificate and the MITM has the revoked private key, so it can sign as if it were the original, real server. Client won't know because it didn't check revocation. Middle server, again runs another DH exchange with remote, real server and sits in the middle.
Moral of the story is watch your client configurations and up your key lengths.
EDIT #3: Found the reference to the DH attack a couple of decades back:
B.A. LaMacchia and A.M. Odlyzko. Computation of discrete logarithms in prime fields. Designs, Codes, and Cryptography, 1:46-62, 1991.
One method of breaking them is by finding ways around it. There are almost always ways around all types of security. I subscribe to the mentality of, "If man can build it, man can destroy it."
You can Install backdoors in common software such as Adobe Flash, PDF and, of course, in Java. Let's not forget Windows services. Then you have things like hardware that come pre-installed with back-doors.
All you have to do is implement something that allows you to run arbitrary code when properly executed. There are many ways to do this on many platforms and in pretty much any programming language.
Purposely implementing security flaws is one of the things that certain agencies really like doing.
Then encryption isn't even needed. Who cares about your quad-layer Dr. Dalek encrypted VPN connection when there are many different ways around it?
