"Cube" cryptanalysis?

David Wagner daw at cs.berkeley.edu
Thu Aug 21 03:16:33 EDT 2008


Steve Bellovin writes:
>Greg, assorted folks noted, way back when, that Skipjack looked a lot
>like a stream cipher.  Might it be vulnerable?

I'm still absorbing Adi's new ideas, and I haven't looked at this in any
detail, so anything I say should be taken with an enormous grain of salt.
But, off-hand, I'd guess not.  I don't see anything that immediately
makes me worried about Skipjack, or AES for that matter.

In its most basic form, Adi Shamir's cube attack applies when some bit of
the output of the stream cipher (or block cipher, etc.) can be written as
a polynomial of the key and input such that the degree of the polynomial
is not too large.  One major innovation is that the attack applies even
if the number of terms in the polynomial is enormous -- say, way too
many to explicitly write down the polynomial.  When the degree is not
too large, Adi showed some powerful techniques for recovering the key.

Adi pointed out that this might be especially relevant to many LFSR-based
stream ciphers.  The reason is that many LFSR-based stream cipher use a
non-linear filter function of low degree.  Often, the key loading process
also has relatively low degree.  The LFSR itself is linear and hence does
not increase the degree.  The attack only seems directly relevant to a
subset of stream cipher architectures -- for instance, Adi mentioned that
he does not know how to apply it to some clock-controlled LFSR-based
stream ciphers, such as A5/1 -- but the class of stream ciphers it
applies to is an important and common class of stream ciphers.

In contrast, I don't expect this to threaten most modern block ciphers.
Most block ciphers contain enough rounds, and enough non-algebraic
structure in each round, to ensure that the degree of the resulting
polynomial will be large, so in those cases the attack does not seem
applicable.  But of course I could well be missing something, and it's
always possible there could be further advances.

It's a brilliant piece of research.  If you weren't at CRYPTO, you missed
an outstanding talk (and this wasn't the only one!).

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



More information about the cryptography mailing list