The so-called "Cube attack"

[eprint.iacr.org]

is precisely the AIDA attack presented by myself in 2007 at

[eprint.iacr.org]

([27] in Dinur/Shamir)

Maybe, this paper is a bit of help to understand the AIDA/Cube attack. Please note that the ENF I "introduced" there is just the ANF.

What remains unsolved, and also by Dinur/Shamir, is how to find some linear (in the key vars) parts of the full ANF (algebraic normal form) in some poly-bounded time.
This is what I call Phase A, and which takes "several weeks" also with D/S, (Sect. 7.3, l. 3).

Lexicon:

AIDA == Cube
t: on p.2, l.2 == C_I, with I={i_1,..,i_n}
Prop. 3 == Thm. 1
Prop. 3 == Thm. 2 (equivalent to Thm 1 with C_I replaced by C_I union {x_j})
Table p.5 (for t >= 625), last l. of Sect 7. (for t=640) == Tables 1,2 (for t >= 672, 770, resp.)

Although I am proud and happy to have anticipated Adi Shamir by almost a year, this is just a plagiarism, and the attack should be called Algebraic IV Differential Attack, or AIDA for short, like the opera.

Comments, please!



Edited 1 time(s). Last edit at 28-Feb-2009 19:12 by Vielhaber.

The Cube attack authors acknowlege your anticipation of the attack in the linked paper:

"Vielhaber [27] recovered 47 key bits of Trivium with 576 initialization rounds in negligible time. The key bits were recovered after some small IV special subsets were found, each one with the following property: The result of summing on some keystream bit produced by assigning a special subset all possible IV values, while keeping the other IV bits fixed, is equal to some key bit or to the sum of two key bits. Note that this is a very special case of our cube attack, and it is not clear why the author imposed this unnecessary restriction."

Could you clarify more on what remains unsolved? The linked paper describes a variety of "black-box" techniques for finding those linear parts in section 4.2.

It's hot. In Chinese ºÃÈÈÄÖ¡£

Shamir's "cube attack": A plagiarism of AIDA

has been submitted to (*this) (pr)eprint server and is available at
[www.hs-bremerhaven.de]



@Luo Lan: I agree.

@ ciphergoth: This is Orwellian Newspeak. By induction the first N papers on anything do not matter, just anticipating the N+1st, \forall N in N

I read your article before the introduction of the cube attack by Shamir. It is very interesting, but it lacks one thing.

The main difference is that your article doesn't clearly state how to check the linearity of the function obtained after applying the summing.

At the other side,the "momomial degree test" introduced by Khazaei, tests the linearity without identifying the linear form.

Shamir made the synthesis.

After reading your article I was able to check exhaustively by testing each key bit for a given summing set if k_i= \sum_IV Cipher(X). The cube attack is more effective, first find a linear form, then identify it. Maybe was it trivial for you, not for the reader.

@Skeptic:

You certainly may do linear algebra and get away with 80+\varepsilon, on average 81, simulations (given that Trivium has 80 key bits).

BLR, as described by D&S, requires 4 simulations per 1 BLR test, and with 2 BLR tests on average, you need 8 simulations instead of 81.

This accelerates the SAME attack by a factor of 10.
This is nice, CPU-time-wise.

This does not constitute a novel attack though.

Had they called the paper "Fast implementation of AIDA", my heartfelt congratulations.
As it is, it is plagiarism.



Edited 1 time(s). Last edit at 20-Apr-2009 20:35 by Vielhaber.

OK, for sparse equations but in a more general way, if a particular unique non sparse linear form exist for random coefficients,the AIDA dont find it.

For what I understood AIDA is:
-choose IV set
-make the summing
-test for K_i= 1 to 80 if Ki=form
While Cube attack is
-chooseIV set
-make the summing
-test the linearity
-if OK identify implied variables
-identify linear form


For example if there is a unique linear form of 40 non null coefficients of the key, you have Binomial(80,40) linear forms to test exhaustively with AIDA, while with cube attack its only 40. This is not linear gain.

But in Trivium, Forms are sparse so AIDA~Cube in this case.

This is an example where AIDA fails, and Cube attack succeeds :

-take the original trivium specification
-replace the key/iv copy by a linear introduction with some LFSR to mix the key terms a large number of times.

Now the forms in ANF are non sparse.

@Skeptic:
Maybe, we should continue by eMail: vielhaber At gmail.com

First, the forms are *always* sparse, when linear
(see my forthcoming paper)

Anyway, you will identify ANY linear form in 81+ simulations:
You may use any random key and get the hypercube sum, 0 or 1. Repeat this 81+ times, and you get a system of 81 equations in 81 unknowns c_0,c_1..c_80 in {0,1}.

You pretend \sum_i=0..80 c_i k_i = hypercube sum (with "k_0"=1, the constant term), where the k_i of each simulation fill one row of the matrix (A), the result is the corresponding right hand side (b).

So, you can resolve Ac=b -> c=A^(-1)b (Gauss) and obtain the c_i, hence the precise linear form (which you should certainly check against more keys),
else you get a contradiction, ergo not linear.

See you in Cologne?



Edited 1 time(s). Last edit at 22-Apr-2009 06:22 by Vielhaber.

Skeptic Wrote:
-------------------------------------------------------
> I read your article before the introduction of the
> cube attack by Shamir. It is very interesting, but
> it lacks one thing.
>
> The main difference is that your article doesn't
> clearly state how to check the linearity of the
> function obtained after applying the summing.
>
> At the other side,the "momomial degree test"
> introduced by Khazaei, tests the linearity without
> identifying the linear form.
>
> Shamir made the synthesis.
>
> After reading your article I was able to check
> exhaustively by testing each key bit for a given
> summing set if k_i= \sum_IV Cipher(X). The cube
> attack is more effective, first find a linear
> form, then identify it. Maybe was it trivial for
> you, not for the reader.


I agree



Edited 2 time(s). Last edit at 17-Jul-2009 17:25 by mike365.

Visit my homepage
[www.hs-bremerhaven.de]
and check the paper
[www.hs-bremerhaven.de]
to verify the following points:
1. Mathematically, both attacks are the same.
(this *alone* makes the renaming of AIDA into "cube" a plagiarism)
2. Precisely, by the above mentioned citation, Dinur and Shamir reveal that they understood my attack. The "special" case of having "some key bit or to the sum of two key bits" applies in praxi as well to D./Sh.'s findings. My paper treats, of course, also the general case of many linear or even quadratic terms.
3. The main difference between the AIDA paper and the "cube attack" paper seem to be the faster linearity tests. These are implementation details, to be distinguished sharply from the actual attack itself.
Also, real attacks require *lots* of hypercubes to be searched. Here, the "Wavefront Model" and applying the Fast-Reed-Muller Transform are mandatory, BLR alone does not help. See my paper "Speeding up AIDA, the Algebraic IV DIfferential Attack, by the Fast Reed-Muller Transform" in Proc. ISKE 2009, p.504-513.

* * * * * * *

He who steals a car, is a thief.
He, who then repaints it, puts on bigger tyres, and more comfortable seats, does not become the owner.

The fact that such thief already had a Rolls-Royce (RSA) and a Mercedes (DCA) in his garage (both partly owned) would not make the "taking" of the new car any more legal.

And, finally, applause for such action by by-standers blinded by the sheer beauty of the Rolls is less a sign for acquired legality but more for the perverted thinking going on in todays Crypto "community".