Prev: True Random Number Generator
Next: Confused about random strings
From: Peter Fairbrother on 20 Jan 2010 15:42
In general there is the idea that random permutations, or sequences, are
not compressible.

While this may be true, it need not be true of a particular permutation.

Suppose that, by random chance, the particular randomly-generated
permutation is the sequence 1,2,3,4 ... etc.

That's compressible. It won't occur often, but it can occur.

Cartoon at:

http://www.google.com/imgres?imgurl=http://www.random.org/analysis/dilbert.jpg&imgrefurl=http://www.random.org/analysis/&h=257&w=680&sz=65&tbnid=nstbI3k78X1MrM:&tbnh=53&tbnw=139&prev=/images%3Fq%3Ddilbert%2Brandom&usg=__eOy0f5JovE_JsEMpRRNUbfUa-vM=&ei=H2hXS-iyJJ380wSsvYnzBA&sa=X&oi=image_result&resnum=4&ct=image&ved=0CBMQ9QEwAw


Referring to the recent encrypting twice thread etc, the "magic
permutation" (where a chosen plaintext outputs the key, or something
close to that - or even some permutation which is sufficiently close to
that to give an advantage over brute force) may be compressible.

It's unlikely, but it's not impossible. And there are usually lots of
chosen plaintexts (and suitable permutations) to choose from.


If we don't know what it is, or they are, does that weaken the cipher?


-- Peter Fairbrother
From: Peter Fairbrother on 20 Jan 2010 16:19
Peter Fairbrother wrote:
> In general there is the idea that random permutations, or sequences, are
> not compressible.
>
> While this may be true, it need not be true of a particular permutation.
>
> Suppose that, by random chance, the particular randomly-generated
> permutation is the sequence 1,2,3,4 ... etc.
>
> That's compressible. It won't occur often, but it can occur.
>
> Cartoon at:
>
> http://www.google.com/imgres?imgurl=http://www.random.org/analysis/dilbert.jpg&imgrefurl=http://www.random.org/analysis/&h=257&w=680&sz=65&tbnid=nstbI3k78X1MrM:&tbnh=53&tbnw=139&prev=/images%3Fq%3Ddilbert%2Brandom&usg=__eOy0f5JovE_JsEMpRRNUbfUa-vM=&ei=H2hXS-iyJJ380wSsvYnzBA&sa=X&oi=image_result&resnum=4&ct=image&ved=0CBMQ9QEwAw
>
>
>
> Referring to the recent encrypting twice thread etc, the "magic
> permutation" (where a chosen plaintext outputs the key, or something
> close to that - or even some permutation which is sufficiently close to
> that to give an advantage over brute force) may be compressible.
>
> It's unlikely, but it's not impossible. And there are usually lots of
> chosen plaintexts (and suitable permutations) to choose from.

Suppose that there are 2^128 different possible chosen plaintext
attacks, as in AES. On average, that reduces the entropy of at least one
of the resulting permutations by 128 bits.

And the permutation doesn't have to be the "accurate magic permutation"
in order to be better than brute force, something close will do. Or even
something which is only very distant, but maybe 0.00001% similar.


Which reduces the required entropy of the better-than-brute-force
permutation still further.

And it doesn't have to be a chosen plaintext attack.

(very drunk now)

>
>
> If we don't know what it is, or they are, does that weaken the cipher?
>
>
> -- Peter Fairbrother
From: unruh on 20 Jan 2010 16:55
On 2010-01-20, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote:
> Peter Fairbrother wrote:
>> In general there is the idea that random permutations, or sequences, are
>> not compressible.
>>
>> While this may be true, it need not be true of a particular permutation.
>>
>> Suppose that, by random chance, the particular randomly-generated
>> permutation is the sequence 1,2,3,4 ... etc.

With the right compressor, any permuation can be compressed. A
compressor is a mapping from the permutation into the numbers. And there
is always a mapping which maps your favourite permutation to the number
1. On average a good compressor will map a permutation into an number
the same size as the permutation element.

>>
>> That's compressible. It won't occur often, but it can occur.
>>
>> Cartoon at:
>>
>> http://www.google.com/imgres?imgurl=http://www.random.org/analysis/dilbert.jpg&imgrefurl=http://www.random.org/analysis/&h=257&w=680&sz=65&tbnid=nstbI3k78X1MrM:&tbnh=53&tbnw=139&prev=/images%3Fq%3Ddilbert%2Brandom&usg=__eOy0f5JovE_JsEMpRRNUbfUa-vM=&ei=H2hXS-iyJJ380wSsvYnzBA&sa=X&oi=image_result&resnum=4&ct=image&ved=0CBMQ9QEwAw
>>
>>
>>
>> Referring to the recent encrypting twice thread etc, the "magic
>> permutation" (where a chosen plaintext outputs the key, or something
>> close to that - or even some permutation which is sufficiently close to
>> that to give an advantage over brute force) may be compressible.
>>
>> It's unlikely, but it's not impossible. And there are usually lots of
>> chosen plaintexts (and suitable permutations) to choose from.

But all an analysys can do is talk about the averages. If I simply guess
the cleartext I am far far more likely to guess the right cleartext than
that your permutation is compressible.

>
> Suppose that there are 2^128 different possible chosen plaintext
> attacks, as in AES. On average, that reduces the entropy of at least one
> of the resulting permutations by 128 bits.

So what? I talso increases the entropy of most of them by a tiny amount.


>
> And the permutation doesn't have to be the "accurate magic permutation"
> in order to be better than brute force, something close will do. Or even
> something which is only very distant, but maybe 0.00001% similar.
>
>
> Which reduces the required entropy of the better-than-brute-force
> permutation still further.
>
> And it doesn't have to be a chosen plaintext attack.
>
> (very drunk now)

Agreed.

>
>>
>>
>> If we don't know what it is, or they are, does that weaken the cipher?
>>
>>
>> -- Peter Fairbrother
From: Peter Fairbrother on 20 Jan 2010 17:07
unruh wrote:
> On 2010-01-20, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote:
>> Peter Fairbrother wrote:
>>> In general there is the idea that random permutations, or sequences, are
>>> not compressible.
>>>
>>> While this may be true, it need not be true of a particular permutation.
>>>
>>> Suppose that, by random chance, the particular randomly-generated
>>> permutation is the sequence 1,2,3,4 ... etc.
>
> With the right compressor, any permuation can be compressed.

And any second ciphering could do the "magic permutation" if it was the
right compressor/cipher, with less work than brute force.

Not to say it would be likely - but it could.

-- Peter Fairbrother
From: Phoenix on 20 Jan 2010 19:06
On 20 Jan, 19:42, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:
> In general there is the idea that random permutations, or sequences, are
> not compressible.
>
> While this may be true, it need not be true of a particular permutation.
>
> Suppose that, by random chance, the particular randomly-generated
> permutation is the sequence 1,2,3,4 ... etc.


"Algorithmic information theory studies, among other topics, what
constitutes a random sequence. The central idea is that a string of
bits is random if and only if it is shorter than any computer program
that can produce that string (Kolmogorov randomness)—this means that
random strings are those that cannot be compressed. Pioneers of this
field include Andrey Kolmogorov and his student Per Martin-Löf, Ray
Solomonoff, and Gregory Chaitin." from Randomness wikipedia

But I agree with you, some sequences can be like 1,2,3,... or
1,1,1,1....

Like in the real world, good algorithms can, some times, (very
little), generate that kind of sequences.

I think that's why George Marsaglia on his Diehard tests, say 'p
happens".

Alvo
 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: True Random Number Generator
Next: Confused about random strings