分组密码的密钥编排方案研究及单密钥攻击研究

发布时间：2018-03-31 17:41

本文选题：分组密码　切入点：密钥编排方案　出处：《上海交通大学》2014年博士论文

【摘要】：作为最重要的对称密码算法之一,分组密码算法由于运行速度快,软硬件实现方便,适用于加密大数据量等特点,在实际安全领域中应用广泛。作为这些领域中的核心算法,分组密码的设计和安全性评估近几十年来一直是密码学者研究的热点。安全而高效的分组密码是研究的重中之重。分组密码的实际安全性基于其抵抗密码攻击的能力。多数密码攻击技术利用密码结构和轮函数本身的弱点,如线性攻击,差分攻击等。而作为分组密码中不可或缺的独立模块,近年来密钥编排方案在攻击中所起的作用逐渐被重视,涌现了一些新兴的利用密钥编排方案弱点的攻击,如中间相遇攻击及其变体。尽管如此,和密码结构和轮函数相比,针对密钥编排方案设计的研究相对较少。当前多数的设计准则都是针对密码结构和轮函数提出的,对密钥编排方案缺乏具有实际指导意义的设计准则。本文的研究对象为分组密码,重点研究密钥编排方案对密码安全性的影响,同时也研究不考虑密钥编排方案影响的单密钥攻击技术。研究贡献主要分为两大块。第一块贡献是研究受密钥编排方案影响的攻击和避免这些攻击的设计准则,包括如何利用密钥编排方案的弱点获得更好的攻击结果、如何设计安全高效的密钥编排方案,以及给出具体的设计实例。这部分研究成果为密钥编排方案的设计提供了新的指导思想。具体研究成果及创新性如下:1.探讨密钥编排方案在密码攻击技术中所处的地位。首先,定义实际密钥信息(actual key information,AKI),用于精确刻画密钥编排方案的弱点导致实际攻击的一般规律。我们发现,多数和密钥编排方案相关的攻击均利用了计算路径上实际密钥信息AKI不足这一弱点。而AKI不足的一个重要原因是密钥编排方案的扩散层和算法轮函数的扩散层存在相互作用,从而导致了计算路径上密钥比特信息的泄露。在此基础上,本文提出一个密钥编排方案设计准则以避免密钥比特泄漏现象,为分组密码轮函数和密钥编排方案扩散层的设计提供科学依据。同时,本文开发出一个高效的密钥编排方案检测工具来自动搜索密钥编排方案的弱点。对攻击者而言,该工具可以用于检测现有密码的安全漏洞,从而进行攻击。对设计者而言,该工具可以用于检测设计中的密钥编排方案,为构造安全有效的密钥编排方案提供实际保障。2.基于上述研究成果给出实际的攻击范例,利用AKI不足的计算路径获得了对多个分组密码的新的攻击结果。包括,优化了Serpent中间相遇攻击的时间复杂度,优化了AES-256中间相遇攻击的内存复杂度,延伸了一轮对Safer++256的积分攻击,给出了TWINE-80的首个具有极低数据复杂度的攻击;发现了对XTEA的一个新的中间相遇攻击,该攻击结果和XTEA现有最好的攻击结果相当,但攻击过程更简单。3.给出AES的一个新的密钥编排方案设计,该设计提高了AES在单密钥和相关密钥攻击模型下的安全性。由于该设计没有额外引入非线性模块(如S盒),也没有额外引入其它增加扩散程度的操作(如模加、异或等),其执行效率和AES原有的密钥编排方案几乎相当,远远快于其它的AES密钥编排方案变体。第二块贡献是研究不考虑密钥编排方案影响的单密钥模型下的密码攻击技术,如线性攻击及其变体。此类攻击的研究成果能帮助更好地理解分组密码轮函数和结构的设计和安全性。具体研究成果如下:1.对降低轮数的Serpent分组密码考查了线性攻击的选择明文变体。通过合理地固定部分明文输入比特,对10轮Serpent,使用单个逼近式的线性攻击的数据复杂度可以降低222个数量级。本文还给出目前为止最好的攻击10轮Serpent的数据复杂度,即,280个明密文对。同时,本文将固定明文技术扩展到多维线性攻击,并在不同的攻击场景下改进了时间和/或数据复杂度。最后,对5轮Serpent进行了实验攻击以验证该固定明文技术的正确性。2.对19轮的MIBS轻量级分组密码给出了一个多维线性攻击。该攻击在数据复杂度和攻击轮数上都是目前最优的。在前人的工作基础上,进一步发现了594个线性逼近式,利用这一发现,降低了攻击的数据复杂度。同时,本文改进了Nguyen等对多维线性攻击计数阶段时间复杂度的优化技术,使该技术不局限用于掩码相同的线性逼近式,也可用于掩码不同的逼近式。利用新发现的逼近式和改进的优化技术,对MIBS的攻击时间复杂度得以降低。3.本文提出一个适用于任意实际分组密码的中间相遇攻击。该攻击的成功率逼近于1,数据复杂度极低,时间复杂度可表示为2k(1-?),其中?0。先前,普遍认为主密钥长度为k的分组密码的安全界为k比特,本文的攻击结果表明这一安全界被高估了。由于实际分组密码存在不可避免的密钥比特损失,其实际的安全界无法达到k比特。本文实际计算了常见分组密码的有效密钥比特,同时发现当迭代轮数固定时,密钥长度和分组长度相等可以尽可能避免密钥比特损失。
[Abstract]:......
【学位授予单位】：上海交通大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN918.4

【共引文献】