Re: Self-shrinking MT19937 as stream cipher

Greg Rose wrote:
In article <451ba638$1_2@xxxxxxxxxxxx>,
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)).

There is not a single "the" attack. They showed
only that it has high linear complexity. The
attack that actually breaks the Self-Shrinking
Generator is a variant of fast correlation.

Please, read the page 213; they wrote another thing.
http://homes.esat.kuleuven.be/~jlano/stream/papers/SSGms.pdf#search=%22SSGms.pdf%22

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?

There are at least two different ways to do this.
One is to treat the output as a bit stream, and
apply the usual SSG construction to it; but doing
this is incredibly bit-fiddly, and any pretence of
efficiency of the generator would be lost in a
software implementation. Another way would be to
decimate the output *words* based on a single bit
of a particular word. I think this is breakable,
because the essential linearity of MT would still
remain, giving the analyst lots of redundant
information to bring to bear.

The huge state and initialization requirements of
MT also argue against its use as a stream cipher.

But the huge state can also be useful.

So, personally, I think anything this simplistic
is not going to be useful. But if you give a
concrete construction, maybe we could give
concrete answers.

1) Generate N bits of entropy (N>128);
2) put the bit sequence into the state of MT19937;
3) initialize MT;
4) generate the shrunken sequence of bits:
unsigned int a;
do a=MT19937(); while(MT19937()&1);
return a&1;
5) use it as usual for a stream cipher.

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", ... Although a low linear complexity is proof of insecurity, ... attribute of 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
    ... 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
    ... 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)