典型Sponge类密码算法的新型条件立方攻击
发布时间：2020-07-13 09:47
【摘要】：信息技术尤其是互联网的蓬勃发展,使得个体间的联系愈加密切,信息安全问题同时日益凸显,而密码学是信息安全的基石。密码算法可分为对称密码算法和非对称密码算法。对称密码算法包括分组密码、流密码、Hash函数、消息鉴别码(MAC)、认证加密算法等。SPONGE结构具有固定大小的内部状态,但可以处理任意长度的输入,生成任意给定长度的输出,近年来被广泛应用于Hash函数、MAC和认证加密算法等的设计。立方攻击由Dinur和Shamir在2009年欧密会上提出,将对称加密算法看作多项式系统,根据某些公开变量的乘积项(称为极大项),提取秘密变量(密钥)信息。黄森洋等在2017年欧密会上提出了条件立方攻击的方法,在第一轮中为公开变量添加关于密钥比特的控制条件,利用极大项的存在性恢复密钥信息。本文对几种典型的SPONGE类密码算法展开研究,分别给出了新型条件立方攻击。在对CAESAR认证加密竞赛获胜算法ASCON的研究中,建立了更为一般化的条件立方攻击模型。对代数表达式提取部分公因子,并根据每个公因子构造比特控制方程,加入功能性立方变量的调控,进而得到立方攻击区分器,给出了缩减为5轮、6轮、7轮ASCON初始化阶段的密钥恢复攻击,时间复杂度分别为224、240、2103.92。目前,本文提出的7轮理论攻击和6轮实际攻击是ASCON初始化阶段的最优分析结果。在对KECCAK相关算法的研究中,引入了混合整数线性规划(MILP)方法,丰富了KECCAK相关算法的自动化分析工具;提出了控制变量扩散的新模式,对变量的控制从第一轮延伸到了第二轮,扩展了分析轮数,大幅降低了KEECCAK相关算法的分析难度。系列分析结果包括美国国家标准与技术研究院(NIST)标准KMAC256、KECCAK-MAC-384/-512和CAESAR认证加密竞赛第三轮候选算法KETJE等缩减版本的(新型)条件立方攻击。·缩减轮数Ascon的密钥分割与条件立方攻击认证加密算法AsCON是CAESAR认证加密竞赛获胜算法之一。Dinur等在2015年欧密会上首次提出了类立方的密码分析方法,要求立方变量在第一轮中两两不乘,并应用于带密钥模式、状态大小为1600比特的KECCAK算法。在2015年CT-RSA会议上,Dobraunig等将类立方的密码分析方法用于5轮、6轮ASCON算法。在原有的密钥恢复攻击工作中,对ASCON算法进行密钥恢复攻击的最高轮数是6轮,而对于带密钥模式、状态大小为1600比特的KECCAK算法(包括KECCAK-MAC、KEYAK),其密钥恢复攻击的最高轮数大于等于7轮。究其原因,ASCON算法状态大小为320比特,远远小于1600比特,且具有更为复杂的非线性层设计,所以攻击者很难找到足够数量的在第一轮两两不乘的立方变量,因此其密钥恢复攻击的轮数较KECCAK算法更短。针对条件立方攻击,本文提出了更为一般化的模型。在对5轮、6轮ASCON的分析中,找到了新的立方变量集合,而其所依赖的条件只与密钥比特有关,在原有的工作中,对6轮ASCON进行密钥恢复攻击的时间复杂度为266,为理论分析结果,本文给出了时间复杂度为240的6轮实际攻击。此外,提出了7轮ASCON的密钥恢复攻击:引入基于密钥分割的条件立方攻击方法,基于不同的密钥条件,将整个密钥空间分为多个子空间;对于每个密钥子空间,建立不同的立方区分器,确定当前密钥是否属于此密钥子空间;以此类推,检测完成所有密钥子空间,从而可以完全恢复整个密钥空间。7轮ASCON密钥恢复攻击的时间复杂度大约为2103.9,特别地,对于一个大小为2117的弱密钥集,可以实施更为高效的攻击,时间复杂度为277。将ASCON初始化阶段的密钥恢复攻击延长了一轮。·缩减轮数Keccak(密钥模式)的新型条件立方攻击及MILP模型KECCAK算法是一族SPONGE函数,具有状态大小不同的7种置换部件。美国国家标准与技术研究院(NIST)发布的最新Hash函数标准SHA-3即基于KECCAK算法。在2017年欧密会上,针对带密钥模式的KECCAK算法,黄森洋等提出了一种高效的密钥恢复攻击方法,即条件立方攻击。通过设置比特条件,有效控制了条件立方变量的扩散;然后通过一种贪婪算法,逐一添加普通立方变量,最终找到满足如下要求的足够数量的普通立方变量:首先所有立方变量在第一轮中两两不乘,其次普通立方变量在第二轮中与条件立方变量不乘。利用立方变量的乘积项(极大项)的存在性恢复密钥信息:若输出中存在极大项,则密钥比特条件不成立;若输出中不存在极大项,则判断密钥比特条件成立。其中,找到足够数量的普通立方变量是条件立方攻击成功的关键。事实上,在逐一添加普通立方变量的过程中,新添加的普通立方变量有可能与很多待选比特在第一轮中相乘,所以添加这一个变量有可能导致很多变量无法被选,这无疑是一种损失。本文引入一种新的混合整数线性规划(MILP)模型,用于搜索足够数量的普通立方变量。将普通立方变量的扩散控制纳入规划模型,统筹处理立方变量的选取。同时将普通立方变量第一轮中两两不乘,第二轮中与条件立方变量不乘的性质纳入规划模型。事实上,模型中使用一系列线性不等式,准确刻画选取普通立方变量的要求。设置目标为求解普通立方变量的最大数目,求解MILP问题给出的最优结果优于原有结果。新的MILP模型利用统筹优化的方法,将之前对于KECCAK-MAC-384和KECCAK-MAC-512的密钥恢复攻击结果都延长了一轮,达到了7轮KEECCAK-MAC-384和6轮KECCAK-MAC-512的密钥恢复攻击,复杂度分别为275和258.3。对于认证加密算法KETJE MAJOR,其状态大小为1600比特,如果初始状态中的自由消息长度不小于704比特,那么可以达到7轮的攻击。对于认证加密算法KETJE MINOR,其状态大小为800比特,使用6-6-6扩散模式的条件立方变量,可以实施7轮密钥恢复攻击。2018年亚密会上,宋凌等提出了改进的MILP模型,降低了6轮KECCAK-MAC-512密钥恢复攻击的复杂度。事实上,在带密钥模式KECCAK相关算法当中,有一些自由度非常低的算法实例。对于这些算法,攻击者即使利用MILP模型也无法找到足够数量的普通立方变量,从而无法实施条件立方攻击。本文提出了一种新型条件立方攻击。首先,去除立方变量在第一轮中相互不乘的限制,于是,第一轮的输出中存在一些二次项。其次,引入一些新的比特条件,使得在第二轮中所有二次项不与其他立方变量相乘,因此第二轮的输出中不存在三次项。此外,引入“核心二次项”的概念,构建新的扩散模式,即“6-2-2模式”,这些显著地控制了二次项的扩散,对于核心二次项来说,甚至将第二轮的θ运算限制成为恒等变换。综上,与之前的条件立方变量相比,核心二次项的分布更加稀疏,因此普通立方变量的选取有了更高的自由度,此外,第二轮中消除三次项所使用的比特条件数目显著减少。继续使用MILP方法搜索立方变量,对自由度非常低的带密钥模式KECCAK相关算法,也成功实施了新型条件立方攻击。通过新型条件立方攻击的研究,将7轮KECCAK-MAC-512和7轮KETJE SR v2密钥恢复攻击的时间复杂度分别由2111和299降低到了272和277。此外,9轮KMAC256和7轮KETJE SR v1密钥恢复攻击的时间复杂度也得到不同程度的降低。将KEECCAK-MAC-512和KETJE SR v2的条件立方攻击延长了一轮。在试验验证中,给出了6轮KEETJE Sr v1和v2密钥恢复的实际攻击。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TN918.1
【图文】：
Ｋｅｔｊｅ采用的是基于ＭｏｎｋｅｙＤｕｐｌｅｘ［２１的ＭｏｎｋｅｙＷｒａｐ认证加密模逡逑式，包含四部分：初始化，相关数据处理，明文处理和终结部分。忽略终逡逑结部分的Ｋｅｔｊｅ邋ｖ２算法如图２．６所示，其置换函数是由Ｋｅｃｃａｋ－ｐ调整得逡逑来的邋ＫＥＣＣＡＫ－ｐ＊，ＫＥＣＣＡＫ－ｐ＊［６］＝７ｒ0ＫＥＣＣＡＫ－ｐ［６］0７ｒ＿１，目的是高效地重排逡逑状态比特。如图２．７所示，７Ｔ的逆为７Ｔ－１邋：逦＋邋３|幔唬蒎澹藉瓮迹玻吨校义希
本文编号：2753293
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2019
【分类号】：TN918.1
【图文】：
Ｋｅｔｊｅ采用的是基于ＭｏｎｋｅｙＤｕｐｌｅｘ［２１的ＭｏｎｋｅｙＷｒａｐ认证加密模逡逑式，包含四部分：初始化，相关数据处理，明文处理和终结部分。忽略终逡逑结部分的Ｋｅｔｊｅ邋ｖ２算法如图２．６所示，其置换函数是由Ｋｅｃｃａｋ－ｐ调整得逡逑来的邋ＫＥＣＣＡＫ－ｐ＊，ＫＥＣＣＡＫ－ｐ＊［６］＝７ｒ0ＫＥＣＣＡＫ－ｐ［６］0７ｒ＿１，目的是高效地重排逡逑状态比特。如图２．７所示，７Ｔ的逆为７Ｔ－１邋：逦＋邋３|幔唬蒎澹藉瓮迹玻吨校义希
本文编号：2753293
本文链接：https://www.wllwen.com/kejilunwen/xinxigongchenglunwen/2753293.html
