SHAvite算法的各种密码分析方法全面盘点

SHAvite算法的各种密码分析方法全面盘点一、算法背景SHAvite-3是由Eli Biham和Orr Dunkelman设计的SHA-3竞赛第二轮候选算法基于HAIFA迭代框架和AES组件构建。其压缩函数采用Davies-Meyer模式底层分组密码是一个广义Feistel结构轮函数基于完整的AES轮。SHAvite-3包含两个实例SHAvite-3-256输出224/256位12轮和SHAvite-3-512输出384/512位14轮。在SHA-3竞赛第一轮后由于Peyrin发现了选择盐和选择计数器的碰撞攻击压缩函数被微调以增强安全性。以下按攻击类型对SHAvite-3的密码分析结果进行分类梳理。二、针对完整哈希函数的分析1.第二原像攻击Gauravaram等人2010对SHAvite-3-512的10轮缩减版本实施了第二原像攻击。该攻击的复杂度为2⁴⁹⁷次压缩函数调用内存需求仅为2¹⁶。这一结果基于对Bouillaguet等人先前工作的改进——后者曾利用广义Feistel结构上的“抵消性质”cancellation property对9轮SHAvite-3-512实施第二原像攻击复杂度约为2⁴⁴⁸。2.选择盐第二原像攻击针对完整14轮压缩函数Gauravaram等人给出了一个选择计数器、选择盐的原像攻击复杂度为2³⁸⁴次压缩函数调用和2¹²⁸内存若不使用内存则复杂度升至2⁴⁴⁸。该攻击利用了SHAvite-3压缩函数的抵消性质当两个轮函数的内部密钥满足特定关系时非线性组件的效果可以被抵消从而将输出表达为输入的一个相对简单的函数再通过逆推求解。三、针对压缩函数和分组密码的分析1.碰撞攻击针对完整14轮压缩函数Gauravaram等人提出了一个碰撞攻击复杂度为2¹⁹²次压缩函数调用和2¹²⁸内存。该攻击同样基于选择计数器和选择盐的框架利用抵消路径在两个方向同时构造满足碰撞条件的输入对。2.伪原像攻击Leurent等人FSE 2010报告了对完整14轮SHAvite-3-512压缩函数的伪原像攻击复杂度约为2³⁸⁴级别内存需求为2¹²⁸。此外文献中还指出SHAvite-3压缩函数存在大量零伪原像这是一个值得关注的结构性属性。不过这些零伪原像需要使用特定的计数器值而该计数器值仅用于最后一个消息块在最终块中伪原像似乎无法构造因此该结果不构成对哈希函数本身的直接威胁。3.自由启动碰撞Minier、Naya-Plasencia和PeyrinFSE 2011对第二轮微调后的SHAvite-3-256进行了首次独立分析。他们利用回弹攻击和Super-Sbox密码分析技术实现了针对7轮缩减压缩函数的自由启动碰撞攻击。自由启动碰撞是指攻击者可以完全控制进入压缩函数的链变量。4.区分攻击同一研究还给出了选择相关盐区分攻击可区分多达8轮共12轮的SHAvite-3-256压缩函数。该攻击的核心思想是精心控制内部密码密钥调度中的差分利用回弹攻击在差分路径中间部分消耗自由度从而以较低复杂度找到满足条件的差分对。5.积分攻击与不可能差分Bouillaguet等人利用广义Feistel结构上的积分攻击对9轮SHAvite-3-512实施了攻击这是对该哈希函数最早的密码分析结果之一且同时适用于微调前后的版本。此外设计文档中报告了针对底层分组密码的不可能差分区分器SHAvite-3-256的分组密码存在5轮不可能差分SHAvite-3-512的分组密码存在9轮不可能差分。四、主要分析方法总结攻击类型目标缩减轮数复杂度内存代表工作第二原像SHAvite-3-512哈希函数10/142⁴⁹⁷2¹⁶Gauravaram et al.选择盐原像完整压缩函数14/142³⁸⁴2¹²⁸Gauravaram et al.碰撞完整压缩函数14/142¹⁹²2¹²⁸Gauravaram et al.伪原像完整压缩函数14/14~2³⁸⁴2¹²⁸Leurent et al.自由启动碰撞SHAvite-3-256压缩函数7/12——Minier et al.区分攻击SHAvite-3-256压缩函数8/12——Minier et al.积分攻击SHAvite-3-512哈希函数9/14——Bouillaguet et al.不可能差分分组密码5轮/9轮——设计文档五、安全性评估与总体结论从理论层面看SHAvite-3基于PGV5压缩函数和HAIFA迭代结构在底层分组密码理想化的假设下其碰撞抵抗性达到了最优安全界Θ(q²/2ⁿ)且哈希函数被证明与随机预言机不可区分。然而压缩函数本身由于存在不动点与随机预言机是容易区分的。在实际密码分析方面SHAvite-3的主要安全裕度体现在完整14轮压缩函数在2¹⁹²复杂度下可找到碰撞完整14轮的选择盐原像攻击复杂度为2³⁸⁴——这些结果虽然显著低于理想安全界对512位输出来说碰撞的理想复杂度应为2²⁵⁶但攻击均需要选择盐和选择计数器这一强假设条件在实际哈希函数的使用场景中通常不成立。针对完整哈希函数的最强攻击仅覆盖10/14轮未能突破完整轮数的安全防线。总体而言SHAvite-3在SHA-3竞赛中展现出了合理的安全裕度其密码分析结果主要集中在缩减轮版本或需要额外控制能力的压缩函数层面未发现对完整哈希函数的实用攻击。