[131100] in cryptography@c2.net mail archive
Re: "Cube" cryptanalysis?
daemon@ATHENA.MIT.EDU (Greg Rose)
Tue Aug 19 19:01:52 2008
Date: Tue, 19 Aug 2008 15:38:43 -0700
From: Greg Rose <ggr@qualcomm.com>
To: "Perry E. Metzger" <perry@piermont.com>
CC: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
In-Reply-To: <878wusmz7u.fsf@snark.cb.piermont.com>
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@metzdowd.com
