Re: why compression doesn't perfectly even out entropy

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. :)

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

An entity claiming to be rick hoselton wrote:
: 
: 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. 

By the same token, if an admin runs crack on /etc/passwd to weed out poor
passwords isn't going to be faulted for reducing the key space for user's
passwords. The question is, how much of the keyspace should be eliminated
as "obviously a poor choice"?

Also, how much of this falls under "security through obscurity"?  If an
attacker knows what you omit .. his/her job is a bit easier.

Is it possible to find a percentage of the key space to eliminate that
will optimize security assuming that the attacker will try the easy
stuff first (and is it possible to quantify "easy stuff")?

- -- 
  Mark Rogaski    | Why read when you can just sit and |      Member
  System Admin    |         stare at things?           | Programmers Local
  GTI GlobalNet   | Any expressed opinions are my own  |     # 0xfffe
wendigo@pobox.com | unless they can get me in trouble. |     APL-CPIO


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

iQCVAwUBMXVWfQ0HmAyu61cJAQHltwP8Coe0i13a7NtFRYlCBdt1AEVEbz9jQhLp
6WPqGc80ETo8knHZAPVFP6ae1MmHYfbWhOY0y7I/Cv4kN8Smmu6mwIeYsuPRjCl9
ODK6qDUX1CcQX74t4ZvkTL2Umsnvwchvl1wHnaINGtud9C6nVREf34880vmJsYrl
5vsRJ1wo5Ng=
=zY9A
-----END PGP SIGNATURE-----

On Wed, 17 Apr 1996, Mark Rogaski wrote:

> 
> Is it possible to find a percentage of the key space to eliminate that
> will optimize security assuming that the attacker will try the easy
> stuff first (and is it possible to quantify "easy stuff")?

Hmmm- I think this could be interesting to study; if we treat the space 
of possible passwords as a non-uniform probability distribution 
(Zipfian?), and then transform it in such a way to be uniform (by 
having the probability of certain passwords being disqualified be 
based on their relative probability it should be possible to get a 
situation where all passwords are possible, and all have equal probability.
This gives optimum security ( I think). Of course there's then the game 
theory assumption that the attacker will know about this and try paswords 
randomly; if they instead attack passwords with a non-random approach, 
the optimum passwords will be tuned to their attack strategy, unless they 
know you're tuning to their attack in which case they will tune their 
attack to your [stack overflow - bus error, core dumped]

 Interesting exercise.


>   Mark Rogaski    | Why read when you can just sit and |      Member
>   System Admin    |         stare at things?           | Programmers Local
>   GTI GlobalNet   | Any expressed opinions are my own  |     # 0xfffe
> wendigo@pobox.com | unless they can get me in trouble. |     APL-CPIO

"There is power in a packet, power in a LAN
Power in the hands of the hacker,
But it all amounts to nothing if together we don't stand
There is power in a UNIX