From: rick hoselton <hoz@univel.telescan.com>
To: cypherpunks@toad.com
Message Hash: 9bd0f52bd16624aef8bf4bebe0fab5cd0736dfa04e6cf90102b713b24b53f3a2
Message ID: <199604171558.IAA02972@toad.com>
Reply To: N/A
UTC Datetime: 1996-04-17 20:45:08 UTC
Raw Date: Thu, 18 Apr 1996 04:45:08 +0800
From: rick hoselton <hoz@univel.telescan.com>
Date: Thu, 18 Apr 1996 04:45:08 +0800
To: cypherpunks@toad.com
Subject: Re: why compression doesn't perfectly even out entropy
Message-ID: <199604171558.IAA02972@toad.com>
MIME-Version: 1.0
Content-Type: text/plain
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. :)
Return to April 1996
Return to “Simon Spero <ses@tipper.oit.unc.edu>”