Prev: RC4 / RC4A (Was: One time pad)
Next: What is the next Prime that is 3 mod 4 from this one?
From: David Wagner on 22 Aug 2008 21:56
Here's a bare-bones description of the basic ideas underlying the cube
attack. It won't convey everything, but it's enough that you may be
able to work out some of the consequences of the attack.

Suppose we have a stream cipher that accepts both a key and an IV.
Let's focus attention on any single output bit of a stream cipher, say z.
Suppose we can express z as a polynomial of the key and IV bits whose
degree is not too large, i.e.,
z = p(k_0, .., k_127, v_0, .., v_31)
where k_0,..,k_127 are the key bits and v_0,..,v_31 are the bits of
the IV.

In other words, write p() as a sum of terms, where each term is a product
of some set of key/IV bits. The polynomial p() might have a ridiculous
number of terms (maybe far too many to contemplate writing down) but if
the total degree is not too large, the cube attack is likely to apply.
[Side note: Previously it was believed that as long as the number of
terms is enormous, the cipher is likely safe. The cube attack shows
that this ain't necessarily so.]

Suppose we know that the total degree of p() is n. This means that p
is a sum of terms, where every term is a product of at most n variables.
For simplicity I'm going to assume we're working over GF(2), i.e., each
variable represents a boolean value and all polynomials are taken mod 2.

We'll start with a basic lemma about polynomials. Suppose a(x,y,z)
is a polynomial with three variables, and suppose we can express it in
the form
a(x,y,z) = b(y,z) x + c(y,z).
Then
a(1,y,z) - a(0,y,z) = b(y,z).
In other words we have eliminated x from the equation. When working
in GF(2), we'll never have x^2 or x to any higher power, since x^2 = x,
so the polynomial a(x,y,z) can always be written in this form. Also
in GF(2), subtraction is the same as addition, so:
a(1,y,z) + a(0,y,z) = b(y,z).

We can use a similar technique to eliminate multiple variables.
For instance, if
a(x,y,z) = b(z) yz + c(x,y,z)
where c(x,y,z) is a polynomial that does not contain any terms that
are a multiple of yz, then
a(1,1,z) + a(1,0,z) + a(0,1,z) + a(0,0,z) = b(z).
Notice how the points (1,1), (1,0), (0,1), (0,0) can be viewed as
the corners of a square in 2 dimensions. The same can be generalized
to any number of variables. For instance, with 3 variables, we'll
evaluate at 8 points, corresponding to the corners of a cube in 3
dimensions -- hence the name cube attack.

So now let's return to our stream cipher. Suppose we can express
the polynomial p() in the form, say,
p(k_0, .., k_127, v_0, .., v_31)
= l(k_0, .., k_127) v_0 v_1 v_2
+ q(k_0, .., k_127, v_0, .., v_31)
where l(k_0, .., k_127) is a linear sum of key bits, v_0 v_1 v_2
is a product of some subset of IV bits, and q() is any polynomial that
does not contain any terms that are a multiple of v_0 v_1 v_2.
If we can express p() in this form, then we can eliminate variables
to find
p(..., 0,0,0, ...) + p(..., 0,0,1, ...) + p(..., 0,1,0, ...)
+ p(..., 0,1,1, ...) + p(..., 1,0,0, ...) + p(..., 1,0,1, ...)
+ p(..., 1,1,0, ...) + p(..., 1,1,1, ...)
= l(k_0, .., k_127).
Here we have plugged in all 2^3 possible combinations of values
for v_0,v_1,v_2 into p(). After summing these 8 outputs from p(),
the result can be expressed as a linear combination of key bits.

Notice what this means for the stream cipher. If we can get the
keystream corresponding to 8 different IVs, where v_0,v_1,v_2 vary
over all 2^3 possible combinations and the remaining key bits remain
fixed, then this corresponds to learning the value of p() after
evaluating p() on these 8 inputs. By the above reasoning, if we
sum these 8 known outputs from p(), we get l(k_0, .., k_127): a
known linear combination of key bits. So this leaks a linear function
of the key bits.

If we can find 128 of these leakages, then this leaks 128 linear
functions of the unknown key bits, so we can set up 128 linear
equations with 128 unknowns and solve for the key. This gives a
key-recovery attack.

Of course there is nothing special about v_0,v_1,v_2 in the above.
We can replace the term v_0 v_1 v_2 with any term that can be written
as a product of a subset of IV bits (and only IV bits). If the total
degree of the polynomial is n, and if the terms of p are reasonably
random, then heuristically we'd expect to succeed by looking at terms
that are a product of n-1 IV bits.

The rest of the attack Adi described consists of clever ways for
figuring out how to express p() in this form, how to make the attack
work with only black-box access to the stream cipher, and various
other clever improvements. He also showed how to break a stream
cipher that seems plausibly immune to all other attacks previously known:
in his talk, he described a hypothetical stream cipher that seemed
ridiculously hard to break by all known methods (he just piled on one
security feature after another until he got a design where I just had
to laugh -- since it seemed ridiculous to imagine an attack on the
design, yet I knew if he was describing this cipher he had to have
some trick up his sleeve to break it), and then showed how to break
it with a cube attack. Wow!

It was a brilliant talk.
From: David Wagner on 22 Aug 2008 21:57
Incidentally, after looking at E0, it made me think that it
would be interesting to throw a SAT solver at this. SAT solvers
have gotten pretty good and it wouldn't surprise me if they are
able to make some headway on attacking E0. It would be interesting
to see what you get if you code up the second level of E0 (say, as
an input to STP or another SAT solver/decision procedure) and
experimented with breaking the cipher. Can one recover the key
given sufficiently many output bits? I don't know whether anyone
has looked at this before, but if not, it could be a fun little
rainy day project.
From: biject on 22 Aug 2008 22:14
On Aug 22, 12:38 pm, Simon Johnson <simon.john...(a)gmail.com> wrote:
> Now the dust has settled a bit on his Crypto 2008 talk, does anybody
> have an explanation how this attack works?
>
> It sounds like it could have a deep impact on the E-Stream ciphers?
>
> Simon

Simple don't use Stream ciphers. Use very large block ciphers
preferrable
the blolck should match the length of the message.

David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
From: shahram.khazaei on 25 Aug 2008 19:52
On Aug 23, 3:56 am, d...(a)taverner.cs.berkeley.edu (David Wagner)
wrote:
> Here's a bare-bones description of the basic ideas underlying the cube
> attack. It won't convey everything, but it's enough that you may be
> able to work out some of the consequences of the attack.
>
> Suppose we have a stream cipher that accepts both a key and an IV.
> Let's focus attention on any single output bit of a stream cipher, say z.
> Suppose we can express z as a polynomial of the key and IV bits whose
> degree is not too large, i.e.,
> z = p(k_0, .., k_127, v_0, .., v_31)
> where k_0,..,k_127 are the key bits and v_0,..,v_31 are the bits of
> the IV.
>
> In other words, write p() as a sum of terms, where each term is a product
> of some set of key/IV bits. The polynomial p() might have a ridiculous
> number of terms (maybe far too many to contemplate writing down) but if
> the total degree is not too large, the cube attack is likely to apply.
> [Side note: Previously it was believed that as long as the number of
> terms is enormous, the cipher is likely safe. The cube attack shows
> that this ain't necessarily so.]
>
> Suppose we know that the total degree of p() is n. This means that p
> is a sum of terms, where every term is a product of at most n variables.
> For simplicity I'm going to assume we're working over GF(2), i.e., each
> variable represents a boolean value and all polynomials are taken mod 2.
>
> We'll start with a basic lemma about polynomials. Suppose a(x,y,z)
> is a polynomial with three variables, and suppose we can express it in
> the form
> a(x,y,z) = b(y,z) x + c(y,z).
> Then
> a(1,y,z) - a(0,y,z) = b(y,z).
> In other words we have eliminated x from the equation. When working
> in GF(2), we'll never have x^2 or x to any higher power, since x^2 = x,
> so the polynomial a(x,y,z) can always be written in this form. Also
> in GF(2), subtraction is the same as addition, so:
> a(1,y,z) + a(0,y,z) = b(y,z).
>
> We can use a similar technique to eliminate multiple variables.
> For instance, if
> a(x,y,z) = b(z) yz + c(x,y,z)
> where c(x,y,z) is a polynomial that does not contain any terms that
> are a multiple of yz, then
> a(1,1,z) + a(1,0,z) + a(0,1,z) + a(0,0,z) = b(z).
> Notice how the points (1,1), (1,0), (0,1), (0,0) can be viewed as
> the corners of a square in 2 dimensions. The same can be generalized
> to any number of variables. For instance, with 3 variables, we'll
> evaluate at 8 points, corresponding to the corners of a cube in 3
> dimensions -- hence the name cube attack.
>
> So now let's return to our stream cipher. Suppose we can express
> the polynomial p() in the form, say,
> p(k_0, .., k_127, v_0, .., v_31)
> = l(k_0, .., k_127) v_0 v_1 v_2
> + q(k_0, .., k_127, v_0, .., v_31)
> where l(k_0, .., k_127) is a linear sum of key bits, v_0 v_1 v_2
> is a product of some subset of IV bits, and q() is any polynomial that
> does not contain any terms that are a multiple of v_0 v_1 v_2.
> If we can express p() in this form, then we can eliminate variables
> to find
> p(..., 0,0,0, ...) + p(..., 0,0,1, ...) + p(..., 0,1,0, ...)
> + p(..., 0,1,1, ...) + p(..., 1,0,0, ...) + p(..., 1,0,1, ...)
> + p(..., 1,1,0, ...) + p(..., 1,1,1, ...)
> = l(k_0, .., k_127).
> Here we have plugged in all 2^3 possible combinations of values
> for v_0,v_1,v_2 into p(). After summing these 8 outputs from p(),
> the result can be expressed as a linear combination of key bits.
>
> Notice what this means for the stream cipher. If we can get the
> keystream corresponding to 8 different IVs, where v_0,v_1,v_2 vary
> over all 2^3 possible combinations and the remaining key bits remain
> fixed, then this corresponds to learning the value of p() after
> evaluating p() on these 8 inputs. By the above reasoning, if we
> sum these 8 known outputs from p(), we get l(k_0, .., k_127): a
> known linear combination of key bits. So this leaks a linear function
> of the key bits.
>
> If we can find 128 of these leakages, then this leaks 128 linear
> functions of the unknown key bits, so we can set up 128 linear
> equations with 128 unknowns and solve for the key. This gives a
> key-recovery attack.
>
> Of course there is nothing special about v_0,v_1,v_2 in the above.
> We can replace the term v_0 v_1 v_2 with any term that can be written
> as a product of a subset of IV bits (and only IV bits). If the total
> degree of the polynomial is n, and if the terms of p are reasonably
> random, then heuristically we'd expect to succeed by looking at terms
> that are a product of n-1 IV bits.
>
> The rest of the attack Adi described consists of clever ways for
> figuring out how to express p() in this form, how to make the attack
> work with only black-box access to the stream cipher, and various
> other clever improvements. He also showed how to break a stream
> cipher that seems plausibly immune to all other attacks previously known:
> in his talk, he described a hypothetical stream cipher that seemed
> ridiculously hard to break by all known methods (he just piled on one
> security feature after another until he got a design where I just had
> to laugh -- since it seemed ridiculous to imagine an attack on the
> design, yet I knew if he was describing this cipher he had to have
> some trick up his sleeve to break it), and then showed how to break
> it with a cube attack. Wow!
>
> It was a brilliant talk.

The so-called cube attack recently presented by Adi Shamir at
Crypto'08 gives an answer in a special case to an open question which
we recently presented in [1].
The work in [1] treats exactly the same problem in a quite similar
framework in a somehow general model.
The problem has been already explained by D. Wagner and G. Rose but we
try to re-explain it using the notation from [1] to make the
connection easier to follow.

It deals with finding an unknown n-bit key K given access to the
output of a keyed Boolean function f(K,V) where the attacker has the
ability to choose the m-bit parameter V (which we called it IV).
The idea is to derive a simpler function C from f which can be useful
in an attack. In [1] we did this by making a partitioning V = (U,W)
of the IV bits and then by considering f as a function of U.
Then we focused on a single coefficient from f(U) which is a function
of K and W (W is the remaining IV bits which are fixed), and of
course, the corresponding index of the monomial from U.
Any of these coefficients (functions) can be potentially useful in an
attack, depending on its structure. We mostly focused on the Maximum
Degree monomial since it turned out to be more vulnerable.

We considered different scenarios in which one might achieve a
successful attack. In cube attack ones looks for a derived function
C(K,W) which is linear in its inputs.

We referred to any subset U which leads to a successful attack as weak
IV bits (see the slides [1]) and we rose the question how to find weak
IV bits.
The nice feature of the cube attack is to answer this question for the
special case where f has degree d. The answer is very simple and
cute. Any U containing d-1 IV bits is weak, since the corresponding
maximum degree coefficient is linear in key bits.

In a recent work, we have introduced a more systematic method to find
weak IV bits, targeting a T-function based self-synchronizing stream
cipher (proposed at FSE'05 by Shamir and Klimov). Yet, more advanced
methods are open to research.


[1] S. Fischer, S. Khazaei and W. Meier, "Chosen IV Statistical
Analysis for Key Recovery Attacks on Stream Ciphers". In the
proceedings of AFRICACRYPT 2008, LNCS 5023, pp. 236–245, 2008. The
paper and slides available at: http://www.simonfischer.ch/science/africa08.php.

Shahram Khazaei and Willi Meier
From: Quadibloc on 26 Aug 2008 08:11
On Aug 25, 5:52 pm, shahram.khaz...(a)gmail.com wrote:

> The problem has been already explained by D. Wagner and G. Rose but we
> try to re-explain it using the notation from [1] to make the
> connection easier to follow.

> In cube attack ones looks for a derived function
> C(K,W) which is linear in its inputs.

This will be helpful while one is waiting for Adi Shamir's paper. From
the brief descriptions appearing in news items, though, it seems the
attack depends on the cipher being represented as a low-degree
polynomial.

Many stream cipher's don't admit of such a construction. One thinks,
for example, of RC4, as hypothetically reconstructed. Or of, say, the
SIGABA rotor machine. Or, for that matter, of the stream ciphers of
Terry Ritter.

Using a cipher based on LFSRs with only a thin veneer of non-linearity
was like wearing a big "Break Me" sign on one's back even *before*
this attack came out. Thus, while this discovery is still an important
event that will add to the public understanding of cryptanalysis, its
practical consequences might have been overstated.

Might have been - if it weren't for the fact that too many people in
real life *are* actually using ciphers "based on LFSRs with only a
thin veneer of non-linearity", something they should have known better
than to do all along.

John Savard
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: RC4 / RC4A (Was: One time pad)
Next: What is the next Prime that is 3 mod 4 from this one?