Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Decimation

2 views
Skip to first unread message

Mok-Kong Shen

unread,
Dec 21, 2009, 11:18:22 AM12/21/09
to

Decimation in crypto means selecting every tenth, and in general,
selecting every nth element from a sequence in order to hide
exploitable patterns in it. (See
http://www.ciphersbyritter.com/GLOSSARY.HTM#Decimation).

A tiny generalization in my humble view would be choosing elements from
a sequence with a probability p by a statistically good PRNG. Suppose
one chooses p=0.1, pseudo-randomly pick a starting point and "decimate"
thus the digit sequence of Pi, is there any conceivable yet practical
way that an anylist could succeed to do prediction in such cases?

Thanks,

M. K. Shen

Joseph Ashwood

unread,
Dec 22, 2009, 3:05:22 AM12/22/09
to
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:hgo74e$kdq$00$1...@news.t-online.com...

Absolutely. Although it does increase the difficulty, it does not change an
insecure PRNG to a cryptographically secure PRNG.
Joe

Mok-Kong Shen

unread,
Dec 22, 2009, 6:27:54 AM12/22/09
to
Joseph Ashwood wrote:

> "Mok-Kong Shen" wrote:
>> Decimation in crypto means selecting every tenth, and in general,
>> selecting every nth element from a sequence in order to hide
>> exploitable patterns in it. (See
>> http://www.ciphersbyritter.com/GLOSSARY.HTM#Decimation).
>>
>> A tiny generalization in my humble view would be choosing elements from
>> a sequence with a probability p by a statistically good PRNG. Suppose
>> one chooses p=0.1, pseudo-randomly pick a starting point and "decimate"
>> thus the digit sequence of Pi, is there any conceivable yet practical
>> way that an anylist could succeed to do prediction in such cases?
>
> Absolutely. Although it does increase the difficulty, it does not change
> an insecure PRNG to a cryptographically secure PRNG.

It may be noted however that there is an "indirectness" involved, i.e.
the insecure PRNG employed is not directly used to encrypt (xor with
the plaintext), so that the analyst can't get its bits in order to
break it.

M. K. Shen

Cristiano

unread,
Dec 22, 2009, 6:49:04 AM12/22/09
to
Joseph Ashwood wrote:
> [...] Although it does increase the difficulty, it does not

> change an insecure PRNG to a cryptographically secure PRNG.

If you decimate the output of a LFSR (which is "an insecure PRNG") you get a
cryptographically secure PRNG (self-shrinking LFSR).

Cristiano


Greg Rose

unread,
Dec 22, 2009, 3:32:16 PM12/22/09
to
In article <4b30...@news.x-privat.org>,

No you don't. There are attacks against the SSG.

Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C

Cristiano

unread,
Dec 23, 2009, 5:47:28 AM12/23/09
to
Greg Rose wrote:
> In article <4b30...@news.x-privat.org>,
> Cristiano <cristi...@NSquipo.it> wrote:
>> Joseph Ashwood wrote:
>>> [...] Although it does increase the difficulty, it does not
>>> change an insecure PRNG to a cryptographically secure PRNG.
>>
>> If you decimate the output of a LFSR (which is "an insecure PRNG")
>> you get a cryptographically secure PRNG (self-shrinking LFSR).
>
> No you don't. There are attacks against the SSG.

There are attacks against many ciphers, but it doesn't mean that they are
not cryptographically secure.
Here:
http://en.wikipedia.org/wiki/Self-shrinking_generator#Cryptanalysis
I read that there is an attack against the SSG which requires 2^(0.7*L)
steps. If you take, say, L=256 or longer, the time needed to break that SSG
will be very big. I would call that SSG cryptographically secure PRNG.

Cristiano


0 new messages