[merkle@xxxxxxxxxxxxxx: Snefru and Alcor Chapter Meetings]

[Mark S. Miller <mark>]

Return-Path: <merkle@xxxxxxxxxxxxxxxxxxxxxxx>
Date: Tue, 20 Feb 90 13:13:46 PST
From: Ralph Merkle <merkle@xxxxxxxxxxxxxx>
To: mark@xxxxxxxxxx
Subject: Snefru and Alcor Chapter Meetings

The one-way hash function, Snefru 2.0, is available
by anonymous FTP from arisia.xerox.com in directory
/pub/hash.  It is available for use by anyone interested.

A $1,000 reward is offered to the first person to break it.


General:  Snefru 2.0 is a one-way hash function.  One-way
hash functions have also been called manipulation detection
codes (MDC's), message digests, cryptographically secure
checksums, cryptographically secure hash totals, and sometimes
fingerprints.

One way hash functions do not involve use of a secret key
or any secret information.  They are used to authenticate
information, and to verify that the information has not
been tampered with.  One-way hash functions have the
following properties:

1.)  Given any input of any size (a file, for example) it is
easy to compute the output of the one-way hash function.  If
the one-way hash function is designated H, then
      output = H(input)
is easy to compute (takes time linear in the size of the input).

2.)  Although the input might be very large, the output is
relatively small and of fixed size.  In Snefru 2.0, the output
can be either 128 or 256 bits (selectable by the user).

3.)  It is computationally infeasible to find two inputs x and
x' that produce the same output.  That is, finding x and x' such
that:

       H(x) = H(x')

is infeasible.  Finding such a pair of inputs is known as
"cracking" or "breaking" the one-way hash function.

4.)  Given an output, it is computationally infeasible to
find an input that produces that output.  (This property
is not always used).


One-way hash functions are not the same as Message Authentication
Codes, or MAC's, which involve the use of a secret key.



History of Snefru:

Snefru version 1.0 was designed and made public over a year ago.
No significant security flaws were found then or since in Snefru 1.0,
but several improvements were suggested.  Most significantly, the
tables used in Snefru 1.0 were not generated in a publicly verifiable
fashion.

Snefru version 2.0 uses a set of tables generated from publicly
known random information:  "A Million Random Digits with
100,000 Normal Deviates" by the RAND Corporation, published
by the Free Press in 1955.  In addition, the algorithm used
to derive the tables is also publicly known (and available
for anonymous FTP along with Snefru 2.0).

During the redesign, the basic algorithm was made simpler
and some features of modest utility which increased the
complexity of the design were eliminated.  The revisions
for Snefru 2.0 were completed in July.  The C source for
Snefru 2.0 was made available by anonymous FTP in November
of 1989.


Security of Snefru:

The security of one-way hash functions can (at present) only
be assessed by making them widely available for review and
attack.  At the present time, Snefru has undergone some internal
review at Xerox and has been subjected to two separate and
independent reviews by two outside consultants hired
for the purpose.  No security problems have been uncovered.

During the past decade, however, many one-way hash functions
have been proposed and then broken.  The security of any particular
one-way hash function should therefore be viewed with caution.
And, of course, Xerox Corporation makes no representations
concerning either the merchantability of Snefru or the suitability
of Snefru for any particular purpose.  It is provided "as is"
without express or implied warranty of any kind.

Various groups not connected with Xerox have begun to examine
the security of Snefru since it was made publicly available.
It will probably be a while before these groups develop an
opinion about its security.

To encourage examination of Snefru, a reward of $1,000 is offered
to the first person who shows they have broken it.  A "break"
is defined as providing two different inputs that produce the
same output.  The output size will be 128 bits, and the "security level"
parameter will be set at 2 (these are the default settings).
(Note that a more secure setting for the security level parameter (4)
and a larger output size (256 bits) are available in Snefru 2.0
as options).

Fine print:  Xerox employees cannot enter.  The winner must send his
name, address, and social security number (if available) along with the
inputs x and x' that produce the same output.  It is expected that
other relevant information (the nature of the algorithm used, the
hardware, etc) will also be sent, though this is not required.  Any
taxes are the responsibility of the winner.   We reserve the right
to decide ties (multiple entries on or about the same date) and our
decision will be final.


Implementations:

Snefru 2.0 is a C version.  Snefru 2.1 is identical algorithmically,
but is partially implemented in assembly language to improve
performance.  The two implementations produce the same result,
which increases the belief that both are correct.  Snefru 2.1 is
now also available for anonymous FTP.  The assembly language version
hashes slightly over 8 megabits per second (slightly over 1 megabyte
per second) on a SUN SPARC station 1 when I/O time is not included
(the actual execution time of the hash algorithm by itself is measured).
The same version hashes at slightly over 6 megabits per second
when the I/O time is included.  The C version of Snefru 2.1 hashes
at 4 megabits per second (including I/O time). 



Free Availability:

Anyone who wishes to use Snefru can do so without charge.
The following notices appear in the source, and are the only
restrictions on the use of Snefru:

Copyright (c) Xerox Corporation 1989.  All rights reserved.

License to copy and use this software is granted provided
that it is identified as the "Xerox Secure Hash Function"
in all material mentioning or referencing this software
or this hash function.

License is also granted to make and use derivative works
provided that such works are identified as "derived from
the Xerox Secure Hash Function" in all material mentioning
or referencing the derived work.

Xerox Corporation makes no representations concerning either
the merchantability of this software or the suitability of
this software for any particular purpose.  It is provided
"as is" without express or implied warranty of any kind.



Re-posting of this announcement to appropriate groups is encouraged.


Ralph C. Merkle
merkle@xxxxxxxxx
Xerox PARC
3333 Coyote Hill Road
Palo Alto, CA 94304