Path: gmdzi!unido!mcvax!uunet!cs.utexas.edu!rutgers!
tut.cis.ohio-state.edu!ucbvax!hoptoad!gnu
From: gnu@hoptoad.uucp (John Gilmore)
Newsgroups: sci.crypt
Subject: Ralph Merkle's new cryptosystems
Message-ID: <7785@hoptoad.uucp>
Date: 28 Jun 89 10:00:26 GMT
Organization: Grasshopper Group in San Francisco
Lines: 31
Posted: Wed Jun 28 11:00:26 1989

I have been hearing rumors about some new cryptosystems invented by
Ralph Merkle <merk...@xerox.com> of Xerox PARC.  They are a one-way
hash function (for taking a large document and computing a small
"checksum" from it, to verify its authenticity) and two conventional
ciphers.

These cryptosystems seem to have several advantages over the ones
in common use.  They are designed for fast software implementation, so
they use 8-bit and 32-bit quantities rather than odd numbers of bits.
The level of security is choosable by the user by setting how many
internal iterations to perform and how large a key to use (or how
large a hash value to generate).  And the tables used internally
are not of mysterious origin, as with DES, but are derived from the
old RAND 'million random digits' by a publicly known algorithm.

Rumor is that the one-way hash function, called Snefru, has been
approved for use in the USA (export approval is pending) and that Xerox
PARC wants it to be widely used; a freely distributed implementation
will exist.  This may tie in with the recent announcement that NSA will
soon allow the export of cryptosystems of any strength as long as they
are used for authentication, not information hiding.

The difference between a good one-way hash function and a checksum or
CRC is how hard it is to find two input blocks that map to the same
hash value.  It's not hard to find another block that has the same CRC
value as the message you are trying to subvert; CRC's don't protect
against active tampering.  Strong one-way hash functions do.
-- 
John Gilmore      {sun,pacbell,uunet,pyramid}!hoptoad!gnu      g...@toad.com
Love your country but never trust its government.
		     -- from a hand-painted road sign in central Pennsylvania