密码攻击技术

现代密码技术的攻击方法授课老师：张秉晟浙江大学区块链与数据安全全国重点实验室

bingsheng@密码学技术发展历程阿兰图灵破译Enigma一战二战RSA算法古典密码机械密码现代密码安全密码系统：已知攻击无法破译以数学中的困难问题为基础，以可证明安全理论为核心安全密码系统：安全性实现数学严格语言学家为主导的艺术数学家为主导的科学密码学历史发展历史斯巴达密码器雅典信使----斯巴达密码器----密码学历史发展历史斯巴达与雅典正在进行长达十年的伯罗奔尼撤战争，雅典信使为了将军事情报从波斯安全地送往雅典，因而采用此种密码装置来隐藏机密信息。但不幸的是，一位斯巴达的军官房了该信使并得到了所谓的这个密码装置。----斯巴达密码器----密码学历史发展历史----斯巴达密码器----密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。----虎符----密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。----信使----密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。----虎符----用什么来证明信息的真实性？密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。春秋战国时期，君王可以将他所写的书信或者军令，连同君王所持有的虎符一同让信使送到驻军首领，驻军首领在收到信和虎符之后，将自己的虎符和信使的虎符进行合并，如果严丝合缝，说明消息真是来自国君传达的命令。----凭证----密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。魏安王二十年（公元前257年），秦国围困赵国都城邯郸，赵国求救于魏国，魏国惧怕秦国，不敢出兵救赵。情急之下，信陵君魏无忌听取侯赢之计，以国家利益为重，置生死度外，借魏王姬妾如姬之手窃得兵符，夺取了魏国兵权，不仅成功击败秦军、救援了赵国，也巩固了魏国在当时的地位。----窃符救赵----信陵君黑客密码学历史发展历史古代中国军队使用的密码：虎符：最早出现于春秋战国时期，铜制的虎形令牌，作为中央发给地方官或驻军首领的调兵凭证。阴书：古代兵书《六韬》记载的一种军事文书。使用方法：先把所要传递的机密内容写在一个竹简或木简上，再将这个竹简或木简拆开、打乱分成三份，称“一合而再离”。----阴书----古典密码:起源密码学的起源与政治和军事有很深的渊源。密码学的起源古典密码:起源凯撒密码如果需要传输机密消息，他们将会将消息加密成密文，通过改变字母表中字母的顺序，使得密文不能直接被识别。如果需要获取密文中的信息，就必须将密文中的字母按照字母表上的顺序进行固定数目的偏移来进行解密。比如用D代替A，用E代替B，以此类推。

—— 苏埃托尼乌斯，《凯撒大帝传》明文:我是中国人明文:

wo

shi

zhong

guo

ren

密文:

zr

vkl

ckrqj

jxr

uhq凯撒密码加密示例古典密码:发展电的产生实现电磁波在开放环境下通信电磁波通信能够在空间中自由传播，密码学成为该先进通信方式的重要安全保障手段古典密码:巅峰恩尼格玛密码机

古典密码:落幕计算机之父艾伦图灵和Bombe密码破译机艾伦·麦席森·图灵(1912—1954)数学家，逻辑学家战时密码破解者计算机之父Bombe密码破译机计算机技术的发展开启了现代密码学的新篇章古典密码:落幕在现代普通电脑的算力下，Enigma密码机可在10分钟内被完全破译。分组密码的基本概念分组密码的定义分组密码的发展历史分组密码的设计原则分组密码的主要结构PARTONE现代分组密码的发展历史历史2006年SM4算法公开发布，2012年3月成为国家密码行业标准，2016年8月成为我国国家标准。1997年1月2日，美国国家标准与技术研究院(NIST)开展AES的征集，以代替DES，掀起了分组密码研究的新高潮，2001年底Rijndael成为高级加密标准AES。1991年Biham和Shamir提出差分分析方法，1994年，Matsui提出线性分析方法。算法的安全性分析成为密码研究领域经久不衰的研究热点，新的分析技术和分析结果不断出现。1990年IDEA的出现打破DES类密码的垄断局面，随后出现了一系列SPN结构的分组密码算法，如SQUARE、SHARK、SAFER-64等。1980年涌现出一系列Feistel结构的算法，例如：LOKI，FEAL，GOST，SKIPJACK，CAST等。1977年美国国家标准局颁布数据加密标准（DES），第一个公开的、完全说明实现细节的商业级现代算法。发展历史现代分组密码的发展历史历史轻量级密码算法成为密码学研究领域的一个热点研究问题。随着传感器网络和RFID射频网络的发展和普及PresentCLEFIA算法入选ISO的轻量级分组密码标准，各国纷纷提出自己的轻量级密码算法，我国也正在开展轻量级算法设计竞赛。分组密码的设计原则历史理想分组密码理想的分组密码，可以允许生成最大数量的加密映射，来映射明文分组。Feistel提出：加密和解密映射用表定义分组密码的设计原则历史允许生成最大数量的加密映射来映射明文分组分组密码的设计原则历史允许生成最大数量的加密映射来映射明文分组

