为什么SHA-1算法有正好80轮?是为了减少碰撞?如果是,那么SHA-2和SHA-3的回合数为什么更少?

评论

注意,较大版本的SHA-2也有80发子弹。

SHA-2(SHA-256和SHA-224)具有64发子弹,是的较大版本具有80发子弹。

该线程中的答案还回答了一个更大的问题,即为什么我们首先要对分组密码和哈希函数进行取整。 TL; DR:更多回合意味着更多的扩散。更大的扩散意味着对差分密码分析攻击的更高抵抗力。更多的回合还意味着更高的计算成本。设计师寻找最佳选择。

#1 楼

大多数散列都是根据排列(如MD5,SHA-1和SHA-2中的键排列/块密码或Keccak / SHA-3和CubeHash中的无键排列)构建的。排列是输入的混洗。一旦有了良好的随机排列,就可以轻松地从中构建哈希。有关详细信息,请参见从维基百科上的块密码构造单向压缩函数。

类似地,您可以手工想到洗牌(除非使用的加密货币介于$ 2 ^ {128} $和$ 2 ^ { 512} $卡)。

改组的常见策略是多次通过牌组,每次都执行一堆简单的操作。每次穿过甲板都称为“回合”。

为什么SHA-2和SHA-3的回合数较少?

对于一回合来说,既可以选择执行更复杂的操作,从而获得更多的昂贵操作,也可以选择执行更简单,更便宜的操作,从而减少工作量。 SHA-1比SHA-2具有更简单的回合,因此需要更多回合才能正确地混合值。

设计对称图元的艺术,该对称原语可实现尽可能多的混合并尽可能便宜地进行操作。在这方面,SHA-2和SHA-3比SHA-1更好。

为什么要进行多轮攻击?

多轮攻击使加密分析攻击更加困难,但无济于事(很多)反对蛮力。尤其是,它增加了对称为差分密码分析的技术的抵抗力,该技术是一种用于攻击哈希和分组密码的流行技术。您可以定义卡座的功能,例如将两个特定的卡紧挨着放置。穿过甲板一次后,该功能可能会以10%的较高概率保留。多次经过套牌后,某个特征全部幸存的概率呈指数下降。因此,处于最终状态的特征的概率将很快接近理想概率。

在密码分析中,您可以定义类似的特征,称为“差异特征”。一轮以一定概率保留此特征。例如,如果某个特征以$ 10 ^ {-3} $的概率幸存一轮,则它可能以$ 10 ^ {-3 \ cdot 80} = 10 ^ {-240} $的概率幸存了80回合。

如果您具有足够高的几率幸存下来的特征,通常可以利用它来更快地找到碰撞或原像。设计师的目标是进行足够的回合,利用这些混洗缺陷要比蛮力攻击要昂贵,同时要选择足够的回合以获得更好的性能。

(以上描述中有一些错误之处,但是我相信总体思路是正确的。)

SHA-1为什么要进行80发子弹?

更多的发子弹可以提高针对密码分析的安全性。但这也会降低性能。因此,有必要在安全性和性能之间找到折衷方案。 SHA-1的设计人员选择了80发子弹。

事后看来,他们选择了一个过低的值,因为自那时以来,我们发现针对SHA-1的攻击比暴力攻击更快地发现了碰撞。

评论


$ \ begingroup $
另外,由于状态由5个单词组成,因此舍入计数为5的倍数
$ \ endgroup $
– Richie车架
2014年3月14日在9:42

$ \ begingroup $
作为对加密货币不太熟悉的人,这是一个写得很好的解释。
$ \ endgroup $
– Etheryte
14年3月14日在11:23

$ \ begingroup $
关于差分密码分析的Wiki页上有一个实际的例子,它给出了更多回合,给出了更高的扩散率:“攻击的早期目标是FEAL分组密码。最初建议的四回合版本(FEAL-4)可以使用只有八个选定的明文,甚至是FEAL的31轮版本都容易受到攻击。”
$ \ endgroup $
– Tejas Shah
20年5月7日在16:12



#2 楼

在散列函数(和类似的分组密码)中,每轮将非线性函数应用于其输入。向后计算该函数有些困难(它需要一些其他属性,但让我们保留它)。这一概念称为扩散。

