Design and Cr yptanalysis of Symmetric Key Primitives

摘要

分组密码作为密码学中重要的组成部分，在许多密码算法的构造中起到了重要作用。本论文主要阐述了对称密码算法，尤其是分组密码和流密码算法的设计与安全性分析方法。论文共分为三个部分。
　　首先，我们介绍了混合整数线性规划（MILP），并讨论了其在对称密码安全性分析中的应用。众所周知，差分分析和线性分析方法是对称密码算法分析最有效的两种统计分析方法。所以抵抗差分分析和线性分析是现代密码算法设计的最重要原则。我们提出一种基于MILP的方法，可以给出算法针对差分分析和线性分析的安全界。我们的方法应用范围广泛，能够大大减少算法设计者和分析人员的工作量，进而提高其工作效率。本论文将MILP成功地应用在对称密码算法的几个方面：首先我们成功证明了流密码Enocoro-128v2的差分和线性分析的安全上界。其次，对于具有扩散转换机制（DSM）的类CLEFIA的一般Feistel结构（GFN），我们证明了更好的线性活性S盒的下界，并首次证明了GFN采用DSM的扩散方法，可以获得更多的活性S盒，进而提高算法抵抗线性分析的能力。再次，在认证加密算法CAESAR竞赛候选算法PRIMATEs的设计中，基于抵抗差分分析和线性分析的理论，我们利用MILP的方法搜索选定底层置换PRIMATE的行变换（ShiftRows）的值，并且给出PRIMATE抵抗差分分析、线性分析和碰撞攻击的安全上界。最后，利用MILP的方法，我们首先构造了Rijndael-160/160和Rijndael-192/192的相关密钥矩形区分器，并在此基础上对其分别给出了到论文写作时最多轮数的攻击。
　　其次，本论文也研究了分组密码的安全性分析:首先我们对Rijndael-224和Rijndael-256进行不可能差分分析，据我们所知，我们的不可能差分攻击仍是最好的攻击结果。其次我们也对NSA设计的轻量级分组密码SIMON进行了分析，并首次尝试了积分攻击和零相关线性攻击。最后我们研究了Eurocrypt2015上提出的针对多方计算（MPC）和同态加密（FHE）设计的分组密码LowMC，基于高阶差分区分器，我们对全轮LowMC做的优化插值攻击成功驳斥了设计者的安全性声明。
　　最后，我们研究了统计分析方法之间的联系，并建立了不可能差分分析、零相关线性分析和积分攻击之间的关联。

目录

Preface

Abbreviations

Part I Symmetric Key Primitives

Chapter 1 Introduction

1.1 Cryptography model

1.2 Symmetric key primitives

1.3 About this dissertation

Chapter 2 Blo ck Ciphers

2.1 Definitions

2.2 Design methods

2.3 Modes of operation

2.4 Conclusions

Chapter 3 Cryptanalysis Metho ds

3.1 Attack models

3.2 Differential cryptanalysis and extensions

3.3 Linear cryptanalysis and extensions

3.4 Algebraic cryptanalysis

3.5 Conclusions

Chapter 4 Contributions of this thesis

4.1 MILP and its applications to symmetric-key primitives

4.2 ID, ZC, integral cryptanalysis and their links

4.3 Interpolation attack of LowMC

4.4 Conclusions

Chapter 5 Conclusion and future work

5.1 MILP and its applications

5.2 Cryptanalysis of block ciphers

5.3 Links among cryptanalysis methods

5.4 Directions for future work

Bibliography

Part I I Publications

List of publications

Chapter 6 Differential and Linear Cryptanalysis Using Mixed-Integer Linear Programming

Chapter 7 The provable constructive effect of diffusion switching mechanism in CLEFIA-typ e blo ck ciphers

Chapter 8 Related-Key Rectangle Cryptanalysis of Rijndael-160 and Rijndael-192

Chapter 9 PRIMATEs

Chapter 10 Improved Imp ossible Differential Attacks on Large-Blo ck Rijndael

Chapter 11 Cryptanalysis of Reduced-Round SIMON32 and SIMON48

Chapter 12 Links Among Imp ossible Differential, Integral and Zero Correlation Linear Cryptanalysis

Chapter 13 Optimized Interp olation Attacks on LowMC

App endix A

Curriculum Vitae