H（k || length || x）是安全的MAC结构吗？

#1 楼

我们对$ H $做什么假设，以及我们希望$ H'_k \冒号m \ mapsto H（k \ mathbin \ | \ operatorname {len}（m）\ mathbin \ | m）$有什么属性？以下是一些合理的选择：


$ H $是随机预言，我们希望$ H'_k $与随机预言是不可区分的。在这种情况下，前缀构造$ m \ mapsto H（k \ mathbin \ | m）$已经实现了此目的，因此将自己限制在以自己的长度开始编码的消息中是不可能的。
$ H $是BLAKE2，SHA-3或另一个现代的“哈希函数”，我们希望$ H'_k $是伪随机函数族。在这种情况下，$ H $被设计为使得$ m \ mapsto H（k \ mathbin \ | m）$已经被推测为是PRF，因此将自己限制为那些以自己的长度开始编码的消息可能会改变它。 （而且这些都具有本地PRF构造：键控BLAKE2，KMAC。因此，要点很不重要。）安全属性是基础压缩功能的推测-无论是HMAC du jour的受青睐的安全声明我们需要什么属性。大概这是最感兴趣的情况。答案基本上是肯定的，它的安全性与HMAC一样简单，而且要简单得多。在MDx-MAC论文[1]的命题4中–与HMAC以及任何迭代函数完全相同，查询成本与可能的中间状态数的平方根成正比。*

同样在1996年，Bellare，Canetti和Krawczyk研究了他们所谓的“级联构造” [2]，并表明如果$ F_k \冒号m \ mapsto F（k，m）$是PRF，则级联$$ F ^ * _ k \冒号（m_1，m_2，\ dots，m_n）\ mapsto F（F（\ dots F（F（k（m_1），m_2）\ dots），m_n）$$几乎是PRF，具体来说， $ F ^ * _ k $从统一的随机函数到从未向其查询任何消息（作为另一条消息的前缀）的任何对手都无法区分。 $ F ^ * $也不完全是Merkle–Damgård函数的应用，因为键$ k $取代了IV的作用，但是假设$ k \ mapsto F（\ mathit {IV }，k）$是伪随机数生成器，而$ H（k \ mathbin \ | m）= F ^ * _ {F（\ mathit {IV}，k）}（m）$（围绕块大小的模数篱笆柱）。

在这些适度的假设下（并且比HMAC持续发展的传奇中的任何事物都简单得多的证明），函数$ m \ mapsto H（k \ mathbin \ | m）$几乎是PRF以上意义。如果我们在对消息进行任何无前缀编码之前将其提供给它，那么我们将获得PRF，根据通常的定理，它也是MAC。还有定长$ m \ mapsto \ operatorname {len}（m）\ mathbin \ | m $是无前缀编码的示例。





*仅对于像MD5这样的小型哈希函数，这可能是一个潜在的问题-对于SHA-256，这是完全不可想象的，但即使对于MD5，它也需要对oracle进行$ 2 ^ {64} $个查询，而不是$ 2 ^ {64} $个离线计算。您的应用服务器可以在人类煮熟地球之前处理$ 2 ^ {64} $个查询吗？我对此表示怀疑！ （提示：假设您的服务器需要一纳秒的时间来回答查询。
$ 2 ^ {64} $纳秒是多少年？）

#2 楼

这种结构是不安全的。本文提出了一个简短的句子，它可能从另一个问题$ \ mathcal {H}（k || m）$修复不安全的秘密前缀构造。然后，作者提出并分析了一种包络方法：$ \ mathcal {H}（k_1 || x || k_2）$。

涉及发现内部碰撞的攻击适用于$ \ mathcal {H} （k || \ ell_m || m）$。这有点复杂，但是如果您好奇的话，它就是本文的“命题4”（另请参阅第4.1节第1款）。作者还注意到，该构造还涉及散列函数的其他假设，而不是标准假设（防碰撞，（第二）原像电阻）。它不像对其他结构进行长度扩展攻击那样有效，但从理论上讲，它相对于HMAC的安全性而言是一种突破。

我还将注意到“明确”地编码长度可能有问题。例如（使用10为底数以提高可读性），如果我将长度= 2的m = 08哈希值和一些k散列，则长度扩展攻击可能会发现m = 0896346218569465994320，可以将其解释为length = 20且m = 896346218569469494394320。明确定义消息长度的一种解决方法是修复一定长度的字节，但现在您不再拥有可以接受任意长度输入的MAC。

最后，HMAC构造非常简单，可以接受任意长度的输入，并且不依赖于编码方案。