几个重要对称密码和通用密码结构的分析

发布时间：2019-08-11 15:32

【摘要】：随着互联网等技术的迅猛发展,网络空间安全成为关系到国家安全战略的重要课题。密码学作为网络空间安全的基础学科,在我国网络空间安全建设中发挥着重要的作用。密码学中将密码算法分为对称密码算法和非对称密码算法两大类。对称密码算法包括分组密码、流密码、哈希函数以及认证加密算法等。对称密码具有运算速度快、易于标准化、便于软硬件实现等特点,已成为信息与网络空间安全中实现数据加密、消息认证和密钥管理等关键领域的核心部件,被广泛应用。本文研究对象包括国际通用分组密码结构Feistel-SP以及通用哈希模式(MMO、Miyaguchi-Preneelmodes)的安全性分析,认证加密竞赛CAESAR第三轮候选算法KETJE的安全性分析,国际ISO/IEC标准算法Camellia的安全性分析。在研究中发现了一些有意义的密码学性质,并构造了新的分析模型,得到了一些较好的研究成果。·国际通用密码结构的安全性分析目前通用的分组密码结构都采用了迭代结构,主要包括Feistel结构、SPN结构和Lai-Massey结构等。Feistel结构是20世纪60年代末IBM公司的Feistel等提出的,著名的数据加密标准DES即采用该结构。对于分组长度为2n的r轮Feistel结构的密码,首先将2n比特的明文P划分为两个n比特,记为(L0,R0),然后按照如下方式迭代r轮,对于第i=1,2,...,r,令2013年亚密会上,日本密码学者Isobe和Shibutani将Feistel结构进一步划分为三类,记为Feistel-1/2/3.分组密码和哈希函数是很多密码协议的基础部件。随着传感器、智能卡等的广泛使用,轻量级的密码受到工业界和密码学界的高度重视。很多轻量级的应用环境中,完整性认证和保密两个功能同时被需要,采用分组密码构造哈希函数的技术使这种要求成为可能。著名密码学家Bart Preneel等提出或分析了几种采用分组密码构造哈希函数的工作模式,即著名的PGV模式,包括著名的 Davies-Meyer(DM)模式、Matyas-Meyer-Oseas(MMO)模式和Miyaguchi-Preneel(MP)模式等。因此分析由通用分组密码和以上重要哈希模式构造的哈希函数的安全性尤为重要。2007年,Knudsen和Rijmen在亚密会首先提出对分组密码的已知密钥攻击模型,并给出由7轮Feistel-2类分组密码构造的MMO、MP类哈希函数的半碰撞(half-collision)攻击。2009年,Biyukov等在美密会上提出选择密钥攻击模型,并给出了由全轮AES-256分组密码构造的DM类哈希函数的q维差分多碰撞,将AES-256与理想算法进行区分。2011年,Sasaki和Yasuda在2011年FSE会议上提出Feistel-SP类分组密码的11轮已知密钥区分攻击,并给出了由Feistel-SP类分组密码构造的MMO、MP类哈希函数的9轮碰撞(full-collision)攻击。本文中,我们进一步探索Feistel-SP类分组密码的区分攻击,以及采用该类分组密码构造的MMO、MP类哈希函数的碰撞攻击。我们构造了 7轮反弹攻击内部对接路线,将Sasaki和Yasuda提出的5轮路线提高了两轮,并利用密钥自由度筛选出正确的7轮对接数据对,给出了 12轮选择密钥区分攻击,将之前的11轮区分攻击提高了 1轮。在分析通过Feistel-SP类分组密码和MMO、MP哈希模式构造的哈希函数类时,我们采用两消息块构造碰撞的攻击技术,第一个消息块用来提供密钥自由度,在第二个消息块中,我们构造了11轮反弹攻击路线,最终给出了 11轮实际碰撞攻击,复杂度为2486,将之前由著名密码学家Sasaki和Yasuda共同提出的9轮碰撞攻击提高了 2轮,进而证明在采用Feistel-SP结构设计分组密码时,轮数必须大于11轮,否则其对应的MMO、MP类哈希函数将存在碰撞攻击。·认证加密竞赛CAESAR第三轮候选算法Ketje的安全性分析认证加密算法属于对称密码算法中的一种,它不仅支持数据的保密功能,也支持数据完整性认证功能。目前被广泛使用的认证加密算法为AES-GCM,为获得安全性高、适用环境广和稳定性强的认证加密算法,国际密码学界启动了 CAESAR竞赛。由于认证加密标准的重要性,自2014年竞赛启动开始,共57个算法被密码学家提出并分析,经过两轮的筛选,目前只有16个候选算法进入第三轮的评估。新的设计满足新环境的应用需要,但是同样带来未知的安全威胁。探索新的攻击方法对提出安全可靠的认证加密新标准至关重要。在2015年欧密会上,Dinur等首先提出对KEYAK的立方攻击,将流密码的攻击方法立方攻击应用到KEYAK当中,给出了一些缩减轮的密钥恢复攻击和伪造攻击。随后在CT-RSA2015会议上,该方法被应用到对缩减轮ASCON的分析中。2017年欧密会上,黄森洋等提出带条件立方攻击,改进了 Dinur等的结果。在FSE 2017会议上,李铮等将带条件的立方攻击模型化,并结合密钥划分技术将之前ASCON的分析结果提高了 1轮,提出7轮的密钥恢复攻击,并给出6轮ASCON的实际攻击(复杂度240)。本论文我们给出了 KETJE的立方攻击。KETJE是CAESAR第三轮16个候选算法之一,由KECCAK团队(SHA-3设计者)设计,软硬件效率高。我们利用立方攻击技术给出了 KETJE主算法的6/7轮密钥恢复攻击,并讨论了其他KETJE族算法的安全性。首先我们将线性结构技术应用到寻找稀疏的立方变量集合中,并找到32维和64维立方变量集合,满足第一轮中立方变量之间不相乘。然后我们引入新的动态变量,达到同时降低密钥和立方变量扩散的目的。这使得只有少量的密钥影响6轮、7轮后的立方变量加和,从而将立方攻击的分治法应用到6轮、7轮KETJE SR的密钥恢复攻击中,复杂度较穷搜分别降低2634和215倍。另外,我们还讨论上述方法在其他KETJE族算法中的应用,以及当初始向量长度缩减为128比特时攻击的效果,并给出了系列密钥恢复攻击。·国际ISO/IEC标准算法Camellia的安全性分析Camellia是由日本电报电话公共公司NTT和三菱电子公司联合设计的一个分组密码,最早在2000年SAC会议上提出。Camelligi分组长度为128比特,密钥长度包括128比特、192比特和256比特三个版本。该算法由国际标准化组织(ISO)选定为国际标准ISO/IEC 18033-3,也被日本的CRYPTREC计划推荐为日本e-government算法,被欧洲NESSIE竞赛的列为获胜算法之一。鉴于该算法的重要性,其安全性引起世界范围内密码学家的关注,已有的分析包括不可能差分、中间相遇攻击、零相关等。本文研究Camellia算法的多差分分析。结合Camellia-128组件差分扩散性质,采用搜索算法找到很多概率优势相对较弱的差分路线,并基于此构造多差分路线。根据不同的多差分路线,将整个密钥空间划分为224 + 1个子集合,这些密钥使得不同的差分在通过FL-1层时扩散最低。总之,我们构造出了224种8轮多差分路线,对于每个多差分路线,有243个概率较低的差分路线。基于该8轮多差分路线,我们对每个密钥子集攻击了 10轮Camellia-128,攻击覆盖大约99.99%的密钥,攻击复杂度仅为2104.5.最后,通过数学模型,我们将弱密钥攻击转化为全密钥攻击,数据复杂度为291,时间复杂度为2113.该攻击降低了原来10轮Camellia-128攻击的复杂度。
【图文】：

