Hacker News Reader

Comment by olympus | Hacker News Reader

This recent publication illustrates a problem that we have trying to keep our communications secure. If we all use a single "strong" prime number with our crypto then the NSA has a huge incentive to pre-compute results from that single strong number. Now that we know that the NSA is doing this, we won't all use a proven strong number, and we will all start to do key exchanges with another method, and it will become the common thread that the NSA can attack.

So the NSA will pretty much always attack whatever common procedure we all use and find the weak point. If we all used different methods for key exchanges and encryption then we will all be fractured and the NSA can easily pick off their targets individually. What's the answer to this problem? Is there crypto that we can all use that the NSA won't be able to crack even if they have a strong incentive to do so? And why aren't we all using if such a solution exists?

View on HN

Not really. This precomputation attack only works because attacks on 1024 bit discrete logs were already plausible.

We don't choose cryptographic parameters to make the NSA's job harder; we choose them to make the job implausible.

So it's exactly the wrong message to take from this paper that we should mix up parameters more; rather, the message is: don't use weak moduli.

> don't use weak moduli.

By this do you mean don't use 1024 bit keys? Would using 2048 bit (or larger) mean that the NSA wouldn't be able to buy a computer that could do the computation within a year?

Why don't we all use 2048 bit keys then? Is the communication and processing overhead so high that we'd rather be vulnerable?

Edit to add: I'm not an expert, but I'm competent enough to force a certain level of crypto on my computer and to know not to trust the communication when a website forces a fallback to a lower level. But sometimes I wish there was a level of explanation (of why we want to do certain things) that was above what you would give to "Joe off the street" and below the explanation that you would give to a graduate student in cryptography.

NSA almost definitely can't buy a computer that can break 2048 bit conventional multiplicative group discrete logs, and if by same insane space-alien-technology chance they can, the implication is that conventional multiplicative group discrete logs are probably entirely unsuitable for secure cryptography: no amount of jazz-hands with parameters will save you.

Reminder: 2048 bit discrete logs aren't just twice as hard as 1024 bit discrete logs!

Yes: 2048 bit RSA and DH are significantly slower than 1024 bit, and that's a big part of why they're still in use.

> By this do you mean don't use 1024 bit keys? Would using 2048 bit (or larger) mean that the NSA wouldn't be able to buy a computer that could do the computation within a year?

Keep in mind, going from 1024 to 2048 bit DH parameters doesn't double the search space, it raises it from 2^1024 to 2^2048. At some point the search space gets so large that you'd need more energy than required to boil all of Earth's oceans to find the key, which makes such a brute-force attack implausible.

I haven't had much crypto-in-practice background (outside of thought experiments), but I have some math background so I'm quite curious. Shouldn't people also be worried about non brute force attacks based on finding mathematical solutions? I mean, "The Uneasy Relationship Between Mathematics and Cryptography"[0]?

[0] http://www.ams.org/notices/200708/tx070800972p.pdf

The attacks we're talking about are non-brute-force mathematical attacks (specifically, in this case, the index calculus). A pure brute-force attack on a 2^1024 search space would be comically implausible.

Actually that is wrong. The search space of 1024 bit Diffie Hellman is about 2^80, of 3248 bit about 2^128. I failed to find a number for 2048 bit DHE.

Reply on news.ycombinator.com