The problem of 'Common DH Primes'

Question

NSA crack multiple encrypted channel by some tricks on 'Common DH Primes', which is a old news, but how actually they crack it? I still can't get the concept why using a 'Common DH Primes' will comprise a system. Can someone explain the process to crack a encrypted channel by using 'Common DH Primes'?

Answer 1

I'm assuming you're referring to logjam.

Using a common DH prime doesn't by itself compromise a system. But using a DH prime that is potentially within computational reach of an organization, especially one that is widely used, is. The authors estimated that cracking a 1024 bit prime might be possible for an organization such as the NSA, given a huge amount of resources (several hundred million dollars) and time (1 year).

Attacking DH is done by computing the discrete log, using an algorithm called NFS. It turns out that for the classical DH (using the multiplicative group of integers, modulo a prime $p$), the attack can be amortized over all discrete logs in a group. In other words, most of the work needed to solve the discrete log using NFS only requires knowledge of the group (defined by the prime $p$), and not the computed value $g^a$ (different for every connection). This means that the attacker can do a huge amount of precomputation and then attack individual connections very quickly.

So the authors suggest that since most of the internet uses only 1 or 2 specific 1024 bit primes, an organization could invest heavily to do the necessary precomputation. Then individual connections can be broken quickly, by computing the last step in NFS. If you want to know how that works, read the link K.G. gave, or learn how NFS (Number Field Sieve) for the discrete log works.

All this can be prevented in a couple of ways. One, simply use larger primes. Even if the entire world used one specific 2048 bit prime, it would (probably) be impossible for an organization to crack encryption in this manner, amortization or not. Better yet, switch to elliptic curve DH. Elliptic curves don't suffer from the same precomputation woes, meaning attacks on parameters that are barely within computational reach only compromise one connection, rather than all those using that group.

Answer 2

bkjvbx has explained this in detail. I'm going to summarize the specific point that you asked about.

Using the same DH group (“same primes”) for many communications is not in itself a problem. There is no weakness in reusing the same group, even a very large number of times: it doesn't make attacks easier.

However, using the same group a lot makes it a more attractive target. Most of the work in doing the attack is independent of the specific secrets that are exchanged: it can be done for the group as a whole. So if everybody uses the same group, an adversary with a lot of computing power can perform the (extremely expensive) computations for that particular group, and once this is done they can break all communications that use this group. If everybody used different groups, the adversary would have to perform those expensive computations many times instead of once and for all, and the attack would switch from being just barely feasible to infeasible.