Re: why compression doesn't perfectly even out entropy

[rick hoselton <hoz@univel.telescan.com>]

At 08:12 PM 4/16/96 -0400, Perry E. Metzger wrote:

>> Are you sure you want to claim that the text of Hamlet would make 
>> a good key for a one-time pad?

... much deleted ....

>It is far, far more probable for the cryptanalyst, thinking the
>key was "Hamlet", to get out a plausible but totally bogus text, than
>it is for the key to actually be "Hamlet". 

I can agree with this.

>Of course, it is also far,
>far more probable for you to be stupid than for a random number
>generator to put out "Hamlet".

I agree here too.  I've been stupid many times, but 
I never expect to see a fair random number 
generator produce Hamlet.  (I should live so long!)

>but if you go around getting rid of
>RNGs that produce "Hamlet" or anything close, you have in theory given
>information to the attacker that gives them a slightly better chance
>of attacking you since your pads are no longer purely random.

And I could agree with this too, except that cryptanalysts do not 
consider every string to be equally likely.  If they did, they would 
never even bother to look at XORing a bitstream with ciphertext to 
produce plaintext.  

>The reason all this isn't stupid to discuss and actually has some
>importance is just this fact. If you build a system that discards
>things that "don't look like they have enough entropy" (which certain
>people around here have proposed), you are giving the cryptanalyst a
>very strong piece of information about the key, so your key is no
>longer totally unpredictable. 

This is true.  But it is also unavoidable.  Actually, I'm pleased to give 
up one-percent of my keyspace, if that's the one-percent that an analyst 
will check first.

Another example: What if I selected a nonsense passphrase, 
"Dagmar shaved Howard's cocker spaniel"  Not great, but adequate for my needs.
If, by some wild coindence, a book by that title became a best seller, I would 
change my passphrase.  A cryptanalyst who knew that was my feeling could
simplify 
his cracking by not bothering to search for best selling book titles.  On
the other 
hand, a cryptanalyst who was not so convinced of my paranoia, and who DID check 
book titles, would not find my passphrase.  I assume that BOTH philosophies 
would be used in a serious attack.  When I do the math, it says that, assuming 
BOTH types of attack are done, it is better to have a passphrase that is not 
the title of a book. 

>An irony, but something important to
>keep in mind. Every once in a while (once in every four billion bits,
>or so) your random number generator will put out 32 1's in a row if it
>is functioning properly. 

Agreed.  And if that produces a "weak key" for your cipher, you'll get broken.

>Any given small segment of the output of a
>good RNG might not look "random", but "random" isn't a property of a
>given number -- it is the property of the infinite sequence itself.

I agree here too.  But the analyst doesn't see the infinite sequence, 
only the number itself.

I am enjoying this discussion, but I feel like I'm running out of 
useful new ways to try to express this idea.  If I don't reply, 
it doesn't mean you have convinced me. :)