Diff: draft-eastlake-fnv-06.txt - draft-eastlake-fnv-07.txt

	< draft-eastlake-fnv-06.txt	draft-eastlake-fnv-07.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 31, 2013 October 1, 2013	Expires: October 5, 2014 April 6, 2014

	The FNV Non-Cryptographic Hash Algorithm	The FNV Non-Cryptographic Hash Algorithm

	<draft-eastlake-fnv-06.txt>	<draft-eastlake-fnv-07.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 20 ¶	skipping to change at page 2, line 20 ¶

	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 Code.............................................9	5.1 FNV-1a Code............................................9
	5.1.1 FNV32 C Code.........................................9	5.1.1 FNV32 Code...........................................9
	5.1.2 FNV64 C Code.........................................9	5.1.2 FNV64 C Code.........................................9

	5.1.3 FNV128 C Code........................................9	5.1.3 FNV128 Code..........................................9
	5.2 FNV Test Code..........................................9	5.1.4 FNV256 C Code........................................9
		5.1.5 FNV512 C Code........................................9
		5.1.6 FNV1024 C Code......................................10
		5.2 FNV Test Code.........................................10


	6. Security Considerations................................10	6. Security Considerations................................11
	6.1 Why is FNV Non-Cryptographic?.........................10	6.1 Why is FNV Non-Cryptographic?.........................11


	7. IANA Considerations....................................11	7. IANA Considerations....................................12
	8. Acknowledgements.......................................11	8. Acknowledgements.......................................12


	9. References.............................................12	Normative References......................................13
	9.1 Normative References..................................12	Informative References....................................13
	9.2 Informative References................................12


	Appendix A: Work Comparison with SHA-1....................13	Appendix A: Work Comparison with SHA-1....................14
	Appendix B: Previous IETF Reference to FNV................14	Appendix B: Previous IETF Reference to FNV................15
	Appendix C: A Few Test Vectors............................15	Appendix C: A Few Test Vectors............................16
	Appendix Z: Change Summary................................16	Appendix Z: Change Summary................................17


	Author's Address..........................................18	Author's Address..........................................19

	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 9, line 9 ¶	skipping to change at page 9, line 9 ¶
	868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 =	868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 =
	0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1	0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1
	6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000	6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000
	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 provide reference C source code and a test
	include reference C source code and a test driver for FNV-1a.	driver for FNV-1a.


	5.1 FNV C Code	Section 5.1 provides the direct FNV-1a function for each of the
		lengths for which it is specified in this document. Note that for
		applications of FNV-32 where 32-bit integers are supported and FNV-64
		where 64-bit integers are supported, the code is sufficiently simple
		that use of open coding or macros may be more appropriate to
		maximize performance.


	5.1.1 FNV32 C Code	Section 5.2 provides a test driver.

		5.1 FNV-1a Code

		TBD

		5.1.1 FNV32 Code

	TBD	TBD

	5.1.2 FNV64 C Code	5.1.2 FNV64 C Code

	TBD	TBD


	5.1.3 FNV128 C Code	5.1.3 FNV128 Code

		TBD

		5.1.4 FNV256 C Code

		TBD

		5.1.5 FNV512 C Code

		TBD

		INTERNET-DRAFT FNV

		5.1.6 FNV1024 C Code

	TBD	TBD

	5.2 FNV Test Code	5.2 FNV Test Code

	TBD	TBD

	INTERNET-DRAFT FNV	INTERNET-DRAFT FNV

	6. Security Considerations	6. Security Considerations

	skipping to change at page 12, line 7 ¶	skipping to change at page 13, line 7 ¶
	delete this section before publication.	delete this section before publication.

	8. Acknowledgements	8. Acknowledgements

	The contributions of the following are gratefully acknowledged:	The contributions of the following are gratefully acknowledged:

	Frank Ellermann, Bob Moskowitz, and Stefan Santesson.	Frank Ellermann, Bob Moskowitz, and Stefan Santesson.

	INTERNET-DRAFT FNV	INTERNET-DRAFT FNV


	9. References	Normative References

	Below are the normative and informative references for this document.

	9.1 Normative References

	[ASCII] - American National Standards Institute (formerly United	[ASCII] - American National Standards Institute (formerly United
	States of America Standards Institute), "USA Code for	States of America Standards Institute), "USA Code for
	Information Interchange", ANSI X3.4-1968, 1968. ANSI X3.4-1968	Information Interchange", ANSI X3.4-1968, 1968. ANSI X3.4-1968
	has been replaced by newer versions with slight modifications,	has been replaced by newer versions with slight modifications,
	but the 1968 version remains definitive for the Internet.	but the 1968 version remains definitive for the Internet.


	9.2 Informative References	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

	[IPv6flow] - https://researchspace.auckland.ac.nz/bitstream/handle/	[IPv6flow] - https://researchspace.auckland.ac.nz/bitstream/handle/
	2292/13240/flowhashRep.pdf	2292/13240/flowhashRep.pdf

	[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm	[RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm

	skipping to change at page 14, line 16 ¶	skipping to change at page 15, line 16 ¶

	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 application.	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:


		<CODE BEGINS>
	/**	/**
	* 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;

	public class FNV {	public class FNV {

	static public BigInteger getFNV1aToByte(byte[] inp) {	static public BigInteger getFNV1aToByte(byte[] inp) {

	skipping to change at page 15, line 4 ¶	skipping to change at page 15, line 43 ¶
	BigInteger digest = fnvOffsetBasis;	BigInteger digest = fnvOffsetBasis;

	for (byte b : inp) {	for (byte b : inp) {
	digest = digest.xor(BigInteger.valueOf((int) b & 255));	digest = digest.xor(BigInteger.valueOf((int) b & 255));
	digest = digest.multiply(fnvPrime).mod(m);	digest = digest.multiply(fnvPrime).mod(m);
	}	}
	return digest;	return digest;

	}	}
	}	}

		<CODE ENDS>

	INTERNET-DRAFT FNV	INTERNET-DRAFT FNV

	Appendix C: A Few Test Vectors	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:


	skipping to change at page 18, line 5 ¶	skipping to change at page 18, line 23 ¶
	1. Add Twitter as a use example and IPv6 flow hash study reference.	1. Add Twitter as a use example and IPv6 flow hash study reference.

	2. Update dates and version number.	2. Update dates and version number.

	From -05 to -06	From -05 to -06

	1. Add code subsections.	1. Add code subsections.

	2. Update dates and version number.	2. Update dates and version number.


		From -06 to -07

		1. Update Author info.

		2. Minor edits.

	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

	Email: gsf@research.att.com	Email: gsf@research.att.com
	URL: http://www.research.att.com/~gsf/	URL: http://www.research.att.com/~gsf/

	Landon Curt Noll	Landon Curt Noll
	Cisco Systems	Cisco Systems
	170 West Tasman Drive	170 West Tasman Drive
	San Jose, CA 95134 USA	San Jose, CA 95134 USA

	Telephone: +1-408-424-1102	Telephone: +1-408-424-1102

	Email: fnv-rfc-mail@asthe.com	Email: fnv-ietf-mail@asthe.com
	URL: http://www.isthe.com/chongo/index.html	URL: http://www.isthe.com/chongo/index.html

	Kiem-Phong Vo	Kiem-Phong Vo
	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: kpv@research.att.com	Email: kpv@research.att.com
	URL: http://www.research.att.com/info/kpv/	URL: http://www.research.att.com/info/kpv/


	skipping to change at page 19, line 9 ¶	skipping to change at page 20, line 9 ¶
	155 Beaver Street	155 Beaver Street
	Milford, MA 01757 USA	Milford, MA 01757 USA

	Telephone: +1-508-333-2270	Telephone: +1-508-333-2270
	EMail: d3e3e3@gmail.com	EMail: d3e3e3@gmail.com

	INTERNET-DRAFT FNV	INTERNET-DRAFT FNV

	Copyright, Disclaimer, and Additional IPR Provisions	Copyright, Disclaimer, and Additional IPR Provisions


	Copyright (c) 2013 IETF Trust and the persons identified as the	Copyright (c) 2014 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

End of changes. 20 change blocks.
	31 lines changed or deleted	62 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/