Prev: RC4 / RC4A (Was: One time pad)
Next: What is the next Prime that is 3 mod 4 from this one?
From: shahram.khazaei on 26 Aug 2008 08:38
On Aug 26, 2:11 pm, Quadibloc <jsav...(a)ecn.ab.ca> wrote:
> 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

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.
From: Quadibloc on 26 Aug 2008 11:07
On Aug 26, 6:38 am, shahram.khaz...(a)gmail.com wrote:
> On Aug 26, 2:11 pm, Quadibloc <jsav...(a)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
From: Greg Rose on 26 Aug 2008 18:35
In article <0d600b79-aa11-4df9-8d0f-6bccb3ef3fe8(a)o40g2000prn.googlegroups.com>,
Quadibloc <jsavard(a)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.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
From: shahram.khazaei on 27 Aug 2008 11:34
On Aug 26, 1:52 am, shahram.khaz...(a)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
From: shahram.khazaei on 27 Aug 2008 11:34
On Aug 26, 1:52 am, shahram.khaz...(a)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
First  |  Prev  | 
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?