From: nobody@neva.org (Neva Remailer)
Date: Thu, 13 Nov 1997 08:57:33 +0800
To: cypherpunks@cyberpass.net
Subject: Re: Secure Hashing for Entropy
Message-ID: <199711130047.SAA02607@dfw-ix6.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain




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

Jon Leonard wrote:
>Monty Cantsin wrote:
>> Often we have a source of entropy whose output we use as the input to
>> a secure hash function.
>> 
>> Does it matter if the hashing function is secure?  I don't think so.
>> All that really matters is that the function hashes evenly so that any
>> input string is about as likely as any other input string to result in
>> a particular hash.  Even if the hash function is weak and collisions
>> can be found, if it is even the same level of entropy is still
>> available.
>> 
>> Have I got this right?
>
>In the case where:
>1) Your entropy source is as good as you think it is
>2) Your opponent knows nothing about the data from your entropy source
>and
>3) Your entropy mixes the way you expect it to.
>
>this is indeed the case.
>
>If you're not completely sure about the above, using a cryptographic
>hash requires your hypothetical opponent to be able to reverse the hash
>to exploit what they know, rather than simpler computations.
>
>Since it seems that paranoia pays off in the design of cryptographic
>software, I'd recommend always using a strong hash.

Let's say you are using the entropy to create a session key for a
symmetric cipher.  If The Enemy can guess the session key, you have
already lost the game.  It doesn't matter if the original
entropy-containing string can be guessed because the hash was weak.

If your entropy source is weak and the original string can be guessed,
then you've lost the game even if the hash function is strong.  The
Enemy knows how to compute hashes as well as you do.

But, I think I now see a way a secure hash can sort of help you.

Let's say you have an entropy source which gives you a base 3 number
of arbitrary length.  There is no even way to map base 3 numbers into
base 2 numbers.  Use of a hash function obscures the mapping.

For example, we want a random 8 bit number.  We can get this by
generating a 6 digit base 3 number, P, and computing P mod 2^8.

This has the unappealing property that it overlaps unevenly.

3^6 = 729 = 2 * 256 + 217.

There is an 89.3% chance that the resulting number will be between 0
and 216, inclusive.  The probability should be 84.7%.  This gives The
Enemy an edge if there are a number of messages to be broken.  The
cost to guarantee a break on a particular message is still the same.

The use of a secure hash means that we can hope that the nature of the
overlap cannot be determined.

The downside is that there are no secure hash functions whose
properties are completely understood.  All we know for sure is that
not much is really known to the public.

So, the secure hash function in your crypto system could be reducing
your effective entropy substantially if your entropic strings just
happen to hash down to a smaller subset of possible hashes than
expected.  The use of the secure hash function may obscure what is
happening from The Enemy.  All we know for sure is that it obscures it
from ourselves.

Ideally, we want to match our sources of entropy with the base of the
random number desired and eliminate the question.

In the field, the most widely available and reliable entropy generator
is a six sided die.  If we are using a cipher which takes a base 2
key, this is inconvenient.  You can only get one really good bit out
of each throw.

How hard would to be to construct a secure symmetric cipher which
accepted a base 6 key?

Monty Cantsin
Editor in Chief
Smile Magazine
http://www.neoism.org/squares/smile_index.html
http://www.neoism.org/squares/cantsin_10.htm

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

iQEVAwUBNGoiSJaWtjSmRH/5AQFzaAf+Jm1wlPlC9obQQLoRoss2qpLv5z900X9Z
2u3NO5eG/W9QQRUWTeqzeXOK3Ps8DYKhYXhgYy35AJy6uRrd5820MUUGULAhr0zH
JqfVFU6FUGEgEpZsxxLTAVvU/OPx5g3LqeQJfsp92pOsIoeObhiBh6+1zxNLWHU5
fxSrDJAe9eANeUJ5nXlLBGtGwg9ZfvVw4+OWsLpO3ZsQXp+mke+dvz423WukqaQi
VJ1VM+XTRBetRCZIuIcqKoCdkYrB2h/S0KIprp/7lHFOpIZWfo++p87BZm0LQuF5
Suo+NGSMtooCZwLYpPQrlQLtB51An8TjdVfr7k2YkUXpxPLcEp6CEg==
=om47
-----END PGP SIGNATURE-----