Re: Selfshrinking MT19937 as stream cipher
 From: da5id65536@xxxxxxxxx
 Date: 15 Oct 2006 10:19:02 0700
Cristiano wrote:
The BerlekampMassey 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 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
Isn't there a paper by Mihaljevic from 1995 titled something like
"Security examination of the selfshrinking generator" that presented a
much more efficient attack? The Meier and Staffelbach article was
1994, right?
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. 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.
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.
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?
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. On the other hand,
people have found long LFSRs with few taps that actually have a lot of
"goodness" (which means, as we know, that "goodness" is not a guarantee
of security, though a lack of "goodness" implies a lack of security).
David Sexton
.
 FollowUps:
 Re: Selfshrinking MT19937 as stream cipher
 From: Cristiano
 Re: Selfshrinking MT19937 as stream cipher
 Prev by Date: Re: Utimaco Safeguard Easy vulnerability
 Next by Date: Re: Selfshrinking MT19937 as stream cipher
 Previous by thread: Re: What's wrong with AES?
 Next by thread: Re: Selfshrinking MT19937 as stream cipher
 Index(es):
Relevant Pages
