Re: Self-shrinking MT19937 as stream cipher

Mike Amling wrote:
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?

"Why not use ..." or "Why don't we use..." (Hi, Cristiano!)

Your last correction was on Apr, 4 2003 and that is the result. :-)

IIRC, it uses more RAM than other stream ciphers.

Yes, it has an huge state (19937 bits).

It wouldn't have a
built-in MAC like Phelix. Unlike VMPC, it can't be implemented with a
pack of cards. How's its speed?

It won't be the fastest, but it should be reasonably fast.

Could it have unexpected vulnerabilities, like RC4?

I proposed that scheme because it is based on MT19937 and on SS generators
which both have a sound proof. So, I think that with that simple scheme, the
cipher shouldn't have any unexpected vulnerability. The "usual" cipher
algorithms are much more complex than the scheme I proposed and they can
hide some weakness, while MT and SS, afaik, are well known.

Cristiano


.

Relevant Pages

  • 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)
  • 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)
  • 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
    ... new very efficient attack can be discovered. ... a 19937-bit SSG is much stronger than any other ... modern cipher. ... Is that trick implementable also for a LFSR? ...
    (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)