PDF质疑评估非加密哈希函数的标准
也许我们需要更多地思考非加密哈希函数。
Catherine Hayes 和 David Malone
计算机从业人员几乎每天都会遇到哈希函数，尽管它们可能不一定是关注的中心。当您安装软件包或更新时，软件包的真实性通常会通过加密哈希进行验证。实际上，在幕后，如今每个浏览网络的人都在使用加密哈希来检查 Web 服务器使用的证书是否有效。
非加密哈希函数也无处不在。编写代码的人经常使用字典，字典通常使用哈希函数来实现（以至于 Perl 将它们称为哈希）。使用负载均衡器的人经常使用哈希函数来分配负载。甚至还有一些智能算法用于计数和数据去重，它们利用非加密哈希来提高效率。
加密和非加密哈希函数的共同特点是，它们接受任意大小的数据输入，并将其转换为特定长度的确定性输出。与加密不同，这旨在成为单向过程（即，永远不需要解密）。
加密哈希具有安全要求，通常以抵抗碰撞和原像来表达。实际上，对于加密哈希函数，知道哈希输出不应让您了解如何重建输入数据。理论上，您可以通过为每个输入分配一个随机输出并将它们存储在一个巨大的表中来实现这一点。然而，在实践中，已经出现了巧妙的哈希函数设计，它们涉及位运算、查找表和重复轮次来混合输入数据。
在非加密哈希函数的情况下，安全性不是主要要求。通常，您希望哈希函数以合理的方式将输入数据（例如，通常是字符串/IP 地址/对象）映射到某些资源（例如，链表、服务器或数据结构）。通常，合理意味着均匀分布的输出，或者至少尽可能快地接近均匀。
这种期望的均匀性可能会受到攻击，从而在非加密设置中产生安全要求；正如 Scott Crosby 和 Dan Wallach 指出的那样，6 攻击者可能会尝试通过呈现所有分配给同一资源的输入来破坏事情。然而，为了速度，通常会使用更简单的函数，至少与要求更高的加密哈希设计目标相比是这样。这些非加密哈希函数是本文的重点。
一些示例
多年来，人们提出了许多哈希函数，16 但让我们看看表 1 中列出的一些著名的简单示例。
您可以通过让（非加密）哈希函数工作来评估其行为，以查看其性能如何。一种常见的用途是在填充哈希表时。在这种情况下，我们使用模运算将输入分配到 M 个“桶”之一，方法是取输入的哈希值 h，并使用 h mod M 来标识桶。期望的均匀外观输出与实际结果相比如何？为了找出答案，让我们选择一些示例输入集（见表 2）并运行一些代码。我们选择了您期望填充哈希表的项目（名称、单词、IP 地址）以及一些可能存在问题的项目（仅在一个位上与固定字符串不同的位字符串）。这称为偏差数据集。
您会认为主要目标是确保表格尽可能均匀地填充。实际上，对于使用每个桶中的列表实现的哈希表，很容易证明均匀输出是最佳的，因为这避免了将长数据链存储在任何一个桶中，同时避免了未使用的桶。让我们看看哈希输出模 M 的分布有多均匀。
由于每个数据集包含 1,000 行输入，因此使用 M = 500 个桶将导致负载因子为 2。这意味着理想情况下，每个桶会有两个条目，并且没有空桶。为了了解实际情况，您可以在图 1 中看到每种情况下观察到的空桶数量：大约 64 个空桶，但偏差数据除外，偏差数据使四个哈希中的三个哈希的许多桶为空，因此，必然会使其他桶挤满数据。Murmur2 对这个问题具有抵抗力；我们将稍后回到这一点。
有多种方法可以衡量桶上的分布与均匀分布的差距有多大。例如，您可以使用统计方法并使用卡方检验。在图 2 中，您可以看到检验的 p 值。如果每个输出值真的独立且均匀地分布在 M 个桶上，那么这些 p 值将均匀地分布在 0 和 1 之间。另一方面，重复的接近 0 的值将是可疑的，这再次是偏差数据的情况。这一次，DJBX33A 存在一簇小值，该函数可以证明可以保留输入数据中的位模式。奇怪的是，Murmur2 的值也低于预期。
有趣的是，虽然不良行为在偏差数据集中很明显，但在 IP 地址 集中，有更多值接近 1。进一步调查表明，IP 地址包含几个连续地址运行，这些地址对于某些哈希来说表现得特别好。这表明，有时根据数据中常见的模式匹配您的哈希函数可能会有所收获。
退一步说，您可以在某种程度上玩一个选择指标的游戏，并且根据您的应用程序的需求这样做可能是合理的。您也可以玩选择 M 值的游戏。为了进行比较，图 3 显示了在选择附近数字 M = 499 和 M = 512 之后空桶的发生率。关于哈希表存在一些民间传说，表明 M 是素数或 2 的幂可能很好。原始选择 M = 500 和 2 的幂 M = 512 具有相似的行为。这是因为偏差数据集的结构导致低位中出现重复模式，而这些模式会被模 2 的幂的数字运算保留下来。素数 M，例如 499，将缓解这类问题，实际上，任何奇数 M 值也会缓解这类问题。
为了探索这一点，我们尝试了 488 到 522 之间的所有桶数 M，再次使用偏差数据集并将其与 FNV-1a 结合使用（见图 4，红色突出显示素数）。
空桶的数量（蓝线，右侧轴）在约 60 到 270 之间非常规则地反弹。一般来说，当桶的数量为偶数时，只填充偶数桶，这意味着一半桶是空的。同样，任何偶数桶数都会导致零 p 值（图 4 中的橙色线）。虽然奇数桶也看到了数量一致的空桶，但 p 值显示出更多样化的模式。有趣的是，p 值在 507 或 513 个桶时最大，这些桶是奇数但不是素数。民间传说就到此为止。
因此，当使用更“真实生活”的数据集（即，排除偏差）时，前三个哈希（FNV 和 Murmur2）的空桶数量和分布大致相似，这似乎是显而易见的。似乎您也可以通过使用奇数 M 值来隐藏一些问题，尽管不一定是素数。您还可以查看其他指标，例如具有冲突的桶的数量，并且故事保持不变。
雪崩准则
这引出了一个问题，是否存在一些通用原则可以用于设计非加密哈希函数？一种常用的度量是雪崩准则。要理解这一点，请回顾通过列出每个输入并存储相应的随机生成的 N 位输出来设计哈希函数的理论示例。如果您选择任意两个输入，则输出将彼此独立。实际上，输出的每一位都将独立设置，这意味着在比较两个输出的每一位时，有 50/50 的机会翻转。
雪崩准则对此进行测试，通常表述为：如果您更改输入中的一位，则此更改会以 50% 的概率影响输出的每一位。12 对于小输入大小，哈希设计人员可以测试每个可能的输入，但对于较大的大小，输入通常是随机采样的。
图 5 显示了雪崩指标的典型评估方式。对于每个哈希函数，我们都遵循了 Bret Mulvey12 的工作，并选择了随机的 32 位输入，然后切换每个输入位以观察 10,000 次测试中 32 个输出位中的每个位发生更改的机会。结果显示在输出矩阵中，颜色如下
• 绿色 ⇒ 切换输入位 i 导致输出位 j 大约 50% 的时间发生更改（45-55%）。这是理想情况。
• 黄色 ⇒ 更改机会为 25-45% 或 55-75%。
• 红色 ⇒ 切换输入位 i 的效果是输出位 j 在 0-25% 或 75-100% 的时间内发生更改。这是最坏的情况。
Murmur2 显示出令人印象深刻的雪崩性能，所有条目均为绿色。实际上，Murmur2 的设计考虑了雪崩准则。表 1 中 Murmur2 的结构表明，它一次读取四个字节的数据，然后对当前输入进行彻底的混合步骤，然后再以类似于 FNV 的方式与之前的输入组合。此混合步骤本质上将简单的位更改隐藏在更随机的外观更改中。Murmur2 还使用“最终步骤”来混合输出位，然后再生成最终哈希输出。
相比之下，FNV 哈希每个数据字节仅涉及两个简单的步骤（XOR 和乘以素数），而 DBJX33A 更简单：接收每个数据字节，乘以 33，然后添加到先前的值。对于 FNV，这会导致输入字节中的某些模式保留在输出字节中。例如，在 FNV-1a 和 FNV-1 的较低输出位中观察到的独特的锯齿模式是因为任何低于切换输入位的输出位都不会发生更改。
这是 FNV 素数中 1 位的分布结果，这也导致了两个 FNV 矩阵顶部的大片红色区域：这些代表最近处理的字节，对其的更改尚未有机会消散到所有位中。对于 DJBX33A，乘以 33 或 0b00100001 等效于向左移动五位，然后添加原始字节。因此，关于输入的大量信息以模 32 的形式保留下来，并且需要多次运行算法才能将更改传播到更高的输出位。这些问题可以在图 5 中清楚地观察到。
请注意，尽管 Murmur2 在雪崩准则方面表现出更好的行为，但它在这些数据集上的抗冲突性和分布性能并不那么出色，偏差数据集除外。构建该数据集是为了具有许多单位输入差异，这正是雪崩准则针对的更改类型。可以通过将 Murmur2 的输入混合步骤的逆运算应用于偏差数据集来生成 Murmur2 的挑战性数据集。这是一个普遍的教训——每个哈希函数都有一个数据集，如果数据选择得足够仔细，它会发现该数据集具有挑战性。
雪崩是一个有趣的准则，但它针对的是特定形式的输入差异，其中单位更改很重要。鉴于这在实际数据中似乎不太常见，让我们快速回顾一下历史，了解雪崩准则如何引起设计人员的兴趣。
一些历史
当讨论 DES（数据加密标准）密码中的 S 盒（替换盒）时，最早提到类似雪崩准则的内容。攻击密码的一种策略可能是对输入进行微小的更改，然后尝试了解密钥。在这里，雪崩被描述为确保更改输入的单个位将更改 S 盒输出中的至少两位，10 这反过来会导致雪崩式的更改位，因为 DES 密码的内部轮次会重复进行。在应用密码学中，在分析 DES 系统时，Bruce Schneier 描述了这种加密优势
通过允许一位影响两个替换，输出位对输入位的依赖性传播得更快。这称为雪崩效应。DES 的设计目的是尽快达到密文的每一位都依赖于明文的每一位和密钥的每一位的条件。13
这些雪崩的原始用途显然是在加密上下文中，并且可以合理地应用于加密哈希，其中存在类似的安全要求。现在的问题是，雪崩是如何从加密背景迁移到非加密世界的？我们查看了许多论文，以了解在哪里提到了雪崩作为非加密哈希的准则的起源，并在文献中进行了发展。
例如，在他们的论文“用于 FPGA 上的网络和安全应用的新型非加密哈希函数”中，Claesen 等人指出，“用于 Bloom 过滤器、哈希表和草图等应用的非加密哈希必须快速、均匀分布并且必须具有出色的雪崩特性。”4 两篇论文被引用来支持这一点（Bloom3 和 Cormode 和 Muthukrishnan5），但两者都没有直接提到雪崩。
同样，在“最常见的非加密哈希函数的性能”中，Estébanez 等人提到雪崩效应对于非加密哈希函数很重要，并提供了几个参考文献。7 其中之一是 Valloud 关于评估哈希函数的书Smalltalk 中的哈希：理论与实践，该书实际上对雪崩准则不温不火
尽管雪崩测试非常流行，但请注意...它并没有说明实际哈希值的分布。特别是，完全有可能构造出质量极差但毫不费力地实现一般雪崩的哈希函数。16
另一个常见的参考文献是 Uzgalis 1996 年的“哈希概念和 Java 编程语言”。15 作者确实指出，用于为 Java 选择候选哈希的两个标准之一是混合标准：“该算法必须保证密钥中任何一位的更改都应导致哈希值的每一位发生等概率的更改。”这显然是雪崩准则，但作者继续区分了随机外观的输出和均匀分布的输出。同样，雪崩仅对那些寻求随机结果的人至关重要。
事实上，在我们确定的所有适用论文中，雪崩准则要么本身被视为一个目标，要么提供的参考文献要么是死胡同，要么导致对雪崩的普遍适用性持谨慎态度的讨论。1,8,9
重新包装雪崩
雪崩带来的另一个挑战是，它实际上针对的是在 32 位输出上均匀的输出。然而，应用程序通常希望的是在 M 个资源上均匀的输出。实际上，除非 M 是 2 的幂，否则不可能将均匀的 32 位输出均匀地打包到 M 个桶中，正如之前看到的那样，这会带来自身的缺点。多年前，随机数生成器就认识到了这个问题，并将其描述为模偏差。这导致引入了诸如 arc4random_uniform() 之类的函数，这些函数使用额外的随机位来解决偏差。目前正在进行优化随机数模偏差修复的工作。11 哈希函数的情况在某种程度上不太发达，可能是因为输入数据本身始终可能成为不均匀性的来源。
一些最后的想法
尽管加密和非加密哈希函数无处不在，但它们的设计方式似乎存在差距。加密哈希存在许多受各种安全要求驱动的标准，但在非加密方面，存在一定程度的民间传说，尽管哈希函数历史悠久，但尚未得到充分探索。虽然针对真实世界数据集的均匀分布非常有意义，但在面对具有特定模式的数据集时，它可能是一个挑战。
雪崩可能是加密哈希函数的重要准则，但其关注输入和输出之间关系的随机化可能对哈希表中条目的分布没有太大影响。在哈希表中分布输出引发了长期争论的问题，即是否选择 M 为素数或 2 的幂，但通常不考虑简单地使用奇数的选项。
所有这些证据都符合这样一种观点，即非加密哈希函数或许值得更多关注。有些人已经认为对单个加密哈希的要求过高：也许一刀切的方法是行不通的。14 另一种方法是设计针对中间地带的哈希；这些哈希将具有一些安全要求，但保持非加密哈希的速度和效率——例如，SipHash。2 或许研究针对一系列特定情况的哈希将有助于阐明我们应该如何（或是否应该）总体上评估非加密哈希函数。
参考文献
1. Akoto-Adjepong, V., Asante, M., Okyere-Gyamfi, S. 2020。增强型非加密哈希函数。国际计算机应用杂志 176 (15), 10-17； https://www.ijcaonline.org/archives/ volume176/number15/akotoadjepong-2020-ijca-920014.pdf。
2. Aumasson, J.-P., Bernstein, D. J. 2012。SipHash：一种快速的短输入 PRF。在密码学进展 (IndoCrypt) 中，489-508。施普林格； https://link.springer.com/chapter/10.1007/978-3-642-34931-7_28。
3. Bloom, B. H. 1970。允许错误的哈希编码中的空间/时间权衡。 通讯 13 (7), 422-426； https://dl.acm.org/doi/10.1145/362686.362692.
4. Claesen, T., Sateesan, A., Vliegen, J., Mentens, N. 2021。用于 FPGA 上的网络和安全应用的新型非加密哈希函数。欧洲微型数字系统设计会议； https://www.computer.org/csdl/proceedings-article/dsd/2021/270300a347/1xCb7oBYCvS。
5. Cormode, G., Muthukrishnan, S. 2005。改进的数据流摘要：计数最小草图及其应用。算法杂志 55 (1), 58-75； https://dl.acm.org/doi/10.1016/j.jalgor.2003.12.001。
6. Crosby, S. A., Wallach, D. S. 2003。通过算法复杂性攻击拒绝服务。第 12 届 Usenix 安全研讨会； https://www.usenix.org/legacy/events/sec03/tech/full_papers/crosby/crosby.pdf。
7. Estébanez, C., Saez, Y., Recio, G., Isasi, P. 2014。最常见的非加密哈希函数的性能。软件杂志：实践与经验 44 (6), 681-698。约翰威立父子出版公司； https://onlinelibrary.wiley.com/doi/10.1002/spe.2179； https://e-archivo.uc3m.es/rest/api/core/bitstreams/c2735ec2-8ae9-47f1-b663-dcda0c4f6204/content。
8. Estébanez, C., Saez, Y., Recio, G., Isasi, P. 使用遗传编程自动设计非加密哈希函数； https://e-archivo.uc3m.es/bitstream/handle/10016/30762/automatic_CI_2014_ps.pdf。
9. Henke, C., Schmoll, C., Zseby, T. 多点测量的哈希函数的实证评估。 SIGCOMM 计算机通信评论 38 (3), 39-50； https://dl.acm.org/doi/10.1145/1384609.1384614。
10. Katz, J., Lindell, Y. 2014。替换置换网络（第 6.2.1 章）。在现代密码学导论中。CRC 出版社。
11. Lemire, D. 2019。区间内的快速随机整数生成。 建模和计算机模拟学报 29 (1), 1-12； https://dl.acm.org/doi/10.1145/3230636。
12. Mulvey, B. Pluto Scarab； https://web.archive.org/web/20230603152138/https://papa.bretmulvey.com/post/124027987928/hash-functions。
13. Schneier, B. 1996。DES 描述（第 12.2 章）。在应用密码学：C 语言中的协议、算法和源代码，第二版中。约翰威立父子出版公司。
14. Noll, L. C. 单个加密哈希函数难以满足太多需求； http://www.isthe.com/chongo/tech/comp/crypto-hash.html.
15. Uzgalis, R. 1996。哈希概念和 Java 编程语言； http://www.serve.net/buz/hash.adt/java.000.html。
16. Valloud, A. 2008。Smalltalk 中的哈希：理论与实践。自出版， lulu.com.。
Catherine Hayes 于 2004 年在梅努斯大学获得数学学位，此后 20 年一直在金融投资组合管理领域工作。当数学的诱惑变得过于强烈时，她回到梅努斯大学完成了由 David Malone 指导的理学硕士学位，并被引入了迷人的哈希函数世界。
David Malone 是一位研究员、系统管理员或教授，这取决于您何时与他交谈。他曾从事 FreeBSD、IPv6、猜测密码，甚至在都柏林周围骑自行车战争游戏。他在都柏林圣三一学院获得了数学学位，并在梅努斯大学工作。
版权所有 © 2024，由所有者/作者持有。出版权已许可给 。
最初发表于 Queue 第 22 卷，第 4 期—
在 数字图书馆 中评论本文
更多相关文章
Nicole Forsgren, Eirini Kalliamvakou, Abi Noda, Michaela Greiler, Brian Houck, Margaret-Anne Storey - DevEx 在行动
随着领导者寻求在财政紧缩和人工智能等变革性技术的背景下优化软件交付，DevEx（开发者体验）在许多软件组织中越来越受到关注。技术领导者凭直觉接受，良好的开发者体验可以提高软件交付的效率和开发者的幸福感。然而，在许多组织中，旨在改善 DevEx 的拟议举措和投资难以获得支持，因为业务利益相关者质疑改进的价值主张。
João Varajão, António Trigo, Miguel Almeida - 低代码开发效率
本文旨在通过展示使用基于代码、低代码和极端低代码技术进行的实验室实验结果来研究生产力差异，从而为该主题提供新的见解。低代码技术已明确显示出更高的生产力水平，为低代码在短期/中期内主导软件开发主流提供了强有力的论据。本文报告了程序和协议、结果、局限性和未来研究的机会。
Ivar Jacobson, Alistair Cockburn - 用例至关重要
虽然软件行业是一个快节奏且令人兴奋的世界，其中不断开发新的工具、技术和技巧来服务于商业和社会，但它也很健忘。在其快速前进的过程中，它容易受到时尚的异想天开的影响，并且可能会忘记或忽略针对其面临的一些永恒问题的久经考验的解决方案。用例最初于 1986 年引入，后来普及，是这些久经考验的解决方案之一。
Jorge A. Navas, Ashish Gehani - OCCAM-v2：结合静态和动态分析以实现有效且高效的全程序特化
OCCAM-v2 利用可扩展的指针分析、值分析和动态分析来创建一个有效且高效的工具，用于特化 LLVM bitcode。实现的码大小缩减程度取决于特定的部署配置。每个要特化的应用程序都附带一个清单，该清单指定了先验已知的具体参数，以及运行时将提供的剩余参数的计数。部分评估的最佳情况发生在参数完全具体指定时。OCCAM-v2 使用指针分析来取消虚拟化调用，从而可以消除任何直接调用都无法访问的函数的整个主体。
© 保留所有权利。