On compressibility of random permutations
in [Cryptography]
|
From: David Eather on 21 Jan 2010 00:26 unruh wrote: > On 2010-01-21, David Eather <eather(a)tpg.com.au> wrote: >> Peter Fairbrother wrote: >>> In general there is the idea that random permutations, or sequences, are >>> not compressible. >> Random permutations are always compressible. > > Since there are fewer numbers less than the size, and compression means > a one to one mapping, random permutations are not compressible in > general. There are not enough compressed outputs. I am assuming a permutation with a defined range eg elements in the range of 0 - 255 etc. They are compressible unless I have missed something about the context in the thread (not impossible) > >>> 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 21 Jan 2010 06:29 David Eather wrote: > unruh wrote: >> On 2010-01-21, David Eather <eather(a)tpg.com.au> wrote: >>> Peter Fairbrother wrote: >>>> In general there is the idea that random permutations, or sequences, >>>> are not compressible. >>> Random permutations are always compressible. >> >> Since there are fewer numbers less than the size, and compression means >> a one to one mapping, random permutations are not compressible in >> general. There are not enough compressed outputs. > > I am assuming a permutation with a defined range eg elements in the > range of 0 - 255 etc. They are compressible unless I have missed > something about the context in the thread (not impossible) You are correct, and it's my bad for not being more precise. I wasn't talking about the compressibility of a permutation to a string of numbers (as eg the last entry is uniquely fixed, the second-to-last entry is a choice of two etc), what I was talking about was the compressibility of a string of random numbers. But I was also talking about permutations, and confused the issue. Sorry. -- Peter Fairbrother
From: Peter Fairbrother on 21 Jan 2010 06:39 Phoenix wrote: > On 20 Jan, 23:27, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote: >> Phoenix wrote: >>> 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 >> A nice idea, and useful for some purposes - though it's defined >> backwards from another idea. >> >> The problem is that, for finite random numbers above about 2^8, the >> number of possible ways of defining them in ways shorter than the number >> is greater than the number itself. >> >> Statistically, some actual numbers may not be be so defineable - but >> then we can define them as the first non-Kolgogorov-random number, and >> so on. >> >> It's a pretty concept - but in real life there is no such thing as a >> Kolmogorov-random number. >> >> --Peter Fairbrother >> > > > Now the question is: > > How many sequences are defineable and how many are not, in a field of > permutations with i.e. 2^128. There's no fixed answer to that - it depends on the instruction set of your computer. -- Peter Fairbrother
From: Peter Fairbrother on 21 Jan 2010 07:27 WTShaw wrote: > On Jan 20, 10:33 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: >> On 2010-01-21, David Eather <eat...(a)tpg.com.au> wrote: >> >>> Peter Fairbrother wrote: >>>> In general there is the idea that random permutations, or sequences, are >>>> not compressible. >>> Random permutations are always compressible. >> Since there are fewer numbers less than the size, and compression means >> a one to one mapping, random permutations are not compressible in >> general. There are not enough compressed outputs. Indeed, in general - ie using one compressor. (but let's call them random strings from now, as that's what we are really talking about, my bad for that confusion) > > Unruh is absolutely correct. It's not just an idea, it's the > definition of an order of n different elements. yes, though mangled a bit Hash something down > to a permutation and you can go not further in reducing it. see below Capture a > random permutation and you are done with the task of defining it. You have defined it, but there may be more to the task. > Of > course, a secret parent sequence of the elements need not be defined > but can be a essential separate key to the use of any selected > permutation from the available domain of them. If you can find the secret parent sequence and define it, it may well break a cipher. -- Peter Fairbrother
From: Joseph Ashwood on 21 Jan 2010 07:28
"Peter Fairbrother" <zenadsl6186(a)zen.co.uk> wrote in message news:4b576ab4$0$2532$da0feed9(a)news.zen.co.uk... > In general there is the idea that random permutations, or sequences, are > not compressible. Actually permutations are compressible. Labeling each permutation with an integer, significantly abbreviated the permutation. As an example take AES, the key can be trivially converted to an integer, and serves as such an index. Using that index as the key to AES in CTR mode will restore the permutation. For a complete permutation set of all 128-bit blocks would require (2^128)! as an upper limit, not a small number. > 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? Yes it does weaken the cipher. Since 2^128 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< (2^128)! there will always be omitted permutations in AES (128-bit key), this is a significant bias, and will be present in all permutation systems that have a key space smaller than the factorial. The real question is whether or not it is exploitable, and that is actually an open question. Joe |