PKLAMMER@CUDENVER.BITNET (Pete Klammer 303/556-3915) (02/24/90)
[Ed. From the CERT-Tools mailing list.] "Re-posting of this announcement to appropriate groups is encouraged." >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> From: smb@ulysses.att.com Subject: Snefru algorithm for checksumming Date: Wed, 21 Feb 90 13:39:59 EST A few days ago, I wrote a message suggesting that CRCs were inappropriate for security uses, and that Snefru or MD4 might be better. Several people wrote back asking where they could obtain them. Ralph Merkle -- the author of Snefru -- has posted the following note; as per the permissions at the end of the note, I am resending it to this list. --Steve Bellovin smb@ulysses.att.com - ------- Forwarded Message Date: Tue, 20 Feb 90 14:06:50 PST From: Ralph Merkle <merkle@parc.xerox.com> Subject: $1,000 reward for breaking Snefru 2.0 The following was posted to sci.crypt: - - -------------------------------------- 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@xerox.com Xerox PARC 3333 Coyote Hill Road Palo Alto, CA 94304 - ------- End of Forwarded Message **CERT-Tools Information:**************************************************** * Submissions : cert-tools@cert.sei.cmu.edu * * Address additions/deletions/changes : cert-tools-request@cert.sei.cmu.edu * * Moderator : tools@cert.sei.cmu.edu * ***************************************************************************** >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> /** --poko " I'm half Estonian, which makes up for the other half. " Pete Klammer /(303)556-3915 FAX:(303)556-4822 PKLAMMER@PIKES.COLORADO.EDU CU-Denver Computing Services / Campus Box 169 BITNET: PKLAMMER@CUDENVER 1200 Larimer St NC2506 / Denver CO 80204-5300 UU:!boulder!pikes!pklammer **/