半随机输入破键散列函数

Question

假设我们有键散列函数，它将256-bit输入转换为256-bit输出，而攻击者知道密钥(假设键是256-bit long)。现在，让我们考虑构建一个输入块，如下所示：

• 128-bit消息(第一位)，
• 128随机比特(最后一次128比特)。

现在输出可以是随机的。我认为找不到128-bit消息的方法。我说的对吗？在这种情况下信息安全吗？

Answer 1

如果我们考虑具有\ell=256键空间的键控哈希函数，则可以将其形式化为

H(k,m): \{0,1\}^{\ell} \times \{0,1\}^{256} \to \{0,1\}^{256}

现在假设H是一个加密安全的密钥哈希函数。该哈希具有预图像、第二预图像和碰撞电阻。该哈希函数的密码强度与HMAC类似，强度取决于所使用的秘密密钥的大小。假设我们有足够好的来自蛮力的键大小，\ell > 128和H没有其他的弱点。

现在，假设攻击者知道密钥，在本例中，它只是一个常见的散列函数。

我认为找不到128位信息的方法。我说的对吗？在这种情况下信息安全吗？

要找到实际消息，攻击者需要执行图像前攻击。这需要花费\mathcal{O}(2^{256})，因为攻击者知道关键所在。图像前攻击可以返回输入x，这样H(x) = target和x可以不同于128位消息，也可以返回多条目标消息。

攻击者有一个更好的方法，因为输入是128位.他们可以搜索128位。128位仍然超出搜索范围，被认为是安全的.比特币矿商的集体力量可以在一年内到达\approx 2^{92}，人们仍然需要2^{36}年才能达到128位搜索。在这个计算中，随机128位被丢弃，因为它不是安全性的一部分.如果随机被认为是秘密(不应该)，那么攻击者的工作就是预先图像。

现在输出可能是随机的

我们期望哈希函数有雪崩准则，也就是输入中的一些变化，应该以50%的概率翻转每个输出位。雪崩准则是一个重要的设计准则，因为如果发生一些变化，可能更容易发现一些碰撞。

特别注意:将键控哈希函数的键固定起来需要进行特殊的分析。有些键可以将哈希函数转换为弱哈希函数。因为我们不知道散列函数和键，所以我们不能谈论这个。