"Cube" cryptanalysis?

[Greg Rose]

James Muir wrote:
> Greg Rose wrote:
>> Basically, any calculation with inputs and outputs can be represented as
>>  an (insanely complicated and probably intractable) set of binary
>> multivariate polynomials. So long as the degree of the polynomials is
>> not too large, the method allows most of the nonlinear terms to be
>> cancelled out, even though the attacker can't possibly handle them. Then
>> you solve a tractable system of linear equations to recover key (or
>> state) bits.
> 
> I would like to know how Dinur and Shamir's work differs from Courtois'
> previous work on Algebraic cryptanalysis of block ciphers.  It is a
> refinement of Courtois' technique?  Greg, do you, or someone else have
> some insight on this?

I spent about an hour trying to come up with a short but legible 
explanation of the technique, and failed. Sorry about that. I can 
visualize it, and could probably reproduce Adi's drawings on a 
whiteboard, but not with typing. The following is as close as I could come.

Basically the method focuses on terms of the polynomial in which only 
one secret bit of the key appears, and many of the non-secret bits. 
Using chosen (or lucky) plaintexts, vary all but one of the non-secret 
bits, and sum the output bits (mod 2, that is, XOR). Fix the other 
non-secret bit to 1. Now all the terms that involve less than the full 
complement of non-secret bits will appear an even number of times in the 
sum, and because it is mod 2, they will all cancel out! The only terms 
that will be left are the ones with one secret bit, and all ones for the 
non-secret bits... but that is linear in the secret bit! So what you are 
left with is a simple, linear, polynomial relating unknown (key) bits. 
Gather enough such equations, just a few more than the number of key 
bits will do, and solve the linear system in trivial time. Note that you 
had to have 2^(d-2) chosen plaintexts to sum over for each of the 
equations... that's where the complexity comes from. The attack is 
called Cube because in the case where d=4, each time you sum over all of 
the varying known bits, it can be visualized as the face of a cube, the 
corners of which are the possibilities for the 3 known inputs.

Hope that helps. Note that the formula I typed from memory for the 
complexity was wrong... it's O(n * 2^(d-2)), if the above is correct.

For anything more than this, you'll have to wait for the paper.

Greg.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com