下载文档原格式
几个国际标准分组密码算法的安全性分析分组密码是加解密双方用同一密钥进行加密和解密运算的密码算法,是保障数据机密性与完整性的重要技术。
分组密码的安全性分析有利于发现算法中存在的不足,以确保算法在实际应用中的安全,并指导新的算法设计。
上世纪末,随着美国AES计划[1]、欧洲NESSIE计划[2]和日本CRYPTREC计划[3]的相继实施,对相应标准密码算法的安全性分析被国际密码学者广泛关注,极大地推动了分组密码分析与设计工作的发展。
本文主要对三个国际标准分组密码算法AES、Camellia和CLEFIA的安全性进行分析,提出一些有意义的密码学性质,并与国际上最前沿的分析结果相比得到最优的结果。
1、分组密码AES的安全性分析分组密码Rijndael是由两位比利时密码学者Daemen和Rijmen于1997年设计,并于2000年10月被美国国家标准和技术研究所(NIST)公布为高级加密标准AES (Advanced Encryption Standard)。
之后,AES 被CRYPTREC工程和NESSIE工程推荐,并由国际标准化组织(ISO)选定为国际标准ISO/IEC18033-3。
AES的分组长度为128比特,采用SPN结构,密钥长度有128比特、192比特和256比特三个版本,本文分别用AES-128、AES-192与AES-256表示。
AES的中间相遇攻击是由Demirci和Selcuk于2008年FSE会议上提出[7],他们利用4轮AES区分器给出了7轮AES-192和8轮AES-256的分析结果。
在2010年亚密会上,Dunkelman, Keller和Shamir提出了差分列举技术思想和Multiset技术,有效的减少了Demirci和Selquk攻击的存储和时间复杂度。
同时,利用数据/时间/存储折衷技术给出了7轮AES-128的中间相遇分析结果。
在2013年欧密会上,Derbez, Fouque和Jean利用Hash函数分析中的反弹(Rebound)技术,极大减少了Dunkelman等人攻击的时间和存储复杂度。
《现代密码学习题》答案第一章判断题×√√√√×√√选择题1、1949年，（ A ）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。
A、ShannonB、DiffieC、HellmanD、Shamir2、一个密码系统至少由明文、密文、加密算法、解密算法和密钥5部分组成，而其安全性是由（ D）决定的。
A、加密算法B、解密算法C、加解密算法D、密钥3、计算和估计出破译密码系统的计算量下限，利用已有的最好方法破译它的所需要的代价超出了破译者的破译能力（如时间、空间、资金等资源），那么该密码系统的安全性是（ B ）。
A无条件安全B计算安全C可证明安全D实际安全4、根据密码分析者所掌握的分析资料的不通，密码分析一般可分为4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其中破译难度最大的是（ D ）。
A、唯密文攻击B、已知明文攻击C、选择明文攻击D、选择密文攻击填空题：5、1976年，和在密码学的新方向一文中提出了公开密钥密码的思想，从而开创了现代密码学的新领域。
6、密码学的发展过程中，两个质的飞跃分别指 1949年香农发表的保密系统的通信理论和公钥密码思想。
7、密码学是研究信息寄信息系统安全的科学，密码学又分为密码编码学和密码分析学。
8、一个保密系统一般是明文、密文、密钥、加密算法、解密算法 5部分组成的。
9、密码体制是指实现加密和解密功能的密码方案，从使用密钥策略上，可分为对称和非对称。
10、对称密码体制又称为秘密密钥密码体制，它包括分组密码和序列密码。
第二章判断题：×√√√选择题：1、字母频率分析法对（B ）算法最有效。
A、置换密码B、单表代换密码C、多表代换密码D、序列密码2、（D）算法抵抗频率分析攻击能力最强，而对已知明文攻击最弱。
A仿射密码B维吉利亚密码C轮转密码D希尔密码3、重合指数法对（C）算法的破解最有效。
A置换密码B单表代换密码C多表代换密码D序列密码4、维吉利亚密码是古典密码体制比较有代表性的一种密码，其密码体制采用的是（C ）。
南开大学21秋学期《密码学》在线作业下面属于对称算法的是()-A数字签名-B序列算法-CRSA算法-D数字水印上题正确答案：BCA的主要功能为()-A确认用户的身份-B为用户提供证书的申请、下载、查询、注销和恢复等操作-C定义了密码系统使用的方法和原则-D负责发放和管理数字证书上题正确答案：D以下有关软件加密和硬件加密不正确的是()-A硬件加密对用户是透明的，而软件加密需在操作系统或软件中写入加密程序-B硬件加密的兼容性比软件加密好-C硬件加密的安全性比软件加密好-D硬件加密的速度比软件加密快上题正确答案：BSMS4加密算法中只用到了一个S-盒,其输入是()比特位。
-A4-B6-C8-D16上题正确答案：C1949年,Shannon证明了只有一种密码算法是绝对安全的,这种密码算法是()-A Vernman密码-B一次一密密码-CRC4密码-DRC6密码上题正确答案：B若有一个序列的周期为15,则至少需要()级的线性反馈移位寄存器才能产生该序列-A3-B4-C5-D6上题正确答案：B在RSA密码算法中,选p=11,q=23,则模n的欧拉函数φ(n)的值为()-A253-B220-C139-D5上题正确答案：C在多重DES算法中,二重DES可以采用两个56比特的密钥进行加密,从而可以抵抗穷举密钥的攻击,但它易遭受下列哪种攻击()-A穷举密钥攻击-B字母频率攻击-C中间相遇攻击-D差分攻击上题正确答案：C加密有对称密钥加密、非对称密钥加密两种,数字签名采用的是()。
-A对称密钥加密-B非对称密钥加密上题正确答案：B在RSA密码算法中,选加密密钥e=139,若欧拉函数φ(n)的值为220,则解密密钥d为() -A11-B19-C23-D253上题正确答案：BElGamal算法是一种基于()的公钥体系。
-A素数不能分解-B离散对数困难性问题-C大数分解困难性假设-D背包问题上题正确答案：BSMS4加密算法中每一轮都需要用到一个子密钥,则每一个子密钥的长度是()比特位。
square分组密码算法
Square分组密码算法是一种对称密钥加密算法。
它的主要特点是使用代数结构来提供安全性，而不是使用传统的基于位操作的方法。
Square分组密码算法的主要步骤如下：
1. 初始化：选择一个随机的密钥，并将其用于生成密钥调度表。
这个表包含了加密过程中需要使用的所有信息。
2. 分组：将明文数据分组，每组包含一个固定数量的比特。
在Square 算法中，分组大小通常为40比特。
3. 加密：使用密钥调度表和一些代数操作（例如乘法和加法）来加密明文数据。
4. 解密：使用相同的密钥调度表和一些代数操作来解密密文数据。
Square算法的主要优点是它的安全性基于代数结构，而不是传统的位操作。
这意味着它能够抵抗某些类型的攻击，例如侧信道攻击和定时攻击。
然而，Square算法也有一些缺点。
首先，它需要使用大量的代数运算，这可能会导致加密和解密的速度变慢。
其次，它的分组大小相对较小，这可能导致一些安全问题。
一一、是非判断题（10分）1.差分分析是一种攻击迭代密码体制的选择明文攻击方法，所以，对于DES和AES都有一定的攻击效果。
（对）2.反馈移位寄存器输出序列生成过程中，抽头位对输出周期长度的影响起着决定性的作用，而初态对输出周期长度没影响。
（对）二、选择题（15分）1.公钥密码体制至少能抵御的攻击是（C.选择明文攻击）2.适合文件加密，而且有少量错误时不会造成同步失败，是软件加密的最好选择，这种分组密码的操作模式是指（D.输出反馈模式）3.按目前的计算能力，RC4算法的密钥长度至少应为（C.128）位才能保证安全强度。
4.密钥在其生命生命周期中处于不同的状态，每种状态包含若干时期，那么密钥备份时期是密钥处于（B.使用状态）5.量子密码更适合实现下面哪项密码技术。
（D.密钥分发）6.当用户收到一个证书是，应当从（C.CRL）中检查证书是否已经被撤销。
（CRL：证书撤销列表）A.在PKI中，关于RA的功能，下面说法正确的是（B.验证申请者身份）。
7.数字水印是信息隐藏技术研究领域的重要分支，现主要应用领域是（A.版权保护）8.在DES算法中，如果给定初始密钥K，经子密钥产生器产生的各个子密钥都相同，则称该密钥K为弱密钥，DES算法中弱密钥的个数为（B.4个）。
9.生日攻击是针对于下面哪种密码算法的分析方法（D.MD5）。
10.指数积分法是针对下面哪种密码算法的分析方法（C.ElGamal）11.密钥存档是密钥处于（C.过期状态）三、填空题（15分）1.关于DES算法的安全性，若Ek（m）=Dk（m），则这样的密钥称为弱密钥，又其互补性使DES在选择明文攻击下所需的工作量减半。
2.选择合适的n级线性反馈移位寄存器可使序列的周期达到最大值2^n-1，这样序列称为m 序列，但敌手知道这序列中一段长为 n 的明密文对即能破译其后序列的密文。
3.密钥分配和协商的最大区别是：密钥分配是通信双方中一方或密钥分配中心选取一个秘密密钥发给双方，而密钥协商是保密通信双方（或更多方）通过公开信道的通信来共同形成秘密密钥的过程。
第32卷第1期电子与信息学报Vol.32No.1 2010年1月 Journal of Electronics & Information Technology Jan. 20103D密码的Square攻击王美一①唐学海①李超①屈龙江①②①(国防科技大学数学与系统科学系长沙 410073)②(东南大学移动通信国家重点实验室南京 210096)摘要：3D密码是CANS 2008提出的新的分组密码算法，与以往的分组密码算法不同，该密码采用3维结构。
该文根据3D密码的结构特性，得到了3D密码的5.25轮和6.25轮新的Square区分器，重新评估了其抗Square 攻击的强度。
攻击结果表明：新区分器对6轮3D密码攻击的数据复杂度和时间复杂度比已有的结果好，并且还可应用到7轮，8轮和9轮的3D密码攻击中。
关键词：分组密码；3D密码；Square攻击中图分类号：TN918.1 文献标识码：A 文章编号：1009-5896(2010)01-0157-05 DOI: 10.3724/SP.J.1146.2008.01846Square Attacks on 3D CipherWang Mei-yi① Tang Xue-hai①Li Chao① Qu Long-jiang①②①(Department of Mathematics and System Science, National University of Defense Technology, Changsha 410073, China)②(National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)Abstract:3D cipher is a new block cipher proposed in CANS 2008. It is different from all known block cipher as it uses the three dimension structure. According to the structure properties of 3D cipher, a new 5.25-round and a new6.25-round square distinguishers are presented, and the square attacks on reduced- round 3D are improved.Attacking results demonstrate that 6-round attack is better than the known square attacks in data complexity and time complexity. Moreover, these two new distinguishers can be applied to 7/8/9-round 3D cipher.Key words:Block cipher;3D cipher; Square attack1引言3D密码是Nakahara Jr. J在CANS 2008上提出的一种新的SPN型分组密码算法[1]，其主要设计思想来源于AES密码[2]。
浅谈中途相遇攻击--meet-in-the-middleattack
貌似挖的坑也够多了。
好多都没填，这篇最后会不会TJ还得看⼼情TUT
看过⼤⽩书的⼈应该都会发现⼀种神奇的算法：中途相遇法。
（在第58页）这种算法将以空间换时间的思路运⽤到了极致，但事实上它在密码学中的作⽤更⼤
DES在过去的很长时间⾥都是作为标准出现的，⼈们花了很多⼒⽓都没有发现它有什么唯密⽂攻击的⽅法（当然，当密钥恰巧为很少的⼏个弱密钥时是可⾏的TUT 不过我们不考虑这种情况），只有暴⼒破解这⼀条道。
你如果去⾃习查看下它S-box的构造，肯定为赞赞叹它算法的精妙
DES⼀共有64bit密钥，其中56bit是需要我们⼿动设置的，剩下8位为奇偶校验位。
因此暴⼒破解的话最坏情况下需要2^56次⽅！！但在各种⼤触计算机层出不穷的今天，在⼗⼏个⼩时内破解DES也成为了可⾏，这才有了AES招标的这⼀出
但在那之前就有⼈提出了DES的改进，即三重DES。
那问题就来了，⼆重DES你需要设置的密钥为112bit（56*2），那⼆重DES是否可⾏？
你也许会想，这时破解需要计算的的次数为2^112，这和2^56次⽅⽐⼏乎是天⽂数字，⼜何必三重DES呢？但事实上，只要制造出的计算机内存够⼤，我们就能以空间换时间，仅计算2^57就能破解⼆重DES。
其中⽤到的就是中途相遇攻击。
在我看来，中途相遇攻击其实和hash攻击中的⽣⽇攻击很类似。
针对密码协议的常见攻击方法密码协议是一种用于保护通信中的数据安全的方法。
它通过对数据进行加密和解密，使得只有授权的用户能够访问和使用这些数据。
然而，密码协议并非完美的，它们可能会受到各种攻击手段的威胁。
下面介绍一些常见的针对密码协议的攻击方法。
1. 重放攻击（Replay Attack）：在重放攻击中，攻击者截获了一个或多个通信中的消息，并将其重新发送给目标。
这种攻击可以导致目标无法区分真实的消息和重复的消息，从而可能导致数据泄露或身份伪造。
2. 中间人攻击（Man-in-the-Middle Attack）：中间人攻击是一种攻击者通过截获和篡改通信流量来获取信息的方法。
攻击者可以伪装成合法的通信方，并在其与通信方之间进行信息交流。
这样，攻击者可以窃取通信中的敏感信息，或者篡改通信内容。
3. 字典攻击（Dictionary Attack）：字典攻击是一种通过尝试大量的可能密码组合来破解密码的方法。
攻击者使用一个事先准备好的密码字典，将其中的密码逐个尝试，直到找到正确的密码。
这种攻击方法强调了密码的强度与复杂性的重要性。
4. 差分攻击（Differential Attack）：差分攻击是一种针对加密算法的攻击方法，攻击者通过对不同输入的加密结果之间的差异进行分析，来推断出加密算法的一些关键细节或密钥信息。
这种攻击方法通常需要大量的样本数据和高度专业的分析技术。
5. 肉眼攻击（Shoulder Surfing）：肉眼攻击是一种直接观察密码输入过程的攻击方法。
攻击者可能站在密码输入者的背后，或者通过监控摄像头等手段来观察到密码输入的过程。
这种攻击方式不需要依赖计算机技术，而是依靠人类的视觉观察。
为了应对这些攻击方法，设计密码协议时需要考虑以下几点：1. 身份验证：使用可靠的身份验证方法，例如使用双因素身份验证，可以有效防止中间人攻击和字典攻击。
2. 安全传输：采用可靠的加密算法和协议来确保通信数据的机密性和完整性。
《现代密码学》练习题（含答案）一、填空题（每空1分，共7分）1. 加密算法的功能是实现信息的保密性。
2. 数据认证算法的功能是实现数据的完整性即消息的真实性。
3. 密码编码学或代数中的有限域又称为伽罗华(Galois)域。
记为GF(pn)4. 数字签名算法可实现不可否认性即抗依赖性。
信息安全基本要求：可用性、保密性、完整性、不可否认性、可控性、真实性。
5. Two-Track-MAC算法基于带密钥的RIPEMD-160。
密钥和输出MAC值都是20B6. AES和Whirlpool算法是根据宽轨迹策略设计的。
7. 序列密码的加密的基本原理是：用一个密钥序列与明文序列进行叠加来产生密文。
8. Rabin密码体制是利用合数模下求解平方根的困难性构造了一种非对称/公钥/双钥密码体制。
1. 现代对称密码的设计基础是：扩散和混淆。
2. 加密和解密都是在密钥控制下进行的。
3. 在一个密码系统模型中，只截取信道上传送信息的攻击方式被称为被动攻击。
4. Caesar密码体制属于单表代换密码体制。
（字母平移）5. 尽管双重DES不等价于使用一个56位密钥的单重DES，但有一种被称为中途相遇攻击的破译方法会对它构成威胁。
（成倍减少要解密的加密文本）6. 设计序列密码体制的关键就是要设计一种产生密钥流的方法。
2. 椭圆曲线密码是利用有限域GF(2n)上的椭圆曲线上点集所构成的群上定义的离散对数系统，构造出的公钥/非对称密码体制。
3. 在公钥密码体制中，加密密钥和解密密钥是不一样的，加密密钥可以公开传播而不会危及密码体制的安全性。
2. 密码学上的Hash函数是一种将任意长度的消息压缩为某一固定长度的消息摘要的函数。
3. 数字签名主要是用于对数字消息进行签名，以防止消息的伪造或篡改，也可以用于通信双方的身份认证。
2. CTR/计数器加密模式与CBC认证模式组合构成CCM模式；GMAX算法与CTR加密模式组合构成GCM模式。
密码科学技术国家重点实验室开放课题2018年度申请指南本着“开放、流动、联合、竞争”的建设方针，实验室面向全国高等院校、科研机构和其它相关单位设立开放课题基金，支持密码及相关交叉领域的基础性和前沿性研究，欢迎并鼓励多个团队就某一方向联合申请。
申请方向及研究内容如下(申请人可以对申请方向的部分研究内容开展研究):1.密钥同态伪随机函数及其应用构造基于LWE（Learning with Error）、LPN（Learning Parity with Noise）的可证明安全的密钥同态伪随机函数，并设计基于该伪随机函数的一些应用，如对称密钥代理重加密、分布式伪随机函数、可更新加密并用于不经意传输扩展等。
2.抗量子攻击的伪随机数发生器及伪随机函数研究构造可以抵抗量子计算攻击、低电路复杂度的伪随机函数、伪随机数发生器和随机性提取器；研究包括LWR（Learning with Rounding）等数学问题在内的几个常用问题在经典计算和量子计算下的安全强度；完善量子随机预言机模型的理论，并研究以上随机性构件和底层数学困难问题在该模型下的安全强度。
3.密码学困难问题研究对密码学中的一些基础理论问题：如大整数分解问题、离散对数问题、格困难问题、椭圆曲线同源计算、多变元代数方程组求解、纠错码译码等的困难性进行研究，给出更优求解算法；探索提出新的困难问题并给出密码学应用。
4.非交互零知识证明研究研究非交互零知识证明在各种安全模型下基于不同假设的高效构造；针对一些经典的非交互零知识证明，建立它们与可抽取单向函数之间的联系，探索利用非交互零知识证明构造可抽取单向函数；研究简洁非交互零知识证明（snark）的构造，探索snark 在金融科技等方面的应用。
5.安全多方计算的轮复杂性理论研究研究安全多方计算（MPC）协议的准确轮复杂性（交互的最优轮数）；突破自适应安全MPC协议的设计理论；针对在Plain 模型下安全的MPC协议开展研究；研究达到最优轮数、且基于标准假设可证明安全的MPC协议。
收稿日期:2018-04-12 修回日期:2018-08-16 网络出版时间:2018-12-19基金项目:国家自然科学基金(61703278)作者简介:李蒙福(1989-),女,硕士,研究方向为信息安全㊁分组密码;苏凡军,博士,讲师,研究方向为计算机网络和网络安全㊂网络出版地址: /kcms /detail /61.1450.TP.20181219.1532.046.html6轮Square 密码算法的中间相遇攻击李蒙福,苏凡军(上海理工大学光电信息与计算机工程学院,上海200093)摘 要:分组密码具有速度快㊁易于标准化和便于软硬件实现等特点,通常是信息和网络安全中实现数据加密㊁数字签名㊁认证及密钥管理的核心体制㊂密码算法的安全性分析与设计两者难以分离,一方面,在对密码进行安全性分析的过程中,可以为设计出更加安全的密码积累经验,另一方面,在密码算法的设计中也会涉及很多具有现实意义的技术和应用价值的知识㊂作为分组密码的一个重要组成部分 SPN 型分组密码,对其进行研究和分析具有很大的现实意义㊂Square 是SPN 型分组密码其中之一,其密钥长和分组长都为128bit㊂通过研究Square 算法的结构特征和一类截断差分的性质,利用差分枚举技术和多重集构造了Square 算法的4轮中间相遇区分器,给出了对6轮Square 密码算法的中间相遇攻击㊂新的区分器由10个参数决定㊂基于新的区分器,实现了对6轮Square 算法的中间相遇攻击,攻击数据复杂度为2109,时间复杂度为2109,存储复杂度为284㊂关键词:Square 密码;差分枚举;多重集;中间相遇攻击中图分类号:TN918.1 文献标识码:A 文章编号:1673-629X (2019)03-0106-05doi:10.3969/j.issn.1673-629X.2019.03.023Meet-in-the-middle Attack on 6-Round SquareLI Meng -fu ,SU Fan -jun(School of Optoelectronic Information and Computer Engineering ,University of Shanghai forScience and Technology ,Shanghai 200093,China )Abstract :Block ciphers are characterized by their high speed ,easy standardization and hardware and software implementation ,usually as the core system of data encryption ,digital signature ,authentication and key management in information and network security.It is diffi⁃cult to separate the security analysis and design of cryptographic algorithms.On the one hand ,in the process of ciphers security analysis ,experience can be accumulated for the design of more secure ciphers.On the other hand ,in the design of cryptographic algorithms ,there will be a lot of practical significance of technology and application value of knowledge.SPN block ciphers are an important part of block ciphers ,which is of great significance to be studied and analyzed.Square is a block cipher with substitution -permutation network ,which operates on 128-bit blocks and 128-bit keys.By studying the structural characteristics and the properties of truncated differential of Square ,we construct a 4-round meet -in -the middle distinguisher by using differential enumeration technique and multiple sets ,and give a meet -in -the -middle attack on 6-round Square.The new distinguisher is determined by 10parameters.Based on the new distinguis⁃her ,we extend the meet -in -the -middle attack on 6-round Square for the first time with 2109chosen plantexts ,2109computations and 284memories.Key words :Square ;differential enumeration ;multiple sets ;meet -in -the -middle1 概 述随着信息技术的高速发展,数据安全的问题愈加凸显㊂无论是在理论上还是技术上,密码学在信息安全领域都是不可或缺的㊂分组密码具有速度快㊁易于标准化和便于软硬件实现等特点,通常是信息和网络安全中实现数据加密㊁数字签名㊁认证及密钥管理的核心体制,也是对称密码学的一个重要分支㊂分组密码已经在信息安全领域得到了非常广泛的应用,如数字通信安全㊁工业网络控制安全㊁无线传感器网络感知安全㊁无线射频识别安全以及电子商务支付安全等领域㊂分组密码的研究内容主要包括分组密码的设计和分析,两者相互作用,共同推动着分组密码理论的发展㊂第29卷 第3期2019年3月 计算机技术与发展COMPUTER TECHNOLOGY AND DEVELOPMENT Vol.29 No.3Mar. 2019一方面,在对密码进行安全性分析的同时,可以为设计出更加安全的密码积累更多的经验,另一方面,在密码算法的设计中也会涉及到很多具有现实意义的信息安全技术和一些具有实际应用价值的理论知识㊂Square算法是由Joan Daemen和Vincent Rijmen 提出的分组密码[1],发表于1997年,是Rijndael的先驱㊂Square也是一个具有8轮代换-置换网络[2] (SPN)结构的分组密码,可以在各种处理器上实现非常高效的操作㊂该算法采用了2维4×4的字节矩阵,分组长度和密钥长度都是128bit㊂通常,实施对整轮密码算法攻击的难度是非常大的,但是可以利用一些攻击方法减少迭代次数并对密码算法进行分析以衡量其安全性,这样不仅能够促进密码的发展,而且对信息安全也具有重要意义㊂当前,分组密码的安全性研究也是一个热点问题㊂很多密码学研究者在多篇文献中对多种密码算法的安全性进行分析和研究,另外,许多高效的分析方法也被陆续提出,如差分密码分析㊁截断差分分析㊁中间相遇攻击等[3-6]㊂截断差分密码分析是由Knudsen等提出的差分密码分析的一个变形,与经典的差分分析考虑的具体差分值不同,截断差分只考虑差分的一部分性质㊂利用截断差分的思想,可以对某些抵抗经典差分密码分析的算法进行攻击㊂截断差分分析的一般流程是:首先,寻找一条高概率且有效的r-1轮截断差分路径;然后,加密符合要求的明文进而获得密文,从得到的密文对中筛选除差分对符合要求的密文对;最后,对上一步中的密文对进行部分解密,通过计数的方法确定正确的密钥㊂文献[7]给出了Crypton算法的不可能差分分析㊂中间相遇攻击是在文献[8]中提出,最早是用来对分组密码的一种尝试性扩展进行攻击,之后广泛应用于分组密码和Hash函数的安全性分析中㊂它通过存储加密或解密的中间值,并使用这些中间值来改善强制解密密钥所需的时间,从而削弱了使用多重加密的安全性好处㊂这使得中间相遇攻击(MITM)成为通用的时空权衡密码分析方法㊂该种攻击方法的攻击原理是:首先构造出一个合适的区分器,然后将区分器前面的明文从前向后进行加密,后面的密文从后向前进行解密,接着和前面构造出的区分器连接,最后形成一条连贯的攻击路线㊂其中可能会出现两种结果,假设加密和解密的部分能够顺利连接上区分器,那么猜出的密钥值是无误的,不然为错误的,最后获取符合的密钥值㊂通过以上步骤,多数的不对密钥会被排除掉㊂尽管在构造区分器的过程中预计算的复杂度和存储复杂度可能有点大,不过由于仅仅只进行一次的预计算过程,从而在很大程度上也能降低攻击的时间复杂度,所以中间相遇攻击还是一种比较有效的攻击方法㊂近年来,中间相遇攻击已成为比较成熟和富有成效的密码分析方法之一,广泛应用于多种分组密码的安全性分析中㊂文献[9]给出了8轮AES的中间相遇攻击,文献[10]给出了利用多重集和差分枚举技术进行8轮AES中间相遇攻击,文献[11]给出了利用差分枚举技术和有序差分集合进行11轮3D中间相遇攻击,文献[12]给出了缩减轮Crypton的中间相遇攻击分析,文献[13]使用中间相遇攻击对Kalyna算法进行安全性分析㊂Square密码算法的安全性分析最早是文献[1]中提出的Square攻击,其成功给出了6轮Square密码的攻击结果,时间复杂度为272㊂文献[14]对Square进行了Boomerang攻击,运用了7轮Boomerang区分器,实现了全轮的攻击,这也是目前最好的攻击结果㊂但是,限于计算机的计算能力,其可行性还有待验证㊂2011年,文献[15]给出了5轮Square的中间相遇攻击分析,预计算时间复杂度为234,空间复杂度为272㊂Dunkelman等在分析AES时提出了中间相遇攻击 多重集”的概念㊂主要思想为:在构造区分器的过程中,完整的输出序列不需要进行存储,只将符合要求的无序的差分筛选集合进行存储,同时再结合有关截断差分的性质,进一步减少决定区分器的参数个数,达到降低存储复杂度的目的㊂在分析Square算法的结构特征和一类截断差分的性质的基础上,文中利用差分枚举技术和反弹式思想构造出Square算法的4轮中间相遇区分器,该区分器由11个参数决定㊂在4轮区分器的基础上前后各扩展一轮,首次实现了对6轮Square算法的中间相遇攻击㊂在6轮Square密码的攻击过程中,文中通过减少明文数量以降低数据复杂度,又通过使用了多重集进而将决定区分器的参数个数减少为10个,从而进一步降低了预计算的存储复杂度㊂2 预备知识2.1 Square算法描述Square是一个分组长为128bit,密钥长为128bit 的SPN型迭代分组密码㊂Square的轮变换由四个不同的变换组成㊂128bit的分组可以用4×4的2维字节矩阵表示㊂16个字节分组A={a0,a1, ,a15}可表示为如下形式:A=a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14aæèççççöø÷÷÷÷15㊃701㊃ 第3期 李蒙福等:6轮Square密码算法的中间相遇攻击(1)M :列混合,对一个状态的每一列进行操作㊂M ∶b =M (a )⇔b i ,j =c j a i ,0⊕c j -1a i ,1⊕c j -2a i ,2⊕c j -3a i ,3(2)S :非线性变换,S 是一个可逆的8位替换表或S 盒㊂S ∶b =S (a )⇔b i ,j =S (a i ,j )(3)T :转置,状态的行列交换㊂T ∶b =T (a )⇔b i ,j =a i ,j ,T-1=T(4)σ:轮密钥加㊂σ[k t ]∶b =σ[k t ](a )⇔b =a ⊕k t每一轮进行以上4个操作后,迭代8轮即可得到相关密文,解密操作基本上和加密操作一样,只是调换了密钥的顺序,Square 的密钥编排详见文献[15]㊂在某些情况下,在两个连续的轮次中交换M 和k i的顺序㊂由于这些操作是线性的,所以可以互换[2]㊂具体操作是:首先用相等的密钥M -1(k i )排除数据,然后再应用操作M ㊂例如,k 0⊕M (x )=M (M -1(k 0)⊕x )㊂2.2 符号说明x i :第i 轮经过密钥加k i 的状态;y i :第i 轮经过M 变换的状态;z i :第i 轮经过S 的状态;w i :第i 轮经过T 的状态;Δx :状态x 的差分;x [i ]:状态x 的第i 个字节;x [i , ,j ]:状态x 从第i 个字节到第j 个字节;u i =M -1(k i );x ‖y :x 与y 连接;⊕:异或;Δx m :=x m ⊕x i ㊂3 6轮Square 算法的中间相遇攻击这一节中,将描述在6轮Square 上的MITM 攻击㊂首先,给出需要的定义㊁引理和推论㊂然后,提出4轮MITM 区分器,并在6轮Square 上进行MITM 攻击㊂最后,通过改进4轮区分器,以实现相应攻击复杂度的降低㊂3.1 4轮中间相遇区分器定义1:Square 算法的1个字节遍历256个所有可能值,其他15个字节取固定值,这样的结构称为δ集,表示为{X 0m ,X 1m , ,X 255m },其中X im 是256bit ,0≤i ≤255,m (m ∈{1,2, ,8})为Square 算法的迭代轮数㊂一个δ集的例子如下所示:ca 1a 2a 3a 4a 5a 6a 7a 8a 9a 10a 11a 12a 13a 14a æèççççöø÷÷÷÷15定义2[10]:允许元素出现多次,不计元素顺序的集合称为多重集㊂δ集中的元素X i m 构造的多重集:(X 0m [0]⊕X 0m [0],X 1m [0]⊕X 0m [0], ,X 255m [0]⊕X 0m [0]),记为(ΔX 0m ,ΔX 1m , ,ΔX 255m ),一个无序的多重集有2506.17个可能的取值㊂引理1:给定Δi 和Δo 两个非零差分元素,方程S (x )⊕S (x ⊕Δi )=Δo ,平均有一个解㊂这个属性也适用于s -1㊂推论1:选择δ集{w 00,w 10, ,w 2550}前128个值进行4轮Square 加密,若存在明文对(w i 0,w j0)(0≤i ,j ≤255)符合图1截断差分特征,则对应差分序列(X 05[0]⊕X i 5[0],X 15[0]⊕X i 5[0], ,X 1275[0]⊕X i 5[0])可由以下25个字节决定:y i 1[0,4,8,12]‖y i 2[{m |0≤m ≤15}]‖y i3[0,1,2,3]‖y i 4[0]证明:通过y i 1[0,4,8,12]可计算出Δy i 1[0,4,8,12],利用S 盒的非线性替换性质可推算Δz i 1[0,4,8,12],Δz m 1[0,4,8,12]=S (y i 1[0,4,8,12])⊕S (Δy i 1[0,4,8,12]⊕y i 1[0,4,8,12]),Δx m 2[0,1,2,3]可通过等式Δx m 2[0,1,2,3]=T (z m 1[0,4,8,12])得到㊂同样,可以通过y i 2推导出Δz i 2,然后推算Δx i 3,接着利用y i 3[0,1,2,3]推导差分Δz i 3[0,1,2,3],计算Δx i 4[0],最后利用y i 4[0],从而推导出序列(X 05[0]⊕X i 5[0],X 15[0]⊕X i 127i xxx图1 6轮Square 攻击的截断差分特性图然而,以上给出的25个字节其实可以由以下11个字节决定:Δw i 0[0]‖y i 1[0,4,8,12]‖z i 3[0,1,2,3]‖z i 4[0]‖㊃801㊃ 计算机技术与发展 第29卷Δw i4[0]证明:已知Δw i0[0],可推算Δy i1[0,4,8,12],而Δz i1[0,4,8,12]可以由Δy i1[0,1,2,3]和y i1[0,4,8, 12]计算得到,Δx i2[0,1,2,3]可由Δz i1[0,4,8,12]推导计算出,然后推导出Δy i2㊂利用Δw i4[0]经过T-1操作可以得Δz4[0],又已知z i4[0]可以计算出Δy i4[0]和Δx i4[0,4,8,12],从而求出Δw i3[0,4,8,12],进而推导出Δz i3[0,1,2,3],同样利用z i3[0,1,2,3]推导出Δz i2㊂根据引理1,y i2可由Δy i2和Δz i2算出㊂所以差分序列(X05[0]⊕X i5[0],X15[0]⊕X i5[0], ,X1275[0]⊕X i5[0])可以完全由11个字节决定㊂3.2 6轮中间相遇攻击6轮Square算法中间相遇攻击由两个阶段组成:预计算阶段和在线攻击阶段㊂攻击过程如图2所示㊂1.预计算阶段㊂遵循推论1的证明,预计算阶段需建包含211×8= 288个差分序列(X05[0]⊕X i5[0],X15[0]⊕X i5[0], , X1275[0]⊕X i5[0])的预计算表㊂存储这些预计算表需要211×8×27×8/27=291个128bit块㊂2.在线攻击阶段㊂首先找到满足图1中截断差分特征的明文对(p i, pj),并确定δ集,然后计算差分序列并检测它是否在预计算阶段建立的预计算表中,在线阶段的攻击过程描述如下:(1)定义一个232个明文结构P[0,4,8,12],其余12个字节固定为常数㊂使用这一结构可构成232×(232-1)/2≈263个明文对,并且每个明文对都满足明文差分特性㊂攻击过程中还需对281个明文结构进行加密以找到281×263×2-12×8=248个对应的密文对以验证密文差分㊂因此,对于正确的密钥,248对中有248×2-2×3×8=1对遵循整个截断差分特征㊂因为在第1轮和第5轮的M操作中有两个4→1的转换㊂注意,不必检查每一对去找到248个密文对,可以将结构存储在由密文中的12个非活动字节索引的散列表中,以获得正确的对㊂(2)对248对中的每一对,假设它遵循图1中的整个截断差分特征,进行如下操作:(a)猜测Δw0[0],推导出Δz0[0],根据明文差分推导出Δy0[0],根据引理1得到y0[0],然后推出u0[0]㊂(b)猜测值Δx5[0],推导出Δy5[0,4,8,12],根据密文差分,推导出Δz5[0,4,8,12],根据引理2可得出z5[0,4,8,12],z5[0,4,8,12]经过T操作后得到w5[0,1,2,3],最后推出k6[0,1,2,3]㊂(c)根据步骤a中的28个值推出的子密钥,改变w00[0]的值,并计算(w00[4,8,12],w10[4,8,12], , w1270[4,8,12]),然后计算出对应的明文(P0,P1, , P127)并查询它们对应的密文㊂(d)利用步骤b中的28个推导的子密钥,对在步骤c中推导出的每个密文进行部分解密以得到差分序列(X05[0]⊕X i5[0],X15[0]⊕X i5[0], ,X1275[0]⊕X i5[0])㊂检查该序列是否在预计算表中,如果在,则认为猜测的子密钥是正确的,否则删除子密钥㊂而错误子密钥通过的概率是288×2-1024=2-936,非常小,所以可认为猜测出来的子密钥都是正确的㊂(3)最后只剩下1+248×216×2-936≈1个子密钥㊂根据得到的部分密钥,通过穷举搜索剩余未知字节以恢复全部密钥㊂图2 6轮中间相遇攻击图㊃901㊃ 第3期 李蒙福等:6轮Square密码算法的中间相遇攻击 为了评估在线阶段的时间复杂度,文中计算了6轮Square 加密的数量㊂在步骤1中,时间复杂度约为281×232=2113㊂步骤2的时间复杂度由步骤d 决定,其时间复杂度等于248×216×27×1+46×16=266.74㊂在步骤3中,时间复杂度为212×8=296㊂预计算的时间复杂度为211×8×27×1+4+16+46×16=293.06㊂综上,总的攻击时间复杂度为2113,数据复杂度为281×232=2113,存储复杂度为291㊂3.3 对6轮Square 攻击的改进通常,为了降低存储复杂度,可利用多重集把对6轮Square 中间相遇攻击决定区分器的参数减少一个(w 0[0]可不要)㊂由定义2可知,一个δ集会遍历256个状态,第m轮σ变换进行之后遍历的仍然是256个状态,同样进行M 变换后还是遍历256个状态,对差分ΔX i m =X i m ⊕X 0m (0≤i ≤255)进行考虑,因为攻击过程中考虑的多重集是无序的,它也遍历256个状态,所以差分集合{ΔX 0m,ΔX 1m, ,ΔX 255m}不影响后面的攻击㊂而对6轮Square 攻击的改进就可以考虑推论1中{w 0,w 10, ,w 2550}的所有值,因为w 0m +1是活动字节,通过选择w 0m 使w 0m +1,0=0是可能的,所以就可以把决定区分器的参数个数减少一个,为10个㊂首先,使用一个杂凑表将多重集的所有可能值存储起来,因为在构建预计算区分器的过程中都会用到㊂然后,筛选出符合要求的若干明文进行加密㊂同时对特定的密钥进行搜寻,再解密部分密文从而得到多重集,同时检验前一步骤中获取的多重集是不是在预计算阶段的杂凑表中㊂如果在,那么猜测出来的密钥值在很大程度上是无误的㊂文中改进的6轮Square 密码算法的中间相遇攻击使用的多重集为(X 05[0]⊕X i 5[0],X 15[0]⊕X i 5[0], ,X 2555[0]⊕X i 5[0]),它对应的δ集是{w 00,w 10, ,w 2550},最终将攻击预计算的存储复杂度降为210×8×28×8/27=284㊂根据6轮Square 的中间相遇攻击过程可以看出,主要的时间复杂度是对选择的明文进行加密,所以还可以通过减少选择明文的数量以降低时间复杂度㊂在图1对6轮Square 攻击的截断差分特性中,因为对w 0活动字节的差分位置有0㊁1㊁2㊁3这4个位置,每个选择可构造22个对应差分表,而x 5处的活动字节也会有0㊁1㊁2㊁3这四个位置,所以就可以构造出4×4=16条不同的区分器链,从而可将数据复杂度减少24,但需要额外的预计算表,即存储复杂度则会增加24㊂综上,整个攻击的时间复杂度为2109,数据复杂度降为2109,存储复杂度为284㊂4 结束语利用差分枚举技术和反弹式思想,文中构造了Square 算法的4轮区分器,又通过多重集降低了预计算的存储复杂度以及通过减少明文数量降低了数据复杂度㊂研究了Square 密码算法的中间相遇攻击技术,首次给出了6轮Square 算法的中间相遇攻击,整个攻击的数据复杂度为2109,时间复杂度2109,存储复杂度为284㊂参考文献:[1] DAEMEN J ,KNUDSEN L ,RIJMEN V.The block cipherSQUARE [C ]//FSE 1997.Berlin :Springer ,1997:150-153.[2] KATZ J ,LINDELL Y.Introduction to modern cryptography :principles and protocols [M ].[s.l.]:Chapman and Hall /CRC ,2007.[3] 冯国登,吴文玲.分组密码的分析和设计[M ].北京:清华大学出版社,2000.[4] 李 超,孙 兵.分组密码的攻击方法与实例分析[M ].北京:科学出版社,2010.[5] DERBEZ P ,PERRIN L.Meet -in -the -Middle attacks andstructural analysis of round -reduced PRINCE [C ]//FSE 2015.Istanbul ,Turkey :[s.n.],2015:190-216.[6] BIRYUKOV A ,DERBEZ P ,PERRIN L.Differential analysisand Meet -in -the -Middle attack against round -reduced TWINE [C ]//FSE 2015.Berlin :Springer ,2015:3-27.[7] 崔竞一,郭建胜,刘翼鹏.Crypton 算法的不可能差分分析[J ].计算机研究与发展,2017,54(7):1525-1536.[8] DIFFIE W ,HELLMAN M E.Special feature exhaustive cry⁃ptanalysis of the NBS data encryption standard [J ].Comput⁃er ,1977,10(6):74-84.[9] DEMIRCI H ,SELCUK A A.A meet -in -the -middle attackon 8-round AES [C ]//FSE 2008.[s.l.]:[s.n.],2008:116-126.[10]DUNKELMAN O ,KELLER N ,SHAMIR A.Improved sin⁃gle -key attacks on 8-round AES [C ]//ASIACRYPT 2010.[s.l.]:[s.n.],2010:158-176.[11]李永光,曾 光,韩文报.11轮3D 密码算法的中间相遇攻击[J ].信息工程大学学报,2015,16(2):133-138.[12]刘 超,廖福成,卫宏儒.对简化轮数的Crypton 算法的中间相遇攻击[J ].软件工程与应用,2012,1(2):17-23.[13]LIN Li ,WU Wenling.Improved meet -in -the -middle attackson reduced -round Kalyna -128/256and Kalyna -256/512[J ].Designs Codes &Cryptography ,2017,86(4):1-21.[14]KOO B ,YEOM Y ,SONG J.Related -key boomerang attackon block cipher square [J ].IEICE Transactions on Funda⁃mentals of Electronics ,Communications and Computer Sci⁃ences ,2011,94(1):3-9.[15]王 哲,张文英.对5轮Square 的中间相遇攻击[J ].计算机技术与发展,2011(6):132-139.㊃011㊃ 计算机技术与发展 第29卷。
