密码算法TWINE和NTRU的安全性分析_郑学欣.docx

《密码算法TWINE和NTRU的安全性分析_郑学欣.docx》由会员分享，可在线阅读，更多相关《密码算法TWINE和NTRU的安全性分析_郑学欣.docx（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 单位代码： 10422 学 号： ： 2J0 9I(丨书 分类号 了叫 密级： _ yi SHANDONG UNIVERSITY 博士学位论文 Dissertation for Doctoral Degree 论文题目： 氣 4气忒丁也廉积 /mu k奋 F TMB AM) MO 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的 研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声 明的法律责任由本人承担。 论文作者签名： _ 日 _ 关于学位

2、论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存论文和汇编本学位论文。 (保密论文在解密后应遵守此规定 ） 论文作者签名 导师签名 曰 期 :wd M W . i ABSTRACT . v 主要符号对照表 . ix 第 1 章引言 . 1 1.1研宄背景和意义 . 1 1.2研究进展 . 4 1.3本文的结构安排 . 6 第 2 章预备知识 . 9 2.1分组密码及其经典分析方

3、法 . 9 2.1.1 分组密码简介 . 9 2.1.2 分组密码的分析方法 . 11 2.2能量分析 . 15 2.2.1 能量分析攻击 . 15 2.2.2能量分析防御对策 . 18 第 3 章轻量级分组密码 TWINE 的不可能差分分析 . 19 3.1 TWINE 算法描述 . 19 3.2 些有用的性质 . 23 3.3对约减轮数 TWINE-80和 TWINE-128 的不可能差分分析 . 26 3.3.1 TWINE 不可能差分路线及有关性质 . 26 3.3.2对 23轮 TWINE-80的不可能差分分析 . 30 3.3.3对 24轮 TWINE-128的不可能差分分析 .

4、38 3.4 . 44 第 4 章对受保护的 NTRU 体制的碰撞攻击 . 45 4.1 NTRU 加密算法介绍 . 45 4.1.1 卷积的计算 . 47 4.2 Lee 等给出的攻击方法和相应的对策 . 47 4.2.1 Lee 等对未受保护的 NTRU 的攻击 . 48 4.2.2 Lee 等的抗能量分析攻击的对策 . 49 2 目录 4.3碰撞攻击受保护的 NTRU 加密算法 . 50 4.3.1 分析此三个对策 . 51 4.3.2基于汉明重量模型的碰撞攻击 . 51 4.3.3基于汉明距离模型的碰撞攻击 . 54 4.3.4攻击其他参数版本 . 56 4.4实验与效率比较 . 57

5、 4.4.1 实验结果 . 57 4.4.2 与 Lee 等的攻击比较 . 60 4.5 . 61 第 5章结论和研究计划 . 63 参考文献 . 65 酬 . 71 个人简历 . 73 山东大学博士学位论文 密码算法 TWINE 和 NTRU 的安全性分析 郑学欣 山 东 大 学 数 学 学 院 密码技术与信息安全教育部重点实验室 摘 要 密码学作为信息安全的重要基础，在现代网络社会中发挥着极其重要的作 用。密码学中的加密算法分为非对称加密算法（又称为公钥加密算法）和对称 加密算法（又称为私钥加密算法）两大类。本文的研究对象 TWINE 是对称加 密算法， NTRU是非对称加密算法。 对称密

6、码包括分组密码、流密码和哈希函数。随着手持设备、 RFID 等的 发展，在资源受限的环境中使用的分组密码（即轻量级分组密码 ） 得到了广泛 关注并迅速发展起来。轻量级分组密码算法 TWINE即是在此背景下提出的 。 TWINE是由 Suzaki等在 2011 年的 ECRYPT 轻量级密码会议上首次提出的，并 发表在 2012 年的 SAC会议上。它的分组长度是 64比特，密钥长度有 80比特和 128比特两个版本，其米用广义的 Feistel 结构 （ Generalized Feistel Structure， 简 称 GFS)， 并由 36 轮轮函数构成。 公钥密码算法 NTRU 是由

7、Hotfstein 等在 1996年的美密会上提出的。它是 基于多项式环 /? = 2闵 /(， -1)上的运算。虽然没有严格的规约证明，但是它 的安全性被认为是基于求解格上困难问题的困难性，所以 NTRU 算法具有抵抗 量子计算攻击的能力。在计算效率方面，因为 NTRU 算法的简洁设计，它的计 算速度比 RSA算法和椭圆曲线算法快很多。正是因为它具有高效和安全的双重 属性，出现了很多针对它的安全性研究。 在密码学的发展过程中，密码设计和密码分析是相互对立又相互促进的。 密码学家利用许多数学方法设计出好的密码算法，然后密码分析学者试图找出 算法的缺陷并进行攻击尝试，之后设计者避免己知缺陷、设计

