< draft-eastlake-fnv-01.txt		draft-eastlake-fnv-02.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: March 5, 2011 September 6, 2011		Expires: March 23, 2011 September 24, 2011
	The FNV Non-Cryptographic Hash Algorithm		The FNV Non-Cryptographic Hash Algorithm
	<draft-eastlake-fnv-01.txt>		<draft-eastlake-fnv-02.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 26 ¶		skipping to change at page 2, line 26 ¶
	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
	6.1 Why is FNV Non-Cryptographic?.........................10		6.1 Why is FNV Non-Cryptographic?.........................10
	7. IANA Considerations....................................11		7. IANA Considerations....................................11
			8. Acknowledgements.......................................11
	8. References.............................................12		9. References.............................................12
	8.1 Normative References..................................12		9.1 Normative References..................................12
	8.2 Informative References................................12		9.2 Informative References................................12
	Appendix A: Work Comparison with SHA-1....................13		Appendix A: Work Comparison with SHA-1....................13
	Appendix B: Previous IETF Reference to FNV................14		Appendix B: Previous IETF Reference to FNV................14
	Appendix C: A Few Test Vectors............................15		Appendix C: A Few Test Vectors............................15
			Appendix Z: Change Summary................................16
			From -00 to -01...........................................16
			From -01 to -02...........................................16
	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.
	skipping to change at page 4, line 37 ¶		skipping to change at page 4, line 37 ¶
	FNV-1a is suggested for general use.		FNV-1a is suggested for general use.
	2.1 FNV Primes		2.1 FNV Primes
	The theory behind FNV_Prime's is beyond the scope of this document		The theory behind FNV_Prime's is beyond the scope of this document
	but the basic property to look for is how an FNV_Prime would impact		but the basic property to look for is how an FNV_Prime would impact
	dispersion. Now, consider any n-bit FNV hash where n is >= 32 and		dispersion. Now, consider any n-bit FNV hash where n is >= 32 and
	also a power of 2. For each such an n-bit FNV hash, an FNV_Prime p is		also a power of 2. For each such an n-bit FNV hash, an FNV_Prime p is
	defined as:		defined as:
	The smallest prime of the form p = 2**t + 2**8 + b where:		When s is an integer and 4 < s < 11, then FNV_Prime is the
	- t is an integer such that:		smallest prime p of the form:
	If n == 32, then t == int((3/4)*n) == 24, or
	If n >= 64, then t == 8*int((n+5)/12).		256**int((5 + 2^s)/12) + 2**8 + b
	- b is an integer such that:
	0 < b < 2**8, and		where b is an integer such that:
			0 < b < 2**8
	The number of one-bits in b is 4 or 5		The number of one-bits in b is 4 or 5
			and where p mod (2**40 - 2**24 - 1) > (2**24 + 2**8 + 2**7).
	Experimentally, FNV_Primes matching the above constraints tend to		Experimentally, FNV_Primes matching the above constraints tend to
	have better dispersion properties. They improve the polynomial		have better dispersion properties. They improve the polynomial
	feedback characteristic when an FNV_Prime multiplies an intermediate		feedback characteristic when an FNV_Prime multiplies an intermediate
	hash value. As such, the hash values produced are more scattered		hash value. As such, the hash values produced are more scattered
	throughout the n-bit hash space.		throughout the n-bit hash space.
			INTERNET-DRAFT FNV
			The case where s < 5 is not considered because the resulting hash
			quality is too low. Such small hashes can, if desired, be derived
			from a 32 bit FNV hash by XOR folding (see Section 3). The case where
			s > 10 is not considered because of the doubtful utility of such
			large FNV hashes and because the criteria for such large FNV_Primes
			is more complex, due to the sparsity of such large primes, and would
			needlessly clutter the criteria given above.
	Per the above constraints, an FNV_Prime should have only 6 or 7 one-		Per the above constraints, an FNV_Prime should have only 6 or 7 one-
	bits in it. Therefore, some compilers may seek to improve the		bits in it. Therefore, some compilers may seek to improve the
	performance of a multiplication with an FNV_Prime by replacing the		performance of a multiplication with an FNV_Prime by replacing the
	multiplication with shifts and adds. However, note that the		multiplication with shifts and adds. However, note that the
	INTERNET-DRAFT FNV
	performance of this substitution is highly hardware-dependent and		performance of this substitution is highly hardware-dependent and
	should be done with care. FNV_Primes were selected primarily for the		should be done with care. FNV_Primes were selected primarily for the
	quality of resulting hash function, not for compiler optimization.		quality of resulting hash function, not for compiler optimization.
	2.2 FNV offset_basis		2.2 FNV offset_basis
	The offset_basis values for the n-bit FNV-1a algorithms are computed		The offset_basis values for the n-bit FNV-1a algorithms are computed
	by applying the n-bit FNV-0 algorithm to the following 32 octets:		by applying the n-bit FNV-0 algorithm to the 32 octets representing
			the following character string in [US-ASCII]:
	chongo <Landon Curt Noll> /\../\		chongo <Landon Curt Noll> /\../\
	The \'s in the above string are not C-style escape characters. In C-		The \'s in the above string are not C-style escape characters. In C-
	string notation, these 32 octets are:		string notation, these 32 octets are:
	"chongo <Landon Curt Noll> /\\../\\"		"chongo <Landon Curt Noll> /\\../\\"
	2.3 FNV Endianism		2.3 FNV Endianism
	skipping to change at page 10, line 24 ¶		skipping to change at page 10, line 24 ¶
	6.1 Why is FNV Non-Cryptographic?		6.1 Why is FNV Non-Cryptographic?
	A full discussion of cryptographic hash requirements and strength is		A full discussion of cryptographic hash requirements and strength is
	beyond the scope of this document. However, here are three		beyond the scope of this document. However, here are three
	characteristics of FNV that would generally be considered to make it		characteristics of FNV that would generally be considered to make it
	non-cryptographic:		non-cryptographic:
	1. Work Factor - To make brute force inversion hard, a cryptographic		1. Work Factor - To make brute force inversion hard, a cryptographic
	hash should be computationally expensive, especially for a general		hash should be computationally expensive, especially for a general
	purpose processor. But FNV is designed to be very inexpensive on a		purpose processor. But FNV is designed to be very inexpensive on a
	general purpose processor. (See Appendix A.)		general-purpose processor. (See Appendix A.)
	2. Sticky State - A cryptographic hash should not have a state in		2. Sticky State - A cryptographic hash should not have a state in
	which it can stick for a plausible input pattern. But, in the		which it can stick for a plausible input pattern. But, in the very
	unlikely event that the FNV hash variable becomes zero and the		unlikely event that the FNV hash variable becomes zero and the
	input is a sequence of zeros, the hash variable will remain at		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		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		will be unaffected by the length of that sequence of zero input
	bytes. Of course, for the common case of fixed length input, this		bytes. Of course, for the common case of fixed length input, this
	would not be significant because the number of non-zero bytes		would not be significant because the number of non-zero bytes
	would vary inversely with the number of zero bytes and for some		would vary inversely with the number of zero bytes and for some
	types of input runs of zeros do not occur. Furthermore, the		types of input runs of zeros do not occur. Furthermore, the
	inclusion of even a little unpredictable input may be sufficient		inclusion of even a little unpredictable input may be sufficient
	to stop an adversary from inducing a zero hash variable.		to stop an adversary from inducing a zero hash variable.
	3. Diffusion - Every output bit of a cryptographic hash should be an		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		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		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		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		on any other input bit. If this is considered a problem, it can be
	easily fixed by folding (see Section 3).		easily fixed by XOR folding (see Section 3).
	Nevertheless, none of the above have proven to be a problem in actual		Nevertheless, none of the above have proven to be a problem in actual
	practice for the many applications of FNV.		practice for the many applications of FNV.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	7. IANA Considerations		7. IANA Considerations
	This document requires no IANA Actions. RFC Editor Note: please		This document requires no IANA Actions. RFC Editor Note: please
	delete this section before publication.		delete this section before publication.
			8. Acknowledgements
			The contributions of the following are gratefully acknowledged:
			Frank Ellermann, Bob Moskowitz, and Stefan Santesson.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	8. References		9. 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		9.1 Normative References
	None.		[US-ASCII] - ANSI, "USA Standard Code for Information Interchange",
			X3.4, American National Standards Institute: New York, 1968.
	8.2 Informative References		9.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
			[IEEE] - http://www.ieee.org
	[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm		[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm
	1 (SHA1)", RFC 3174, September 2001.		1 (SHA1)", RFC 3174, September 2001.
	[RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security		[RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security
	Considerations for the SHA-0 and SHA-1 Message-Digest		Considerations for the SHA-0 and SHA-1 Message-Digest
	Algorithms", RFC 6194, March 2011.		Algorithms", RFC 6194, March 2011.
	[RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash		[RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash
	Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May		Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May
	2011.		2011.
	skipping to change at page 13, line 26 ¶		skipping to change at page 13, line 26 ¶
	SHA-1 is a relatively weak cryptographic hash producing a 160-bit		SHA-1 is a relatively weak cryptographic hash producing a 160-bit
	hash. It that has been partially broken [RFC6194]. It is actually		hash. It that has been partially broken [RFC6194]. It is actually
	designed to accept a bit vector input although almost all computer		designed to accept a bit vector input although almost all computer
	uses apply it to an integer number of bytes. It processes blocks of		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		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		processing a full block. Ignoring SHA-1 initial set up, transfer of
	control, and conditional tests, but counting all logical and		control, and conditional tests, but counting all logical and
	arithmetic operations, including counting indexing as an addition,		arithmetic operations, including counting indexing as an addition,
	SHA-1 requires 1,744 operations per 64 bytes block or 27.25		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		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		times the effort of FNV for large amounts of data. However, FNV is
	is commonly used for small inputs. Using the above method, for inputs		commonly used for small inputs. Using the above method, for inputs of
	of N bytes, where N is less than 55 so SHA-1 will take one block		N bytes, where N is <= 55 so SHA-1 will take one block (SHA-1
	(SHA-1 includes padding and an 8 byte length at the end of the data		includes padding and an 8-byte length at the end of the data in the
	in the last block), the ratio of the effort for SHA-1 to the effort		last block), the ratio of the effort for SHA-1 to the effort for FNV
	for FNV will be 872/N. For example, with an 8 byte input, SHA-1 will		will be 872/N. For example, with an 8 byte input, SHA-1 will take 109
	take 109 times as much effort as FNV.		times as much effort as FNV.
	Stronger cryptographic functions than SHA-1 generally have an even		Stronger cryptographic functions than SHA-1 generally have an even
	high work factor.		high work factor.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	Appendix B: Previous IETF Reference to FNV		Appendix B: Previous IETF Reference to FNV
	FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has		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		since expired. It was later decided that it would be better to use a
	cryptographic hash for that use.		cryptographic hash for that application.
	Below is the Jave code for FNV64 from that TLS draft include by the		Below is the Jave code for FNV64 from that TLS draft include by the
	kind permission of the author:		kind permission of the author:
	/**		/**
	* Java code sample, implementing 64 bit FNV-1a		* Java code sample, implementing 64 bit FNV-1a
	* By Stefan Santesson		* By Stefan Santesson
	*/		*/
	import java.math.BigInteger;		import java.math.BigInteger;
	skipping to change at page 16, line 7 ¶		skipping to change at page 16, line 7 ¶
	Strings including null (zero byte) termination:		Strings including null (zero byte) termination:
	String FNV32 FNV64		String FNV32 FNV64
	"" 0x050c5d1f 0xaf63bd4c8601b7df		"" 0x050c5d1f 0xaf63bd4c8601b7df
	"a" 0x2b24d044 0x089be207b544f1e4		"a" 0x2b24d044 0x089be207b544f1e4
	"foobar" 0x0c1c9eb8 0x34531ca7168b8f38		"foobar" 0x0c1c9eb8 0x34531ca7168b8f38
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
			Appendix Z: Change Summary
			RFC Editor Note: Please delete this appendix on publication.
			From -00 to -01
			1. Add Security Considerations section on why FNV is non-
			cryptographic.
			2. Add Appendix A on a work factor comparison with SHA-1.
			3. Add Appendix B concerning previous IETF draft referenced to FNV.
			4. Minor editorial changes.
			From -01 to -02
			1. Correct FNV_Prime determination criteria and add note as to why s
			< 5 and s > 10 are not considered.
			2. Add acknowledgements list.
			3. Add a couple of references.
			4. Minor editorial changes.
			INTERNET-DRAFT FNV
	Author's Address		Author's Address
	Glenn Fowler		Glenn Fowler
	AT&T Labs Research		AT&T Labs Research
	180 Park Avenue		180 Park Avenue
	Florham Park, NJ 07932 USA		Florham Park, NJ 07932 USA
	Email: gsf@research.att.com		Email: gsf@research.att.com
	URL: http://www.research.att.com/~gsf/		URL: http://www.research.att.com/~gsf/
End of changes. 24 change blocks.
	34 lines changed or deleted		85 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/