Prev: RC4 / RC4A (Was: One time pad)
Next: What is the next Prime that is 3 mod 4 from this one?
From: Simon Johnson on 22 Aug 2008 14:38
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
From: amzoti on 22 Aug 2008 16:54
On Aug 22, 11:38 am, 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

Did you see this?

http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html

~A
From: Simon Johnson on 22 Aug 2008 17:31
> http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html
>
> ~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.
From: Greg Rose on 22 Aug 2008 18:00
>On Aug 22, 11:38�am, 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?

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
From: David Wagner on 22 Aug 2008 21:31
It was mentioned in discussion that it might be interesting to have
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.
 |  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?