哈希设计与古德哈特定律

主要观点:

  • SMHasher 是 Austin Appleby 为测试哈希函数弱点和速度而创建的流行测试套件,有更新的 fork。它广泛用于非加密哈希函数的设计和审查,但对于大输出大小的哈希存在问题。
  • 介绍 Goodhart 定律,指出用实证测试捕捉大输出哈希的所有问题是不可行的,SMHasher 只是质量的不完全度量。
  • 设计一个 128 位哈希函数 goodhart_hash_1,看似通过 SMHasher 但有明显分析问题,通过逐步修改得到 goodhart_hash_2、goodhart_hash_3 等,最终得到看似高质量但速度慢的 goodhart_hash_3,以及速度提升但质量仍有问题的 goodhart_hash_4、goodhart_hash_5。
  • 强调 SMHasher 的“通过”并不意味着哈希真正稳健,以 goodhart_hash_6 为例说明即使通过 SMHasher 也可能存在隐藏问题。
  • 分析多个常见的大输出非加密哈希函数,发现它们普遍存在块间混合不足的问题,缺乏对设计的公开分析和论证。

关键信息:

  • SMHasher 用于测试哈希函数,适用于小输出哈希,不适用于大输出哈希。
  • Goodhart 定律适用于哈希函数设计,实证测试有局限性。
  • 设计的哈希函数 goodhart_hash_1 到 goodhart_hash_6 展示了不同阶段的问题和改进。
  • 多个常见大输出哈希函数存在块间混合不足问题,缺乏设计分析。

重要细节:

  • 混合函数的选择及特性,如 bijective 和 good avalanche。
  • goodhart_hash_1 的问题及后续改进步骤,如加入输入长度、在块间添加混合等。
  • goodhart_hash_4 到 goodhart_hash_5 调整混合轮数对测试结果的影响。
  • 各哈希函数的 avalanche 图表及相关分析。
  • 多个常见大输出哈希函数的平均和最差扩散情况及相关图表。
阅读 7
0 条评论