密码分析学

密码学专家王小云院士、沈昌祥院士主编丛书;

山东大学领衔网络安全行业知名专家团队打造;

从学科布局发展出发，撰写密码学系列核心教材;

坚持需求导向, 注重创新精神和实战能力培养;

教材资源丰富，配电子课件+程序代码+视频;

为网络安全人才培养提供一整套教学解决方案!

《密码分析学》系统介绍了对称密码算法和杂凑函数的主流分析理论与方法，如差分分析、线性分析、积分分析、中间相遇攻击、立方攻击、比特追踪法、侧信道攻击等.注重数学模型构建与编程测试技术相结合，以缩减轮数的算法或小版本的算法为例进行讲解和实验测试，部分内容来自参编人员的原创性研究成果，从研究角度还原模型提出和建立全过程，便于读者学习掌握发现问题、分析问题与解决问题的思路和方法.《密码分析学》配备了丰富的拓展学习资源，读者扫描二维码即可学习.

王美琴，现任山东大学网络空间安全学院常务副院长、密码技术与信息安全教育部重点实验室副主任，是中国密码学会理事、中国密码学会密码数学理论专业委员会副主任和教育部高等学校网络空间安全专业教学指导委员会委员, 国务院特殊津贴专家. 王美琴教授长期从事密码分析与设计理论的教学和科研工作，在EUROCRYPT、ASIACRYPT等国际密码学顶级会议和顶级刊物发表高水平论文百余篇,主持国家“变革性技术关键科学问题”重点专项课题、国家自然科学基金重点项目等多个项目，获得国家科技进步奖一等奖、党政机要密码科技进步奖一等奖等奖励.

密码作为网络安全的核心技术, 其重要性越来越被理解. 密码可分为对称密钥密码和非对称密钥密码, 简称为对称密码和非对称密码. 杂凑函数是密码系统中一类重要函数, 其研究技术与对称密码研究技术有比较强的关联性. 对称密码的研究分为设计与分析两个范畴, 对称密码算法的安全性比较多地依赖于其抵抗各种已有攻击方法的能力, 因此, 设计过程中的绝大多数研究工作仍然聚焦于密码算法的分析. 从这一角度看, 密码分析构成了对称密码算法研究领域的主旋律.

    山东大学《密码分析学》教材编写团队长期从事杂凑函数和对称密码算法分析相关研究, 取得了一系列突破性研究成果, 成果发表在国际五大密码会议和重要学术期刊上, 提出的新分析方法和新工具被国内外众多密码研究人员引用和使用. 本书编写历时三年, 内容涵盖了国内外学术界对称密码分析的主要研究成果, 特别突出了他们一线教学过程中总结的密码分析教学经验和科研成果, 内容新颖、完整, 表述清晰、规范, 既包含易于本科生理解的初等密码分析原理, 也涵盖了便于研究生和密码科研人员进行深入研究的进阶内容. 教材介绍的大部分分析方法都借助小版本的算法进行了实例演示, 对于学生理解密码分析思想和教师课堂讲授都十分友好.

