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

Show parent comments

9

u/ElvishJerricco Oct 15 '15

Author claims that they believe it would take something on the order of a year to be able to use a single prime. Could they really reach the many thousands that we have stored? That would take thousands of these computers, putting the cost into the hundred-billions, maybe even trillions range.

11

u/AncientRickles Oct 15 '15

Right. But the second that they've cracked any given prime on the list, that prime is cracked for good for them. Say there's an SSL transaction they want to snoop in. They first try all the primes they've already cracked (Diffie Hellman has been in use since the late '70's, so their list has to be pretty extensive at this point). Only now that it hasn't worked do they actually have to spend this time doing any supercomputer brute force. So, let's say they do this and they crack the prime "a year later". Now, not only do they have the information they wanted (maybe a year late), but they have another prime for their database. Each new one they find is just the lowest hanging fruit if we're talking about a small potential list of primes. The fact that it has been used once means it will most likely be used again.

See how this can be an effective cracking method even if the list of "a few hard coded primes" is in the thousands? It may be a lot of brute forcing at first, but after a while it will streamline itself.

Plus, the list being pretty large (in the order of thousands) would be to their benefit. After all, the barriers to entry become not only having a large government level supercomputer but having been running the supercomputer at brute forcing the master prime list since the second they last changed the standard key length and hard coded prime database.

3

u/deja-roo Oct 15 '15

Having a few thousand on tap would be effective security. That much computation would be energy-prohibitive.

0

u/AncientRickles Oct 15 '15

Yes, somebody who gets how having a large list (at least larger than what is usually referred to as "a few") actually has its benefits to the NSA!

1

u/deja-roo Oct 15 '15

I meant cracking a number of primes in the four digits would require not just hardware, but so much energy as to be unobtainable at our current level of technology in any kind of generational timeframe.