假定它是基于AES-256加密的哈希(可能是因为它是硬件加速的,但没有标准哈希);并且使用了Merkle–Damgård结构,即将消息填充到$ n $填充的消息块$ M_i $中(附加到消息1,最小数目为0和64位消息长度,以位为单位) ,以及根据




Davies-Meyer的构造的压缩函数,用于具有256位块$ M_i $的128位哈希,即

$ H_0 $设置为一个128位无内容的常量;
对于$ i $从$ 0 $到$ n-1 $:
$ \ text {} H_ {i + 1} = \ text {AES-256} _ {M_i}(H_i)\ oplus H_i $
结果为$ H_n $;



Hirose(FSE 2006),用于具有128位块$ M_i $的256位哈希,即

$ G_0 $和$ H_0 $设置为128位none-up-my -sleves常量;
用于$ i $从$ 0 $到$ n-1 $(其中$ C $为非零的我的袖子128位常量)
$ \ text { } \ begin {align *}
G_ {i + 1}&= \文本{AES-256} _ {H_i || M_i}(G_i)\ oplus G_i \\
H_ {i + 1 }&= \ text {AES-256} _ {H_i || M_i}(G_i \ oplus C)\ oplus(G_i \ oplus C)
\ end {align *} $
结果为$ G_ n || H_n $。



请注意,在这两种构造中,对手可以操纵的消息都被输入到密码的密钥输入中,从而使-

问题:在这些情况下,是否存在任何已知或可预见的AES-256相关密钥弱点可被利用或严重威胁?

如果是,我们是否有其他散列结构中,AES(任何大小)相关的关键弱点将不再引起人们的关注吗?

注意:对于128位哈希,我们期望相当于$ 2 ^ {64} $加密的工作量会显示冲突(可以有效分配,请参阅使用密码分析应用程序的并行冲突搜索);和$ \ min(2 ^ {128},2 ^ {129} / n + 2 ^ {65})$加密来显示(第二个)原像(通过对RD Dean归因于Merkle–Damgård哈希的一般攻击) 1999年的论文(第5.3.1节),由J. Kelsey和B. Schneier更好地进行了披露和完善,该书在关于小于2n工作的n位哈希函数的第二张原像中提供。至少相当于$ 2 ^ {128} $加密才能产生冲突,而付出更多的努力来展现原像。

#1 楼

在我的博士论文中,总结了对AES-256的最有效的相关密钥攻击以及由此产生的弱点基于AES-256的哈希函数。尽管对散列函数的冲突和映像前攻击还遥不可及,但这些函数的组件仍会暴露一些良好的散列函数或随机预言不到的属性。

详细介绍关键AES-256的时间表允许进行许多相关的关键差分路径,最有可能的路径包括19个S盒(第96页),概率为2 ^ {-119} $。通过研究本实验的第一轮,可以获得基于AES-256的压缩函数的各种属性。
$$
F(IV,M)= AES_ {M}(IV)\ oplus IV
$$的持有概率很高。例如,一个人可以固定值$ \ Delta I $和$ \ Delta M $并产生许多伪冲突$ \ { (IV_i,M_i)\} $,使得对于所有$ i $:
$$
F(IV_i,M_i)= F(IV_i \ oplus \ Delta I,M_i \ oplus \ Delta M)。
$$

可以证明,用相同的$(\ Delta I,\ Delta M)$构造这样的伪冲突$ q $需要差不多$ 2 ^ {n} $的工作当$ q> 2 $时,而对于Davies-Meyer模式下的AES-256,复杂度约为$ q \ cdot 2 ^ {67} $。

这并不是对$ q> c $ 2的直接威胁。如果使用完全散列函数,恶意设计者可能会选择IV来最大化第一轮的差异属性。在无袖情况中,必须有一些允许较高概率的差分路径。

评论


$ \ begingroup $
我注意到您的一篇论文从以前的一篇文章中说,它“显示了在所选关键方案中对AES-256的实际攻击,这表明AES-256不能替代理想的密码。理论上合理的构造,例如Davies-Meyer模式”。你能对此发表评论吗?
$ \ endgroup $
–fgrieu♦
14年4月14日在18:20



$ \ begingroup $
这意味着,如果使用理想密码(= random cipher)实例化Davies-Meyer模式,则证明是安全的。但是,我们证明了AES-256具有难以为理想密码构建的属性,但对于AES-256则更容易。
$ \ endgroup $
–德米特里·霍夫拉托维奇(Dmitry Khovratovich)
14年4月15日在10:58

$ \ begingroup $
因此,对AES-256的成功攻击会使基于理想密码模型的论点/安全性证明无效,但不会转化为我们知道的直接攻击,对吗? -关于您的答案中探讨的攻击:哈希表的设计者选择$ IV $的能力比用户能做的有显着优势:随机尝试$ M_0 $直到得到的$ H_1 $具有所需的属性?并且您能详细说明假设设法使$ IV $或$ H_1 $达到正确值之后所取得的成就吗?
$ \ endgroup $
–fgrieu♦
14-4-15在11:42



$ \ begingroup $
1.正确2.是,明显的优势。我们可以生成许多弱IV,从而可以实现高概率的微分。我无法立即告诉您几率和几率,但是可以通过论文计算得出。
$ \ endgroup $
–德米特里·霍夫拉托维奇(Dmitry Khovratovich)
2014年4月15日12:10

#2 楼

我不知道对这些方案的任何实际攻击都会破坏抗碰撞性或图像前抵抗性,但是对AES的相关密钥攻击仍然令人担忧。从这种意义上说,Miyaguchi-Preneel哈希结构更好,因为攻击者无法直接控制输入到密钥输入中的任何内容。

Miyaguchi-Preneel如下所示。请注意,该消息将纯文本输入输入到AES,而不是密钥输入。密钥由链接值驱动,这使攻击者很难对其进行控制。因此,Miyaguchi-Preneel似乎更能抵抗AES上的相关密钥攻击。与Davies-Meyer或Hirose相比,Miyaguchi-Preneel具有优势。不幸的是,Miyaguchi-Preneel仅给出128位哈希,因此比某些替代方案慢2倍。这可能使其在实践中没有吸引力。



评论


$ \ begingroup $
是的,对于AES,Miyaguchi-Preneel似乎更健壮:分组密码采用的是已知密钥设置,而不是选择密钥(Davies-Meyer)或半选择密钥(Hirose)。但是,Miyaguchi-Preneel仅给出了128位的哈希值(如今,它的耐碰撞性很窄),并且使用128位的块而不是Davies-Meyer的256位,从而使其效率降低了约2倍。如果我们有理由相信利用AES相关关键漏洞的攻击可能永远代价比预期的对蛮力攻击的抵抗力更高,那么这将是一项长期的高性能损失。
$ \ endgroup $
–fgrieu♦
2014年4月14日19:31