目录
丛书序
序一
序二
前言
第1章 密码分析学概述1
1.1 密码分析学的基本概念1
1.2 各类算法的攻击目标4
1.3 密码分析的一般模型5
第2章 恩尼格玛密码机的破解10
2.1 猜测明密文的对应10
2.2 恢复扰频器的设置12
2.2.1 利用环路实现分割12
2.2.2 连接多台机器恢复扰频器设置14
2.3 恢复线路接线板的设置15
2.4 密钥恢复攻击16
第3章 分组密码的差分分析及相关分析方法18
3.1 差分分析18
3.1.1 差分分析原理19
3.1.2 CipherFour算法的差分分析21
3.2 截断差分分析38
3.2.1 截断差分分析原理38
3.2.2 CipherFour算法的截断差分分析40
3.3 飞去来器攻击及矩形攻击44
3.3.1 飞去来器攻击原理45
3.3.2 增强的飞去来器攻击原理47
3.3.3 矩形攻击原理49
3.4 不可能差分分析49
3.4.1 不可能差分分析原理49
3.4.2 Feistel结构的不可能差分分析53
3.5 相关密钥差分分析58
第4章 分组密码的线性分析及相关分析方法61
4.1 线性分析61
4.1.1 线性分析的研究动机与可行性分析61
4.1.2 线性分析框架62
4.1.3 S盒线性性质的提取66
4.1.4 密码算法线性近似的构造69
4.1.5 利用线性近似恢复更多子密钥信息72
4.1.6 统计假设检验73
4.1.7 线性分析复杂度与成功率的评估74
4.1.8 进一步阅读建议79
4.2 多重线性分析80
4.2.1 多重线性分析框架81
4.2.2 错误密钥下TMP的分布82
4.2.3 正确密钥下TMP的分布84
4.2.4 多重线性分析复杂度的评估87
4.3 多维线性分析88
4.3.1 多维线性分析框架88
4.3.2 错误密钥下TMD的分布89
4.3.3 正确密钥下TMD的分布90
4.3.4 多维线性分析复杂度的评估91
4.4 零相关线性分析92
4.4.1 零相关线性分析框架92
4.4.2 零相关线性分析复杂度的评估94
4.4.3 减少数据量的零相关线性分析94
4.5 多重和多维零相关线性分析94
4.5.1 多重和多维零相关线性分析框架95
4.5.2 多重和多维零相关线性分析复杂度的评估97
4.6 差分-线性分析98
4.6.1 差分-线性分析框架98
4.6.2 CipherFour算法的差分-线性分析100
4.7 密钥差分不变偏差技术102
4.7.1 密钥差分不变偏差技术的分析框架104
4.7.2 密钥差分不变偏差技术的通用攻击过程109
4.7.3 Mini-AES算法的相关密钥不变偏差攻击109
第5章 积分分析113
5.1 积分分析基本原理113
5.2 分离特性117
5.2.1 分离特性的思想117
5.2.2 向量化的分离特性121
5.2.3 比特级的分离特性122
第6章 中间相遇攻击126
6.1 中间相遇攻击原理126
6.2 相遇函数为值的攻击127
6.2.1 全状态值相遇的情况127
6.2.2 部分状态值相遇的情况130
6.2.3 拼切技术131
6.3 相遇函数为集合映射关系的中间相遇攻击132
6.3.1 DS中间相遇攻击的区分器133
6.3.2 密钥恢复攻击136
第7章 分组密码的其他攻击方法139
7.1 代数攻击139
7.1.1 插值攻击139
7.1.2 线性化141
7.1.3 Gr.bner基攻击143
7.2 滑动攻击144
7.2.1 滑动攻击原理145
7.2.2 Feistel结构的滑动攻击146
第8章 分组密码的各种分析方法的等价性149
8.1 基础知识150
8.1.1 相关定义150
8.1.2 主要结论151
8.2 不可能差分区分器与零相关线性壳的等价性153
8.3 零相关线性壳与积分区分器的联系155
8.4 不可能差分区分器与积分区分器的联系156
第9章 区分器的自动化搜索158
9.1 MILP自动化求解工具158
9.1.1 MILP简介158
9.1.2 差分区分器的搜索158
9.1.3 线性区分器的搜索163
9.1.4 不可能差分/零相关线性路线的搜索164
9.1.5 分离特性的搜索165
9.2 SAT自动化求解工具166
9.2.1 差分区分器的搜索166
9.2.2 线性区分器的搜索168
9.2.3 不可能差分/零相关线性路线的搜索170
9.2.4 分离特性的搜索171
9.2.5 DS中间相遇攻击的搜索173
第10章 分组密码工作模式的攻击概述180
10.1 电码本模式180
10.2 密文分组链接模式182
10.2.1 初始向量的作用与注意事项184
10.2.2 明文填充:处理明文长度非n整数倍的情形186
10.2.3 CBC的安全性188
10.2.4 CBC的选择密文攻击189
10.2.5 数据复杂度为2n/2的CBC通用攻击192
10.3 输出反馈模式197
10.4 计数器模式199
10.4.1 初始向量重用对OFB与CTR的损害201
第11章 序列密码的**安全性分析技术202
11.1 序列密码概述202
11.2 B-M算法203
11.3 相关攻击206
11.3.1 布尔函数的线性相关性207
11.3.2 Walsh-Hadamard变换207
11.3.3 LFSR驱动的序列密码的相关攻击209
第12章 序列密码的立方攻击211
12.1 布尔函数211
12.1.1 代数标准型211
12.1.2 莫比乌斯变换212
12.2 立方攻击原理213
12.3 动态立方攻击215
12.3.1 零化技术216
第13章 杂凑函数的安全性分析概述218
13.1 杂凑函数的通用攻击218
13.1.1 生日攻击原理219
13.1.2 广义生日攻击原理221
13.2 杂凑函数的常见结构224
13.3 杂凑函数的原像攻击226
13.3.1 中间相遇攻击226
13.3.2 差分中间相遇攻击227
13.3.3 完全二分结构体技术228
13.3.4 Keccak算法的原像攻击228
13.3.5 伪原像攻击转化原像攻击技术231
13.3.6 强制前缀的原像攻击232
13.4 杂凑函数的第二原像攻击234
13.4.1 基础知识234
13.4.2 基于拓展消息的第二原像攻击234
13.5 杂凑函数的碰撞攻击236
13.5.1 反弹攻击237
13.5.2 比特追踪法和消息修改技术239
第14章 消息认证码的安全性分析概述262
14.1 消息认证码概述262
14.2 消息认证码的伪造攻击263
14.2.1 R-型区分攻击和存在性伪造263
14.2.2 选择性伪造264
14.2.3 通用性伪造265
14.3 消息认证码的密钥恢复攻击266
14.3.1 5轮Keccak-MAC-512的密钥恢复267
第15章 侧信道分析概述268
15.1 侧信道分析原理269
15.2 时间攻击270
15.3 功耗分析272
15.3.1 功耗泄露采集方法272
15.3.2 简单功耗攻击273
15.3.3 差分功耗分析274
15.3.4 相关功耗分析276
15.3.5模板攻击278
15.4 侧信道安全研究热点279
附录A 算法说明281
A.1 恩尼格玛密码机281
A.1.1 线路接线板(S)282
A.1.2 扰频器组合(R)283
A.1.3 反射器(T)284
A.1.4 恩尼格玛密码机的使用284
A.2 CipherFour算法285
A.3 高级加密标准AES算法287
A.4 Mini-AES算法288
A.4.1 Mini-AES算法的轮函数288
A.4.2 Mini-AES算法的密钥生成算法289
A.5 Grain-128算法290
A.6 Keccak算法291
A.7 Whirlpool算法293
A.8 MD4算法294
A.9 MD5算法295
参考文献297