分组密码的设计原则历史理想分组密码的密钥长度理想的分组密码，虽然安全性高，可能的置换非常多，但是并不可行。

分组密码的设计原则历史安全性原则byShannon(1994)混淆与扩散：分组密码设计的本质

混淆

扩散打乱密文、明文、密钥之间的依赖关系。明文的统计特性消散于密文中，每个明文比特尽可能地影响多个密文，密文每个比特受多个明文比特影响。实现混淆扩散一种有效方法——“乘积密码”交替使用代替(substitution)与置换(permutation)两种或两种以上基本密码的逐次应用分组密码的设计原则历史实现原则

软件实现灵活性强、代价低使用子块与简单运算硬件实现高速率尽量使用规则结构0102分组密码的主要结构历史Feitel结构（例如DES、CAST、Skipjack）

分组密码的主要结构历史

加密解密

Feistel结构

分组密码的主要结构历史很多基于Feistel结构算法的轮数比基于SPN结构算法的轮数要长一些F:S-box和P1不要求F可逆，设计更加灵活2雪崩效应3轮数4Feistel结构分组密码的主要结构历史060504030201每一轮包含了代替(S-box)和置换(P)比Feistel结构更易于并行处理要求S盒可逆加解密函数不同轮数较短软硬件需求较大SPN结构数据加密标准DESPARTTWODES的历史历史IBM成立由HorstFeistel负责的计算机密码学研究项目，1971年设计出LUCIFER(128位)。20世纪60年代1973年5月13日美国国家标准局在联邦记录中发布公告，征求保护数据传输和存储安全的密码算法。1977年1月15日DES被正式批准为美国联邦信息处理标(FIPS-46），同年，7月15日生效。每隔五年评估一次，1998年12月以后停止使用。1972年美国国家标准局(NBS-NationalBureauofStandards)提出计算机数据保护标准的发展规划。1975年3月17日DES在联邦记录中公布。DES算法描述历史DES是一个16轮Feistel型密码，分组长度为64比特，密钥长度为56比特。DES由IBM开发，是对Lucifer体制的改进

DES算法描述–整体架构历史

DES算法描述–轮函数概述历史

+

E扩展S盒（S-box）P置换

E：固定的扩展函数，32bits48bits

密钥生成方案历史

解密历史

DES的安全性历史期望的安全性密文的每个比特都依赖于密钥和明文的所有比特。

分析布尔函数表达式明密文之间没有明显的统计关联。频率的特性改变任意单个明文比特或密钥比特都会使密文的每一个比特以1/2的概率改变。消除密文、明文、密钥之间的关系改变密文的一个比特会使被恢复的明文分组产生不可预见的变化。DES的安全性历史S-盒的设计原则（唯一的非线性部件）每个S-盒的每一行都是整数0~15的一个置换；每个S-盒的输出都不是它的输入的线性或仿射函数；改变S-盒的一个输入比特，其输出至少有2比特发生变化；DES的安全性历史

DES的安全性历史雪崩效应明文或密钥的某一位发生变化会导致密文的很多位发生变化。混淆和扩散DES有较好的雪崩效应。DES的安全性历史雪崩效应选定一个密钥，用两个仅有最高位不同的明文：00

00

00

00

00

00

00

00x和80

00

00

00

00

00

00

00x所用的密钥为：0000001

1001011

0100100

1100010

0011100

0011000

0011100

0110010结果表明，仅经过3迭代后，两段数据有21位不同。全部迭代完成后得到的两个密文有34位不同。DES的安全性历史在不知道密钥的情况下，明文的1比特发生改变，密文的每一个比特变与不变的概率均为1/2。固定明文，选择两个不同的密钥得到的密文基本上稳定在32比特。DES算法测试雪崩效应的常用方法：固定密钥，选择不同的明文或固定明文，选择不同的密钥，

看密文比特变化的数量。

DES的安全性历史密钥的安全隐患互补性选择明文攻击DES的安全性历史

四个DES弱密钥DES的安全性历史

DES的安全性历史

强力攻击PARTTHREE强力攻击

3一个算法的安全性是如何定义的？怎么才是安全的算法

分组密码的安全性历史

DES的安全性历史基本假设Kerckhoffs假设在密码分析中，除密钥以外，密码分析者知道密码算法的每一个设计细节。密码算法的安全性应依赖于密钥的保密性，而非算法本身的保密性。常见的攻击类型历史根据攻击环境的不同分为如下四种类型唯密文攻击(Ciphertext-only

attack):密码分析者能利用的资源仅为同一密钥加密的一个或多个密文，这是对密码分析者最不利的情况。已知明文攻击(Known-plaintext-attack):密码分析者根据已经知道的某些明密文对来恢复密钥。选择明文攻击(Chosen-plaintextattack)：密码分析者能够选择明文并获得相应的密文。是对密码分析者十分有利的情况。选择密文攻击(Chosen-ciphertext-attack):密码分析者能够选择密文并获得相应的明文。也是对密码分析者十分有利的情况。强力攻击历史

强力攻击历史强力攻击查表攻击预计算（离线）强力攻击历史

时间存储权衡攻击——Hellman(1980)强力攻击历史时间-存储权衡攻击（Time-memory

trade-off）Hellman，1980年提出选择明文攻击综合穷举攻击和查表攻击，以时间换取空间或者以空间换取时间，取得二者的平衡。建立密文、密钥之间的链接关系，分割密钥空间。强力攻击历史

强力攻击历史

强力攻击历史

强力攻击历史

强力攻击历史

强力攻击历史

强力攻击历史数量级对比双重和三重DES

DES致命弱点：密钥长度太短PARTFOUR双重DES历史

加密解密双重DES的中间相遇攻击历史

双重DES的安全性历史

三重DES（TripleDES,TDEA）历史

两个密钥的TDEA历史

直接进行分别搜索有难度若能从A处断开，即可进行中间相遇攻击。将A设为固定值，想办法将算法链接起来，不妨设A=0。

三重DES的缺点历史

差分分析PARTFIVE分组密码常见分析方法的总体思路历史攻击思想区分攻击经过加密之后的相同的明文，一定会对应相同的密文。发现不随机特征，将密码算法和伪随机函数区分开。构造区分器

分别征服攻击(Divide-and-Conquer

Attack)利用区分器降低搜索空间的大小，提高求解效率。将搜索或求解空间进行“分割”，将必须整体搜索的大空间分割为可局部搜索的小空间。常见的攻击技术历史

----AdiShamir----常见的攻击技术历史

常见的攻击技术历史

常见的攻击技术历史

常见的攻击技术历史

常见的攻击技术历史不均匀性——构造区分器的关键构造差分分析表的过程中，可以把满足输入差分得到的所有可能的输出差分对应的明文常见的攻击技术历史

常见的攻击技术历史

常见的攻击技术历史

常见的攻击技术历史一轮加密运算的差分传播概率——由S盒决定以DES为例，将

由S盒向外扩展常见的攻击技术历史12(1100)Ex0x0x0x0x0x0x0x0Cx0x0x0x0x0x0x0x0Cx00110001101110000000000000000000000000000000000000100000001000001000000000

00808200常见的攻击技术历史一轮加密运算的差分传播概率——由S盒决定一个特殊的一轮差分传播特性历史输入差分为零，输出差分一定为零。二轮差分传播特性历史

三轮差分传播特性历史

短轮数：搜索较优路线长轮数：输入差分为零迭代差分自动化搜索MILPSAT/SMT等等由短构造长的小技巧：利用概率为一的差分路线去进行拉长。

对于一个伪随机函数，给定一个输入差分，输出差分应该均匀的分布在所有可能的取值里面。正确对和错误对历史

信噪比历史

备注历史差分分析基于的假设轮密钥独立且均匀分布随机等价假设：假设对大多数密钥而言，固定密钥下的差分传播概率与各轮密钥相互独立且均匀分布时的差分传播概率近似相等。差分分析的基本原理历史

差分分析的基本原理历史

差分分析的一般步骤历史

差分分析的一般步骤历史所有明文对处理完毕后，计数器中计数最大的作为正确子密钥。换一个区分器求解剩下的密钥比特，或穷举搜索剩下的密钥比特。采样、去噪、提取信息。注：密钥恢复攻击只关心区分器的头尾，即高概率差分，与具体哪一条差分特征无关。5轮区分器历史缩减到8轮的DES的差分分析———5轮区分器DES算法一共有16轮先假设DES算法做8轮就输出密文如果8轮不安全，就增加1轮，以此类推如果8轮安全，可以体现16轮的安全性5轮区分器历史缩减到8轮的DES的差分分析———5轮区分器

缩减到8轮的DES的差分分析历史

缩减到8轮的DES的差分分析历史

缩减到8轮的DES的差分分析历史

缩减到8轮的DES的差分分析历史

缩减到8轮的DES的差分分析历史

密钥恢复攻击——有关S盒的方程组历史

密钥恢复攻击——有关S盒的方程组历史

密钥恢复攻击——有关S盒的方程组历史

密钥恢复攻击——有关S盒的方程组历史

替代置换网络Substitution-PermutationNetwork(SPN)替代置换网络史处理16位的输入通过重复四轮基本操作来完成加密过程每一轮包括：替代、置换、密钥混合替代置换网络历史替代历史

置换