论文部分内容阅读
在众多的分组密码分析方法之中,不可能差分分析是被广泛应用的经典分析方法。本文针对SPN密码的不可能差分分析展开研究。一方面探索可以降低攻击方案复杂度的不可能差分技术,另一方面研究SPN密码不可能差分的长度上界。首先,利用SPN密码中的新型结构特性,针对最近提出的密码算法Fork AES、Twe AES和Saturnin进行了不可能差分分析,评估了新型密码抵抗不可能差分的安全性;其次,提出差分强遍历函数簇的概念,在S盒是差分强遍历函数簇的条件下,研究了相应的SPN密码、广义类AES密码的不可能差分长度上界。本文取得的研究成果如下:提出了Fork AES-*-5-4算法的通用不可能差分攻击方案。Fork AES是一种运用新型“分叉结构”的分组密码,我们利用分叉特性构造了两类不可能差分区分器。基于两类截断差分值不同的调柄,构造两条攻击路径并提出了对Fork AES的多重不可能差分攻击。利用多条攻击路径,不仅可以得到更多的轮密钥字节,而且在不增加时间复杂度情况下,可以提高对错误轮密钥的筛选效率。此外,我们研究了主密钥恢复过程,可以高效地排除错误候选密钥,进一步降低了攻击方案的复杂度。该攻击方案适用于加密查询和重构查询这两种模式,故攻击者不必因模式不同,重新设计其它的攻击方案。与已有结果相比,本文的攻击方案在加密模式下多攻击了一轮,即在加密模式下首次提出了Fork AES-*-5-4的攻击方案。提出了Twe AES算法的最优不可能差分攻击方案。首先,根据Twe AES算法的具体调柄生成过程,构造了两类6轮不可能差分区分器,往前后各扩展一轮可得两条8轮不可能差分攻击路径,每条攻击路径需要攻击14字节密钥。值得注意的是,这两条攻击路径不仅具有相同明文结构,而且拥有12字节公共密钥。利用这两点特征,可以提高对子密钥的筛选效率。其次,利用密钥生成算法的不完全性,有针对性地选择子密钥字节。利用子密钥之间的相关性,提高主密钥恢复效率。最后,针对这一类不可能差分攻击方案,证明了时间复杂度存在最小值,并利用插值拟合对最小值进行求解。本文攻击方案在时间、数据、存储复杂度的结果上均有所改进,得到了迄今为止对8轮Twe AES密码分析的最好结果。提出了对Saturnin算法的最优不可能差分分析。针对Saturnin算法的不可能差分分析,设计报告中只构造了两条3.5轮的不可能差分区分器,设计者们声称“我们构造的攻击路径均需要攻击全部密钥,我们认为可能可以设计出4轮或4.5轮的不可能差分攻击方案,但是到目前为止还没达成这个目标。”为弥补这个安全性缺项,我们对Saturnin算法进行不可能差分分析。首先,基于Saturnin算法的结构特性,提出并证明了Saturnin算法3.5轮不可能差分区分器的充分条件,基于此可以快速构造270.1个截断式不可能差分区分器。其次,从构造的270.1个区分器中,有针对性地挑选了64个区分器并分成了四类。将四类区分器往前扩展两轮可得四条5.5轮攻击路径,且这四条攻击路径均不需要攻击全部密钥。在设计攻击方案时,优先使用公共密钥较多的攻击路径,可以利用攻击路径中的公共密钥信息,进一步降低攻击方案的整体复杂度。结合上述多种改进方法,首次提出了对Saturnin算法的5.5轮不可能差分攻击方案。研究了基于特定S盒函数簇的SPN模型不可能差分的长度上界。不可能差分区分器的长度上界是评估分组密码安全性的重要指标之一。本文提出了S盒的差分强遍历函数簇的概念,当S盒是差分强遍历函数簇,且S盒的个数n与S盒的规模b满足限制条件n?2b-1-1时,可以得到相应的SPN密码的不可能差分上界。此外,对于广义类AES密码,放宽了S盒规模与个数之间的限制条件,并以轻量级分组密码Saturnin模型为实例,证明了其不可能差分的长度上界。与已有结果相比,本文的工作放宽了相应的证明条件,也进一步揭示了S盒部件如何影响不可能差分长度。对于SPN密码抵抗不可能差分的设计与分析,本文结论具有实际的应用价值。