SHA-3的安全定义在数量上意味着什么？

Question

在沙-3标准 (第31页)中，SHA-3的安全性是定量定义的，例如，他们说SHA3-256提供256位的预图像电阻。如何解释这个位数？

我所知道的预像电阻的定义并不是指位，而是指运行时t (以及成功概率\epsilon)。

直觉上，我会这样解释它:攻击者在运行t = 2^{256} \cdot t_H之后只能找到一个预映像(概率相当大)，其中t_H是计算一个散列所需的时间。对吗？

奖金:这有(可选的)来源吗？SHA-3标准的引用少得令人震惊，而Keccak标准根本没有提到预图像电阻。

Answer 1

Aleph的评论和指向Keccak参考的指针对回答这个问题有很大帮助(第9页)：

这里的关键词是“工作负载相当于N对\mathrm{Keccak-}f[r + c]或其逆调用”。Keccak置换的调用被用作时间单位。您的直觉认为，它是哈希函数调用离此不远，但请注意，单个SHA-3调用可能导致一个或多个置换调用，因此声明1更严格。

在更抽象的背景下，我们谈论的是海绵结构，而不是像Keccak这样的具体实现，我们把置换(及其逆)说成是敌人可以随意调用的甲骨文(通常是人们所说的“查询”)。然后，根据对手提出的查询数量来表示结构的安全性。甲骨文调用被视为输出在恒定时间内随机排列的结果。

另见：Keccak团队对海绵功能的更通用的治疗。

Answer 2

如何解释这个位数？

在密码学中，我们讨论比特数。256位意味着您需要在2^{256}元素中搜索，或者说是256位搜索空间。

跑步时间是一个模糊的术语。你说的CPU、内存、计算机、服务器、硬件是什么？这和其他没有提到的可以改变运行时间。

预图像电阻的定义，即运行时间t (和成功概率\epsilon)。

它是运行时间的形式化，就像大号(\mathcal{O})符号在CS中所做的那样。我们考虑多项式时间对手，这样我们就为它们设置了一个界，否则我们就不能讨论无界对手。

因此，我们说多项式时间对手具有\epsilon优势。如果epsilon是可忽略，那么对手就没有优势。

在运行t = 2^{256} \cdot t_H之后，攻击者只能找到一个预图像(概率相当大)，其中t_H是计算一个散列所需的时间。对吗？

同样，在密码学中，在计算安全性时不考虑运行时间。然而，在设计时，人们考虑到快速和安全的算法更好。但是，这在哈希函数中有一个缺点，因为搜索预图像的时间更短。同样，对于块密码来说，更短的蛮力时间也是如此。

奖励：

在艾尔见罗格威。密码散列函数Basic，你已经看过了，还有一本好的密码书“卡兹-林德尔的书”.