几个重要对称密码和通用密码结构的分析

图２．１：邋ＭＤ结构逡逑

结构示意图,轮函数,类分,密钥

都采用该类结构，例如数据加密标准ＤＥＳ、ＩＳＯ标准Ｔｒｉｐｌ（ＫＤＥＳ、ＭＩＳＴＹ１、逡逑Ｃａｍ址ｉａ、ＣＡＳＴ－１％．为了更深入的研究Ｆｅｉｓｔｅｌ结构，日本学者Ｉｓｏｂｅ和逡逑ＳＷｂｕｔａｎｉ按照密钥的介入方式和轮函数的类型将Ｆｅｉｓｔｅｌ划分为Ｈ类，如图２．２，逡逑分别记为Ｆｅｉｓｔｅｌ－１／２／３．本章我们将集中讨论Ｆｅｉｓｔｅｌ－３型，其轮函数是基于替逡逑换－置换（ＳＰＮ）结构，即密钥通过异或介入，然后状态依次通过替换层（Ｓ－ｂｏｘ逡逑ｌａｙｅｒ）和置换层（Ｐｅｉ－ｍｕｔａｔｉｏｎ邋ｌａｙｅｒ）。因此，Ｆｅｉｓｔｅｌ－３邋又被记为邋Ｆｅｉｓｔｅｌ－ＳＰ．在逡逑２０１４年亚密会上，郭建等Ｐｉ］给出了邋Ｆｅｉｓｔｅｌ－ＳＰ类分组密码的１０轮密钥恢复攻逡逑击。目前有很多分组密码算法采用该结构设计，例如扮０标准Ｃａｍ}0ｉａＭ、轻逡逑量级分组密码ＬＢｌｏ浊［２２］等，很多相关的密钥恢复攻击［６２’６３１被提出。逡逑通常，，Ｆｅｉｓｔｅｌ－ＳＰ类分组密码处理的分组大小为１２８比特或者６４比特，采逡逑用的Ｓ盒大小一般有８邋Ｘ邋８和４邋Ｘ邋４．依据分组大小和Ｓ盒的大小
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TN918.2

【相似文献】