Happy Happy Joy Joy (was: On to Hydro)

[Mark S. Miller]

At 01:09 AM 8/24/00 , Tyler Close wrote:
>It might be better if you think of cryptographic hashs as "message
>digests", or MACs (Message Authentication Codes), instead of hashs.
>This makes it clear that there are additional requirements for these
>hashs than for hashtable hashs (requirements that a hashtable does not
>need to meet).

Terminology alert: MACs need to be based on a cryptohash, but are more than 
just the cryptohash.  A MAC uses a cryptohash to do symmetric authentication 
(authentication based on a shared secret, as opposed the the asymmetric 
authentication provided by signing with an asymmetric key).  The definition 
of "cryptohash" by itself has everything to do with integrity but nothing to 
do with authentication or secrets.

Also, cryptohashes *can* be used for hash-table lookup, as the Electric 
Communities "Repository" effectively did.  
http://www.eros-os.org/~majordomo/e-lang/1273.html 
http://www.eros-os.org/~majordomo/e-lang/1270.html  The cool thing about 
using the cryptohash of a key for lookup is that the table doesn't need to 
remember the keys themselves, only their cryptohash, since cryptohashes by 
assumption never collide.  (It's sort of "by definition", since if anyone 
ever finds a collision, that hash algorithm would no longer be considered a 
cryptohash.)

Note that the cryptohash, being at least 128 bits, is too long to use 
directly as in index into a lookup table data structure, so a smaller number 
needs to be derived from it.  But the same statement applies to the 32 bit 
hashes gotten from Java's Object.hashCode().  Therefore, cryptohash are not 
a disjoint category but are a kind of hash.  They satisfy more requirements 
than hash tables need, as Tyler says, but they do satisfy all the 
requirements that hashtables need.  Therefore, making the distinction by 
adding an adjective is fine.  How about "cryptohash"?

---------------------

For E, everyone needs to remember that "==" based lookup uses a hash that's 
never exposed to the E programmer, but used privately within the hashtable 
implementation.  To do otherwise would be to expose the inherent 
non-determinism of object-identity-based hash values. This is why E's hash 
tables need to be primitive.  KeyKOS (and presumably EROS?) makes KeyBits 
closely held (accessible only within the TCB) for the same reason.


         Cheers,
         --MarkM