2
$\begingroup$

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)?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.