Cryptogram: AES Broken? 277
bcrowell writes "The latest CryptoGram reports
that AES (Rijndael) and Serpent may have been broken. The good news is that when cryptographers say 'broken' they don't necessarily mean broken in a way that is practical to exploit right now. Still, maybe we need to assume that any given type of crypto is only temporary. All of cryptography depends on a small number of problems that are believed to be hard. And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy."
I'm no mathematician, (Score:1, Interesting)
Quantum (Score:2, Interesting)
Is it really back to XORing our messages with random data known to both ends?
That sucks.
And the cry went up - make quantum computers illegal. Only terrorists want quantum computers...
Comment removed (Score:3, Interesting)
What Schneier really meant to say... (Score:4, Interesting)
Seriously, though - any approach that manages to reduce the difficulty of cracking these algorithms by a factor of 2^100 is impressive, and Schneier at least simplifies it enough that us folks with very rusty number theory can appreciate the achievement.
His comment later in Cryptogram about his name appearing on a list of banned words is much, much scarier - looks like he's upset someone in the content censorship Gestapo. That same content filter would deny access to today's Slashdot front page - nasty.
Re:Maybe? (Score:3, Interesting)
Since these are all symmetric, key distribution must either happen over another channel, or through a public key exchange method, all of which (AFAIK) use asymmetric algorithms. I don't know that I'd say that asymmetric algorithms are more susceptible, though. The biggest disadvantage to those algorithms is that they tend to require a lot more computing power, and one of the goals of the NIST AES contest was to provide an algorithm that would be implementable on really small platforms, such as embedded devices and smart cards. In fact, one of the best traits of Rijndael is that it seemed just as secure as the other entries while remaining very simple. It has been implemented on a few small 8-bit microcontrollers, and, when optimized, can take as little as 32 bytes of state (RAM).
The XSL attack (Score:2, Interesting)
All you "so is GPG broken?" put your pants back on.
Summary of attack:
XSL stands for three of the basic operations in Rijndael and Serpent. The reason why this attack works is because the substitution layer of Rijndael/AES and Serpent can be expressed very neatly as the same domain as the Linear layers.
Now when I say 'neatly' I mean 'it would be possible' not no one's shown us this monster set of equations relatnig the (128+128/192/256) bit inputs to the 128 bit outputs. The Rijndael/AES and Serpent ciphers may be what we call "over defined".
Think back to high school when you have N liniearly independent linear equations and N-1 unknowns. You had an infinate number of posibilities for solutions. If you had N eqns and N unkn's you had 1 sol'n. If you had N eqns and N+1 unkn's you were in a funny place.
The authors suggest Rijndael/AES Serpent is in the latter catagory of the differential nature (and not the linear nature you learned in high school).
So what does this mean? The possibility HAS NOT BE EXCLUDED that this attack is possible. It really proves demostrates nothing that it's at all possible. Which is best anyone's been able to do in the past 6 years.
JLC
See sci.crypt thread:
http://groups.google.ca/groups?q=XSL+group%3Asci.
Re:The end of privacy (Score:2, Interesting)
I doubt that. 20 years ago, your neighbour, your baker and your butcher knew more about you than any mass e-mail marketing company does nowadays. The only difference is that they didn't send you spam, but for sure your butcher knew that you didn't know the difference between a normal and an excellent steak, and sold you the first one for the price of the second one. So you were f*cked even then, only you didn't know it.
In order to provide some on-topic content also: I thought the basis of all (public-key) encryption was based on one "hard to solve" problem only, namely the "factoring in prime numbers" problem -- are there any problems that I missed?