idnits 2.17.1 draft-eastlake-fnv-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 199 has weird spacing: '...ed char hash...' -- The document date (September 24, 2011) is 4597 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'N' is mentioned on line 199, but not defined Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Glenn Fowler 2 INTERNET-DRAFT AT&T Labs Research 3 Intended Status: Informational Landon Curt Noll 4 Cisco Systems 5 Kiem-Phong Vo 6 AT&T Labs Research 7 Donald Eastlake 8 Huawei Technologies 9 Expires: March 23, 2011 September 24, 2011 11 The FNV Non-Cryptographic Hash Algorithm 12 14 Abstract 16 FNV (Fowler/Noll/Vo) is a fast, non-cryptographic hash algorithm with 17 good dispersion. The purpose of this document is to make information 18 on FNV and open source code performing FNV conveniently available to 19 the Internet community. 21 Status of This Memo 23 This Internet-Draft is submitted to IETF in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Distribution of this document is unlimited. Comments should be sent 27 to the authors. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF), its areas, and its working groups. Note that 31 other groups may also distribute working documents as Internet- 32 Drafts. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 The list of current Internet-Drafts can be accessed at 40 http://www.ietf.org/1id-abstracts.html 42 The list of Internet-Draft Shadow Directories can be accessed at 43 http://www.ietf.org/shadow.html 45 Table of Contents 47 1. Introduction............................................3 49 2. FNV Basics..............................................4 50 2.1 FNV Primes.............................................4 51 2.2 FNV offset_basis.......................................5 52 2.3 FNV Endianism..........................................5 54 3. Other Hash Sizes and XOR Folding........................6 55 4. FNV Constants...........................................7 57 5. The Source Code.........................................9 58 5.1 FNV C Header...........................................9 59 5.2 FNV C Code.............................................9 60 5.3 FNV Test Code..........................................9 62 6. Security Considerations................................10 63 6.1 Why is FNV Non-Cryptographic?.........................10 64 7. IANA Considerations....................................11 65 8. Acknowledgements.......................................11 66 9. References.............................................12 67 9.1 Normative References..................................12 68 9.2 Informative References................................12 70 Appendix A: Work Comparison with SHA-1....................13 71 Appendix B: Previous IETF Reference to FNV................14 72 Appendix C: A Few Test Vectors............................15 73 Appendix Z: Change Summary................................16 74 From -00 to -01...........................................16 75 From -01 to -02...........................................16 77 1. Introduction 79 The FNV hash algorithm is based on an idea sent as reviewer comments 80 to the [IEEE] POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 81 1991. In a subsequent ballot round Landon Curt Noll suggested an 82 improvement on their algorithm. Some people tried this hash and found 83 that it worked rather well. In an EMail message to Landon, they named 84 it the "Fowler/Noll/Vo" or FNV hash. [FNV] 86 FNV hashes are designed to be fast while maintaining a low collision 87 rate. Their speed allows one to quickly hash lots of data while 88 maintaining a reasonably low collision rate. The high dispersion of 89 the FNV hashes makes them well suited for hashing nearly identical 90 strings such as URLs, hostnames, filenames, text, IP addresses, etc. 91 However, they are generally not suitable for cryptographic use. (See 92 Section 6.1.) 94 The FNV hash is widely used, for example in DNS servers, database 95 indexing hashes, major web search / indexing engines, netnews history 96 file Message-ID lookup functions, anti-spam filters, a spellchecker 97 programmed in Ada 95, flatassembler's open source x86 assembler - 98 user-defined symbol hashtree, non-cryptographic file fingerprints, 99 computing Unique IDs in DASM (DTN Applications for Symbian Mobile- 100 phones), Microsoft's hash_map implementation for VC++ 2005, the 101 realpath cache in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c), and 102 many other uses. 104 FNV hash algorithms and source code have been released into the 105 public domain. The authors of the FNV algorithm took deliberate steps 106 to disclose the algorithm in a public forum soon after it was 107 invented. More than a year passed after this public disclosure and 108 the authors deliberately took no steps to patent the FNV algorithm. 109 Therefore, it is safe to say that the FNV authors have no patent 110 claims on the FNV algorithm as published. 112 If you use an FNV function in an application, you are kindly 113 requested to send an EMail about it to: fnv-mail@asthe.com 115 2. FNV Basics 117 This document focuses on the FNV-1a function whose pseudo-code is as 118 follows: 120 hash = offset_basis 121 for each octet_of_data to be hashed 122 hash = hash xor octet_of_data 123 hash = hash * FNV_Prime 124 return hash 126 In the pseudo-code above, hash is a power-of-two number of bits (32, 127 64, ... 1024) and offset_basis and FNV_Prime depend on the size of 128 hash. 130 The FNV-1 algorithm is the same, including the values of offset_basis 131 and FNV_Prime, except that the order of the two lines with the "xor" 132 and multiply operations are reversed. Operational experience 133 indicates better hash dispersion for small amounts of data with 134 FNV-1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. 135 FNV-1a is suggested for general use. 137 2.1 FNV Primes 139 The theory behind FNV_Prime's is beyond the scope of this document 140 but the basic property to look for is how an FNV_Prime would impact 141 dispersion. Now, consider any n-bit FNV hash where n is >= 32 and 142 also a power of 2. For each such an n-bit FNV hash, an FNV_Prime p is 143 defined as: 145 When s is an integer and 4 < s < 11, then FNV_Prime is the 146 smallest prime p of the form: 148 256**int((5 + 2^s)/12) + 2**8 + b 150 where b is an integer such that: 152 0 < b < 2**8 153 The number of one-bits in b is 4 or 5 155 and where p mod (2**40 - 2**24 - 1) > (2**24 + 2**8 + 2**7). 157 Experimentally, FNV_Primes matching the above constraints tend to 158 have better dispersion properties. They improve the polynomial 159 feedback characteristic when an FNV_Prime multiplies an intermediate 160 hash value. As such, the hash values produced are more scattered 161 throughout the n-bit hash space. 163 The case where s < 5 is not considered because the resulting hash 164 quality is too low. Such small hashes can, if desired, be derived 165 from a 32 bit FNV hash by XOR folding (see Section 3). The case where 166 s > 10 is not considered because of the doubtful utility of such 167 large FNV hashes and because the criteria for such large FNV_Primes 168 is more complex, due to the sparsity of such large primes, and would 169 needlessly clutter the criteria given above. 171 Per the above constraints, an FNV_Prime should have only 6 or 7 one- 172 bits in it. Therefore, some compilers may seek to improve the 173 performance of a multiplication with an FNV_Prime by replacing the 174 multiplication with shifts and adds. However, note that the 175 performance of this substitution is highly hardware-dependent and 176 should be done with care. FNV_Primes were selected primarily for the 177 quality of resulting hash function, not for compiler optimization. 179 2.2 FNV offset_basis 181 The offset_basis values for the n-bit FNV-1a algorithms are computed 182 by applying the n-bit FNV-0 algorithm to the 32 octets representing 183 the following character string in [US-ASCII]: 185 chongo /\../\ 187 The \'s in the above string are not C-style escape characters. In C- 188 string notation, these 32 octets are: 190 "chongo /\\../\\" 192 2.3 FNV Endianism 194 For persistent storage or interoperability between different hardware 195 platforms, an FNV hash shall be represented in the little endian 196 format. That is, the FNV hash will be stored in an array hash[N] with 197 N bytes such that its integer value can be retrieved as follows: 199 unsigned char hash[N]; 200 for ( i = N-1, value = 0; i >= 0; --i ) 201 value = value << 8 + hash[i]; 203 Of course, when FNV hashes are used in a single process or a group of 204 processes sharing memory on processors with compatible endian-ness, 205 the natural endianness of those processors can be used regardless of 206 its type, little, big, or some other exotic form. 208 3. Other Hash Sizes and XOR Folding 210 Many hash uses require a hash that is not one of the FNV sizes for 211 which constants are provided in Section 4. If a larger hash size is 212 needed, please contact the authors of this document. 214 Most hash applications make use of a hash that is a fixed size binary 215 field. Assume that k bits of hash are desired and k is less than 1024 216 but not one of the sizes for which constants are provided in Section 217 4. The recommended technique is to take the smallest FNV hash of size 218 S, where S is larger than k, and calculate the desired hash using xor 219 folding as shown below. The final bit masking operation is logically 220 unnecessarily if the size of hash is exactly the number of desired 221 bits. 223 temp = FNV_S ( data-to-be-hashed ) 224 hash = ( temp xor temp>>k ) bitwise-and ( 2**k - 1 ) 226 Hash functions are a trade-off between speed and strength. For 227 example, a somewhat stronger hash may be obtained for exact FNV sizes 228 by calculating an FNV twice as long as the desired output ( S = 2*k ) 229 and performing such data folding using a k equal to the size of the 230 desired output. However, if a much stronger hash, for example one 231 suitable for cryptographic applications, is wanted, algorithms 232 designed for that purpose, such as those in [RFC6234], should be 233 used. 235 If it is desired to obtain a hash result that is a value between 0 236 and max, where max is a not a power of two, simply choose an FNV hash 237 size S such that 2**S > max. Then calculate the following: 239 FNV_S mod ( max+1 ) 241 The resulting remainder will be in the range desired but will suffer 242 from a bias against large values with the bias being larger if 2**S 243 is only a little bigger than max. If this bias is acceptable, no 244 further processing is needed. If this bias is unacceptable, it can be 245 avoided by retrying for certain high values of hash, as follows, 246 before applying the mod operation above: 248 X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 ) 249 while ( hash >= X ) 250 hash = ( hash * FNV_Prime ) + offset_basis 252 4. FNV Constants 254 The FNV Primes are as follows: 256 32 bit FNV_Prime = 2**24 + 2**8 + 0x93 = 16,777,619 257 = 0x01000193 259 64 bit FNV_Prime = 2**40 + 2**8 + 0xB3 = 1,099,511,628,211 260 = 0x00000100 000001B3 262 128 bit FNV_Prime = 2**88 + 2**8 + 0x3B = 263 309,485,009,821,345,068,724,781,371 264 = 0x00000000 01000000 00000000 0000013B 266 256 bit FNV_Prime = 2**168 + 2**8 + 0x63 = 267 374,144,419,156,711,147,060,143,317,175,368,453,031,918,731,002,211 = 268 0x0000000000000000 0000010000000000 0000000000000000 0000000000000163 270 512 bit FNV_Prime = 2**344 + 2**8 + 0x57 = 35, 271 835,915,874,844,867,368,919,076,489,095,108,449,946,327,955,754,392, 272 558,399,825,615,420,669,938,882,575,126,094,039,892,345,713,852,759 = 273 0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 274 0000000000000000 0000000000000000 0000000000000000 0000000000000157 276 1024 bit FNV_Prime = 2**680 + 2**8 + 0x8D = 5, 277 016,456,510,113,118,655,434,598,811,035,278,955,030,765,345,404,790, 278 744,303,017,523,831,112,055,108,147,451,509,157,692,220,295,382,716, 279 162,651,878,526,895,249,385,292,291,816,524,375,083,746,691,371,804, 280 094,271,873,160,484,737,966,720,260,389,217,684,476,157,468,082,573 = 281 0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 282 0000000000000000 0000010000000000 0000000000000000 0000000000000000 283 0000000000000000 0000000000000000 0000000000000000 0000000000000000 284 0000000000000000 0000000000000000 0000000000000000 000000000000018D 286 The FNV offset_basis values are as follows: 288 32 bit offset_basis = 2,166,136,261 = 0x811C9DC5 290 64 bit offset_basis = 14695981039346656037 = 0xCBF29CE4 84222325 292 128 bit offset_basis = 144066263297769815596495629667062367629 = 293 0x6C62272E 07BB0142 62B82175 6295C58D 295 256 bit offset_basis = 100,029,257,958,052,580,907,070,968, 296 620,625,704,837,092,796,014,241,193,945,225,284,501,741,471,925,557 = 297 0xDD268DBCAAC55036 2D98C384C4E576CC C8B1536847B6BBB3 1023B4C8CAEE0535 298 512 bit offset_basis = 9, 299 659,303,129,496,669,498,009,435,400,716,310,466,090,418,745,672,637, 300 896,108,374,329,434,462,657,994,582,932,197,716,438,449,813,051,892, 301 206,539,805,784,495,328,239,340,083,876,191,928,701,583,869,517,785 = 302 0xB86DB0B1171F4416 DCA1E50F309990AC AC87D059C9000000 0000000000000D21 303 E948F68A34C192F6 2EA79BC942DBE7CE 182036415F56E34B AC982AAC4AFE9FD9 305 1024 bit offset_basis = 14,197,795,064,947,621,068,722,070,641,403, 306 218,320,880,622,795,441,933,960,878,474,914,617,582,723,252,296,732, 307 303,717,722,150,864,096,521,202,355,549,365,628,174,669,108,571,814, 308 760,471,015,076,148,029,755,969,804,077,320,157,692,458,563,003,215, 309 304,957,150,157,403,644,460,363,550,505,412,711,285,966,361,610,267, 310 868,082,893,823,963,790,439,336,411,086,884,584,107,735,010,676,915 = 311 0x0000000000000000 005F7A76758ECC4D 32E56D5A591028B7 4B29FC4223FDADA1 312 6C3BF34EDA3674DA 9A21D90000000000 0000000000000000 0000000000000000 313 0000000000000000 0000000000000000 0000000000000000 000000000004C6D7 314 EB6E73802734510A 555F256CC005AE55 6BDE8CC9C6A93B21 AFF4B16C71EE90B3 316 5. The Source Code 318 The following sub-sections are intended, in later versions, to 319 include reference C source code and a test driver for FNV-1a. 321 5.1 FNV C Header 323 TBD 325 5.2 FNV C Code 327 TBD 329 5.3 FNV Test Code 331 TBD 333 6. Security Considerations 335 This document is intended to provide convenient open source access by 336 the Internet community to the FNV non-cryptographic hash. No 337 assertion of suitability for cryptographic applications is made for 338 the FNV hash algorithms. 340 6.1 Why is FNV Non-Cryptographic? 342 A full discussion of cryptographic hash requirements and strength is 343 beyond the scope of this document. However, here are three 344 characteristics of FNV that would generally be considered to make it 345 non-cryptographic: 347 1. Work Factor - To make brute force inversion hard, a cryptographic 348 hash should be computationally expensive, especially for a general 349 purpose processor. But FNV is designed to be very inexpensive on a 350 general-purpose processor. (See Appendix A.) 352 2. Sticky State - A cryptographic hash should not have a state in 353 which it can stick for a plausible input pattern. But, in the very 354 unlikely event that the FNV hash variable becomes zero and the 355 input is a sequence of zeros, the hash variable will remain at 356 zero until there is a non-zero input byte and the final hash value 357 will be unaffected by the length of that sequence of zero input 358 bytes. Of course, for the common case of fixed length input, this 359 would not be significant because the number of non-zero bytes 360 would vary inversely with the number of zero bytes and for some 361 types of input runs of zeros do not occur. Furthermore, the 362 inclusion of even a little unpredictable input may be sufficient 363 to stop an adversary from inducing a zero hash variable. 365 3. Diffusion - Every output bit of a cryptographic hash should be an 366 equally complex function of every input bit. But it is easy to see 367 that the least significant bit of a direct FNV hash is the XOR of 368 the least significant bits of every input byte and does not depend 369 on any other input bit. If this is considered a problem, it can be 370 easily fixed by XOR folding (see Section 3). 372 Nevertheless, none of the above have proven to be a problem in actual 373 practice for the many applications of FNV. 375 7. IANA Considerations 377 This document requires no IANA Actions. RFC Editor Note: please 378 delete this section before publication. 380 8. Acknowledgements 382 The contributions of the following are gratefully acknowledged: 384 Frank Ellermann, Bob Moskowitz, and Stefan Santesson. 386 9. References 388 Below are the normative and informative references for this document. 390 9.1 Normative References 392 [US-ASCII] - ANSI, "USA Standard Code for Information Interchange", 393 X3.4, American National Standards Institute: New York, 1968. 395 9.2 Informative References 397 [FNV] - FNV web site: 398 http://www.isthe.com/chongo/tech/comp/fnv/index.html 400 [IEEE] - http://www.ieee.org 402 [RFC3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 403 1 (SHA1)", RFC 3174, September 2001. 405 [RFC6194] - Polk, T., Chen, L., Turner, S., and P. Hoffman, "Security 406 Considerations for the SHA-0 and SHA-1 Message-Digest 407 Algorithms", RFC 6194, March 2011. 409 [RFC6234] - Eastlake 3rd, D. and T. Hansen, "US Secure Hash 410 Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 411 2011. 413 Appendix A: Work Comparison with SHA-1 415 This section provides a simplistic rough comparison of the level of 416 effort required per input byte to compute FNV-1a and SHA-1 [RFC3174]. 418 Ignoring transfer of control and conditional tests and equating all 419 logical and arithmetic operations, FNV requires 2 operations per 420 byte, an XOR and a multiply. 422 SHA-1 is a relatively weak cryptographic hash producing a 160-bit 423 hash. It that has been partially broken [RFC6194]. It is actually 424 designed to accept a bit vector input although almost all computer 425 uses apply it to an integer number of bytes. It processes blocks of 426 512 bits (64 bytes) and we estimate the effort involved in SHA-1 427 processing a full block. Ignoring SHA-1 initial set up, transfer of 428 control, and conditional tests, but counting all logical and 429 arithmetic operations, including counting indexing as an addition, 430 SHA-1 requires 1,744 operations per 64 bytes block or 27.25 431 operations per byte. So by this rough measure, it is a little over 13 432 times the effort of FNV for large amounts of data. However, FNV is 433 commonly used for small inputs. Using the above method, for inputs of 434 N bytes, where N is <= 55 so SHA-1 will take one block (SHA-1 435 includes padding and an 8-byte length at the end of the data in the 436 last block), the ratio of the effort for SHA-1 to the effort for FNV 437 will be 872/N. For example, with an 8 byte input, SHA-1 will take 109 438 times as much effort as FNV. 440 Stronger cryptographic functions than SHA-1 generally have an even 441 high work factor. 443 Appendix B: Previous IETF Reference to FNV 445 FNV-1a was referenced in draft-ietf-tls-cached-info-08.txt that has 446 since expired. It was later decided that it would be better to use a 447 cryptographic hash for that application. 449 Below is the Jave code for FNV64 from that TLS draft include by the 450 kind permission of the author: 452 /** 453 * Java code sample, implementing 64 bit FNV-1a 454 * By Stefan Santesson 455 */ 457 import java.math.BigInteger; 459 public class FNV { 461 static public BigInteger getFNV1aToByte(byte[] inp) { 463 BigInteger m = new BigInteger("2").pow(64); 464 BigInteger fnvPrime = new BigInteger("1099511628211"); 465 BigInteger fnvOffsetBasis = 466 new BigInteger("14695981039346656037"); 468 BigInteger digest = fnvOffsetBasis; 470 for (byte b : inp) { 471 digest = digest.xor(BigInteger.valueOf((int) b & 255)); 472 digest = digest.multiply(fnvPrime).mod(m); 473 } 474 return digest; 476 } 477 } 479 Appendix C: A Few Test Vectors 481 Below are a few test vectors in the form of ASCII strings and their 482 FNV32 and FNV64 hashes using the FNV-1a algorithm. 484 Strings without null (zero byte) termination: 486 String FNV32 FNV64 487 "" 0x811c9dc5 0xcbf29ce484222325 488 "a" 0xe40c292c 0xaf63dc4c8601ec8c 489 "foobar" 0xbf9cf968 0x85944171f73967e8 491 Strings including null (zero byte) termination: 493 String FNV32 FNV64 494 "" 0x050c5d1f 0xaf63bd4c8601b7df 495 "a" 0x2b24d044 0x089be207b544f1e4 496 "foobar" 0x0c1c9eb8 0x34531ca7168b8f38 498 Appendix Z: Change Summary 500 RFC Editor Note: Please delete this appendix on publication. 502 From -00 to -01 504 1. Add Security Considerations section on why FNV is non- 505 cryptographic. 507 2. Add Appendix A on a work factor comparison with SHA-1. 509 3. Add Appendix B concerning previous IETF draft referenced to FNV. 511 4. Minor editorial changes. 513 From -01 to -02 515 1. Correct FNV_Prime determination criteria and add note as to why s 516 < 5 and s > 10 are not considered. 518 2. Add acknowledgements list. 520 3. Add a couple of references. 522 4. Minor editorial changes. 524 Author's Address 526 Glenn Fowler 527 AT&T Labs Research 528 180 Park Avenue 529 Florham Park, NJ 07932 USA 531 Email: gsf@research.att.com 532 URL: http://www.research.att.com/~gsf/ 534 Landon Curt Noll 535 Cisco Systems 536 170 West Tasman Drive 537 San Jose, CA 95134 USA 539 Telephone: +1-408-424-1102 540 Email: fnv-rfc-mail@asthe.com 541 URL: http://www.isthe.com/chongo/index.html 543 Kiem-Phong Vo 544 AT&T Labs Research 545 180 Park Avenue 546 Florham Park, NJ 07932 USA 548 Email: kpv@research.att.com 549 URL: http://www.research.att.com/info/kpv/ 551 Donald Eastlake 552 Huawei Technologies 553 155 Beaver Street 554 Milford, MA 01757 USA 556 Telephone: +1-508-333-2270 557 EMail: d3e3e3@gmail.com 559 Copyright, Disclaimer, and Additional IPR Provisions 561 Copyright (c) 2011 IETF Trust and the persons identified as the 562 document authors. All rights reserved. 564 This document is subject to BCP 78 and the IETF Trust's Legal 565 Provisions Relating to IETF Documents 566 (http://trustee.ietf.org/license-info) in effect on the date of 567 publication of this document. Please review these documents 568 carefully, as they describe your rights and restrictions with respect 569 to this document. Code Components extracted from this document must 570 include Simplified BSD License text as described in Section 4.e of 571 the Trust Legal Provisions and are provided without warranty as 572 described in the Simplified BSD License. This Internet-Draft is 573 submitted to IETF in full conformance with the provisions of BCP 78 574 and BCP 79.