Adi Shamir's Cube Attacks
Simon Johnson
have an explanation how this attack works?
It sounds like it could have a deep impact on the E-Stream ciphers?
Simon
amzoti
Simon Johnson
>
> ~A
Yes, I had seen that. Unfortunately, like all things Schneier he's
more about style than substance.
Chocolate fireguards have had more use than that article.
Frankly, the article is so weak on information that I doubt he
understands the attack. The comment about the hashes is pretty strong
evidence of this.
Simon.
Greg Rose
>> Now the dust has settled a bit on his Crypto 2008 talk, does anybody
>> have an explanation how this attack works?
I wrote the following short description for a
mailing list [modified here after subsequent
clarification from Adi]. But it's really difficult
to describe in words... part of his brilliance to
make it understandable I guess. Anyway, I don't
want to be on the spot to answer questions about
my (potentially flawed) description... been there,
done that.
<rehash>
I spent about an hour trying to come up with a
short but legible explanation of the technique,
and failed. Sorry about that. I can visualize it,
and could probably reproduce Adi's drawings on a
whiteboard, but not with typing. The following is
as close as I could come.
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. Let the
degree of the polynomial (that is, the number of
bits in the biggest term) be d.
His example was an insanely complicated
theoretical LFSR-based stream cipher of degree 16;
recovers keys with 2^28 time (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.
Basically the method focuses on terms of the
polynomial in which only one secret bit of the key
appears, and many of the non-secret bits. Using
chosen (or lucky) plaintexts, vary a subset of
(d-2) of the non-secret bits, and sum the output
bits (mod 2, that is, XOR). Fix all the other
non-secret bits. Now all the terms that involve
less than the full complement of non-secret bits
will appear an even number of times in the sum,
and because it is mod 2, they will all cancel out!
The only terms that will be left are some of the
ones with one secret bit, and all ones for the
non-secret bits... but that is linear in the
secret bit! So what you are left with is a simple,
linear, polynomial relating unknown (key) bits.
Gather enough such equations, just a few more than
the number of key bits will do, and solve the
linear system in trivial time. Note that you had
to have 2^(d-2) chosen plaintexts to sum over for
each of the equations... that's where the
complexity comes from. The attack is called Cube
because in the case where d=4, each time you sum
over all of the varying known bits, it can be
visualized as the face of a cube, the corners of
which are the possibilities for the 3 known
inputs.
>> It sounds like it could have a deep impact on the E-Stream ciphers?
I mentioned they're looking at Trivium and hoping
to have a result. I've just gone and rescanned to
refresh my memory... There are a few that I
couldn't remember and don't have the time to
relearn, but mostly they are safe, either
nonlinear feedback, high-degree transformations,
or irregular clocking.
Hope that helps,
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
David Wagner
another look at E0 in light of the new cube attack. I took a brief look
at E0 after hearing Adi's talk. It's not obvious that the cube attack
would apply directly. There are two challenges for a cube attack on E0:
to the 4-bit state ('blender') as well as the more complex key/IV loading
process (there is a two-level process, where one mixes the key and IV,
then runs E0 to get 128 bits, which is then used to key a second E0
instance that generates the actual keystream output). However, it's not
totally implausible that some extension to the cube attack might apply
to E0.
For instance, it seems plausible (though by no means certain) that a E0
variant that only applies one of these two levels might be vulnerable to
a cube attack. Suppose we kept only the first level of E0 and skipped
the second level. The key/IV loading process for the first level makes
every bit of the initial state be a linear function of the key/IV.
Running the cipher for 200 clocks and discarding output doesn't help; at
every time instant, the LFSR states will be a known linear function of
the key and IV. The 'blender' is still a barrier, because the blender
introduces a high degree of nonlinearity. However the blender has only
4 bits of state, which seems like a potential weakness. I wonder whether
there's some way to take advantage of this weakness within the framework
of a cube attack.
Example: Suppose that we introduced four new boolean variables
b0_t..b3_t to represent the state of the blender at time t.
Then we can write the keystream output at time t, z_t, as a
low-degree function of these 4 boolean variables along with the
key and IV boolean variables:
z_t = f(k_0,..,k_127, iv_0, .., iv_31, b0_t, .., b3_t)
The polynomial f has low degree: degree 4 or so, if my calculations
are accurate. Moreover we can write z(t+1) as a function of the
same variables:
z_{t+1} = f'(k_0,..,k_127, iv_0, .., iv_31, b0_t, .., b3_t)
(Note: here we've written z_{t+1} in terms of the same blender
variables b0_t,.., b3_t, not b0_{t+1},.., b3_{t+1}.) The degree
of the polynomial f' is larger than the polynomial f, but still
reasonably small. In general, I think we can express all of
z_{t-2}, z_{t-1}, z_t, z_{t+1}, z_{t+2} as low-degree polynomials
of these same variables (perhaps degree at most 8 or 10 or so).
Perhaps we could try to find some low-degree function g() of these
five keystream bits (perhaps a linear function) so that
y = g(z_{t-2}, z_{t-1}, z_t, z_{t+1}, z_{t+2})
can be expressed as a polynomial
y = f*(k_0,..,k_127, iv_0, .., iv_31, b0_t, .., b3_t)
where f* has some maxterm usable in an attack. For instance,
suppose we can express f*() in the form
f*(...) = p(k_0,..,k_127) q(iv_0, .., iv_31)
+ r(k_0,..,k_127, iv_0, b0_t, .., b3_t)
where p() is a linear function. Then the cube attack will apply:
given sufficient keystream, we can learn p(k_0,..,k_127), which
reveals information about the key. The same attack might apply even
if p() isn't linear.
It's not clear to me whether any attack like this could work, but
it might be interesting to try to see whether the cube attack could
be extended to apply to stream ciphers with a little bit of additional
state (beyond the state of the LFSRs), like E0.
David Wagner
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.
David Wagner
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.
biject
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"
shahram...@gmail.com
wrote:
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
Quadibloc
> 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
shahram...@gmail.com
That is why the attack is not applicable to clock controlled LFSR
based stream ciphers or harder to apply on non-linear feedback shift
registers.
Quadibloc
> On Aug 26, 2:11 pm, Quadibloc <jsav...@ecn.ab.ca> wrote:
> > 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.
> That is why the attack is not applicable to clock controlled LFSR
> based stream ciphers or harder to apply on non-linear feedback shift
> registers.
I thought I had seen a statement that one of the examples where it was
applied was a clock-controlled LFSR, but I could be mistaken. I don't
imagine it could be applicable to a good clock-controlled LFSR (think
of the MacLaren-Marsaglia random number generator as a standard of
comparison), but there are some where 75% of the bits match every
second bit of a plain LFSR, and that would be vulnerable to attack.
Ah, even some very poor ones would still get an arbitrary number of
bits out of syncrhonization. So "not applicable" is usually valid, but
I still wouldn't want to use those ciphers.
John Savard
Greg Rose
Quadibloc <jsa...@ecn.ab.ca> wrote:
>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.
Yes, although what the Cube attack does do is
seriously increase the limit of what would be
considered a "low-degree" polynomial. The
contrived example that Adi used was of degree 16,
and could be solved in minutes. But Toyocrypt, a
relatively recent proposal (although already
broken) can be expressed as a degree-17 polynomial
except for a single term of degree 63 that is
virtually always zero! So the Cube attack does
represent a significant improvement on the state
of the art on ciphers like this. (Hmmm, whether
Cube would apply to Toyocrypt or not would depend
on the key loading, and I can't remember enough,
so don't consider this to be a statement that
Toyocrypt is necessarily vulnerable.)
>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.
Sorry, I think that's a bit revisionist. Such
ciphers were military state of the art until
things like fast correlation attacks appeared in
the late 80's [*]. Many are still in use. Much of
the stream cipher literature in the 90's focused
on how to patch such things up (not using sparse
feedback, for example). Toyocrypt was a new,
2002ish design with a lot of theory backing it up.
And no-one would say that Trivium isn't
state-of-the-art, although it remains to be seen
whether Trivium will be vulnerable or not.
Greg.
* Willi Meier and Othmar Staffelbach: Fast
correlation attacks on certain stream ciphers;
Journal of Cryptology, 1(3):159-176, 1989.
shahram...@gmail.com
> 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.
Find it here:
Shahram Khazaei and Willi Meier, "New Directions in Cryptanalysis of
Self-synchronizing Stream Ciphers", Cryptology ePrint Archive, Report
2008/369. Available at: http://eprint.iacr.org/2008/369.
shahram...@gmail.com
> 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.
Find it here:
Shahram Khazaei and Willi Meier, "New Directions in Cryptanalysis of
Self-synchronizing Stream Ciphers", Cryptology ePrint Archive, Report
2008/369. Available at: http://eprint.iacr.org/2008/369.
Shahram Khazaei and Willi Meier