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.
How is this news? Sounds like they are just describing the logjam attack which was published earlier this year
They are estimating the computation effort to build a number field seive to efficiently compute logs over the 1024 bit prime groups in common use for plain old Diffie Hellman.
They recommend elliptic curves and not the NIST curves. From TFP:
"Transition to elliptic curves. Transitioning to elliptic
curve Diffie-Hellman (ECDH) key exchange with appropriate
parameters avoids all known feasible cryptanalytic
attacks. Current elliptic curve discrete log algorithms for
strong curves do not gain as much of an advantage from
precomputation. In addition, ECDH keys are shorter than
in “mod p” Diffie-Hellman, and shared-secret computations
are faster. Unfortunately, the most widely supported ECDH
parameters, those specified by NIST, are now viewed with
suspicion due to NSA influence on their design, despite no
known or suspected weaknesses. These curves are undergoing
scrutiny, and new curves, such as Curve25519, are
being standardized by the IRTF for use in Internet protocols.
We recommend transitioning to elliptic curves where
possible; this is the most effective long-term solution to the
vulnerabilities described in this paper."
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
If you use 2048 bit or 4096 bit RSA and you dont make mistakes in generating the key, RSA is still perfectly fine to use short of a quantum attack (even if the NSA had a classified supercomputer that was more powerful than all the supercomputers on the top 100 list combined filled with custom RSA-cracking ASICs they still can't crack high-strength RSA using any known mathematical formula)
I do agree that TLS needs replacing with a new protocol that only supports the strongest encryption (that means 256 bit AES, at least 2048 bit RSA, ECDH with perfect forward secrecy and SHA2/SHA3 for hashing) and has no mechanism to downgrade to any older protocols or to weaker encryption like MD5, SHA1, RC4 etc.
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.
There's no need for a new protocol; TLS allows you to configure servers and clients to restrict the available ciphers. That's why the browser vendors have been able to push out MD5 (and moving on SHA-1), RC4, RSA 2048 bit, etc. No protocol changes were necessary; just remove ciphers from the supported list used to negotiate the connection.
BTW: research indicates that AES256 may in fact be slightly weaker than AES128, in some use cases. Both are still have no practical attacks, even for nation-state level attacks; at this time, there is no evidence that AES256 would be "more secure" in practical terms (i.e. billions of years to break one encrypted message) than AES128. Given that, there is no reason to replace AES128 with AES256, now or in the foreseeable future. Odds are that if some attack vector against AES is found, it will be time to move to a new algorithm, not just more bits/rounds.
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.
Yes, there are quantum computer resistant public key crypto algorithms. A quick Google search would have shown you that. Wikipedia has decent summaries of the state of the art, as well.