< draft-eastlake-fnv-07.txt   draft-eastlake-fnv-08.txt >
Network Working Group Glenn Fowler Network Working Group Glenn Fowler
INTERNET-DRAFT AT&T Labs Research INTERNET-DRAFT Google
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 Google
Donald Eastlake Donald Eastlake
Huawei Technologies Huawei Technologies
Expires: October 5, 2014 April 6, 2014 Expires: April 5, 2015 October 6, 2014
The FNV Non-Cryptographic Hash Algorithm The FNV Non-Cryptographic Hash Algorithm
<draft-eastlake-fnv-07.txt> <draft-eastlake-fnv-08.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 33 skipping to change at page 2, line 33
5.1.3 FNV128 Code..........................................9 5.1.3 FNV128 Code..........................................9
5.1.4 FNV256 C Code........................................9 5.1.4 FNV256 C Code........................................9
5.1.5 FNV512 C Code........................................9 5.1.5 FNV512 C Code........................................9
5.1.6 FNV1024 C Code......................................10 5.1.6 FNV1024 C Code......................................10
5.2 FNV Test Code.........................................10 5.2 FNV Test Code.........................................10
6. Security Considerations................................11 6. Security Considerations................................11
6.1 Why is FNV Non-Cryptographic?.........................11 6.1 Why is FNV Non-Cryptographic?.........................11
7. IANA Considerations....................................12 7. IANA Considerations....................................12
8. Acknowledgements.......................................12 Acknowledgements..........................................12
Normative References......................................13 Normative References......................................13
Informative References....................................13 Informative References....................................13
Appendix A: Work Comparison with SHA-1....................14 Appendix A: Work Comparison with SHA-1....................14
Appendix B: Previous IETF Reference to FNV................15 Appendix B: Previous IETF Reference to FNV................15
Appendix C: A Few Test Vectors............................16 Appendix C: A Few Test Vectors............................16
Appendix Z: Change Summary................................17
Appendix Z: Change Summary................................17
Author's Address..........................................19 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
skipping to change at page 9, line 16 skipping to change at page 9, line 16
5. The Source Code 5. The Source Code
The following sub-sections provide reference C source code and a test The following sub-sections provide reference C source code and a test
driver for FNV-1a. driver for FNV-1a.
Section 5.1 provides the direct FNV-1a function for each of the 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 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 applications of FNV-32 where 32-bit integers are supported and FNV-64
where 64-bit integers are supported, the code is sufficiently simple where 64-bit integers are supported, the code is sufficiently simple
that use of open coding or macros may be more appropriate to that use of open coding or macros may be more appropriate to maximize
maximize performance. performance.
Section 5.2 provides a test driver. Section 5.2 provides a test driver.
5.1 FNV-1a Code 5.1 FNV-1a Code
TBD TBD
5.1.1 FNV32 Code 5.1.1 FNV32 Code
TBD TBD
skipping to change at page 11, line 43 skipping to change at page 11, 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. While more complex, the second least on any other input bit. While more complex, the second through
significant bit of an FNV hash has a similar weakness. If these seventh least significant bits of an FNV hash have a similar
properties are considered a problem, they can be easily fixed by weakness; only the top bit of the bottom byte of output, and
XOR folding (see Section 3). higher order bits, depend on all input bits. 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.
8. Acknowledgements 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
Normative References Normative References
[ASCII] - American National Standards Institute (formerly United [ASCII] - American National Standards Institute (formerly United
skipping to change at page 18, line 23 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 From -06 to -07 to -08
1. Update Author info. 1. Update Author info.
2. Minor edits. 2. Minor edits.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Author's Address Author's Address
Glenn Fowler Glenn Fowler
AT&T Labs Research Google
180 Park Avenue
Florham Park, NJ 07932 USA
Email: gsf@research.att.com Email: glenn.s.fowler@gmail.com
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-ietf-mail@asthe.com Email: fnv-ietf2-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 Google
180 Park Avenue
Florham Park, NJ 07932 USA
Email: kpv@research.att.com Email: phongvo@gmail.com
URL: http://www.research.att.com/info/kpv/
Donald Eastlake Donald Eastlake
Huawei Technologies Huawei Technologies
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
 End of changes. 16 change blocks. 
25 lines changed or deleted 21 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/