64 views

Skip to first unread message

Aug 22, 2008, 2:38:50 PM8/22/08

to

Now the dust has settled a bit on his Crypto 2008 talk, does anybody

have an explanation how this attack works?

have an explanation how this attack works?

It sounds like it could have a deep impact on the E-Stream ciphers?

Simon

Aug 22, 2008, 4:54:20 PM8/22/08

to

Aug 22, 2008, 5:31:58 PM8/22/08

to

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

>

> ~A

>

> ~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.

Aug 22, 2008, 6:00:03 PM8/22/08

to

>On Aug 22, 11:38 am, Simon Johnson <simon.john...@gmail.com> wrote:

>> Now the dust has settled a bit on his Crypto 2008 talk, does anybody

>> have an explanation how this attack works?

>> 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

Aug 22, 2008, 9:31:05 PM8/22/08

to

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.

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.

Aug 22, 2008, 9:56:10 PM8/22/08

to

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.

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.

Aug 22, 2008, 9:57:57 PM8/22/08

to

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.

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.

Aug 22, 2008, 10:14:01 PM8/22/08

to

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"

Aug 25, 2008, 7:52:51 PM8/25/08

to

On Aug 23, 3:56 am, d...@taverner.cs.berkeley.edu (David Wagner)

wrote:

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

Aug 26, 2008, 8:11:23 AM8/26/08

to

On Aug 25, 5:52 pm, shahram.khaz...@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

Aug 26, 2008, 8:38:43 AM8/26/08

to

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.

Aug 26, 2008, 11:07:43 AM8/26/08

to

On Aug 26, 6:38 am, shahram.khaz...@gmail.com wrote:

> On Aug 26, 2:11 pm, Quadibloc <jsav...@ecn.ab.ca> wrote:

> 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

Aug 26, 2008, 6:35:17 PM8/26/08

to

In article <0d600b79-aa11-4df9...@o40g2000prn.googlegroups.com>,

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.

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.

Aug 27, 2008, 11:34:16 AM8/27/08

to

On Aug 26, 1:52 am, shahram.khaz...@gmail.com wrote:

> 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.

Aug 27, 2008, 11:34:30 AM8/27/08

to

On Aug 26, 1:52 am, shahram.khaz...@gmail.com wrote:

> 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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu