# At what modulus size does the logjam reduction stage become impractical?

Attacking a Diffie-Hellman exchange with logjam involves a massive precomputation effort once for the group, and then a comparatively simple reduction stage that is necessary to break each individual handshake. At what DH size does the reduction step, which isn't precomputed, become impractical?

For example, if the reduction stage on an 1024-bit DH group is possible to perform in real-time and the precomputation stage takes one year and \$10 million in hardware (estimates from the original logjam paper), how large would the DH group need to be for the reduction stage to demand the same cost of \$10 million in hardware and a single year (effectively negating the advantage of the precomputation)?

## 1 Answer

It is hard to put concrete costs to these steps at this scale, and the parameters can be tweaked to make the precomputation more expensive to render the individual log cheaper, but we can try to do it asymptotically to get an idea. The complexity of the precomputation step is $$L_p[1/3, 1.923] = \exp\left((1.923 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,,$$ which in the case of a 1024-bit prime field—and assuming $$o(1) = 0$$—would amount to roughly $$2^{86}$$ operations$$^1$$.

The individual logarithm, on the other hand, has a smaller complexity of $$L_p[1/3, 1.232] = \exp\left((1.232 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,.$$ Once again, if assuming $$o(1) = 0$$ we would need a roughly $$2900$$-bit prime for the individual log step to match the cost of the 1024-bit precomputation. The precomputation step for $$2900$$ bits would be beyond $$2^{128}$$ operations.

$$^1$$ This complexity figure often ignores memory and storage costs, which as numbers grow becomes more and more important, but this is a rough approximation anyway.