问对SHA256 MAC和HMAC的实用量子攻击

EN

有两点。首先，您使用的MAC不是HMAC，您构造它的方式(第一个消息比键作为输入没有任何填充)只有假设：( a) SHA2压缩函数是一个随机甲骨文，b)验证器检查消息长度不超过32个字节。否则，您可以在不学习键的情况下，以中间内部状态冲突为代价伪造消息。因此，首先放置键可能是一种更安全的选择，将键附加到块长度(64字节)可能更安全，从一开始就使用HMAC是最安全的选择。

第二，量子攻击:当然，您可以针对这个运行grover :只需收集，比如三个消息(消息、标记)-pairs，然后用它构建一个甲骨文，如果它将所有三个消息映射到相应的标记，那么对于一个关键的k输出1。这个函数是Grover需要的布尔函数。因此，您可以在\mathcal{O}(2^{128})查询到SHA2时破坏这一点。实际花费多长时间则是另一回事了，这取决于实现布尔函数的量子电路的大小。

请注意，速率限制在任何方面都没有帮助，因为我们只需要足够多的对，即只有一个解( k )具有足够高的概率。

附加:对两个消息标记对起作用的密钥对第三个的工作概率是多少？

如果我们将SHA2-256(m \| k) = t建模为一个随机函数，并假定我们得到了使用某些密钥k计算的对(m_1,t_1), (m_2,t_2)，那么给定的密钥k' \neq k映射m_1到t_1的概率是2^{-256}。k'将m_1映射到t_1，m_2映射到t_2的概率是2^{-(2*256)}，依此类推。(在这里，256来自输出长度)。

k'不将m_1映射到t_1，将m_2映射到t_2的概率为(1-2^{-(2*256)})。所有可能的2^{256}-1键k'\neq k没有将m_1映射到t_1而m_2映射到t_2的概率是(1-2^{-(2*256)})^{2^{256}-1} (这里外部256指数来自键空间的大小)。所以，存在一个键k'映射m_1到t_1，m_2映射到t_2的概率是1-(1-2^{-(2\cdot 256)})^{2^{256}-1} \approx \frac{2^{256}-1}{2^{2\cdot 256}}\approx 2^{-256}.。