Shamir had already advertised his talk as introducing "cube attacks," a powerful new attack technique that he had developed with his student Itai Dinur. To illustrate this technique he spent several slides describing a stream cipher with an extremely large key, many S-boxes, etc. David Wagner later wrote that Shamir had "just piled on one security feature after another until he got a design where I just had to laugh -- since it seemed ridiculous to imagine an attack on the design, yet I knew if he was describing this cipher he had to have some trick up his sleeve to break it."
After describing the cipher, Shamir said that the cipher clearly could not be broken by any previous technique. Shamir's words, as I recall, were "I am sure you will agree with me." Wagner wrote that the cipher "seemed ridiculously hard to break by all known methods."
Shamir then explained how to break the cipher quite efficiently with a "cube attack." Bruce Schneier posted a note to his widely read blog saying "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." The news was picked up by some reporters:
Stream ciphers cower before Adi Shamir's cube attackShamir reported in his talk that he had already submitted a paper on cube attacks to the Asiacrypt 2008 conference, with unhappy results. "The paper was rejected from Asiacrypt, demonstrating yet again that the conference review process is broken," Schneier wrote.... Adi Shamir brought a big new wrecking ball to bear on stream ciphers at Crypto2008, the 28th International Cryptology Conference, one that will send architects of the algorithms back to their keyboards.
Dinur and Shamir posted their paper "Cube attacks on tweakable black box polynomials" a few weeks later. They wrote "In this paper we develop a new technique (called a cube attack)" that added cipher outputs over "boolean cubes" and that was "provably successful when applied to random polynomials of degree d over n secret variables whenever the number m of public variables exceeds d + log_d n."
Dinur and Shamir said that their attack was "a major improvement over several previously published attacks of the same type." They cited five previous papers (from 2003, 2007, 2007, 2007, and 2008) that "try to break particular schemes by highly heuristic attacks that sum output values on Boolean cubes of public variables" but said that "the cube attack is much more general, is applicable to block ciphers in addition to stream ciphers, and has a better-defined preprocessing phase which does not need adaptations for each given scheme." They also criticized older "interpolation attacks" as requiring a huge number of queries "to uniquely interpolate the polynomial from its black box representation."
Shamir had said in his talk that he and Dinur were working on the Trivium stream cipher and that the audience should expect news about Trivium. This cipher had been introduced in 2005, had received wide acclaim in the cryptographic community for its extreme simplicity and extremely high speed, had survived extensive cryptanalysis despite its minimalist design, and in 2008 had been selected for the final portfolio in the ECRYPT Stream Cipher Project.
However, when the Dinur-Shamir paper was posted, it turned out to be disappointingly light on examples. It states an attack on simplified versions of Trivium, perhaps marginally less simplified than the versions attacked in previous papers, but it doesn't give any real reason to think that Trivium can be attacked. It also doesn't make progress on any other ciphers. The remainder of 2008 was also remarkably free of news regarding successful cube attacks.
Why haven't cube attacks broken anything? Is there some secret reason that every real-world cipher resists cube attacks? It turns out that the answer is yes.
Is this an accident? No. The cipher-design community has understood the importance of large degrees for many years. The 1992 paper "Higher order derivatives and differential cryptanalysis" by Xuejia Lai explains how to break every small-degree cipher; Shamir was flat-out wrong when he said that his example cipher could not be broken by any previous technique.
A scan of Lai's paper appears below. Section 2 introduces higher-order differentials. Proposition 2 shows that each differentiation reduces degree by at least 1; consequently an order-d differential reduces degree d to a constant. Section 3 expresses higher-order differentials, in the binary case, as sums over Boolean cubes. The last paragraph of Lai's paper recommends choosing functions whose order-d differentials are roughly uniform for all small d; evidently this recommendation prohibits all small-degree functions.
Are Lai's attacks "highly heuristic"? No. Are they limited to "particular schemes"? No. Are they applicable only to stream ciphers? No. Are they less general than cube attacks? I don't see how. Do they need to "interpolate the polynomial from its black box representation"? No. It seems to me that "cube attacks" are simply a reinvention of Lai's higher-order-differential attacks; if Dinur and Shamir had cited Lai's paper (and various followup papers easily located through Google) then they would have been forced to drop essentially all of their advertising.
Here's the scan.