从哈希函数中获取特定范围值的安全实践

本文是继Pascal Junod去年所写优秀博文的后续研究，这也解释了奇怪的标题。前文讨论了哈希不同类型数据时缺乏域分离的缺陷，而本文我们将探讨在现实世界中发现的哈希函数实现相关缺陷——当结果需要落在特定范围内时的问题。

域分离 refresher

正如Pascal Junod文章所述，域分离是从相同原语构造不同哈希函数的方法。当相同哈希函数用于哈希不同数据类型或结构化类型时，它可以避免碰撞。例如，如果有人想哈希数组[104, 101, 108, 108, 111]，他们可能将其编码为字节"68656c6c6f"并传递给哈希函数。结果将与字符串"hello"或数组[6841708, 27759]的哈希碰撞，这对某些应用来说是不可取的。

哈希到特定范围

一些现代构造如基于身份的加密、可验证延迟函数(VDF)、电子投票、BLS数字签名或后量子McEliece密码系统需要将值哈希到特定集合的原语。研究论文通常未定义此函数，但将正确选择的责任留给实现者。

例如SHA3-384将输出可解释为0到2^384-1之间整数的值。对于任何2的幂，可以使用可扩展输出函数(XOF)，如SHAKE256甚至cSHAKE来保证域分离。

模块化偏差（再次）

朴素方法是哈希值并对结果取模。但问题是我们通常需要值在整个范围内均匀分布。此外，它不能解决哈希到更复杂集合（如椭圆曲线点群）的问题。

有缺陷的猎取方法

类似生成随机值时拒绝采样的方法称为"猎取方法"或"尝试递增方法"。其基本思想是哈希一个值，如果不符合期望的输出约束，则再次哈希直到找到满足的值。

我们在瑞士邮政电子投票系统中发现了这种原语的使用。该电子投票系统于2023年6月18日在瑞士3个州进行了真实投票测试。

非常量时间方法

之前的"猎取方法"可以用更健壮的方式实现。例如，BLS签名使用称为MapToGroup的算法将消息映射到椭圆曲线子群的点。

然而这种方法不是恒定时间的，因为总迭代次数取决于要哈希的消息，可能导致定时攻击。

结论

从哈希函数获取特定范围内均匀分布的值可能很棘手，自定义解决方案通常存在导致不安全构造的缺陷。如果需要实现此类方法，哈希到有限域的恒定时间解决方案是使用IETF草案"Hashing to Elliptic Curves"中定义的hash_to_field方法。

致谢：感谢Nils Amiet和Pascal Junod对本文的宝贵评论。