The S-box was constructed in an explicit and simple algebraic way so as to avoid any suspicions of trapdoors built into the algorithm.Really? Can't we trust the government not to put back doors into our standardized cryptographic algorithms?
After reading last week's New York Times article on the NSA, I realize my naivety. The NYT article doesn't go into how and which protocols the NSA has their hand in but I now understand the concern.
It doesn't look like the NSA has actually broken cryptographic protocols, have a secret quantum-like computer in their basement or polynomial-time algorithms for SAT. I could go on for pages but Scott has done an excellent job talking about the complexity issues involved. They've more likely found ways to access your information before it has been encrypted or after its been decrypted.
Matthew Green wrote a nice post speculating on what the NSA might be able to do, so nice that it caused some controversy at Johns Hopkins.
The whole Snowden affair gives us a glimpse into the NSA but they hide their capabilities well and we'll never know the full extent of their knowledge.
The AES was designed by two Belgium researchers, not the NSA.
ReplyDeleteI believe Lance's quote of TW actually refers to the possibility of trapdoors in the S-boxes of DES. I am not sure if anyone understands what fuzzy math works behind those S-boxes. In contrast, the S-box devised by Joan Daemen and Vincent Rijmen has nice clean algebraic construction.
DeleteTo add to above citation from that textbook, I remember my first interaction with a world class cryptographer. I was working on symmetric key encryption, and his idea about AES competition was, to quote him, "..forget about the fast hardware implementations; AES is *transparent* unlike DES."
ReplyDeleteI am not sure whether the dual EC pseudo-random number generator is actually used in practical systems (I would be rather surprised if the answer is yes), but yes, the credibility of NIST has come in to serious doubts. In any case, in CRYPTO 2007 , there was a rump session talk that talked about weak constants in that particular construction of PRNG. The talk is available here http://rump2007.cr.yp.to/15-shumow.pdf
Adding the two bits together, I am not so surprised at the revelation?!
Given how far academic researchers have come on very limited resources, probably the NSA DOES have a quantum computer in its basement. This would let them break private RSA keys. But it is still probably too slow to break EVERYBODY's private key, so they have to target it on the most important keys.
ReplyDeletehttp://www.theguardian.com/commentisfree/2013/sep/10/nsa-matthew-green-takedown-blog-post-johns-hopkins
ReplyDeleteGiven how far academic researchers have come on very limited resources,
ReplyDeleteOh please. Quantum computing related phenomena research is richly supported, particularly if you include the grants on the physics side, at a tune of about a million dollars a week just in the USA alone.