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.)

More later.

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.

Tags: , , , , , , ,

Posted on August 19, 2008 at 1:15 PM • 36 Comments

Comments

Stephen Smoogen • August 19, 2008 2:28 PM

hehehehe blog ciphers.. it turns out that every blog out there is actually a cipher using a high polynomial system also known as the many monkeys cipher.

Actually I was hoping for some info on LFSR scheme and how that affects current hashes.

Jason • August 19, 2008 2:29 PM

Do you think you’ve crossed some kind of meaningful threshold when your finger memory bangs out the word “blog” instead of “block”?

ghoti & tchoghs • August 19, 2008 2:37 PM

LFSR-based constructions are mostly found in stream ciphers and prngs. Can’t remember any applicable hash functions. But I still haven’t seen the details of the attack.

Geoff • August 19, 2008 3:43 PM

“blog cypher” attack:
post the cyphertext on your blog along with the claim that it’s unbreakable.

Someone should post the plaintext in your comments section pretty quickly.

Phillip • August 19, 2008 4:16 PM

@Bruce (et. al.)

Is blowfish vulnerable? How about Twofish?

I’d hate to think our hero’s algorithm has been weakened 🙁

moz • August 19, 2008 4:27 PM

Whilst most blogs seem like meaningless drivel to you, Bruce Schneier can decode blog ciphers with his teeth and see the true hidden meaning.

langholz • August 19, 2008 4:48 PM

Very interesting… please let us know what you think about such attack and if it indeed has revolutionized cryptanalysis.

believer • August 19, 2008 5:46 PM

On your personal joke: After hearing Adi’s talk and sharing opinions with him and others, my intuition is that only very specially structured submissions to the NIST Hash submission (maybe none) will/would have been broken by this technique. But it is a interesting technique nevertheless.

Derick • August 19, 2008 5:50 PM

@Spider

You say broadcast HDTV formats might be vulnerable to this attack if it’s good a cracking LFSR. That’s good news!

Bruce Schneier • August 19, 2008 7:00 PM

“After hearing Adi’s talk and sharing opinions with him and others, my intuition is that only very specially structured submissions to the NIST Hash submission (maybe none) will/would have been broken by this technique. But it is a interesting technique nevertheless.”

Agreed. Unless someone implements a LFSR-based hash function — even a complex one — it’s not going to fall to this technique. I’m certainly not worrying with my design.

Bruce Schneier • August 19, 2008 7:00 PM

“The unbelievable frustration! When do the rest of us get to read a description of what the attack is?”

I had hoped he timed his paper to go live during his talk, but he didn’t.

Grahame • August 19, 2008 7:15 PM

Blog ciphers? … and I thought it was just that people who write blogs don’t make sense

Redfox • August 19, 2008 7:25 PM

(The paper was rejected from Asiacrypt, demonstrating yet again that the conference review process is broken.)

That reminds me of:

SCIgen – An Automatic CS Paper Generator

Using SCIgen to generate submissions for conferences like this gives us pleasure to no end.
In fact, one of our papers was accepted to SCI 2005!
http://pdos.csail.mit.edu/scigen

Clive Robinson • August 20, 2008 3:46 AM

@ 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”?

akly • August 20, 2008 5:02 AM

For those who are at Crypto, does anyone care to give us even a hint as to how these new attacks work? Or did Shamir give very little away in his talk? Is the paper not in the proceedings? What about an abstract?

ghoti & tchoghs • August 20, 2008 6:23 AM

@akly: The paper is not in the proceedings. The title of the talk was “How to Solve it: New Techniques in Algebraic Cryptanalysis” according to the conference program.

Shamir has done work on algebraic attacks before (cf. the Kipnis-Shamir attack on HFE, XL), I expect that the “cube” attack relates to improved linearisation techniques for non-linear boolean equations. Precise details of the breakthrough will clearly have to wait. (The Eurocrypt deadline alluded to by Bruce is in 2-3 weeks.)

Sam Trenholme • August 22, 2008 10:24 AM

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.

Heath • August 23, 2008 2:27 AM

I thought LFSR’s were already known to be insecure via Walsh-Hadamard transformation analysis. (?)

Ismas • August 23, 2008 8:22 AM

Please, don’t wait to EuroCrypt2009. Present the paper for the 25º Chaos Computer Club Conference, Berlin 27-30 Dic. 2008

Thomas • August 26, 2008 7:17 AM

How can you say that “The paper was rejected from Asiacrypt, demonstrating yet again that the conference review process is broken” ??

Have you read the paper submitted ? How can we say this paper had to be accepted without knowing what was exactly inside ?

A good invited talk doesn’t necessarily imply that the paper was well written (though I reckon it’s hard to find a badly written paper from Shamir).

It’s true that the reviewing process is far from perfect, and there are many papers every year which are unfairly rejected. The difference here is that only a few are cryptographic gods enough to tell everyone that their paper has been rejected from a conference.

Ivars Suba • August 28, 2008 2:24 AM

I have read B.Shneiers “Applied Cryptography” and clear LFSR could be broken after 2n LFSR ouput bits using Berlekamp-Massey algorithm, where n is primitive polynomial degree. This is parctical attack. May be Shamir Cube attack are only theoretical, not practical actually?

Steve B • September 15, 2008 9:52 AM

When Bruce writes “pretty much every LFSR scheme”, he doesn’t just mean stream ciphers consisting ONLY of an LFSR (which as Ivars Suba says are well known to be weak). He means stream ciphers built from LFSRs – e.g. one or more LFSRs with many register bits combined using a nonlinear function to yield a keystream bit.

BUT the assertion does need qualifying. It is only REGULARLY CLOCKED LFSR-based stream ciphers that are likely to be vulnerable. Where there is irregular, data-dependent clocking of the LFSRs then it will typically be much harder to build a representation of low algebraic degree, and it is much less likely that the cube attack will apply.

Paul Crowley • December 4, 2008 7:59 AM

The above comment is wrong: irregularly clocked LFSR-based schemes are vulnerable, so long as the irregular clocking is at the keystream output stage rather than the keying stage.

Rudi Schlatte • September 16, 2009 8:06 AM

Adi Shamir just gave a talk at TU Graz (at 11am today) where he described how to break arbitrary / unknown block ciphers using Cube Attacks and 1 bit (!) of side-channel information (e.g. from round 2 of AES-128 or round 3 of SERPENT), using known-plaintext attacks. IIRC the complexity he mentioned was 2^53 for AES-128, less for SERPENT. (Unknown ciphers require an attacker able to manipulate the key as well, and have higher complexity.) I don’t know whether these results are published somewhere already; should have asked.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.