< draft-eastlake-fnv-03.txt		draft-eastlake-fnv-04.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 25, 2012 March 26, 2012		Expires: March 23, 2013 September 24, 2012
	The FNV Non-Cryptographic Hash Algorithm		The FNV Non-Cryptographic Hash Algorithm
	<draft-eastlake-fnv-03.txt>		<draft-eastlake-fnv-04.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 1, line 42 ¶		skipping to change at page 1, line 42 ¶
	Task Force (IETF), its areas, and its working groups. Note that		Task Force (IETF), its areas, and its working groups. Note that
	other groups may also distribute working documents as Internet-		other groups may also distribute working documents as Internet-
	Drafts.		Drafts.
	Internet-Drafts are draft documents valid for a maximum of six months		Internet-Drafts are draft documents valid for a maximum of six months
	and may be updated, replaced, or obsoleted by other documents at any		and may be updated, replaced, or obsoleted by other documents at any
	time. It is inappropriate to use Internet-Drafts as reference		time. It is inappropriate to use Internet-Drafts as reference
	material or to cite them other than as "work in progress."		material or to cite them other than as "work in progress."
	The list of current Internet-Drafts can be accessed at		The list of current Internet-Drafts can be accessed at
	http://www.ietf.org/1id-abstracts.html		http://www.ietf.org/1id-abstracts.html. The list of Internet-Draft
			Shadow Directories can be accessed at
	The list of Internet-Draft Shadow Directories can be accessed at		http://www.ietf.org/shadow.html.
	http://www.ietf.org/shadow.html
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	Table of Contents		Table of Contents
	1. Introduction............................................3		1. Introduction............................................3
	2. FNV Basics..............................................4		2. FNV Basics..............................................4
	2.1 FNV Primes.............................................4		2.1 FNV Primes.............................................4
	2.2 FNV offset_basis.......................................5		2.2 FNV offset_basis.......................................5
	2.3 FNV Endianism..........................................5		2.3 FNV Endianism..........................................5
	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 Headers..........................................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. Acknowledgements.......................................11
	9. References.............................................12		9. References.............................................12
	skipping to change at page 2, line 37 ¶		skipping to change at page 2, line 37 ¶
	7. IANA Considerations....................................11		7. IANA Considerations....................................11
	8. Acknowledgements.......................................11		8. Acknowledgements.......................................11
	9. References.............................................12		9. References.............................................12
	9.1 Normative References..................................12		9.1 Normative References..................................12
	9.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		Appendix Z: Change Summary................................16
	From -00 to -01...........................................16
	From -01 to -02...........................................16
	From -02 to -03...........................................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
	skipping to change at page 5, line 27 ¶		skipping to change at page 5, line 27 ¶
	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
	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 32 octets representing		by applying the n-bit FNV-0 algorithm to the 32 octets representing
	the following character string in [RFC20]:		the following character string in [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 9, line 12 ¶		skipping to change at page 9, line 12 ¶
	0000000000000000 0000000000000000 0000000000000000 000000000004C6D7		0000000000000000 0000000000000000 0000000000000000 000000000004C6D7
	EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3		EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	5. The Source Code		5. The Source Code
	The following sub-sections are intended, in later versions, to		The following sub-sections are intended, in later versions, to
	include reference C source code and a test driver for FNV-1a.		include reference C source code and a test driver for FNV-1a.
	5.1 FNV C Header		5.1 FNV C Headers
	TBD		TBD
	5.2 FNV C Code		5.2 FNV C Code
	TBD		TBD
	5.3 FNV Test Code		5.3 FNV Test Code
	TBD		TBD
	skipping to change at page 10, line 43 ¶		skipping to change at page 10, line 43 ¶
	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. While more complex, the second least
	easily fixed by XOR folding (see Section 3).		significant bit of an FNV hash has a similar weakness. If these
			properties are considered a problem, they can be 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.
	skipping to change at page 12, line 13 ¶		skipping to change at page 12, line 13 ¶
	Frank Ellermann, Bob Moskowitz, and Stefan Santesson.		Frank Ellermann, Bob Moskowitz, and Stefan Santesson.
	INTERNET-DRAFT FNV		INTERNET-DRAFT FNV
	9. References		9. References
	Below are the normative and informative references for this document.		Below are the normative and informative references for this document.
	9.1 Normative References		9.1 Normative References
	[RFC20] - Cerf, V., "ASCII format for network interchange", RFC 20,		[ASCII] - American National Standards Institute (formerly United
	October 1969.		States of America Standards Institute), "USA Code for
			Information Interchange", ANSI X3.4-1968, 1968. ANSI X3.4-1968
			has been replaced by newer versions with slight modifications,
			but the 1968 version remains definitive for the Internet.
	9.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		[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.
	skipping to change at page 16, line 40 ¶		skipping to change at page 16, line 40 ¶
	4. Minor editorial changes.		4. Minor editorial changes.
	From -02 to -03		From -02 to -03
	1. Replace direct reference to US-ASCII standard with reference to		1. Replace direct reference to US-ASCII standard with reference to
	RFC 20.		RFC 20.
	2. Update dates and verion number.		2. Update dates and verion number.
	3. Minor editing change.		3. Minor editing changes.
			From -03 to -04
			1. Change reference to RFC 20 back to a reference to the ANSI 1968
			ASCII standard.
			2. Minor addition to Section 6, point 3.
			INTERNET-DRAFT FNV
			3. Update dates and version number.
			4. Minor editing changes.
	INTERNET-DRAFT FNV		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
End of changes. 11 change blocks.
	18 lines changed or deleted		31 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/