Re: why compression doesn't perfectly even out entropy

At 10:07 AM 4/16/96 -0400, Perry E. Metzger wrote:

>...Usually, random
>sequences are non-compressable, but it is possible (though very
>improbable) for Hamlet to appear out of a random number generator,
>and it is of course quite compressable...

But even if it came from a completely random source, it would 
still make a bad one-time pad.  When people say "compressable" 
or "algorithmic complexity" or "random", a context is always implied.  

In the context of "fair coin flips" the text of Hamlet is NOT compressible.
Because no string is more likely than any other.  Any algorithm that could 
compress that string, will, on the average INCREASE the length of 
"fair coin flip" strings it tries to compress.

Under the context of "pads that might be used for cryptographic purposes" the 
text of Hamlet is quite compressible.  An attacker is much more likely to 
test for such a stream than one that appears more random.  So, even if you 
got "Hamlet" from a perfectly random source, you should reject it for crypto 
purposes.

There is an exception to this rule.  If you are so revered as a cryptographer 
that no analyst would believe that you would deliberately choose a
non-random pad, 
then it would be safe to use Hamlet if it appeared in a random source.

It is amazing that one's reputation can affect the randomness of the bitstrings 
one uses.  

PS:
I have written a compressor that can compress ANY string to the single byte "X".
There are 2**n different decompressor programs, where n is the bit size of the 
original file.  All you have to do is specify the number of the correct 
decompressor program, and you have the original file.  Note that no computer 
is required for either the compressor or the decompressor.  (patent pending)

-----BEGIN PGP SIGNED MESSAGE-----

In article <199604161843.LAA19508@toad.com>,
rick hoselton <hoz@univel.telescan.com> wrote:

> At 10:07 AM 4/16/96 -0400, Perry E. Metzger wrote:
> 
> >...Usually, random
> >sequences are non-compressable, but it is possible (though very
> >improbable) for Hamlet to appear out of a random number generator,
> >and it is of course quite compressable...
> 
> But even if it came from a completely random source, it would 
> still make a bad one-time pad.  When people say "compressable" 
> or "algorithmic complexity" or "random", a context is always implied.  
> 
> In the context of "fair coin flips" the text of Hamlet is NOT compressible.
> Because no string is more likely than any other.  Any algorithm that could 
> compress that string, will, on the average INCREASE the length of 
> "fair coin flip" strings it tries to compress.
> 
> Under the context of "pads that might be used for cryptographic purposes" the 
> text of Hamlet is quite compressible.  An attacker is much more likely to 
> test for such a stream than one that appears more random.  So, even if you 
> got "Hamlet" from a perfectly random source, you should reject it for crypto 
> purposes.

This thread is becoming isomorphic to one that took place on the
Coderpunks list.  Jonathan Wienke was promoting an idea to make the
output of a PRNG "more" random by throwing away output whose statistics
didn't match the ideal statistics of an ideal RNG.  Critics of this
scheme (including Perry) argued along these lines:

Suppose you think that quotes from Hamlet don't belong in your OTP
keystream, and so you filter them out.  In doing so, you are making your
keystream *less* random, not more, because you are making some bit
sequences more likely than others.

Given that Hamlet quotes aren't very likely, you aren't making your
keystream very much weaker, but you *are* weakening it.  

See the Coderpunks archives for more details on this argument.

- -- 
Alan Bostick               | They say in online country there is no middle way
mailto:abostick@netcom.com | You'll either be a Usenet man or a thug for the CDA
news:alt.grelb             |    Simon Spero (after Tom Glazer)
http://www.alumni.caltech.edu/~abostick

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQB1AwUBMXUQuuVevBgtmhnpAQHZpgMApBbI3CPieZc/V/vQt5vAqHX/XcRqWjg3
Rilta9XizlIfq7BYS4NKefov7t2kAW+cgsWESC17rJ7gkXCYIsdvaGg4q1uunDG+
0MXhL406zQbcsPy3iUROGHFIz+IRvkNY
=qjiR
-----END PGP SIGNATURE-----

rick hoselton writes:
> At 10:07 AM 4/16/96 -0400, Perry E. Metzger wrote:
> 
> >...Usually, random
> >sequences are non-compressable, but it is possible (though very
> >improbable) for Hamlet to appear out of a random number generator,
> >and it is of course quite compressable...
> 
> But even if it came from a completely random source, it would 
> still make a bad one-time pad.

No it wouldn't. There is a tiny but nonzero probability that xoring
your one time pad with your text will result in a cyphertext equal to,
say, the Bible. Big deal. If the key is really random, the
cryptanalyst has no way to tell what the underlying text was.

> In the context of "fair coin flips" the text of Hamlet is NOT compressible.

Huh?

There is only one context in which things are compressable or not --
is there a smaller representation for them.

> Because no string is more likely than any other.  Any algorithm that could 
> compress that string, will, on the average INCREASE the length of 
> "fair coin flip" strings it tries to compress.

True enough, but the claim was that a random string has no
representation which is smaller than itself.

.pm

"Perry E. Metzger" writes:
>> In the context of "fair coin flips" the text of Hamlet is NOT compressible.
>
>Huh?
>
>There is only one context in which things are compressable or not --
>is there a smaller representation for them.

Then I propose the following compression algorithm to compress your
"random" one-time pad of 2 million bits with value k.  The algorithm
will decompress the input bit "1" to k, and decompress the input bit
"0" to the bit-string "10101010".  Therefore your "random" pad is
compressible to exactly one bit, and is not "random" as you supposed.

"Smaller representation" indeed.  The decompression *algorithm* must be
accounted for in the "representation" of the compressed text, otherwise
an arbitrary amount of information may be stored in the algorithm
itself.

Hamming codes offer a way to compress any bit stream.  They move
whatever patterns they can find in independent 8-bit segments into the
coding alphabet, and replace them with shorter strings.  If you don't
save the alphabet, you can't decompress the stream, and have lost
information that was originally in the stream.

If an OTP generator accidentally chooses "Hamlet", big deal.  As long
as your opponent believes that you have a good OTP generator he has no
reason to try "Hamlet" before any other pad, so Hamlet's
compressibility as english text is irrelevant.

Scott Brickner writes:
> "Perry E. Metzger" writes:
> >> In the context of "fair coin flips" the text of Hamlet is NOT compressible