[131107] in cryptography@c2.net mail archive
Re: "Cube" cryptanalysis?
daemon@ATHENA.MIT.EDU (Greg Rose)
Tue Aug 19 20:02:38 2008
Date: Tue, 19 Aug 2008 16:53:37 -0700
From: Greg Rose <ggr@qualcomm.com>
To: "Perry E. Metzger" <perry@piermont.com>
CC: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
In-Reply-To: <87tzdglhgn.fsf@snark.cb.piermont.com>
Perry E. Metzger wrote:
> Greg Rose <ggr@qualcomm.com> writes:
>> 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.
>
> There are a bunch of deployed mobile phone ciphers that are in the
> stream cipher class -- any thoughts on whether any of them look
> vulnerable?
With the disclaimer that I think I understand the attack but might
nevertheless have misunderstood something:
A5/1 is difficult for this attack to apply to because of the
clock-controlled shift registers (Adi said this).
A5/3 and the current WCDMA f8/f9 is based on Kasumi, and I'd be
surprised if the attack applys. Ditto for the AES based CDMA security.
The soon-to-be-adopted spare WCDMA algorithm, SNOW-3G, may be vulnerable
if used in other ways, but appears to me to be secure in the way it is
used in 3G phones. Again, somewhat lucky though, the attack comes very
close to working. I believe the appropriate standards committee is going
to go off and check this very closely (I spoke to one of the members).
Greg.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
