6. Security Considerations

この節では 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 原文

6.  Security Considerations

   No assertion of suitability for cryptographic applications is made
   for the FNV hash algorithms.

   The use of a cryptographic hash function should be considered when
   active adversaries are a factor (see Section 1.2).

6.1.  Inducing Collisions

   An attacker could attempt to induce collisions to cause denial or
   degradation of service.  Consider the following simplified example: A
   hash table of n buckets is being maintained with the bucket used by
   some item i determined by

                                  hash(i) mod n

   and with a linked list out of each bucket of the items that all hash
   to that bucket.  Such an arrangement might be used for the symbol
   table in a compiler or for some of the routing information (i.e., a
   RIB (Routing Information Base)) in a router.  A large number of items
   hashing to the same bucket will then likely result in much slower
   times to retrieve from or update the information stored through the
   table for one of those items.  Typically, an attacker could arrange
   for the number of distinct items being hashed to be orders of
   magnitude larger than n, even if n was tens or hundreds of thousands,
   so collisions are guaranteed to occur in this example regardless of
   the nature of the hash function.

   There are a number of different circumstances that might surround
   this example, of which the following three are illustrative:

   *  If a hash function is being used in an exactly known way for the
      above scenario, including a known offset_basis such as a standard
      offset_basis specified in this document, then an adversary could
      test items offline and generate an arbitrary set of items whose
      hash table indexes would collide.  Under these circumstances, the
      adversary would not have to conduct any trials of actually
      submitting items and would not have to measure performance to find
      collisions.  Submitting such a set of items would then degrade or
      deny service.  For FNV, the use of an offset_basis not known by
      the adversary is adequate to defeat this case.

   *  If the adversary cannot detect when collisions occur or when
      service is degraded, then it is sufficient for the adversary to be
      unable to predict the hash outcomes.  For FNV, the use of an
      offset_basis not known by the adversary may be adequate to defend
      against this case.

   *  If the adversary can detect the degradation in service caused by
      collisions in the above example and can feed large numbers of
      variable items to the process, then they can collect sets of items
      that appear to collide.  Even if there are limits to the number of
      items that can be submitted, if there can be multiple trials, the
      adversary can collect multiple sets of items that collide within
      each set or one growing set of items, all of which collide.  Then,
      by submitting such items, the adversary can degrade or deny
      service.  That is true regardless of whether the hash function
      used is a non-cryptographic hash function such as FNV or a
      cryptographic hash function such as those specified in [FIPS202]
      or [RFC6234].  One defense in this case is to detect when a large
      number of collisions are happening (which could, but would be
      unlikely to, occur by chance) and, when that is detected, rehash
      the items with some change to the hash algorithm and use the
      changed hash algorithm for subsequent items -- for example, if FNV
      is being used, to rehash with a different offset_basis and then
      continue using that new offset_basis.  There exist commercially
      deployed routers that use this technique to ameliorate excessive
      hash collisions in internal tables.