8、出更安全高效的 密码算法。正如 NIST 征集美国加密标准 AES,欧洲的 NESSIE 工程，日本的 山东大学博士学位论文 CRYPTREC 工程等使得密码的设计技术和分析技术都得到了快速发展。本论文 对两个重要的密码算法进行安全性分析，有利于深入理解其可能的缺陷和安全 强度。 对密码算法的安全性分析包括对其算法层面的理论分析和对其实现层面的 实际安全性分析。本文的工作对 TWINE 算法进行了理论分析，对 NTRU 进行 了实现算法的实际安全性分析。分组密码算法的理论分析技术包括差分分析、 线性分析、不可能差分分析、代数分析等。本文使用不可能差分分析对轻量级 分组密码算法TWINE 进行了

9、安全性评估。在密码芯片的安全性分析方面，侧 信道攻击是密码芯片系统遭遇的主要威胁之一。自从 Kocher 在 1996 年的美密 会上首次提出时间攻击的概念之后，侧信道攻击得到了迅猛发展，能量攻击是 侧信道攻击中最常见和最容易实现的方法。能量分析攻击包括简单能量分析、 差分能量分析、高阶差分能量分析和碰撞攻击等。鉴于这些攻击给密码芯片系 统带来的实际威胁，抵抗这些攻击的防御对策研究也随之迅速发展。本文使用 碰撞攻击对有 防御对策保护的 NTRU 算法进行安全性评估。 轻量级分组密码 TWINE 的不可能差分分析 根据 TWINE 的密钥生成算法，本工作给出轮密钥之间的一些观察，既有 简单的密钥

10、相等关系，也有较复杂的函数关系。这些密钥关系影响了攻击者对 不可能差分路线的选取和密钥恢复算法的具体操作。在选择最优的不可能差分 路线时，攻击者首先寻找最长的路线，然后依据截断差分路线中轮密钥关系从 多条最长的路线中挑选出最优的一条不可能路线。这条最优路线一方面要使得 截断差分路线中涉及到的不相等密钥的个数最少，同时也要使得这些密钥的函 数关系 相对更简单，从而使过滤密钥阶段的时间复杂度能更低。 在己知文献的不可能差分攻击中，攻击者将满足头部截断差分路线和尾部 截断差分路线的子密钥分别筛选出来，然后两部分子密钥的直接合并就给出了 错误子密钥。因为这些攻击中涉及的不相等子密钥的比特数都没有超过主

11、密钥 比特数，所以假设这些子密钥相互独立并把两部分子密钥直接合并的攻击是可 行的。但是我们试图攻击更多的轮数，因此在我们的攻击路线中，头部截断差 分路线的子密钥和尾部截断差分路线的子密钥之和超出了主密钥比特数，也即 山东大学博士学位论文 这些子密钥之间存在信息冗余。那么将两部分子密钥直接合并作为错误子密钥 的算法不再可行，我们给出了一个新的筛选错误子密钥的算法。我们的算法同 时考虑截断差分路线和密钥关系这两个条件，逐步链接满足这两个条件的子密 钥，直至所有子密钥链接完成。 另外，我们的攻击采用了预计算技术并对攻击的时间复杂度和空间复杂 度进行了平衡；在恢复密钥阶段优化了密钥关系的使用顺序；根据

12、 TWINE 算 法 s 盒的差分特性给出更精确的明密文差分特征，从而加快数据收集阶段正 确明密文对的筛选速度。我们对 23 轮 TWINE-80 攻击的时间复杂度是 27%9次 加密，数据复杂度是257 85个分组，存储复杂度是个分组长度。对 24 轮 TWINE-128 攻击的时间复杂度是 21268次加密，数据复杂度是 258 1个分组，存 储复杂度是 212561个分组长度。 对受保护的 NTRU 体制的碰撞攻击 在 2010 年， Lee 等给出了针对 NTRU 的一种常见软件实现的能量分析，他 们的工作显示未受保护的 NTRU的一种常见软件实现是不能抵抗简单能量分 析和相关能量分析

13、攻击的，他们因此提出了三个对策来抵抗他们提出的攻击。 他们对其对策的安全性评估结论是：只有二阶能量分析才能有效的攻击他们的 第一个对策，而如果将他们的第一个对策和第三个对策合并使用，组合对策保 护下的 NTRU 算法是安全的。本论文给出了针对这些对策的有效的一阶能量分 析。 他们的第一个对策是随机初始化寄存器？，目的是抵抗他们的简单能量分 析（ Simple Power Analysis， 简称 SPA)攻击。具体而言，在解密算法开始前令 每个寄存器 加上一个随机数 6，在算法结束后再把 6从对应的寄存器 ?,中减 去。因此在这个对策下的算法中就不存在 ;c + 0的操作，从 而使得 SPA

