使用秘密对短消息进行快速不可逆转的转换/压缩

Question

我正在寻找一个非常快速的函数f(m, k) ，它接受一个64位整数m和一个几乎任何大小的固定密钥k (由CSPRNG生成)，并将它们转换为64位或32位整数r ，还有一些额外的要求：

1. r 必须同时依赖于m和k ，并且具有合理的良好分布性。
2. 如果已知一对m 和r ，则不可能有效地计算k 或生成f(m_1, k) = r_1 。
3. r 将用作与m 关联的键或标记，但它不必唯一地标识m (即m_1 、m_2 的存在，使f(m_1, k) = f(m_2, k) = r 完全正常)，所以我不太关心碰撞问题。

IOW，我需要一种使用秘密快速和不可逆转地转换/压缩/置乱一个固定大小的整数(可能缩短它)的方法。

我认为理想情况下，这将通过键控密码散列函数来解决，比如Blake*或Siphash。例如，Siphash是专门设计的，可以很好地处理小输入和保持密钥保密，目前它在CPython中用于哈希表查找。就性能而言，Siphash2-4对我的用例来说可能是可以容忍的，并且似乎检查了所有的框，但是由于我只需要处理64位整数，这感觉就像是过火了，而且我仍然对任何更轻量级的东西感兴趣。

我还看过几个非加密的散列函数，它们的性能非常吸引人，但我担心它们中的许多都不能满足我列出的第二个要求(特别是如果我向它们提供k || m ，它简化了FNV-1A和Murmurhash3情况下的野蛮攻击)。XXH3显式地允许我提供一个secret来自定义哈希值，它的性能似乎优于现有的任何其他体面的哈希函数，但它也是显式非加密的，因此不幸的是，我不确定它是否能提供与Siphash相同的安全性，即使对于像我这样简单的用例也是如此。

我还尝试创建自己的混合/压缩函数(这很可能是不安全的)，并考虑使用现有算法中的混合/压缩函数(很可能不会与原始算法单独使用)。

我错过了一种更简单的方法吗？

Answer 1

在这个答案的第一部分，我将阅读要求2限制为“如果一个对(m,r)是已知的…”，并假定k是随机选择的。当对手知道两个不同的对(m,r)时，或者当使用相关的键k时，我完全忽略安全性。

下面的构造使用伽罗瓦场 (\mathbb F_{2^{64}},\oplus,\otimes)，带有一些不可约的多项式：

f:\{0,1\}^{64}\times\{0,1\}^{128}\to\{0,1\}^{64}\\ (m,k)\mapsto (k_1\otimes m)\oplus k_0=r\\ \text{ where }\ k_1\mathbin\|k_0=k\ \text{ and }\ |k_0|=64=|k_1|

给定(m,r)和(m_1,r_1)与m\ne m_1，存在一个具有f(m,k)=r和f(m_1,k)=r_1的唯一的平方键k。因此，无论对手的计算能力如何，该构造都完全符合其安全目标。

注意:对于任何固定的k与k_1\ne0，没有冲突。

注意:我们通过从结果中删除任意数量的位来限制较小的输出。通过删除不影响结果的k (在k_0中)的位数，可以相应地缩短密钥D17。

注意:在内置支持二进制字段算法的CPU上计算f是简单而有效的，包括大多数具有无进位乘法的现代x86 CPU。否则，这种方法就没什么意义了。

#include 
#if OPTIMIZED // for Intel Westmere (2010), AMD Jaguar (2013) and later.
#include 
inline uint64_t f(uint64_t m, const uint64_t k[2]) {
  __m128i u,v;
  u.m128i_u64[0] = k[1];
  u.m128i_u64[1] = 27;                  // X**64 + x**4 + x**3 + x + 1
  v.m128i_u64[0] = m;
  v = _mm_clmulepi64_si128(u, v, 0);    // u.m128i_u64[0] * v.m128i_u64[0]
  u = _mm_clmulepi64_si128(u, v, 17);   // u.m128i_u64[1] * v.m128i_u64[1]
  return k[0] ^ v.m128i_u64[0] ^ u.m128i_u64[0];
}
#else // no _mm_clmulepi64_si128
#pragma warning(disable : 4146)         // silence silly compiler's warning
uint64_t f2(uint64_t m, const uint64_t k[2]) {
  uint64_t a = k[1], x = (m & -(a & 1)) ^ k[0];
  a = (a >> 1) | (1ull << 63);          // insert sentinel
  do                                    // 63 times
    x ^= (m = (27 & -(m >> 63)) ^ (m + m)) & -(a & 1);
  while ((a >>= 1) != 1);
  return x;
}
#endif

现在，我将需求2理解为“如果对<#>some数(m,r)是已知的…”。如果所述数量很大(大于我们愿意处理64位关键块)，我们就不能再构建一个完全安全的系统。

这个问题可以用64位分组密码很好地解决，但是还有选择它的问题。茶？RC5？河豚 王子 西蒙 小斑点，轻量级密码候选？任何人都可以。然后我们就可以尝试一些习俗了。

例如，x^{64}+x^4+x^3+x+1，见Joerg的具有最低可能集位的二元不可约多项式。这个多项式碰巧也是本原，但是我们不需要这个性质。

证明：k可以被发现为k_1\gets(r\oplus r_1)\oslash (m\oplus m_1)，k_0\gets(k_1\otimes m)\oplus r，k\gets k_1\mathbin\|k_0。