1. Introduction

この節では FNV の RFC テキストを保持し, FNV primes, offset_basis, endianism, XOR folding, constants, non-cryptographic security guidance, source code, test code, Makefile, SHA-1 and SHA-256 との比較を扱う.

RFC 原文

1.  Introduction

   FNV (Fowler/Noll/Vo) hashes are designed to be fast and have a small
   code footprint.  Their good dispersion makes them particularly well
   suited for hashing nearly identical strings, including URLs,
   hostnames, filenames, text, and IP and Media Access Control (MAC)
   addresses.  Their speed allows one to quickly hash lots of data.

   The purpose of this document is to make information on FNV and open-
   source code performing all specified sizes of FNV conveniently
   available to the Internet community.  This work is not an Internet
   Standard and does not have the consensus of the IETF community.

1.1.  Conventions Used in This Document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

1.2.  Applicability of Non-Cryptographic Hashes and FNV

   While a general theory of hash function strength and utility is
   beyond the scope of this document, typical attacks on hash functions
   involve one of the following:

   Collision:  Finding two data inputs that yield the same hash output.

   First Pre-Image:  Given a hash output, finding a data input that
      hashes to that output.

   Second Pre-Image:  Given a first data input, finding a second input
      that produces the same hash output as the first.

   For a hash function producing N bits, there necessarily will be
   collisions among the hashes of more than 2^N distinct inputs.  And if
   the hash function can produce hashes covering all 2^N possible
   outputs, then there will exist first and second pre-images.  FNV is
   NOT RECOMMENDED for any application that requires that it be
   computationally infeasible for one of the above types of attacks to
   succeed.

   FNV hashes are generally not applicable for use when faced with an
   active adversary in a security scheme where the modest effort
   required to compute FNV hashes (see Appendix A) and their other non-
   cryptographic characteristics (see Section 1.4) would make the scheme
   ineffective against the threat model being considered.  It is
   sometimes hard to determine whether or not there are attack vectors
   via a hash.

   For a discussion of adversarial inducement of collisions, see
   Section 6.1.

1.3.  FNV Hash Uses

   The FNV hash has been widely used.  Examples include the following:

   *  NFS implementations (e.g., FreeBSD 4.3 [FreeBSD], IRIX, Linux (NFS
      v4)),

   *  text-based referenced resources for video games on the PS2,
      Gamecube, and XBOX,

   *  to improve the fragment cache [FragCache] at X (formerly Twitter),

   *  the flatassembler open-source x86 assembler - user-defined symbol
      hashtree [flatassembler],

   *  used in the speed-sensitive guts of [twistylists], an open-source
      structured namespace manager,

   *  database indexing hashes,

   *  PowerBASIC inline assembly routine [BASIC],

   *  major web search / indexing engines,

   *  the "calc" C-style calculator [calc],

   *  netnews history file Message-ID lookup functions,

   *  [FRET] - a tool to identify file data structures / help understand
      file formats,

   *  anti-spam filters,

   *  used in an implementation of libketama [libketama] for use in
      items such as [memcache],

   *  a spellchecker programmed in Ada 95,

   *  used in the BSD Integrated Development Environments (IDE) project
      [fasmlab],

   *  non-cryptographic file fingerprints,

   *  used in the deliantra game server for its shared string
      implementation [deliantra],

   *  computing Unique IDs in DASM (DTN (Delay Tolerant Networking)
      Applications for Symbian Mobile-phones),

   *  Microsoft's hash_map implementation for VC++ 2005,

   *  the realpath cache in PHP 5.x (php-5.2.3/TSRM/tsrm_virtual_cwd.c),

   *  DNS (Domain Name System) servers,

   *  used to improve [Leprechaun], an extremely fast wordlist creator,

   *  the Smash utility [Smash] for rapidly finding duplicate files,

   *  Golf language hash tables [RimStone],

   *  the libsir logging library [libsir],

   *  a standard library for modern Fortran [Fortran],

   and many other uses.  It is also referenced in the following
   standards documents: [RFC7357], [RFC7873], and [IEEE8021Q-2022].

   A study has recommended FNV in connection with the IPv6 flow label
   value [IPv6flow].  Additionally, there was a proposal to use FNV for
   Bidirectional Forwarding Detection (BFD) sequence number generation
   [BFDseq].  [NCHF] discusses criteria for evaluating non-cryptographic
   hash functions.

   If you use an FNV function in an application, you are kindly
   requested to send a note via the process outlined at
   <http://www.isthe.com/chongo/tech/comp/fnv/index.html#address>.

1.4.  Why Is FNV Non-Cryptographic?

   A full discussion of cryptographic hash requirements and strength is
   beyond the scope of this document.  However, here are three
   characteristics of FNV that would generally be considered to make it
   non-cryptographic:

   1.  Sticky State - A cryptographic hash should not have a state in
       which it can stick for a plausible input pattern.  But in the
       very unlikely event that the FNV hash variable accidentally
       becomes zero and the input is a sequence of zero bytes, the hash
       variable will remain at 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 bytes.  For the common case of fixed-
       length input, this would usually not be significant because the
       number of non-zero bytes would vary inversely with the number of
       zero bytes and for some types of input, runs of zeros do not
       occur.  Furthermore, the use of a different offset_basis or the
       inclusion of even a little unpredictable input may be sufficient,
       under some circumstances, to stop an adversary from inducing a
       zero hash variable (see Section 6.1).

   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 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 on any other input bits.  While more complex, the
       second through seventh least significant bits of an FNV hash have
       a similar weakness; only the top bit of the bottom byte of
       output, and 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).

   3.  Work Factor - Depending on intended use, it is frequently
       desirable 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 applied to slow down testing of possible
       inputs if the output is known or the like.  But FNV is designed
       to be inexpensive on a general-purpose processor (see
       Appendix A).

   Nevertheless, none of the above have proven to be a problem in actual
   practice for the many non-cryptographic applications of FNV (see
   Section 1.3).