EnRUPT – The Simpler The Better

Itai Dinur and Adi Shamir have published their Cube Attack paper. A detailed study reveals that it is a brilliant straightforward linear key recovery attached to the ANF reconstruction that we have been using for 15 years to measure quality of ciphers. Some of our results are presented on our ASD site. Now that the genie is out of the bottle, lots of ciphers will fall. Some of the eSTREAM winners will fall… Now let us unveil some of the hidden historical facts leading to the discovery of the now famous cube attacks:

1. Before we revealed our monomial randomness analysis in Bochum in 2006, mere counting of monomials had been previously suggested by Eric Filiol and used by M-J.O. Saarinen.
2. Bart Preneel [one of the co-authors of Trivium] insisted that we submit a paper to the SASC 2007 workshop where Thomas Johansson [one of the co-authors of Grain] was the program chair.
3. In the only two weeks that were available to us, we had analysed a number of ciphers and submitted a paper that shows incredible weakness of Grain, Mickey and Trivium as far as monomial analysis is concerned.
4. While SASC is not a peer review conference with proceedings but a mere workshop for presenting new ideas and work in progress, our paper got rejected nevertheless, criticised by the reviewers as if it was submitted to Eurocrypt.
5. Thomas Johansson had almost immediately contacted Meltem Turan asking her to verify our results on Grain, Trivium and Mickey presenting them to her as their own: “We have these results…”
6. She did of course reproduce most of our results (limited to attacking only the IV), promptly publishing it as their joint work [known as “A Framework for Chosen IV Statistical Analysis of Stream Ciphers”] at the Tools for Cryptanalysis 2007 workshop [where our ASD tests were presented as well] and at INDOCRYPT 2007.
7. It appears that a year-long investigation of plagiarism by Thomas Johansson has been quietly swept under the carpet by the Lünd University.
8. Fischer, Khazaei, and Meier have explored adding statistical key recovery to our tests (limited to attacking only the IV again) publishing their work at AFRICACRYPT 2008 as “Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers”. Kudos!
9. Dinur and Shamir have announced their cube attacks at Crypto 2008 and published them on ePrint. Lots of Kudos!
10. F-FCSR has been removed from the eSTREAM portfolio of stream chipers leaving only Grain, Trivium and Mickey in the hardware category.

There are three parallel lines in this story: one is the catastrophic state of plagiarism in cryptology, unheard of in any other academic department. Unless one is willing to risk having their work stolen, they must publish it on ePrint immediately. The Cube Attack paper is already on ePrint due to appear in Eurocrypt-2009 in 10 months. It is not even certain yet if it is going to be accepted or not! By failing to observe the rules of this tricky game, we have lost our chance to finish our work and publish a proper paper at a peer review conference. It is of course flattering to see your work stolen like that, but this flattery has a bitter aftertaste. So watch out, cryptology students!

The other line is of course the development of the cryptologic research exactly in the direction we have set by revealing the details of our tests: monomial analysis is not only significantly more superior to linear and differential cryptanalysis as the cube attacks demonstrate and will continue to demonstrate, it can also analyse any black box cipher regardless of its structure, even unknown ciphers such as Mifare Crypto1.

The third line is the eSTREAM competition turning into another flop following the NESSIE competition fiasco failing to find a single good stream cipher… Once Grain, Trivium and Mickey fall victims of cube and algebraic attacks, there will be not a single competition winner in the hardware category. Mark our words.

Let us sit back, relax, and watch the remaining three algorithms by the greatest authorities in cryptology get badly broken as if they were made of paper. I am sorry, but I cannot even call them ciphers – they are that weak. It demonstrates yet again the “state of the art” in cryptology: cryptologists following each other’s research for years making minor improvements to each other’s linear and differential cryptanalysis… Now with the publication of cube attack paper and with an escalating amount of research in the direction of using SAT solvers for cryptanalysis, we will see a lot of old ciphers fall and a lot of new ciphers fall faster than ever before. Good bye, linear and differential cryptanalysis!

The cube attack paper lists our ASD tests among “chosen IV” attacks. It is not correct. Unlike the recent attempts to extend our tests to key recovery by attacking only the IV or the plaintext, our monomial testing includes analysis of proper randomisation of the secret (key) material as well as the public (IV or plaintext) variables. Since algebraic attacks, the cube attacks are the first to exploit the real potential of monomial analysis.

What is going to happen to EnRUPT, VEST and to other ciphers we have designed? – Nothing. Our ciphers are designed to resist any such attacks. Our Algebraic Structure Defectoscopy testing [AKA monomial randomness analysis] ensures that EnRUPT as well as all our other ciphers grow sufficiently complex sufficiently fast. EnRUPT with s=2 is resistant to the basic cube attacks and EnRUPT with s=4, just like all the VEST ciphers designed with s=4, will be resistant to any of the adaptive variants of cube attacks. To everyone else, good luck!