Re: Self-shrinking MT19937 as stream cipher

Cristiano wrote:
The Berlekamp-Massey algorithm shows that the linear complexity of 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

Isn't there a paper by Mihaljevic from 1995 titled something like
"Security examination of the self-shrinking generator" that presented a
much more efficient attack? The Meier and Staffelbach article was
1994, right?

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

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.

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?

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. On the other hand,
people have found long LFSRs with few taps that actually have a lot of
"goodness" (which means, as we know, that "goodness" is not a guarantee
of security, though a lack of "goodness" implies a lack of security).

David Sexton

.

Relevant Pages

  • Re: Self-shrinking MT19937 as stream cipher
    ... MT19937 is equivalent to use a 19937-bit LFSR (also see a recent ... In the paper "The Self-Shrinking Generator", ... There is not a single "the" attack. ... MT also argue against its use as a stream cipher. ...
    (sci.crypt)
  • Re: Self-shrinking MT19937 as stream cipher
    ... MT19937 is equivalent to use a 19937-bit LFSR (also see a recent ... In the paper "The Self-Shrinking Generator", ... showed that the complexity of the attack for an N-bit self-shrinking ... 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. ...
    (sci.crypt)
  • Re: Self-shrinking MT19937 as stream cipher
    ... MT19937 is equivalent to use a 19937-bit LFSR (also see a recent ... In the paper "The Self-Shrinking Generator", ... showed that the complexity of the attack for an N-bit self-shrinking ... My point is that the SSG is very old and it is very unlikely that a new very ...
    (sci.crypt)
  • Re: Self-shrinking MT19937 as stream cipher
    ... MT19937 is equivalent to use a 19937-bit LFSR (also see a recent ... In the paper "The Self-Shrinking Generator", ... Using the LSB of MT19937 to get a self-shrinking generator, ... one of any stream cipher. ...
    (sci.crypt)
  • Re: Self-shrinking MT19937 as stream cipher
    ... this means that taking the LSB of MT19937 is equivalent to use a 19937-bit LFSR. ... 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). ... Why don't use an MT19937 based self-shrinking generator as a stream cipher? ...
    (sci.crypt)