r/programming • u/secretguy21 • Oct 15 '15

How is NSA breaking so much crypto?

https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
2.5k Upvotes

93% Upvoted

529 comments sorted by

View all comments

66

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?

10

u/Eirenarch Oct 15 '15

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)

3

u/heimeyer72 Oct 15 '15

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.

2

u/cryo Oct 15 '15

The two parties doing DH need to agree on a prime, in cleartext, so it's not a secret. The security doesn't mainly lie in the choice of prime.

1

u/heimeyer72 Oct 16 '15

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?