论文部分内容阅读
随着互联网行业的迅猛发展,信息安全的重要性日益凸显,教育部增设了“网络空间安全”一级学科。密码学作为网络空间安全的核心支撑技术,在网络空间安全中发挥着重要的作用。对称密码算法是密码学中的重要组成部分,对称密码包括分组密码、流密码、哈希函数、消息认证码和认证加密算法等。KECCAK是美国国家标准与技术研究院(NIST)征集并选出的新一代的哈希函数标准SHA-3的获胜算法,在密码学研究领域占据着相当重要的地位。认证加密算法能同时保证消息的认证性与机密性,近年来征集新的认证加密算法标准的CAESAR竞赛也受到了世界各国密码学家的广泛关注。本文使用类立方攻击与条件立方攻击等方法,针对KECCAK的密钥模式KECCAK-MAC,以及基于KECCAK置换的KEYAk、KETJE等认证加密算法的安全性进行了分析,主要结果分为两个部分。第一部分,对CAESAR竞赛第三轮的候选算法KEYAK的轻量级版本RIVER KEYAK,我们使用条件立方攻击的方法,找到了一组扩散较弱的条件立方变量,成功地将条件立方攻击应用到了 RIVER KEYAK上,给出了约减为8轮的RIVER KEYAK的密钥恢复攻击,并给出了6、7轮密钥恢复攻击的验证实验,这是对约减轮的RIVER KEYAK的首个公开发表的密钥恢复分析结果;第二部分,针对填充较高或状态小而导致的可利用的自由度较低的KECCAK类算法,我们将类立方攻击与混合整数线性规划(MILP)相结合,提出了一个针对KECCAK的MILP自动化搜索的类立方攻击模型,并将其应用到KECCAK-MAC以及认证加密算法KEYAK和KETJE上。使用该模型,我们成功地将约减轮的KECCAK-MAC-512的密钥恢复攻击延长到了 7轮。两个工作结果均发表于 Designs,Codes and Cryptography(DCC)。·约减轮River Keyak的条件立方攻击KEYAK是由KECCAK团队设计的、提交给CEASAR竞赛的认证加密算法,并且是CAESAR竞赛第三轮的15个候选算法之一。KEYAK的轮函数基于 KECCAk-p 置换,有五个版本 RIVER KEYAk、LAKE KEYAk、SEA KEYAK、OCEAN KEYAK以及LUNAR KEYAk。RIVER KEYAK是唯一的轻量级版本,采用800比特的状态,它的密钥长度是可变的,最小为128比特,输出消息摘要长度为128比特而填充为256比特。立方攻击是由Dinur和Shamir提出的一种选择初始向量(IV)的密钥恢复攻击,并成功地应用于多种密码算法的分析。在2015年欧密会上,Dinur等人将分治法的思想与立方攻击相结合,提出了类立方攻击,并应用在了约减轮的KECCAK-MAC及LAKE KEYAK上;随后在2017年欧密会上,黄森洋等人提出了条件立方攻击,改进了 Dinur等人的分析结果。通过引入一些比特条件,黄等人选择满足特殊条件的一些比特作为条件立方变量,使立方变量的代数次数进一步降低。本文中针对轻量级的RIVER KEYAK,给出了约减轮的密钥恢复攻击。首先我们对800比特状态的RIVER KEYAK的轮函数,找到了一组新的条件立方变量,通过控制比特条件,大大降低了它们的扩散程度,使得它们在第一轮和第二轮都不与其他的立方变量相乘。然后找到了足够多的立方变量,进行了 6、7轮的密钥恢复攻击并给出了验证实验,时间复杂度分别为233和249。对于8轮的密钥恢复攻击,我们通过结合“线性结构体”技术,优化了搜索立方变量的方法,找到了 64个立方变量,将密钥恢复攻击扩展到了 8轮,时间复杂度为 281。·对Keccak密钥模式的类立方攻击的混合整数线性规划模型KECCAK是美国国家标准与技术研究院(NIST)征集的新一代哈希函数标准SHA-3的获胜算法,是几个最重要的密码学标准算法之一,同时也吸引了诸多密码学家的关注,也涌现了许多的分析结果。KECCAK采用海绵体结构,(默认)采用1600比特状态,对于参数n∈ {224,256,384,512},KECCAK-n采用c = 2n的填充及r = 1600-c的比特率,即c比特初始化为0而消息(IV)分割为r比特的数据块并依次介入到状态的前r比特,输出消息摘要长度为n比特。KECCAK的海绵体结构分为两个阶段,第一个阶段为吸收阶段,r比特的数据分组与状态的前r比特进行异或后进行24轮的KECCAK置换,之后再处理下一个r比特的消息分组直至所有的消息分组处理完毕;处理完消息后为第二个阶段即挤出阶段,KECCAK-n每次置换将状态的前r比特作为输出直至输出n比特消息摘要。带密钥的KECCAK即为KECCAK-MAC,KECCAK-MAC在初始化时将密钥级联在消息前作为输入。当n = 256时,2015年欧密会上,Dinur等人对KECCAK-MAC的密钥恢复攻击达到了 7轮;随后2017年欧密会上,黄森洋等人改进了 KECCAK-MAC 7轮攻击的复杂度,并将KECCAK-MAC-384攻击到了 6轮,而KECCAK-MAC-512的密钥恢复攻击仅为5轮;在2017年亚密会上,李铮等人改进了黄等人的条件立方攻击,将黄等人对KECCAK-MAC-384/512的密钥恢复攻击各增加了一轮。然而,对于KECCAK-MAC-512的密钥恢复攻击仍比其他参数下的攻击少一轮。近年来,密码学界发现许多经典的密码分析问题可以转化为数学上的最优解问题,越来越多的自动化搜索工具(求解器)被应用到密码分析领域,混合整数线性规划MILP(Mixed-Integer Linear Programming)是研究使用较为广泛的一种。混合整数线性规划是将限制条件刻画为线性等式或者不等式,在约束条件的限制下求解目标函数最大或最小整数解或者是判断目标函数有无解的求解器模型。MILP模型在密码学领域的研究应用十分广泛。在本文中,我们将混合整数线性规划引入到类立方攻击中,提出了一个针对KECCAK的类立方攻击的混合整数线性规划自动化搜索模型,大大降低了原类立方攻击的复杂度,并成功地将KECCAK-MAC-512的密钥恢复攻击扩展到了 7轮。同时,我们将该自动化搜索模型应用到基于KECCAK的认证加密算法KEYAK和KETJE上,分析结果表明,与黄等人的条件立方攻击相比,我们的攻击模型在填充较高、可利用的自由比特较少的情况下有优势。