Re: Self-shrinking MT19937 as stream cipher
- From: David Eather <eather@xxxxxxxxxx>
- Date: Mon, 16 Oct 2006 08:57:47 +1000
da5id65536@xxxxxxxxx wrote:Cristiano wrote:The Berlekamp-Massey algorithm shows that the linear complexity ofIsn't there a paper by Mihaljevic from 1995 titled something like
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
"Security examination of the self-shrinking generator" that presented
a much more efficient attack? The Meier and Staffelbach article was
I just found a link on Wikipedia in which is said: "A more advanced attack, discovered by Mihaljevic, is able to break a register a hundred bits in length in around 2^57 steps, using an output sequence of only 4.9 x 10^8 bits.", but "my" LFSR is 19937 bits in length!
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
Sure, nobody could say that. Nobody knows the most efficient possible attack for SSG, AES, Serpent, ...
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.
My point is that the SSG is very old and it is very unlikely that a new very efficient attack can be discovered. Using a 19937-bit LFSR, it is very unlikely that an SSG can be broken in a short time.
As far as we know, a 19937-bit SSG is much stronger than any other modern cipher.
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.
The whole generator is very efficient. I guess it is much more efficient than its equivalent LFSR which generates the MSB (consider that I implemented a 256-bit LFSR and it is very slow).
Did you miss the whole point of stream ciphers?
They are also efficient in terms of power consumption and implementations size. Greg uses Sober because it gives him reasonable security and about 30% more battery life in highly mobile applications.
The 19937 bits of state and the other twists and turns you have to go through mean that your stream generator does not provide these advantages.
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.
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?
Afaik, with a dense polynomial it should be harder to break.
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.
I seen the same (if the LFSR is not too short).