Slashdot Mirror
How Is the NSA Breaking So Much Crypto? (freedom-to-tinker.com)
schwit1 writes: There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a "computing breakthrough" that gave them "the ability to crack current public encryption." The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.
However, the documents do not explain how these breakthroughs work, and speculation about possible backdoors or broken algorithms has been rampant in the technical community. Yesterday at ACM CCS, one of the leading security research venues, we and twelve coauthors presented a paper that we think solves this technical mystery.
If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn't just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to "crack" a particular prime, then easily break any individual connection that uses that prime.
However, the documents do not explain how these breakthroughs work, and speculation about possible backdoors or broken algorithms has been rampant in the technical community. Yesterday at ACM CCS, one of the leading security research venues, we and twelve coauthors presented a paper that we think solves this technical mystery.
If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn't just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to "crack" a particular prime, then easily break any individual connection that uses that prime.
Scott Aaronson has an excellent summary of this research on his blog: http://www.scottaaronson.com/b... One point that Scott makes that is easy to lose track of is how much working this out required people on both the theoretical crypto end and the practical crypto end to work together. This is a combination of multiple vulnerabilities and some clever number theory.
Apparently you have no clue how many ages of the universe it would take to enumerate the 256-bit primes.
We are nerds here, so lets calculate it. The number of primes less than N is approx ln(N), so the number of primes less than 2^256 = (2^256/256) = 2^248 = 4.5e74. If you computed one prime per plank time, it would take this long: 4.5e77 * 5.4e-44 secs/planckTime / (1.38e10 years/universe * 3600 * 24 * 365) = 2.3e12, or about 2 trillion times the age of the universe. 512 bit primes would take considerably longer.
Once you calculate the list of primes, you need to figure out where to store it. Storing 4.5e74 numbers is problematic, since that is about a quintillion times the number of atoms in the sun.
We can be fairly certain that the NSA is not just relying on a lookup table.
Here I was about to give you grief on your math ( ln ( 2^512 ) ~= 354 ), and then realized the problem was simply that you mis-typed the initial theorem.
For anyone else thrown off, the correct rule is that there's approximately N / log( N ) primes less than N.
--- Most topics have many sides worth arguing, allow me to take one opposite you.
For anyone else thrown off, the correct rule is that there's approximately N / log( N ) primes less than N.
Sorry about that. But the math is still wrong. It is supposed to be ln (log base e) and I did the calculations with log2. So the number of primes less than 2^256 should be (2^256/177) = 6.5e74, not 4.5e74.