短 (6 位) 密码学密钥哈希

Question

我需要实现一个简单的哈希算法。

输入数据：

• 值（16位整数）。
• 键（任意长度）。

输出数据：

• 6位哈希（数字0-63）。

要求：

• 如果只有输入值而没有键，几乎不可能预测哈希值。更具体地说：如果我已知 x < M 的哈希值 hash(x)，则在不知道键的情况下很难预测哈希(M)。

可能的解决方案：

1. 将完整的映射保留为键。因此，键的长度为 2^16*6 位。但这对我的情况来说太长了。
2. 线性编码。键是一个生成矩阵，其长度为 16*6。但使用多个已知哈希值很容易找到生成矩阵。

是否有其他可能性？

- alexey

Answer 1

HMAC 看起来是你想要的。因此，你可以使用基于SHA的HMAC，并只使用结果哈希的子字符串。这应该相对安全，因为密码哈希的位应尽可能独立和不可预测。

但是，根据你的环境，这可能需要太多的处理时间，因此你可能需要选择一个更简单的哈希方案来构建你的HMAC。

原始评论中讨论的答案：

既然你无论如何都可以忘记密码属性（通过暴力攻击5位哈希可以轻松找到冲突），那么你可以使用类似CRC或海明码之类的东西并免费获得错误检测。

- mensi

---

CRC不是哈希函数。虽然OP没有说明他想要用它做什么，但在某些情况下，CRC作为哈希函数的替代品特别糟糕，例如在哈希表中使用时。 - Nick Johnson

@NickJohnson为什么CRC不适合用于哈希表（除了有更快的方法来获取适当的哈希值之外）？ - mensi

因为正如你所指出的，CRC（循环冗余校验）包括冗余以提供可靠的错误检测，这会影响它们的分布特性。 - Nick Johnson

@NickJohnson 因为 CRC 基本上是多项式除法的余数，所以不应该有聚类现象。维基百科甚至提到 CRC 有时被用作哈希。虽然我对数论不是很熟悉，但我仍然认为我们不能简单地将 CRC 视为哈希（当然，只要你不需要碰撞抗性）。 - mensi

@mensi，感谢您的回答。我的问题不够详细，我已经更正了描述。 算法的主要要求是：对于给定的输入值，预测哈希值应该是实际上不可能的。如果我知道X < M 的哈希(X)，那么在不知道密钥的情况下，预测哈希(M)应该是困难的。 - alexey

Answer 2

Mensi 建议使用截断 HMAC 是一个好主意，但如果您碰巧在一个高度受限制的系统上并且想要更快或更简单的东西，那么您可以使用任何 分块密码，用它加密您的 16 位值（填充到完整块），然后将结果截断为 6 位。

与计算 伪随机函数 的 HMAC 不同，分块密码是一个 伪随机置换-每个输入都映射到不同的输出。但是，当您丢弃分块密码输出的所有但六位之外的内容时，剩下的内容看起来非常像伪随机函数。虽然对于重复的输出会有极小的偏差，但是（假设分块密码的块大小远大于 6 位，这应该是的）它将非常小，几乎无法检测到。

一个非常适合低端系统的好的分组密码选择可能是TEA或其后继者XTEA和XXTEA。虽然这些密码存在一些已知攻击，但它们都需要比您的应用程序应该具有的更广泛的密码访问权限。

- Ilmari Karonen