# Re: Self-shrinking MT19937 as stream cipher

*From*: David Eather <eather@xxxxxxxxxx>*Date*: Mon, 16 Oct 2006 08:57:47 +1000

Cristiano wrote:

da5id65536@xxxxxxxxx wrote:Cristiano wrote:The Berlekamp-Massey algorithm shows that the linear complexity ofIsn't there a paper by Mihaljevic from 1995 titled something like

any bit of the MT19937 is 19937, this means that taking the LSB of

MT19937 is equivalent to use a 19937-bit LFSR (also see a recent

post on sci.crypt.random-numbers).

In the paper "The Self-Shrinking Generator", Meier and Staffelbach

showed that the complexity of the attack for an N-bit self-shrinking

LFSR is O(2^(0.69*N)).

Using the LSB of MT19937 to get a self-shrinking generator, we get

an attack complexity of O(2^13757) which seems much bigger than the

one of any stream cipher.

Why don't use an MT19937 based self-shrinking generator as a stream

cipher?

Cristiano

"Security examination of the self-shrinking generator" that presented

a much more efficient attack? The Meier and Staffelbach article was

1994, right?

I just found a link on Wikipedia in which is said: "A more advanced attack, discovered by Mihaljevic, is able to break a register a hundred bits in length in around 2^57 steps, using an output sequence of only 4.9 x 10^8 bits.", but "my" LFSR is 19937 bits in length!

Wow Cristiano, they've really given you a tough time here...even Greg

Rose. I understand his point, I think. The Meier and Staffelbach

paper didn't assert that the attack presented there was the most

efficient possible.

Sure, nobody could say that. Nobody knows the most efficient possible attack for SSG, AES, Serpent, ...

They didn't try to prove a lower limit of

security for self-shrinking (or shrinking) generators. I _think_

that's Rose's point, but I haven't read the article. Apparently you

and he have.

My point is that the SSG is very old and it is very unlikely that a new very efficient attack can be discovered. Using a 19937-bit LFSR, it is very unlikely that an SSG can be broken in a short time.

As far as we know, a 19937-bit SSG is much stronger than any other modern cipher.

In any case, we'd only need the LFSR that the highest-order bit

position of MT19937 is equivalent to; we wouldn't need the whole

generator. That would make our self-shrinking generator just like any

other, and no less efficient.

The whole generator is very efficient. I guess it is much more efficient than its equivalent LFSR which generates the MSB (consider that I implemented a 256-bit LFSR and it is very slow).

Did you miss the whole point of stream ciphers?

They are also efficient in terms of power consumption and implementations size. Greg uses Sober because it gives him reasonable security and about 30% more battery life in highly mobile applications.

The 19937 bits of state and the other twists and turns you have to go through mean that your stream generator does not provide these advantages.

Anyone who might consider your stream cipher would have to stop at AES or any new block cipher and ask if there is anything extra your stream cipher provides.

.

What other characteristics of an LFSR, other than length (i.e., linear

complexity of its output), are important for designing a good

self-shrinking generator? Does the density of the polynomial (i.e.,

the number of taps used in the LFSR) make any difference?

Afaik, with a dense polynomial it should be harder to break.

I do know from testing that neither the long length of an LFSR nor a

large number of taps seems to correlate with "goodness" of its output,

where "goodness" is the ability to pass the kinds of statistical tests

of randomness that you and I like to implement.

I seen the same (if the LFSR is not too short).

Cristiano

**References**:**Re: Self-shrinking MT19937 as stream cipher***From:*da5id65536

**Re: Self-shrinking MT19937 as stream cipher***From:*Cristiano

- Prev by Date:
**Re: Self-shrinking MT19937 as stream cipher** - Next by Date:
**Re: Self-shrinking MT19937 as stream cipher** - Previous by thread:
**Re: Self-shrinking MT19937 as stream cipher** - Next by thread:
**Re: Self-shrinking MT19937 as stream cipher** - Index(es):