跳到主要内容

1. 引言 (Introduction)

FNV (Fowler/Noll/Vo) hashes 设计为速度快且代码占用小. 它们良好的分散性使其特别适合对几乎相同的字符串进行哈希, 包括 URLs, hostnames, filenames, text, 以及 IP 和 Media Access Control (MAC) addresses. 它们的速度允许快速对大量数据进行哈希.

本文档的目的是使有关 FNV 的信息以及执行所有指定大小 FNV 的开源代码能够方便地提供给 Internet 社区. 此工作不是 Internet Standard, 也不具有 IETF 社区共识.

1.1. 本文档使用的约定​

本文档中的关键词 "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY" 和 "OPTIONAL" 在且仅在它们以此处所示全大写形式出现时, 应按 BCP 14 [RFC2119] [RFC8174] 中的描述解释.

1.2. 非密码学哈希和 FNV 的适用性​

虽然哈希函数强度和用途的一般理论超出本文档范围, 但对哈希函数的典型攻击涉及以下之一:

Collision

: 找到两个数据输入, 它们产生相同的哈希输出.

First Pre-Image

: 给定一个哈希输出, 找到一个会哈希到该输出的数据输入.

Second Pre-Image

: 给定第一个数据输入, 找到第二个输入, 其产生与第一个输入相同的哈希输出.

对于产生 N bits 的哈希函数, 超过 2^N 个不同输入的哈希之间必然存在碰撞. 如果该哈希函数能够产生覆盖所有 2^N 个可能输出的哈希, 则 first pre-images 和 second pre-images 必然存在. 对于任何要求上述任一类型攻击在计算上不可行的应用, 不建议使用 FNV.

当面对安全方案中的主动对手时, FNV hashes 通常不适用, 因为计算 FNV hashes 所需工作量较小 (见附录 A), 且其其他非密码学特性 (见第 1.4 节) 会使该方案无法有效抵御所考虑的威胁模型. 有时很难判断是否存在通过哈希实现的攻击向量.

关于对抗性诱导碰撞的讨论见第 6.1 节.

1.3. FNV 哈希用途​

FNV hash 已被广泛使用. 示例包括:

  • NFS 实现, 例如 FreeBSD 4.3 [FreeBSD], IRIX, Linux (NFS v4).
  • PS2, Gamecube 和 XBOX 上视频游戏的基于文本的引用资源.
  • 用于改进 X (formerly Twitter) 的 fragment cache [FragCache].
  • flatassembler 开源 x86 assembler 的用户定义符号 hashtree [flatassembler].
  • 用于 [twistylists] 中对速度敏感的核心部分, 该项目是开源 structured namespace manager.
  • database indexing hashes.
  • PowerBASIC inline assembly routine [BASIC].
  • 主要 Web 搜索/索引引擎.
  • "calc" C-style calculator [calc].
  • netnews history file Message-ID lookup functions.
  • [FRET], 用于识别文件数据结构和帮助理解文件格式的工具.
  • anti-spam filters.
  • 用于 libketama [libketama] 的一个实现, 以用于 [memcache] 等项目.
  • 用 Ada 95 编写的 spellchecker.
  • 用于 BSD Integrated Development Environments (IDE) project [fasmlab].
  • 非密码学文件指纹.
  • deliantra game server 的 shared string 实现 [deliantra].
  • 在 DASM (DTN (Delay Tolerant Networking) Applications for Symbian Mobile-phones) 中计算 Unique IDs.
  • Microsoft 针对 VC++ 2005 的 hash_map 实现.
  • PHP 5.x 中的 realpath cache (php-5.2.3/TSRM/tsrm_virtual_cwd.c).
  • DNS (Domain Name System) servers.
  • 用于改进 [Leprechaun], 一个极快的 wordlist creator.
  • Smash utility [Smash], 用于快速查找重复文件.
  • Golf language hash tables [RimStone].
  • libsir logging library [libsir].
  • modern Fortran 的标准库 [Fortran].

以及许多其他用途. 它也被以下标准文档引用: [RFC7357], [RFC7873] 和 [IEEE8021Q-2022].

一项研究曾建议将 FNV 用于 IPv6 flow label value [IPv6flow]. 此外, 也曾有提案建议将 FNV 用于 Bidirectional Forwarding Detection (BFD) sequence number generation [BFDseq]. [NCHF] 讨论了评估非密码学哈希函数的标准.

如果你在应用中使用 FNV function, 请按 http://www.isthe.com/chongo/tech/comp/fnv/index.html#address 中概述的流程发送说明.

1.4. 为什么 FNV 是非密码学的?​

对密码学哈希要求和强度的完整讨论超出本文档范围. 不过, FNV 有 3 个通常会被认为使其成为非密码学哈希的特征:

  1. Sticky State - 密码学哈希不应存在一种状态, 使其能够在合理的输入模式下停滞. 但是, 在非常不可能发生的事件中, 如果 FNV hash 变量意外变为 0 且输入是一系列 0 bytes, 则 hash 变量将保持为 0, 直到出现非 0 输入 byte, 并且最终 hash 值不会受这段 0 输入 bytes 序列长度影响. 对于固定长度输入这一常见情况, 这通常并不重要, 因为非 0 bytes 数量会与 0 bytes 数量反向变化, 且对于某些输入类型不会出现连续 0. 此外, 在某些情况下, 使用不同的 offset_basis 或包含哪怕少量不可预测输入, 可能足以阻止对手诱导出 0 hash 变量 (见第 6.1 节).
  2. Diffusion - 密码学哈希的每个输出 bit 都应是每个输入 bit 的同等复杂函数. 但很容易看出, 直接 FNV hash 的最低有效 bit 是每个输入 byte 最低有效 bit 的 XOR, 并且不依赖任何其他输入 bit. 虽然更复杂, FNV hash 的第二到第七个最低有效 bits 也有类似弱点. 只有输出底部 byte 的最高 bit 以及更高阶 bits 依赖所有输入 bits. 如果这些属性被认为是问题, 可通过 XOR folding 轻松修复 (见第 3 节).
  3. Work Factor - 根据预期用途, 通常希望哈希函数对通用处理器和图形处理器来说计算代价高, 因为这些处理器可能通过弹性云服务或 botnets 大量可用. 当输出已知等场景中, 这可用于减慢对可能输入的测试. 但 FNV 设计为在通用处理器上代价低廉 (见附录 A).

尽管如此, 对 FNV 的许多非密码学应用而言, 上述特征在实际实践中都未被证明是问题 (见第 1.3 节).