14、攻击无 效。 他们的第二个对策是用随机值盲化密文多项式 c ,目的是抵抗他们的相关 能量分析 （ Correlation Power Analysis， 简称 CPA)攻击。具体操作是把原始的 算法输入值 Q 替换成 c, + /*，其中 r 是一个随机整数。在算法最后将每个寄存器 匕的值减去增加的随机值。 山东大学博士学位论文 他们的第三个对策是随机化数组 6中元素的存储顺序，也是为了达到抵抗 他们的 CPA 攻击的目的。因为每次运算中第 _/行使用的密钥枓刀是不固定的， 所以就无法利用统计方法得出 M/I -处 /- 1的值。 针对 Lee等设计的保护 NTRU的对策，本工作给出了汉明重量

15、 （ Hamming Weight，简称 HW)模型和汉明距离 （ Hamming Distance， 简称 HD)模型下的 碰撞攻击。第一个对策用随机值初始化寄存器 f。 虽然消除了非零值与零值相 加的操作，抵抗了 SPA 攻击。但是对 /的初始化操作可能会使得它成为某些攻 击的目标。第二个对策掩盖了 Q 的值，因此可以抵抗一阶 CPA 攻击。虽然它确 实隐藏了真实的中间值，但是这个对策是不能抵抗 SPA 攻击的。第三个对策 扰 乱了密钥冲 (/ = 0,1)的执行顺序，记新的密钥序列为 &/ (/ = 0,1) 。 这个对策可以在一定程度上隐藏信息，但是它并没有完全把信息隐藏起来，因 为

16、fe0 = M0成立的概率是 1/d。基于这些观察，我们给出了碰撞攻击。 针对第一个对策，理论计算表明我们的碰撞攻击的攻击效率比 Lee 等给出 的二阶相关能量分析提高了 204.8%， AT89C51RC2微处理器上的实验数据表明 在汉明重量模型和汉明距离模型下我们的攻击效率分别提高了 108.4%和 78%。 针对三个对策同时使用的组合对策，虽然设计者认为组合对策是安全的，但是 我们的攻击使用足够的能量迹就可以破解这个对策。 关键词 .轻量级分组密码 ,不可能差分分析； NTRU;能量分析；碰撞攻 击 山东大学博士学位论文 Cryptanalysis of TWINE and NTRU X

17、uexin Zheng (Key Lab of Cryptologic Technology & Information Security, Ministry of Education School of Mathematics, Shandong University, Jinan 250100, P.R. China) ABSTRACT As the foundation stone of information security, Cryptology plays a very important role in modem world. The encryption algorithm

18、s in cryptology includes symmetric encryption algorithms and asymmetric encryption algorithms. As the study subjects of this dissertation, TWINE is a symmetric encryption algorithm and NTRU is an asymmetric encryption algorithm. Symmetric cryptosystem includes block cipher, stream cipher and hash fu

19、nction. With the development of RFID and handheld devices etc, block cipher used in low resource devices attracts widely attention and is developing very fast. And the lightweight block cipher TWINE is proposed in this background. TWINE was proposed by Suzaki et. al. at the ECRYPT (European Network

20、of Excellence in Cryptology) Workshop on Lightweight Cryptography in 2011, and then published at the SAC conference in 2012, It is a 64-bit lightweight block cipher consisting of 36 round- s with 80-bit or 128-bit keys. The global structure of TWINE is a variant of Type-2 generalized Feistel structu

21、re with 16 nibbles. NTRU cryptosystem, proposed at CRYPTO in 1996 by Hoffstein et. al., is based on the algebraic structures of polynomial ring R = 7xH - 1). Although there is no rigorous reduction from NTRU to some hard problem, breaking NTRU could be expressed as a hard problem over Euclidean latt

22、ice. Therefore, it is believed that NTRU can resist quantum computers. Besides, its encryption and decryption operations are much faster than those of RSA and elliptic curve cryptosystems with the same level of security. Due to its high security and efficient operations, many security assessment v _

23、 山东大学博士学位论文 _ arose in the last few years. In the development of cryptography, cryptographic design and cryptanalysis are on the opposite sides while they improve each other at the same time. After Cryptographers designing some cryptographic algorithms using all kinds of mathematical methods, many r

24、esearchers try to find the weakness of these algorithms and then fix the problem to obtain better cryptographic algorithms. For example, a competition to develop the Advanced Encryption Standard (AES) as a replacement of DES which was hold by the National Institute of Standards and Technology (NIST)

25、, the European NESSIE project, Japanese CRYPTREC project etc have been promoting the fast development of the design and cryptanalysis of block cipher. This dissertation shows some attacks against two important cryptographic algorithms to help the understanding of their security level. The security a

26、nalysis of cryptographic algorithms includes theoretical analysis and practical implementation analysis. This dissertation gives theoretical analysis of TWINE and practical implementation analysis of NTRU. For the theoretical analysis of block cipher, many techniques such as differential cryptanalys

27、is, linear cryptanalysis, impossible differential cryptanalysis, algebraic cryptanalysis etc. are used. The technique of analyzing TWINE in this dissertation is impossible differential cryptanalysis. From the aspect of security assessment of cryptographic chips, side channel attack is the most power

28、ful tool which chips are threatened by. Since the appearance of timing attack given by Kocher on CRYPTO in 1996, side channel attack has been developing very fast. Power analysis which is the most common method and easiest to amount among all kinds of side channel attacks, contains Simple Power Anal

29、ysis, Differential Power Analysis, High Order Differential Power Analysis, Collision Attack etc. Meanwhile, countermeasures which are designed to resist these attacks are developed due to the practical threaten to the cryptographic chip systems. The technique used in our security assessment of NTRU

30、is collision attack. Impossible Differential Attack on Reduced-Round TWINE vi 山东大学博士学位论文 We obtain some important properties about the round subkeys of TWINE according to the Key Schedule. Those subkey relations affect attackers9 choice of impossible differential and the key recovery algorithm. Duri

31、ng the selection of best impossible d- ifFerential among the longest ones, an attacker pick the longest impossible differentials, and then the best one is chosen according to these subkeys relations for the sake of less time complexity in the key recovery step. In former works of impossible differen

32、tial attacks, an attacker selects all the subkeys that satisfy the head truncated differential and the tail trancated differential separately, and then the two parts of subkeys are combined directly to be filtered as wrong keys. Since the subkeys considered in their attacks has no more bits than the

33、 master key, it is feasible to directly discard these subkeys. However, the subkeys involved in the truncated differentials have more bits than the master key in our attack, which means there are some information redundance among the subkeys. Therefore, we give a new algorithm that can deal with the

34、 redundance at the same time when selecting subkeys satisfying the truncated differentials. Besides some precomputation to obtain the time-memory balance, the order of using subkey relations are optimized. Whats more, a more precise description of the plaintext/ciphertext difference is obtained by u

35、sing the differential characteristic of TWINE s box. Therefore, a right plaintext/ciphertext pair can be picked more quickly. The time, data and memory complexity of attacking 23-round TWINE-80 are 279 09 23-round encryptions, 257*85 chosen plaintexts and 278 04 blocks respectively. Besides, the imp

36、ossible differential attack on 24-round TWINE-128 needs 2581 chosen plaintexts, 2126 78 24-round encryptions and 2125 61 blocks of memory. First-order collision attack on protected NTRU cryptosystem Lee et al. gave several power analysis attacks on the most common used software implementation of NTR

37、U and three countermeasures in 2010, where they argued that only second-order power analysis can break their first countermeasure, and the combination of the first and third countermeasure is secure. Vll 山东大学博士学位论文 The first countermeasure is random initialization of registers r, which is aim to pre

38、vent their Simple Power Analysis (SPA) attack. To be more specific, every register ti (/ = 0,2/ - 2) is added by some random number r, at the beginning of decryption algorithm. After the decryption algorithm is done, these r, are subtracted from the cor- responding register f 卜 Hence there is no ope

39、ration like x 十 0 in the modified algorithm, and their SPA attack does not work. The second countermeasure is blinding ciphertext c using random values, which is designed to resist their Correlation Power Analysis (CPA) attack. For the original input values Q (/ = 0,- 1), the countermeasure is to re

40、place them by c,- + r, where r is a random integer. And then every value in the register ti is subtracted by dr mod q at the end of the algorithm. The third countermeasure is randomization of b. The randomized order of bi disables the statistical analysis of bi - bi 1 in their attack. For these coun

41、termeasures, we give efficient first-order collision attacks in HW model and HD model respectively. Although the first countermeasure eliminates the adding operation of zero and non-zero and avoids the SPA attack, the initialization of the register t may make t the attack target. The second counterm

42、easure masks the value of Ci which can help resist CPA attack. However, SPA can easily break the algorithm if it is protected only by the second countermeasure. As for the third countermeasure, we admit that the order of bi (/ = 0,- 1) is disturbed. Denote the new ordered secret key as b i (i = 0,d-). One important observation on the third countermeasure is that the equality b0 = /? 0 holds with probability /d. Using these observations, we propose the first-order collision attack on NTRU protected by Lees countermeasures. For