< draft-eastlake-fnv-00.txt		draft-eastlake-fnv-01.txt >
	Network Working Group Glenn Fowler		Network Working Group Glenn Fowler
	INTERNET-DRAFT AT&T Labs Research		INTERNET-DRAFT AT&T Labs Research
	Intended Status: Informational Landon Curt Noll		Intended Status: Informational Landon Curt Noll
	Cisco Systems		Cisco Systems
	Kiem-Phong Vo		Kiem-Phong Vo
	AT&T Labs Research		AT&T Labs Research
	Donald Eastlake		Donald Eastlake
	Huawei Technologies		Huawei Technologies
	Expires: September 6, 2011 March 7, 2011		Expires: March 5, 2011 September 6, 2011
	The FNV Non-Cryptographic Hash Algorithm		The FNV Non-Cryptographic Hash Algorithm
	<draft-eastlake-fnv-00.txt>		<draft-eastlake-fnv-01.txt>
	Abstract		Abstract
	FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with		FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with
	good dispersion. The purpose of this document is to make information		good dispersion. The purpose of this document is to make information
	on FNV and open source code performing FNV conveniently available to		on FNV and open source code performing FNV conveniently available to
	the Internet community.		the Internet community.
	Status of This Memo		Status of This Memo
	skipping to change at page 2, line 25 ¶		skipping to change at page 2, line 25 ¶
	3. Other Hash Sizes and XOR Folding........................6		3. Other Hash Sizes and XOR Folding........................6
	4. FNV Constants...........................................7		4. FNV Constants...........................................7
	5. The Source Code.........................................9		5. The Source Code.........................................9
	5.1 FNV C Header...........................................9		5.1 FNV C Header...........................................9
	5.2 FNV C Code.............................................9		5.2 FNV C Code.............................................9
	5.3 FNV Test Code..........................................9		5.3 FNV Test Code..........................................9
	6. Security Considerations................................10		6. Security Considerations................................10
	7. IANA Considerations....................................10		6.1 Why is FNV Non-Cryptographic?.........................10
	8. References.............................................11		7. IANA Considerations....................................11
	8.1 Normative References..................................11
	8.2 Informative References................................11		8. References.............................................12
			8.1 Normative References..................................12
			8.2 Informative References................................12
			Appendix A: Work Comparison with SHA-1....................13
			Appendix B: Previous IETF Reference to FNV................14
			Appendix C: A Few Test Vectors............................15
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	1. Introduction		1. Introduction
	The FNV hash algorithm is based on an idea sent as reviewer comments		The FNV hash algorithm is based on an idea sent as reviewer comments
	to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo in		to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo in
	1991. In a subsequent ballot round Landon Curt Noll suggested an		1991. In a subsequent ballot round Landon Curt Noll suggested an
	improvement on their algorithm. Some people tried this hash and found		improvement on their algorithm. Some people tried this hash and found
	that it worked rather well. In an EMail message to Landon, they named		that it worked rather well. In an EMail message to Landon, they named
	it the "Fowler/Noll/Vo" or FNV hash. [FNV]		it the "Fowler/Noll/Vo" or FNV hash. [FNV]
	FNV hashes are designed to be fast while maintaining a low collision		FNV hashes are designed to be fast while maintaining a low collision
	rate. Their speed allows one to quickly hash lots of data while		rate. Their speed allows one to quickly hash lots of data while
	maintaining a reasonably low collision rate. The high dispersion of		maintaining a reasonably low collision rate. The high dispersion of
	the FNV hashes makes them well suited for hashing nearly identical		the FNV hashes makes them well suited for hashing nearly identical
	strings such as URLs, hostnames, filenames, text, IP addresses, etc.		strings such as URLs, hostnames, filenames, text, IP addresses, etc.
	However, they are not suitable for cryptographic use. (For some hash		However, they are generally not suitable for cryptographic use. (See
	algorithms more suitable for cryptographic use see [RFCsha].)		Section 6.1.)
	The FNV hash is widely used, for example in DNS servers, database		The FNV hash is widely used, for example in DNS servers, database
	indexing hashes, major web search / indexing engines, netnews history		indexing hashes, major web search / indexing engines, netnews history
	file Message-ID lookup functions, anti-spam filters, a spellchecker		file Message-ID lookup functions, anti-spam filters, a spellchecker
	programmed in Ada 95, flatassembler's open source x86 assembler -		programmed in Ada 95, flatassembler's open source x86 assembler -
	user-defined symbol hashtree, non-cryptographic file fingerprints,		user-defined symbol hashtree, non-cryptographic file fingerprints,
	computing Unique IDs in DASM (DTN Applications for Symbian Mobile-		computing Unique IDs in DASM (DTN Applications for Symbian Mobile-
	phones), Microsoft's hash_map implementation for VC++ 2005, the		phones), Microsoft's hash_map implementation for VC++ 2005, the
	realpath cache in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and		realpath cache in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and
	many other uses.		many other uses.
	FNV hash algorithms and source code have been released into the		FNV hash algorithms and source code have been released into the
	public domain. The authors of the FNV algorithm took deliberate steps		public domain. The authors of the FNV algorithm took deliberate steps
	to disclose the algorithm in a public forum soon after it was		to disclose the algorithm in a public forum soon after it was
	invented. More than a year passed after this public disclosure and		invented. More than a year passed after this public disclosure and
	the authors deliberatley took no steps to patent the FNV algorithm.		the authors deliberately took no steps to patent the FNV algorithm.
	Therefore, it is safe to say that the FNV authors have no patent		Therefore, it is safe to say that the FNV authors have no patent
	claims on the FNV algorithm as published.		claims on the FNV algorithm as published.
	If you use an FNV function in an application, you are kindly		If you use an FNV function in an application, you are kindly
	requested to send an EMail about it to: fnv-mail@asthe.com		requested to send an EMail about it to: fnv-mail@asthe.com
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	2. FNV Basics		2. FNV Basics
	skipping to change at page 6, line 31 ¶		skipping to change at page 6, line 31 ¶
	temp = FNV_S ( data-to-be-hashed )		temp = FNV_S ( data-to-be-hashed )
	hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 )		hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 )
	Hash functions are a trade-off between speed and strength. For		Hash functions are a trade-off between speed and strength. For
	example, a somewhat stronger hash may be obtained for exact FNV sizes		example, a somewhat stronger hash may be obtained for exact FNV sizes
	by calculating an FNV twice as long as the desired output ( S = 2*k )		by calculating an FNV twice as long as the desired output ( S = 2*k )
	and performing such data folding using a k equal to the size of the		and performing such data folding using a k equal to the size of the
	desired output. However, if a much stronger hash, for example one		desired output. However, if a much stronger hash, for example one
	suitable for cryptographic applications, is wanted, algorithms		suitable for cryptographic applications, is wanted, algorithms
	designed for that purpose, such as those in [RFCsha] should be used.		designed for that purpose, such as those in [RFC6234], should be
			used.
	If it is desired to obtain a hash result that is a value between 0		If it is desired to obtain a hash result that is a value between 0
	and max, where max is a not a power of two, simply choose an FNV hash		and max, where max is a not a power of two, simply choose an FNV hash
	size S such that 2**S > max. Then calculate the following:		size S such that 2**S > max. Then calculate the following:
	FNV_S mod ( max+1 )		FNV_S mod ( max+1 )
	The resulting remainder will be in the range desired but will suffer		The resulting remainder will be in the range desired but will suffer
	from a bias against large values with the bias being larger if 2**S		from a bias against large values with the bias being larger if 2**S
	is only a little bigger than max. If this bias is acceptable, no		is only a little bigger than max. If this bias is acceptable, no
	skipping to change at page 10, line 14 ¶		skipping to change at page 10, line 14 ¶
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	6. Security Considerations		6. Security Considerations
	This document is intended to provide convenient open source access by		This document is intended to provide convenient open source access by
	the Internet community to the FNV non-cryptographic hash. No		the Internet community to the FNV non-cryptographic hash. No
	assertion of suitability for cryptographic applications is made for		assertion of suitability for cryptographic applications is made for
	the FNV hash algorithms.		the FNV hash algorithms.
			6.1 Why is FNV Non-Cryptographic?
			A full discussion of cryptographic hash requirements and strength is
			beyond the scope of this document. However, here are three
			characteristics of FNV that would generally be considered to make it
			non-cryptographic:
			1. Work Factor - To make brute force inversion hard, a cryptographic
			hash should be computationally expensive, especially for a general
			purpose processor. But FNV is designed to be very inexpensive on a
			general purpose processor. (See Appendix A.)
			2. Sticky State - A cryptographic hash should not have a state in
			which it can stick for a plausible input pattern. But, in the
			unlikely event that the FNV hash variable becomes zero and the
			input is a sequence of zeros, the hash variable will remain at
			zero until there is a non-zero input byte and the final hash value
			will be unaffected by the length of the sequence of zero input
			bytes. Of course, for the common case of fixed length input, this
			would not be significant because the number of non-zero bytes
			would vary inversely with the number of zero bytes and for some
			types of input runs of zeros do not occur. Furthermore, the
			inclusion of even a little unpredictable input may be sufficient
			to stop an adversary from inducing a zero hash variable.
			3. Diffusion - Every output bit of a cryptographic hash should be an
			equally complex function of every input bit. But it is easy to see
			that the least significant bit of a direct FNV hash is the XOR of
			the least significant bits of every input byte and does not depend
			on any other input bit. If this is considered a problem, it can be
			easily fixed by folding (see Section 3).
			Nevertheless, none of the above have proven to be a problem in actual
			practice for the many applications of FNV.
			INTERNET-DRAFT FNV
	7. IANA Considerations		7. IANA Considerations
	This document requires no IANA Actions. The RFC Editor should delete		This document requires no IANA Actions. RFC Editor Note: please
	this section before publication.		delete this section before publication.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	8. References		8. References
	Below are the normative and informative references for this document.		Below are the normative and informative references for this document.
	8.1 Normative References		8.1 Normative References
	None.		None.
	8.2 Informative References		8.2 Informative References
	[FNV] - FNV web site:		[FNV] - FNV web site:
	http://www.isthe.com/chongo/tech/comp/fnv/index.html		http://www.isthe.com/chongo/tech/comp/fnv/index.html
	[RFCsha] - D. Eastlake, T. Hansen, "US Secure Hash Algorithms (SHA		[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm
	and SHA based HMAC and HKDF)", draft-eastlake-sha2b-07.txt, in		1 (SHA1)", RFC 3174, September 2001.
	RFC Editor queue.
			[RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security
			Considerations for the SHA-0 and SHA-1 Message-Digest
			Algorithms", RFC 6194, March 2011.
			[RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash
			Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May
			2011.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	Appendix: Test Vectors		Appendix A: Work Comparison with SHA-1
			This section provides a simplistic rough comparison of the level of
			effort required per input byte to compute FNV-1a and SHA-1 [RFC3174].
			Ignoring transfer of control and conditional tests and equating all
			logical and arithmetic operations, FNV requires 2 operations per
			byte, an XOR and a multiply.
			SHA-1 is a relatively weak cryptographic hash producing a 160-bit
			hash. It that has been partially broken [RFC6194]. It is actually
			designed to accept a bit vector input although almost all computer
			uses apply it to an integer number of bytes. It processes blocks of
			512 bits (64 bytes) and we estimate the effort involved in SHA-1
			processing a full block. Ignoring SHA-1 initial set up, transfer of
			control, and conditional tests, but counting all logical and
			arithmetic operations, including counting indexing as an addition,
			SHA-1 requires 1,744 operations per 64 bytes block or 27.25
			operations per byte. So by this rough measure, it is a little over 13
			times the effort of FNV for very large amounts of data. However, FNV
			is commonly used for small inputs. Using the above method, for inputs
			of N bytes, where N is less than 55 so SHA-1 will take one block
			(SHA-1 includes padding and an 8 byte length at the end of the data
			in the last block), the ratio of the effort for SHA-1 to the effort
			for FNV will be 872/N. For example, with an 8 byte input, SHA-1 will
			take 109 times as much effort as FNV.
			Stronger cryptographic functions than SHA-1 generally have an even
			high work factor.
			INTERNET-DRAFT FNV
			Appendix B: Previous IETF Reference to FNV
			FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has
			since expired. It was later decided that it would be better to use a
			cryptographic hash for that use.
			Below is the Jave code for FNV64 from that TLS draft include by the
			kind permission of the author:
			/**
			* Java code sample, implementing 64 bit FNV-1a
			* By Stefan Santesson
			*/
			import java.math.BigInteger;
			public class FNV {
			static public BigInteger getFNV1aToByte(byte[] inp) {
			BigInteger m = new BigInteger("2").pow(64);
			BigInteger fnvPrime = new BigInteger("1099511628211");
			BigInteger fnvOffsetBasis =
			new BigInteger("14695981039346656037");
			BigInteger digest = fnvOffsetBasis;
			for (byte b : inp) {
			digest = digest.xor(BigInteger.valueOf((int) b & 255));
			digest = digest.multiply(fnvPrime).mod(m);
			}
			return digest;
			}
			}
			INTERNET-DRAFT FNV
			Appendix C: A Few Test Vectors
	Below are a few test vectors in the form of ASCII strings and their		Below are a few test vectors in the form of ASCII strings and their
	FNV32 and FNV64 hashes using the FNV-1a algorithm.		FNV32 and FNV64 hashes using the FNV-1a algorithm.
	Strings without null (zero byte) termination:		Strings without null (zero byte) termination:
	String FNV32 FNV64		String FNV32 FNV64
	"" 0x811c9dc5 0xcbf29ce484222325		"" 0x811c9dc5 0xcbf29ce484222325
	"a" 0xe40c292c 0xaf63dc4c8601ec8c		"a" 0xe40c292c 0xaf63dc4c8601ec8c
	"foobar" 0xbf9cf968 0x85944171f73967e8		"foobar" 0xbf9cf968 0x85944171f73967e8
	skipping to change at page 14, line 17 ¶		skipping to change at page 17, line 17 ¶
	Copyright, Disclaimer, and Additional IPR Provisions		Copyright, Disclaimer, and Additional IPR Provisions
	Copyright (c) 2011 IETF Trust and the persons identified as the		Copyright (c) 2011 IETF Trust and the persons identified as the
	document authors. All rights reserved.		document authors. All rights reserved.
	This document is subject to BCP 78 and the IETF Trust's Legal		This document is subject to BCP 78 and the IETF Trust's Legal
	Provisions Relating to IETF Documents		Provisions Relating to IETF Documents
	(http://trustee.ietf.org/license-info) in effect on the date of		(http://trustee.ietf.org/license-info) in effect on the date of
	publication of this document. Please review these documents		publication of this document. Please review these documents
	carefully, as they describe your rights and restrictions with respect		carefully, as they describe your rights and restrictions with respect
	to this document. Code Components extracted from this document must		to this document. Code Components extracted from this document must
	include Simplified BSD License text as described in Section 4.e of		include Simplified BSD License text as described in Section 4.e of
	the Trust Legal Provisions and are provided without warranty as		the Trust Legal Provisions and are provided without warranty as
	described in the BSD License. This Internet-Draft is submitted to		described in the Simplified BSD License. This Internet-Draft is
	IETF in full conformance with the provisions of BCP 78 and BCP 79.		submitted to IETF in full conformance with the provisions of BCP 78
			and BCP 79.
End of changes. 13 change blocks.
	17 lines changed or deleted		138 lines changed or added
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/