Re: Self-shrinking MT19937 as stream cipher

Greg Rose wrote:
In article <451c09b8_1@xxxxxxxxxxxx>,
Cristiano <cristiano.pi@xxxxxxxxxx> wrote:
Peter Pearson wrote:
On 28 Sep 2006 12:38:48 +0200, Cristiano <cristiano.pi@xxxxxxxxxx>
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?

Although a low linear complexity is proof of insecurity, a high
linear complexity is *not* proof of security. It's similar to
period length.

Agreed, but what that has to do with my message?

It seems to me that security is an important
attribute of a stream cipher. So it has a lot to
do with your message. You are proposing something
as a stream cipher, when it is built out of two
components that are individually insecure.

The SS generator is _not_ insecure.

Your only justification is that it has a long period.

Without Mike's corrections my English becomes bad, but would you quote the
line in my message in which I talked about the period?

Cristiano


.

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", ... 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", ... 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
    ... 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)
  • Self-shrinking MT19937 as stream cipher
    ... The Berlekamp-Massey algorithm shows that the linear complexity of any bit ... that the complexity of the attack for an N-bit self-shrinking LFSR is ... Using the LSB of MT19937 to get a self-shrinking generator, ... Why don't use an MT19937 based self-shrinking generator as a stream cipher? ...
    (sci.crypt)