另一方面,密码分析的目标之一是逆转这种扩散,以便在散列函数中找到冲突或破坏分组密码。例如,使用线性密码分析和差分密码分析之类的方法来实现此目标。

因此,通常,使用更多的回合意味着“应用更多的扩散”,从而使密码分析更加困难。但是,还有一个折衷,就是额外的回合需要更多的时间来计算。尤其是对于散列函数和对称密码,速度是一个值得关注的问题,而性能(通常以每秒处理的位或类似比特数衡量)很重要。找到安全性和性能之间的“最佳”权衡。最优在这里是一个非常不确定的陈述,因为针对密码分析(尤其是针对未知攻击)的安全性很难衡量。

答案是“有人认为80发就足够了”。这可能是基于经验,粗略估计或仅因为数字80看起来不错。当然,这种选择背后有一些想法,但是如果不参与决策过程,我们就无法确定。从今天的角度来看,此选择太低,因为SHA-1被认为已损坏。这是因为发现了一个弱点,那在当时是未知的。


是否可以减少碰撞?


当然可以。这就是密码哈希函数的目标。但是,正如我所说的,轮次的选择取决于安全性和性能之间的权衡。由于抗碰撞性也意味着原像抗性,因此重点确实放在抗碰撞性上。今天,我们认为,一旦失去对collisin的抵抗力,哈希函数就被破坏了。例如,SHA-1和MD5在耐碰撞性方面被认为是损坏的。据我所知,两者的原像电阻仍然没有被破坏,但是通常不建议再使用它们。


如果是,那么为什么选择SHA-2和SHA -3轮数较少?


每个哈希函数对轮函数的选择都不同,并且如果轮函数更有效地实现了扩散目标,则更少轮是必需的。但是所有这些哈希函数都是在不同的时间设计的,并且在密码分析和哈希函数设计方面都有进步。总的来说,我想说它们是不可比的。对于每个哈希函数,相应的设计人员根据自己的原因做出选择。不能有任何理由说明为什么在不同的散列函数中进行更多或更少的回合会更好。

评论


$ \ begingroup $
在分组密码中,每个舍入函数实际上都是一个双射,通常,逆运算(几乎)与原始逆运算一样容易。在基于块密码的哈希函数(如SHA-1和SHA-2)中,它是相同的。
$ \ endgroup $
–PaŭloEbermann
2014年3月13日在16:00

$ \ begingroup $
如果您认为子键是固定的,则Feistel网络中的F函数只是一个双射,否则就是$ X + Y $位输入和$ X $位输出。因此,如果您知道相应的子项,那么这只是一个双射(但如果您进行密码分析,则没有)。考虑到哈希函数,这也不是正确的,例如SHA-1中的F函数将$ 3 \ cdot 32 $位输入并返回$ 32 $位输出。
$ \ endgroup $
– tylo
2014年3月13日在16:52



$ \ begingroup $
一般而言,只有在以下情况下,证明双射很容易向后计算的说法才是有效的:a)非线性程度低(例如,表示为低次多项式)b)以这种方式设计(例如具有a的分组密码)固定键用作1个功能)c)您仅可以拥有一个用于所有输入/输出的查找表。
$ \ endgroup $
– tylo
2014年3月13日在17:02



$ \ begingroup $
是的,不是每个“回合”函数都是双射的。我想我在这里从AES概括了太多。
$ \ endgroup $
–PaŭloEbermann
2014年3月13日19:02

$ \ begingroup $
@PaŭloEbermann:在大多数情况下,由于mixcolumns矩阵中的“更差”系数,甚至AES都比加密更难解密。 @ Tylo:v小调-'数字80看上去很好'->'nice';如果您想改善答案(这已经很好),可以在“减少冲突的过程”部分中进行详细说明
$ \ endgroup $
–密码学家
2014年3月14日在9:22

#3 楼

正如其他答案已经提到的那样,这是在许多简单回合或几个复杂回合之间的折衷。

但是请考虑一下,加密设计的挑战之一是使某些东西易于在硬件中实现。即使运行了很多回合,简单的算法也不会占用很大的芯片空间。 SHA-1可以连续80次重复使用同一电路,从而使硬件成本降至最低。如果需要最高的吞吐量,芯片设计人员可以将基本的SHA-1电路复制80次,然后将它们流水线在一起。