< draft-eastlake-fnv-08.txt   draft-eastlake-fnv-09.txt >
Network Working Group Glenn Fowler Network Working Group Glenn Fowler
INTERNET-DRAFT Google 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
Google Google
Donald Eastlake Donald Eastlake
Huawei Technologies Huawei Technologies
Expires: April 5, 2015 October 6, 2014 Expires: October 3, 2015 April 4, 2015
The FNV Non-Cryptographic Hash Algorithm The FNV Non-Cryptographic Hash Algorithm
<draft-eastlake-fnv-08.txt> <draft-eastlake-fnv-09.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 16 skipping to change at page 2, line 16
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........................7
4. FNV Constants...........................................7 4. FNV Constants...........................................8
5. The Source Code.........................................9
5.1 FNV-1a Code............................................9
5.1.1 FNV32 Code...........................................9
5.1.2 FNV64 C Code.........................................9
5.1.3 FNV128 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................................11 5. The Source Code........................................10
6.1 Why is FNV Non-Cryptographic?.........................11 5.1 FNV-1a C Code.........................................10
5.1.1 FNV32 Code..........................................10
5.1.2 FNV64 C Code........................................10
5.1.3 FNV128 C Code.......................................10
5.1.4 FNV256 C Code.......................................10
5.1.5 FNV512 C Code.......................................11
5.1.6 FNV1024 C Code......................................11
5.2 FNV Test Code.........................................11
7. IANA Considerations....................................12 6. Security Considerations................................12
Acknowledgements..........................................12 6.1 Why is FNV Non-Cryptographic?.........................12
7. IANA Considerations....................................13
Normative References......................................13 Normative References......................................13
Informative References....................................13 Informative References....................................13
Acknowledgements..........................................14
Appendix A: Work Comparison with SHA-1....................14 Appendix A: Work Comparison with SHA-1....................15
Appendix B: Previous IETF Reference to FNV................15 Appendix B: Previous IETF Reference to FNV................16
Appendix C: A Few Test Vectors............................16 Appendix C: A Few Test Vectors............................17
Appendix Z: Change Summary................................17 Appendix Z: Change Summary................................18
Author's Address..........................................19 From -00 to -01...........................................18
From -01 to -02...........................................18
From -02 to -03...........................................18
From -03 to -04...........................................18
From -04 to -05...........................................19
From -05 to -06...........................................19
From -06 to -07 to -08....................................19
From -08 to -09...........................................19
Author's Address..........................................20
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 [ASCII]: the following character string in [RFC20]:
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> /\\../\\"
That string was used because the person testing FNV with non-zero
offset_basis values was looking at an email message from Landon and
was copying his standard email signature line; however, they couldn't
see very well and copied it incorrectly. In fact, he uses
"chongo (Landon Curt Noll) /\oo/\"
but, since it doesn't matter, no effort has been made to correct
this. In the general case, almost any offset_basis will serve so
long as it is non-zero.
2.3 FNV Endianism 2.3 FNV Endianism
For persistent storage or interoperability between different hardware For persistent storage or interoperability between different hardware
platforms, an FNV hash shall be represented in the little endian platforms, an FNV hash shall be represented in the little endian
format. That is, the FNV hash will be stored in an array hash[N] with format. That is, the FNV hash will be stored in an array hash[N] with
INTERNET-DRAFT FNV
N bytes such that its integer value can be retrieved as follows: N bytes such that its integer value can be retrieved as follows:
unsigned char hash[N]; unsigned char hash[N];
for ( i = N-1, value = 0; i >= 0; --i ) for ( i = N-1, value = 0; i >= 0; --i )
value = value << 8 + hash[i]; value = value << 8 + hash[i];
Of course, when FNV hashes are used in a single process or a group of Of course, when FNV hashes are used in a single process or a group of
processes sharing memory on processors with compatible endian-ness, processes sharing memory on processors with compatible endian-ness,
the natural endianness of those processors can be used regardless of the natural endianness of those processors can be used regardless of
its type, little, big, or some other exotic form. its type, little, big, or some other exotic form.
skipping to change at page 9, line 19 skipping to change at page 10, line 19
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 maximize that use of open coding or macros may be more appropriate to maximize
performance. performance.
Alternative source code, including such things as 32 and 64 bit FNV-1
and FNV-1a in x86 aseembler, is currently available at [FNV].
Section 5.2 provides a test driver. Section 5.2 provides a test driver.
5.1 FNV-1a Code 5.1 FNV-1a C Code
TBD TBD
5.1.1 FNV32 Code 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 Code 5.1.3 FNV128 C Code
TBD TBD
5.1.4 FNV256 C Code 5.1.4 FNV256 C Code
TBD TBD
INTERNET-DRAFT FNV
5.1.5 FNV512 C Code 5.1.5 FNV512 C Code
TBD TBD
INTERNET-DRAFT FNV
5.1.6 FNV1024 C Code 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
skipping to change at page 11, line 21 skipping to change at page 12, line 21
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? 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. Sticky State - A cryptographic hash should not have a state in
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 very 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 that 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 usually not be significant because the number of non-zero
would vary inversely with the number of zero bytes and for some bytes would vary inversely with the number of zero bytes and for
types of input runs of zeros do not occur. Furthermore, the some 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 2. 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 through on any other input bit. While more complex, the second through
seventh least significant bits of an FNV hash have a similar seventh least significant bits of an FNV hash have a similar
weakness; only the top bit of the bottom byte of output, and weakness; only the top bit of the bottom byte of output, and
higher order bits, depend on all input bits. If these properties higher order bits, depend on all input bits. If these properties
are considered a problem, they can be easily fixed by XOR folding are considered a problem, they can be easily fixed by XOR folding
(see Section 3). (see Section 3).
3. Work Factor - Depending on intended use, it is frequently
desireable that a hash function should be computationally
expensive for general purpose and graphics processors since these
may be profusely available through elastic cloud services or
botnets. This is to slow down testing of possible inputs if the
output is known. But FNV is designed to be very inexpensive on a
general-purpose processor. (See Appendix A.)
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.
delete this section before publication.
Acknowledgements
The contributions of the following are gratefully acknowledged:
Frank Ellermann, Bob Moskowitz, and Stefan Santesson.
INTERNET-DRAFT FNV
Normative References Normative References
[ASCII] - American National Standards Institute (formerly United [RFC20] - Cerf, V., "ASCII format for network interchange", STD 80,
States of America Standards Institute), "USA Code for RFC 20, October 1969, <http://www.rfc-editor.org/info/rfc20>.
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.
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
skipping to change at page 14, line 7 skipping to change at page 14, line 7
[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.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Acknowledgements
The contributions of the following are gratefully acknowledged:
Frank Ellermann, Tony Finch, Bob Moskowitz, and Stefan Santesson.
INTERNET-DRAFT FNV
Appendix A: Work Comparison with SHA-1 Appendix A: Work Comparison with SHA-1
This section provides a simplistic rough comparison of the level of This section provides a simplistic rough comparison of the level of
effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. effort required per input byte to compute FNV-1a and SHA-1 [RFC3174].
Ignoring transfer of control and conditional tests and equating all Ignoring transfer of control and conditional tests and equating all
logical and arithmetic operations, FNV requires 2 operations per logical and arithmetic operations, FNV requires 2 operations per
byte, an XOR and a multiply. byte, an XOR and a multiply.
SHA-1 is a relatively weak cryptographic hash producing a 160-bit SHA-1 is a relatively weak cryptographic hash producing a 160-bit
skipping to change at page 19, line 5 skipping to change at page 19, line 29
1. Add code subsections. 1. Add code subsections.
2. Update dates and version number. 2. Update dates and version number.
From -06 to -07 to -08 From -06 to -07 to -08
1. Update Author info. 1. Update Author info.
2. Minor edits. 2. Minor edits.
From -08 to -09
1. Change reference for ASCII to [RFC20].
2. Add more details on history of the string used to compute
offset_basis.
3. Re-write "Work Factor" part of Section 6 to be more precise.
4. Minor editorial changes.
INTERNET-DRAFT FNV INTERNET-DRAFT FNV
Author's Address Author's Address
Glenn Fowler Glenn Fowler
Google Google
Email: glenn.s.fowler@gmail.com Email: glenn.s.fowler@gmail.com
Landon Curt Noll Landon Curt Noll
skipping to change at page 20, line 9 skipping to change at page 21, 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) 2014 IETF Trust and the persons identified as the Copyright (c) 2015 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. 26 change blocks. 
54 lines changed or deleted 89 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/