迭代散列增加安全位数？

Question

根据WhatsApp安全白皮书的说法，Whatsapp对用户的公钥和身份使用5200次SHA-512迭代。

我想知道为什么？

根据：为什么在计算信号中的安全数字时迭代5200次？，这个问题的信息Security.SE:它是增加安全比特到112。

我理解为什么30位数有\approx 99位熵，所以\approx 99安全位。

\log_2(10)*30 \approx 99

但是迭代散列是如何影响安全性的呢？据我所知，它不影响熵。

文章中的数学确实表明：

\log_2(10^{30} * 5200) \approx 112。在keylength.com上推荐的安全位数。

此外，信号源代码注释也在源代码上声明

我在哪里能读到更多关于为什么'5200‘哈希作为乘法放在'log’中的迭代，以及为什么它会影响安全位呢？

Answer 1

迭代散列如何影响安全性(以位为单位)？

它通过增加通过蛮力解决问题可能需要的操作数来做到这一点，因为操作是每次尝试中断时迭代的操作。

(迭代散列)不影响熵。

实际上，迭代散列不会增加熵。它仍然可以增加安全性。

n-bit安全性意味着对手需要执行2^n操作才能破坏系统。

是的，对于某种操作的定义，以及打破系统的确定性。

如果对N操作的攻击成功的概率为p，并且p与N线性增长，直到p=1作为密钥搜索，那么系统最多有n=\log_2(N/p)=\log_2(N)-\log_2(p)\text{ bit security}

这个公式适用于低p和任何N\ge1。通常，当p只与N线性增长时，它也被使用，直到p达到不可忽略的值，例如在图像前搜索中的p=e^{-N_0/N}。

问题是Whatsapp系统将32字节ECC公钥重新格式化为几乎均匀分布的30位数字字符串。主要的设计目标是很难生成一个私钥，它将公钥重新格式匹配到一个(或多个)给定的字符串，该字符串是通过重新格式化一个(或多个)目标公钥(S)获得的；也就是说，使第二次图像前搜索变得困难。

针对该系统的暴力预图像攻击生成密钥对；使用SHA-512对公钥进行5200次散列；并对目标值进行测试(S)。每个私钥测试都有匹配给定字符串的概率p=10^{-30}。每个测试需要5200次SHA-512迭代，而其他测试则相对较少(私钥的增量，对前一个公钥添加一个常数点，通常与部分SHA-512散列的模块缩减模10^5的给定字符串的5位数字进行比较(最多为6) )。

因此，当以SHA-512散列计算成本时，安全性是\log_2(5200)+30\log_2(10)\approx112.00-bit，这是这里的自然度量，并且只有一个目标键。对于s目标字符串/键，每个测试成功的概率增加了一个因子s，因此\log_2(s)比特降低了安全性。

备注：

这个答案的一个原版本是关于在密码系统中随着迭代次数的增加而增加的安全性，在密码系统中，除了迭代散列之外，还有相当多的其他操作。这与问题的上下文无关，因此被删除了。

1:最简单的迭代散列形式，包括问题中的Whatsapp上下文中的形式，甚至稍微降低了熵；参见这。

Answer 2

不幸的是，你提到的答案是误导人的。此外，源代码中的注释也具有误导性。你提到的答案并不是说熵更高。它使用了一些不标准的、误导性的安全条款。有些人使用措辞的安全强度，这大致意味着用暴力破坏这个算法--强迫一个人需要尝试2^(那麽多)值。答案的作者的意思是，使用迭代计算哈希所需的CPU时间与对较长哈希的单个计算大致相同。

但是熵只取决于散列空间的大小。尤其是哈希碰撞的概率保持不变。

我现在回答了你提到的问题(见你的链接和我的答案)，希望我能更好地解释一些人所说的这种误导的措辞是什么意思。