"Cube" cryptanalysis?

[Greg Rose]

Perry E. Metzger wrote:
> According to Bruce Schneier...
> 
> http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html
> 
> ...Adi Shamir described a new generalized cryptanalytic attack at
> Crypto today.
> 
> Anyone have details to share?

Stunningly smart, and an excellent and understandable presentation.

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.

His example was an insanely complicated theoretical LFSR-based stream 
cipher; recovers keys with 2^28 (from memory, I might be a little out), 
with 2^40 precomputation, from only about a million output bits. They 
are working on applying the technique to real ciphers... Trivium, which 
is a well-respected E*Stream cipher, is in their sights.

My team's last LFSR-based cipher, SOBER-128, is I think well respected 
and fairly conservative. I can say that we are extremely lucky in the 
way we load the key and IV, that the degree of the polynomials piles up 
and is quite high; once the cipher is actually running, there are output 
  bits which would have been attackable (degree 16 is certainly 
tractable), except for lucky use of addition as well as s-boxes... the 
addition carries represent high degree terms.

Greg.

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