Re: Selfshrinking MT19937 as stream cipher
 From: David Eather <eather@xxxxxxxxxx>
 Date: Mon, 16 Oct 2006 08:57:47 +1000
Cristiano wrote:
da5id65536@xxxxxxxxx wrote:Cristiano wrote:The BerlekampMassey 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 19937bit LFSR (also see a recent
post on sci.crypt.randomnumbers).
In the paper "The SelfShrinking Generator", Meier and Staffelbach
showed that the complexity of the attack for an Nbit selfshrinking
LFSR is O(2^(0.69*N)).
Using the LSB of MT19937 to get a selfshrinking 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 selfshrinking generator as a stream
cipher?
Cristiano
"Security examination of the selfshrinking generator" that presented
a much more efficient attack? The Meier and Staffelbach article was
1994, right?
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
efficient possible.
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 selfshrinking (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 19937bit LFSR, it is very unlikely that an SSG can be broken in a short time.
As far as we know, a 19937bit SSG is much stronger than any other modern cipher.
In any case, we'd only need the LFSR that the highestorder bit
position of MT19937 is equivalent to; we wouldn't need the whole
generator. That would make our selfshrinking 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 256bit 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
selfshrinking 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).
Cristiano
 References:
 Re: Selfshrinking MT19937 as stream cipher
 From: da5id65536
 Re: Selfshrinking MT19937 as stream cipher
 From: Cristiano
 Re: Selfshrinking MT19937 as stream cipher
 Prev by Date: Re: Selfshrinking MT19937 as stream cipher
 Next by Date: Re: Selfshrinking MT19937 as stream cipher
 Previous by thread: Re: Selfshrinking MT19937 as stream cipher
 Next by thread: Re: Selfshrinking MT19937 as stream cipher
 Index(es):
Relevant Pages
