Re: Self-shrinking MT19937 as stream cipher

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.

--
To email me, substitute nowhere->spamcop, invalid->net.
.

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 ... Using the LSB of MT19937 to get a self-shrinking generator, ...
    (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)
  • 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
    ... 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, we get an attack ... They didn't try to prove a lower limit of security ...
    (sci.crypt)