第1章 密码分析学概述
　　密码学是一门古老而又年轻的学科.可以说，从人类用笔书写开始，密码就被用于保护通信信息的机密性.随着计算机通信技术的发展，特别是大数据和互联网时代的到来，大量的敏感信息在公开网络上传输，密码已经和我们每个人的日常生活密不可分.密码学主要分为密码设计学和密码分析学.顾名思义，密码设计学致力于设计安全高效的密码算法，保护明文或密钥信息;密码分析学则力图发现密码算法的安全缺陷，尝试打破设计者宣称的安全界限，恢复明文或者密钥信息.新的密码分析方法的出现，影响了密码系统的设计理念，催生更完善的密码体制，而新的密码体制又激发新的分析技术，设计和分析的博弈永远没有尽头，这也正是密码学持续发展的动力.
　　在破与立的过程中，随着计算能力和密码算法设计水平的不断提高，现代密码分析学蓬勃发展，出现了很多新的攻击技术，例如，差分分析、线性分析、积分分析和比特追踪法等等.这些分析技术各有所长，从不同角度评估算法安全性，而一个密码体制抵抗现有各种分析技术的强度已成为衡量算法安全性的重要指标.因此，本书围绕对称密码算法、杂凑函数和消息认证码(Message Authentication Code，MAC)的安全性分析，介绍现代密码分析学的主流分析技术.
　　1.1 密码分析学的基本概念
　　*初，密码算法主要用于保密通信，而如今，现代密码算法的功能更加多样，应用范围更为广泛，除了用于保证机密性的加密算法，如高级加密标准(AES)外，还有用于保证消息完整性的杂凑函数，如ISO/IEC国际标准SHA-2算法;用于实现认证性的消息认证码，如ISO/IEC国际标准HMAC算法;用于同时提供机密性和认证性的认证加密算法，如美国国家标准与技术研究院(National Instituteof Standards and Technology，NIST)标准AES-GCM等.现代密码算法的设计以信息论为理论基础，破解难度大大提高，但是其安全性分析仍是密码学界持续关注的问题，特别是实用化的密码算法的安全性更是一直以来的研究热点.本节主要以对称加密算法的安全性为例，进行阐述.讨论开展密码分析的基本假设、攻击者能力和安全性的定义.
　　现代密码系统的主要设计原则之一是荷兰语言学家奥古斯特？柯克霍夫(AugustKerckhoffs)在1883年提出的六条准则[1]，其核心思想如下:
　　命题1.1 Kerckhoffs准则(Kerckhoffs’s principle)
　　密码体制的安全性仅依赖于密钥，其他一切(包括算法本身)都是公开的.
　　密码体制的安全性完全依赖于密钥的保密性，而非算法本身的保密性.从密码分析者的角度理解，该准则说明在评估密码体制安全性时，攻击者可以得到除密钥以外的有关算法的任何信息，包括每一个设计细节.
　　对密码分析者来说，要评估密码体制的计算安全性，就要尝试各种攻击方法.那么，攻击者除知道算法实现细节外，在不同的攻击环境下，攻击者掌握的信息不同，又可根据攻击者能力将攻击分为如下五种类型.
　　(1)唯密文攻击(Ciphertext-Only Attack):密码分析者能利用的资源仅为同一密钥加密的一个或多个密文.例如，搭线窃听的攻击者，可利用的资源仅为密文，因此，这是对密码分析者*不利的情况.
　　(2)已知明文攻击(Known-Plaintext Attack):密码分析者能够获得某些明密文的对应关系.例如，在某些应用中，用户终端到计算机的密文数据以一个标准词“LOGIN”开头，或者根据语言习惯等进行预判等等.因此，这是密码算法至少需要抵抗的一种攻击.
　　(3)选择明文攻击(Chosen-Plaintext Attack):密码分析者能够选择明文并获得相应的密文.计算机文件系统和数据库系统特别容易受到这种攻击，这是因为用户可以随意选择明文，并获得相应的密文文件和密文数据库，这样攻击者可以特意选择那些*有可能恢复出密钥的明文.对于对称密码算法，因为其密钥既用于加密又用于解密，所以常见的攻击多为选择明文攻击.这也是本书讨论的重点.
　　(4)选择密文攻击(Chosen-Ciphertext Attack):密码分析者能够选择密文并获得相应的明文.
　　(5)选择文本攻击(Chosen-Text Attack):密码分析者能够选择明文并获得相应的密文，也能够选择密文并获得相应的明文.这是选择明文攻击和选择密文攻击的组合，往往是密码分析者通过某种手段暂时控制加密机和解密机来实现的.
　　密码体制的安全性分为无条件安全(理论安全)和计算安全.
　　定义1.1 无条件安全
　　若某种密码体制，密码分析者无论知道多少信息，都不足以唯一确定目标密文对应的明文，则称该体制是无条件安全的.
　　无条件安全与密码分析者的计算资源无关.即无论有多少可用的明密文，花多少时间、占多少存储，密码分析者都无法将密文解密.除一次一密外，实际中应用的加密算法都不是无条件安全的.根据Kerckhoffs准则，实际中应用的加密算法的安全性依赖于一个固定长度的密钥，无论算法设计得如何复杂，都可利用通用攻击——强力攻击(例如，穷举攻击和查表攻击等)，恢复密钥.因此，要求实际中采用的算法达到“计算安全”.顾名思义，“计算安全”即要求从计算资源的角度来评估算法是安全的.这就需要考虑算法的每种现有攻击的效率.设存在某种密码攻击，则该攻击的效率一般从以下两个方面来衡量.
　　(1)成功率PS:密码攻击恢复的密钥为正确密钥的概率à.
　　(2)攻击复杂度:为达到成功率PS，攻击复杂度由以下三个指标决定.
　　(i)数据复杂度D:实现攻击所需的明文或密文的总数.
　　(ii)时间复杂度T:对采集到的数据进行分析和处理所消耗的时间，一般以运行一次算法加密的时间为单位.
　　(iii)存储复杂度M:实现攻击占用存储空间的大小，一般以字节为单位.注一般情况下，攻击复杂度不同，能达到的成功率不同，复杂度和成功率之间存在约束关系.因此，比较两个攻击优劣时，应把复杂度统一在相同的成功率下，再进行比较.
　　以穷举攻击为例.时间复杂度占主项，由穷举密钥的次数所决定.对于一个密钥长度为n比特的加密算法，若穷举密钥的所有2n种可能，依次进行验证，则可达到100%的成功率，复杂度为2n次加密运算.若仅随机选取一半的密钥进行验证，即尝试约2n.1种可能，则复杂度约为2n.1次加密运算，但此时，成功率约为.类似地，当穷举攻击的复杂度为2n.a时，成功率约为2.a.
　　定义1.2 计算安全
　　若某种密码算法体制，密码分析者尝试各种攻击方法进行分析.若在不可忽略的成功率下，各攻击方法的复杂度均超出了分析者的计算资源可达到的合理边界，则称该密码体制是计算安全的.
　　此外，有时还会出现“实际(practical)安全”，这是指密码分析者破译某密码体制的代价超过密文信息的价值，或破译密码的时间超过密文信息的有效期.
　　1.2 各类算法的攻击目标
　　不同的密码算法的安全属性不同，对应的攻击目标也不同.本节主要从本书关注的三类密码算法——对称加密算法、杂凑算法、消息认证码来看攻击者的攻击目标.
　　(1)对称加密算法主要用于保障机密性，同时，也是随机数生成器、杂凑函数或消息认证码等算法的基本部件，因此，对其进行安全性分析，主要考虑以下两类攻击.
　　(i)区分攻击:将分组密码算法与随机置换进行区分.
　　(ii)密钥恢复攻击:恢复出分组密码算法进行加解密运算采用的密钥.
　　密钥恢复攻击往往建立在区分成功的基础上.由于强力攻击的存在，设对称加密算法的密钥长度为n比特，则区分攻击和密钥恢复攻击的复杂度上界为2n.
　　(2)杂凑算法主要用于保障完整性，同时，也是数字签名的关键技术.对杂凑值长度为n比特的杂凑算法h，针对其安全属性，主要考虑以下四种攻击.
　　(i)原像攻击:给定n比特的H，找到消息M，满足h(M)=H.
　　(ii)第二原像攻击:给定消息M1，找到另一个数据串M2，满足h(M1)=h(M2)且M1.=M2.
　　(iii)碰撞攻击:找到两个消息(M1，M2)，满足h(M1)=h(M2)且M1.=M2.
　　(iv)长度扩展攻击à:给定n比特的杂凑值h(M)，其中M为未知的非空数据串，找到任意数据串N和n比特的H′，满足h(M∥N)=H′.
　　由于强力攻击的存在，原像攻击、第二原像攻击和长度扩展攻击的复杂度上界为2n，而对于碰撞攻击，存在生日攻击，故复杂度上界为2n/2.而对不同结构的杂凑算法，各类攻击的复杂度上界可能进一步降低.
　　(3)消息认证码(MAC)主要用于保障认证性，因其也视收发双方共享的密钥为密码体制中唯一保密的信息，故对称加密算法的攻击目标也适用于MAC算法.此外，还可以考虑伪造攻击.具体如下.
　　.区分攻击.
　　(i)R型区分攻击(Distinguishing-R Attack):将MAC算法与随机函数进行区分.
　　(ii)H型区分攻击(Distinguishing-H Attack):将基于具体密码元件(如杂凑函数SHA-1)构造的MAC算法与基于随机函数构造的MAC算法进行区分.
　　.伪造攻击.
　　设MAC算法的输入为M，输出为t，则不知道密钥的攻击者输出能通过验证的(M，t)，即Verf(M，t)=1.具体来说，分为以下三种.
　　(i)存在性伪造(Existential Forgery):攻击者与MAC算法进行交互后，输出(M，t)，满足Verf(M，t)=1且M在交互过程中没有被询问(query)过.例如，攻击者选择若干消息M1，M2，？？？，Ms，访问MAC算法并获得对应的正确的t1，t2，？？？，ts，然后输出(M，t)，满足M.={M1，M2，？？？，Ms}且Verf(M，t)=1.
　　(ii)选择性伪造(Selective Forgery):攻击者在与MAC算法进行交互之前，选定一个消息M.然后，根据交互获得的信息，输出(M，t)，满足Verf(M，t)=1且M在交互过程中没有被询问(query)过.
　　(iii)通用性伪造(Universal Forgery):对在与MAC算法进行交互之前任意给定的消息M，攻击者均可根据交互获得的信息，输出(M，t)，满足Verf(M，t)=1且M在交互过程中没有被询问过.
　　.密钥恢复攻击:恢复出MAC算法采用的密钥.
　　设MAC值t的长度为n比特，密钥长度为k比特，则区分攻击和伪造攻击的复杂度上界为min(2n，2k)，密钥恢复攻击的复杂度上界为2k.而对不同结构的MAC算法，各类攻击的复杂度上界可能进一步降低.例如，文献[3，4]中给出的基于杂凑函数的部分MAC算法的区分攻击的复杂度上界为2l/2，其中，l为中间链接变量的比特长度.
　　对于认证加密算法(AE)、公钥加密和数字签名算法都可类似考虑攻击者的攻击目标.
　　注 值得注意的是，密码分析并不仅仅分析完整的算法，一般会从分析算法的简化版本入手.例如，数据加密标准DES规定要16轮加密后的结果才是密文，那么在分析时，可以假设12轮就出结果，即对缩减到只加密12轮的DES的简化版本进行分析.如果发现算法的简化版本，通过分析算法在设计中存在的问题，随着时间的推移和技术的进步，可能会完成整个算法的破解.