适用于小输入的无冲突/加密哈希函数

问题描述 投票:0回答:1

所以我不需要加密哈希函数,但我确实需要确保碰撞的可能性极低。但我没有建议,我正在生成所有将被散列的对象。我的对象非常小,但内部包含哈希值,因此在某种意义上是“高熵”。但对象的大小范围为 8 到 36 字节(假设为 128 位哈希值),因此非常非常小。较小的对象可以按其本身进行哈希处理,但较大的对象(在 20-36 字节范围内)需要哈希到 128 位。

这些对象本质上形成了对象的有向图,每个对象都包含少量元数据,并且哈希充当指向先前创建的对象的指针。我希望能够每秒在该图中生成尽可能多的节点,但最终需要有一个唯一的节点,理想情况下至少有 128 位,但我可以争论为 64 位位。不需要超过 128 位,我可能会将任何较大的哈希值异或减少到 128 位。

目前我正在使用 smhasher 来探索各种可能性: siphash、xxhash128、metrohash128、farmhash128、cityhash128、cityhash128_crc、cityhash64、Pearson 区块哈希 128、prvhash64_128、幽灵哈希 128。

我可能会进行一次测试运行,模拟一个非常简单的版本,这样我就可以看到实践中发生碰撞的可能性有多大。我也可能找不到我喜欢的每个库。该项目是 Rust 的,所以拥有一个已经在 Rust 中“做事”的优秀库是很好的。此外,能够轻松地实现自己(例如使用 fnv128)是一个巨大的好处。

有人有任何哈希函数或我应该阅读的内容吗?

rust hash hashmap cryptography cryptographic-hash-function
1个回答
0
投票

如果你想要一个不可能发现冲突的哈希,那么你需要一个抗冲突的加密哈希函数。您列出的选项都不属于该类别。

SipHash 是一个 PRF,必须与密钥一起使用才能安全。它不是无密钥选项意义上的通用哈希函数。

您还需要小心,即使使用加密哈希函数,并且输出像您建议的那样非常短,由于生日悖论,冲突的风险仍然很大。如果使用 64 位哈希,与 3 万亿个节点发生冲突的可能性非常高。对于 128 位散列来说要少得多,但我们通常仍然认为对于加密目的来说太高了,尽管您可能认为它可以接受。

假设性能是主要限制,您拥有的加密选项包括 BLAKE2s、BLAKE2b、BLAKE3 和 SHA-256。 SHA-256 在许多最新的 Intel 和 AMD 芯片中都在硬件中进行了加速(尽管这些扩展足够新,以至于仍然有不支持它们的硬件在使用),并且在我的 Core i7-1280P 上,可以处理 124454 kB/s在 16 字节块上。如果需要,您可以将其截断为 128 位。

BLAKE2s 和 BLAKE2b 也非常快,并且可以显式截断为 128 位输出。 BLAKE2b 在 64 位机器上更快,BLAKE2s 在 32 位机器上更快,并且在无法进行硬件加速的情况下,它们将比 SHA-256 更快。 BLAKE3 也是一种可能性,甚至比 BLAKE2 更快。它也可以在大数据上并行(使其非常快),这不是您关心的问题,并且它也可以被截断为任意大小。

所有这些算法都有 Rust 包。您当然可以自己实现它们,但使用 Rust 箱会更不容易出错,而且速度可能会快很多。我已经手动实现了其中的大部分,并且我也建议不要这样做(并且只使用板条箱)。

© www.soinside.com 2019 - 2024. All rights reserved.