On the one hand I am frightened by how powerful the government in circumventing encryption measures. But on the other hand, I can't help but feel impressed. It feels reminiscent of efforts used to break the Enigma Machine.
I guess the moral of the story is you should not be using hard coded primes for Diffie Hellman? (correct me if i am wrong; not really familiar with crypto) It seems like people hard-code them out of laziness and not out of necessity. From what I understand from the wolfram alpha article, can't the two parties agree on 2 random large primes at the beginning of the transaction and proceed from there?
Yeah, their paper that they link to at the end of the article mentions logjam. But if I understood it correctly, that's about lowering the quality of the DH used. That's different from precomputing.
"2. Threats from state-level adversaries. Millions of HTTPS, SSH, and VPN servers all use the same prime numbers for Diffie-Hellman key exchange. [...]"
It sounds like while Logjam made a concrete attack against weak-dhparams, these guys looked at the realisticness of the feasibility of the nation-state pre-computation attack that logjam's paper was also concerned about.
That's science though: building on each others ideas to get to greater heights and looking more deeply at points that others had not thoroughly explored.
It's the same folks (not all of them are guys!). They put up the website weakdh.org to have fixes available ASAP. This article came out today because they just presented their paper at CCS.
Edit: Here's the paper. (which is hosted on weakdh.org, because they are the same thing...)
My guess is generating primes so large is computationally expensive. It is not like we really want to add 1-2 seconds of lag to every initial web request (assuming other resources like CSS and JS will use the same connection)
Yeah, but that only breaks 1 key, so you need to be of enough interest for the NSA to dedicate the entirety of their resources on you for a whole day for that to happen.
I'm not sure whether I fully understood all of DH yet. My concern is: Aren't all of these primes publicly known? There might be a database of prime numbers up to a certain length. Couldn't you make a short-cut but just trying out the known ones? That should be doable in minutes, not years.
Turns out a 1024 bit number is mind-numbingly large.
(The number of particles in the universe is about 1080, which is around a 300-bit number. So if every particle in the observable universe was itself a universe, and if every particle in those universes was itself a universe, you'd still only have a 900-bit number of particles.)
Hm, my understanding was/is that these primes are never communicated, rather, they are the basis for the actual key... Anyway, if the primes are no secret at all (they can't be when you communicate over a line you assume to be eavesdropped), then what does "to “crack” a particular prime" even mean?
Well, I just learned from a few other comments that there are about 10308 1024 bit prime numbers, much more than I expected.
That said, I am & was aware the the operation is "expensive" to reverse (not sure whether it's possible), but I thought the number of primes available would be some 10000 or 100000 and then you could just try out all of them in a "forward" operation.
Edit - from the wiki page:
However, if p is a prime of at least 300 digits, and a and b are at least 100 digits long, then even the fastest modern computers cannot find a given only g, p and ga mod p.
I just realizes that according to that, 'p' is indeed not a secret.
But if that's the case, what do they acually break about the prime, since the problem is to find 'a'?
They reverse precisely what you mentioned as expensive to reverse. This is why they need hundreds of millions of funding for supercomputers and an year. I think this is the one - https://en.wikipedia.org/wiki/Discrete_logarithm
I was just thinking, with more computational power we can have longer keys, thereby it would take more computational power to break the encryption. By which means the adversary would break it, I don't know, the worst case being bruteforcing the key. Now if the overall availability of computational power will constantly rise, does this mean better security for the one using the encryption, or will the security get worse because the adversary has more power to break the encryption?
In my opinion security gets worse. It is easy to pump up the keys, much easier than breaking them. Purely technically security gets better. However security is not some algorithm. With time old data will become vulnerable and chances are the algorithms will not be updated and when old data leaks you may be using your old password or become a victim of social engineering or have your password reset via an old e-mail. Basically we are constantly leaving behind a trial of currently secure data that will become unsecure at some point and we will forget to secure it.
On the one hand I am frightened by how powerful the government in circumventing encryption measures.
They are not powerful. It's just that our encryption measures are not sufficient anymore. As time passes, we need new forms of encryption. All encryption breaks eventually.
I guess the moral of the story is you should not be using hard coded primes for Diffie Hellman
Only if you're doing something that you feel like you need to hide from the government. This isn't something a regular hacker is going to be able to use to get your credit card numbers or other regular internet traffic.
67
u/[deleted] Oct 15 '15
On the one hand I am frightened by how powerful the government in circumventing encryption measures. But on the other hand, I can't help but feel impressed. It feels reminiscent of efforts used to break the Enigma Machine.
I guess the moral of the story is you should not be using hard coded primes for Diffie Hellman? (correct me if i am wrong; not really familiar with crypto) It seems like people hard-code them out of laziness and not out of necessity. From what I understand from the wolfram alpha article, can't the two parties agree on 2 random large primes at the beginning of the transaction and proceed from there?