Schneier on Security
A blog covering security and security technology.
« Cyberattack Against Georgia Preceded Real Attack |
| Mental Illness and Murder »
August 19, 2008
Adi Shamir's Cube Attacks
At this moment, Adi Shamir is giving an invited talk at the Crypto 2008 conference about a new type of cryptanalytic attack called "cube attacks." He claims very broad applicability to stream and block ciphers.
My personal joke -- at least I hope it's a joke -- is that he's going to break every NIST hash submission without ever seeing any of them. (Note: The attack, at least at this point, doesn't apply to hash functions.)
EDITED TO ADD (8/19): AES is immune to this attack -- the degree of the algebraic polynomial is too high -- and all the block ciphers we use have a higher degree. But, in general, anything that can be described with a low-degree polynomial equation is vulnerable: that's pretty much every LFSR scheme.
EDITED TO ADD (8/19): The typo that amused you all below has been fixed. And this attack doesn't apply to any block cipher -- DES, AES, Blowfish, Twofish, anything else -- in common use; their degree is much too high. It doesn't apply to hash functions at all, at least not yet -- but again, the degree of all the common ones is much too high. I will post a link to the paper when it becomes available; I assume Adi will post it soon. (The paper was rejected from Asiacrypt, demonstrating yet again that the conference review process is broken.)
EDITED TO ADD (8/19): Adi's coauthor is Itai Dinur. Their plan is to submit the paper to Eurocrypt 2009. They will publish it as soon as they can, depending on the Eurocrypt rules about prepublication.
EDITED TO ADD (8/26): Two news articles with not a lot of information.
EDITED TO ADD (9/4): Some more details.
EDITED TO ADD (9/14): The paper is online.
Posted on August 19, 2008 at 1:15 PM
• 36 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
@ Bruce, believer,
You both say you went to the presentation, and have made assuring comments about some current systems.
Bruce you note that Adi (for whatever reasons) has not yet posted the paper up anywhere.
Is there any reason you cannot give us a bit more information on what the attack methodology and principles are?
After all you make comments such as "No, not even a little bit." About Blowfish etc and Adi "thinks that AES is immune to this attack -- the degree of the algebraic polynomial is too high". But say LFSRs are vulnerable.
I'm guessing that as LFSRs and AES can be defined as a closed algebraic formula, over a finite field. And Adi used this in his XL / FXL attacks on AES that this is an improvment or variation on them.
As AES used mainly linear building blocks as do LFSRs are other forms of cipher based shift registers but not using linear feedback vulnerable?
Also how about a little blue sky thinking the design of FEAL gave rise to differential attacks becoming effective and thinking about this gave rise to new linear attacks.
Does Adi's "cube attacks." Show potential as first "steping stones"?
I'm no crypto guru, but I have read Schneier's Applied Cryptography and have read various papers describing cryptographic primitives. We don't know, at this point, whether this is a theoretical attack or a practical attack.
What this attack appears to affect is Radio Gatun, a nice, fairly new construction that can either be a hash or stream cipher, taking a key of any length. Radio Gatun is nice because its core can fit in under 2k of memory and it's an elegant, extensible construction.
However, scanning the paper describing Radio Gatun, I note the quote "It has algebraic degree 2" on page 10. So it looks like a nice, small elegant cryptographic primitive might now be fallen.
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.