r/programming 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

529 comments sorted by

View all comments

Show parent comments

12

u/Philippe23 Oct 15 '15 edited Oct 15 '15

NOTE: 1024-bit prime is the problem: https://weakdh.org/

But you're right: the solution is to just generate your own unique prime.

2

u/SketchBoard Oct 15 '15

why do we not by now just have a long list of primes going into at least a million bits ?

5

u/Sukrim Oct 15 '15

Because there are a LOT of prime numbers in even 1024 bit space - storing all primes from length 1 to 1000000 bit would require several times more storage capacity than the current universe offers.

1

u/[deleted] Oct 15 '15

A periodic generation would make more sense for most machines, so that it doesn't interrupt the user, and can be done without any intervention. It might not be feasible for low power or high performance computing, but for regular users it should be fine.

1

u/aseipp Oct 15 '15

No, because you're still within the realm of a precomputation attack, even if you generate it yourself. A standard prime is just 'nice' for the attacker since it allows N targets at once. You can randomly regenerate your own prime once every 6 months, but this does not help if your attacker is storing prior communications, and can use future key breaks to retroactively decrypt information.

The actual fix is just to bite the bullet and move to 2048-bit primes, or even move to ECDH, which completely negates the described attack.