Hacker News Reader

Comment by andyjohnson0 | Hacker News Reader

"For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. [...] an adversary can perform a single enormous computation to “crack” a particular prime [...]"

Can someone explain to me what the authors mean by "cracking" a prime? Is the difficulty of this related to the difficulty factoring a composite number? The language used is annoyingly imprecise.

Edit: Question was already asked by smegel, and has some useful answers.

View on HN

It's called index calculus[1]. Basically, it allows you to do a (huge) amount of work that can be factored out from breaking specific DH exchanges, as long as the same prime is used. Since finding good DH primes is far more expensive than coming up with good primes for RSA, these primes tend to be reused on a massive scale.

[1]: https://en.wikipedia.org/wiki/Index_calculus_algorithm

Traditionally, index calculus attempts for record discrete log calculations attempt to balance the "precomputation" step and the individual log calculation much more closely than in this work. This is more efficient if you only intend to perform one discrete log. One of the contributions here is that because of the massive reuse of primes, it would be more useful in a practical attack to shift much of the work into the steps solely dependent on the primes.

This system sounds incredibly insecure to me. What are the benefits of this over just plain old RSA with everyone using their own keys?

Forward secrecy in the event of a compromised key.

I would imagine it means creating a rainbow table for a particular set of prime numbers. From the article it sounds like many applications use a small handful of prime numbers. A DH key exchange uses two prime numbers (shared publicly) and two secrets (kept, secret...).

In theory the NSA could enumerate ginormous rainbow tables for a large set of secret keys.

Perhaps someone else on HN can provide a more detailed description of the suspected attack?

Edit: the responses to smegel's question below seem much mor e thorough and accurate than mine!

The rainbow table and the attack described here both do a lot of precomputation that can then be re-used for individual attack instances, but the rainbow table is a specific structure that only applies to reversing hashes -- a different problem from computing discrete logarithms.

I think the kind of precomputation you envision here is still too hard to do because the number of possible DH secrets is still much too big to examine all of them by precomputation!

Makes sense. With my primitive understanding I assumed this was why it was so computationally expensive still. But the descriptions by others make much more sense.

Reply on news.ycombinator.com