5

Size: px

Start display at page:

Download "5"

量免连
5 years ago
Views:

1 现代密码学理理论与实践 5 高级加密标准 AES 苗付友, 黄文超主页 : mfy@ustc.edu.cn,

2 高级加密标准 AES 要点 AES 是一种分组密码, 用以取代 DES 的商业应用其分组长度为 128 位, 密钥长度为 128 位 192 位或 256 位 AES 没有使用 Feistel 结构每轮由四个独立的运算组成 : 字节代换置换有限域上的算术运算, 以及与密钥的异或运算

3 本章内容 1. AES 概述 2. The AES Cipher Rijndael 3. AES 的一轮加密过程 4. 安全性分析

4 1. AES 概述动机 DES 的不不安全建议用 3DES, 密钥 168 位, 抵御密码分析攻击但是 3DES 用软件实现速度较慢, 分组短, 仅 64 位

5 1. AES 概述起源美国国家标准技术协会 NIST 在 1997 年年征集新标准, 要求分组 128 位, 密钥或候选算法在 1998 年年 6 月通过了了第一轮评估, 仅有 5 个候选算法在 1999 年年 8 月通过了了第二轮评估 2000 年年 10 月,NIST 选择 Rijndael 作为 AES 算法, Rijndael 的作者是比利利时的密码学家 Joan Daemen 博士和 Vincent Rijmen 博士 2001 年年 11 月,NIST 完成评估并发布了了最终标准 FIPS PUB 197

6 1. AES 概述初选的评估准则安全性实际安全随机性 ( 观察等价 ) 可靠性( 数学基础 ) 其它安全因素 ( 公众提出的攻击方法 ) 成本专利利要求计算效率存储空间要求算法和执行行特征灵活性 ( 长度多平台多用性 ) 软/ 硬件简洁性

7 1. AES 概述最终评估的准则一般安全性依赖于密码学界的公共安全分析软件实现软件执行行速度, 跨平台执行行能力力及密钥长度改变时速度变化受限空间环境在诸如智能卡中的应用硬件实现硬件实现时能够提高执行行速度或缩短代码长度抵御密码分析攻击计时攻击能量量分析攻击密钥灵活性快速改变密钥长度的能力力其他的多功能性和灵活性指令级并行行执行行的潜力力

8 2 AES 密码回顾 1973 年年,Feistel 提出使用乘积密码的概念逼近理理想分组密码乘积密码 : 依次使用两个或两个以上的基本密码, 所得结果的密码强度将强于所有单个密码的强度 Feistel 建议交替使用代换和置换对应于 1949 年年 Shannon 提出的混淆和扩散当前使用的大多数重要对称分组密码的基本结构

9 2 AES 密码回顾 1 2 n n

10 XOR DES 方案轮循环函数子密钥产生算法密钥长度 56 位分组长度 64 位增加 : 初始置换 1 2 增加 : 逆初始置换 n 迭代次数长度 :16 n

11 密钥长度位 2 AES 密码概要子密钥产生算法分组长度 128 位 1 n 迭代次数长度 : n 轮循环函数

12 2 AES 密码概要 1 n n

13 XOR 2 AES 密码概要不不是 Feistel 结构

14 2 AES 密码概要 (128 位 ) n=10 时 1 n K 被扩展成 11 个 128 位的子密钥 (16 字节 ) n

15 2 AES 密码概要 (128 位 ) 迭代过程输入 state 数组 (16 字节 ) 子密钥 (16 字节 ) 输出 state 数组 (16 字节 )

16 运算法则 2 AES 密码概要 (128 位 ) GF(2^8) 算术不不可约多项式 m(x) =x 8 + x 4 + x 3 + x +1 例例 : A =(a 7 a 6...a 1 a 0 ) B =(b 7 b 6...b 1 b 0 ) A + B =(c 7 c 6...c 1 c 0 ) c i = a i b i {02} A =(a 6...a 1 a 0 0), if a 7 =0 {02} A =(a 6...a 1 a 0 0) ( ), if a 7 =1

17 2 AES 密码概要 (128 位 ) 其它特点算法简单仅在轮密钥加时使用密钥每个阶段均可逆 AES 解密算法与加密算法不不同最后一轮只包含前三步

18 State SubBytes S S S S S S S S S S S S S S S S State ShiftRows State MixColumns M M M M State r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 r 9 r 10 r 11 r 12 r 13 r 14 r 15 AddRoundKey State

19 3 一轮加密过程字节代换 y x s 0,0 s 0,1 s 0,2 s 0,3 s 1,1 s 1,0 s 1,2 s 1,3 S-box s' 0,0 s' 0,1 s' 0,2 s' 0,3 s' s' 1,0 1,1 s' 1,2 s' 1,3 s 2,0 s 2,1 s 2,2 s 2,3 s 3,0 s 3,1 s 3,2 s 3, x=8 y=6 s' 2,0 s' 2,1 s' 2,2 s' 2,3 s' 3,0 s' 3,1 s' 3,2 s' 3,3

20 Table 5.2 AES S-Boxes 代换 x=8 y= s=44 y A B C D E F x C 77 7B F2 6B 6F C B FE D7 AB 76 1 CA 82 C9 7D FA F0 AD D4 A2 AF 9C A4 72 C0 2 B7 FD F F7 CC 34 A5 E5 F1 71 D C7 23 C A E2 EB 27 B C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF 6 D0 EF AA FB 43 4D F9 02 7F 50 3C 9F A A3 40 8F 92 9D 38 F5 BC B6 DA FF F3 D2 8 CD 0C 13 EC 5F C4 A7 7E 3D 64 5D F DC 22 2A EE B8 14 DE 5E 0B DB A E0 32 3A 0A C C2 D3 AC E4 79 B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 C BA E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A D 70 3E B F6 0E B9 86 C1 1D 9E E E1 F D9 8E 94 9B 1E 87 E9 CE DF F 8C A1 89 0D BF E D 0F B0 54 BB 16 (a) S-box

21 逆代换 x s= x= y=6 y A B C D E F A D A5 38 BF 40 A3 9E 81 F3 D7 FB 1 7C E B 2F FF E C4 DE E9 CB B A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E E A D9 24 B2 76 5B A2 49 6D 8B D F8 F D4 A4 5C CC 5D 65 B C FD ED B9 DA 5E A7 8D 9D D8 AB 00 8C BC D3 0A F7 E B8 B D0 2C 1E 8F CA 3F 0F 02 C1 AF BD A 6B 8 3A F 67 DC EA 97 F2 CF CE F0 B4 E AC E7 AD E2 F9 37 E8 1C 75 DF 6E A 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B B FC 56 3E 4B C6 D A DB C0 FE 78 CD 5A F4 C 1F DD A C7 31 B EC 5F D F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C F 17 2B 04 7E BA 77 D6 26 E C 7D (b) Inverse S-box

22 3 一轮加密过程字节代换怎样求逆代换? S-Box 构建方式 EA F2 4D D 96 EC 6E 4C 90 5C B0 : 4A C3 46 E7 F0 2D AD C5 8C D8 95 A6

23 3 一轮加密过程字节代换 -SBox Byte at row y, column x initialized to yx yx Inverse in GF(2 8 ) 1. 初始化 : 构建 16*16 的盒子对第 y 行行, 第 x 列列的位置, 设定初值 {yx} 2. 求 {yx} 在 GF(2^8) 下的逆 3. 矩阵变换 ( 可逆 ) = Byte to bit column vector b 0 b 1 b 2 b 3 b 4 b 5 b 6 b b i = b i b (i + 4) mod 8 b (i + 5) mod 8 b (i + 6) mod 8 b (i + 7) mod 8 c i 5. 将列列向量量转为字节, 并填充至 (y,x) Bit column vector to byte S(yx) H X H X H X H X

24 3 一轮加密过程字节代换 -SBox Byte at row y, column x initialized to yx yx Inverse in GF(2 8 ) 例例子 Byte to bit column vector 1. 取输入 {95} ( 第 9 行行, 第 5 列列 ) 2. {95} 的逆为 {8A}={ } 3. M*[ ] +[ ] = b 0 b 1 b 2 b 3 b 4 b 5 b 6 b 结果 ={2A} Bit column vector to byte S(yx)

25 Byte at row y, column x initialized to yx yx Inverse in GF(2 8 ) H X H 3 一轮加密过程 XH X H X 字节代换 X H -SBox Byte at row y, column x initialized to yx yx Byte to bit column vector = Byte to bit column vector Bit column vector to byte b 0 b 1 b 2 b 3 b 4 b 5 b 6 b b 0 b 1 b 2 b X H X 0 0 X H X H 0 B =XB C. 1must show YXB 1 Y(XB C) D = B 0 becomes YXB YC D = B. YC = D = Bit column vector to byte Inverse in GF(2 8 ) b 0 b 1 b 2 b 3 b 4 b 5 b 6 b S(yx) YX equals the identity matrix, ector. XH X XH IS(yx) H H X H X H X

26 S-Box 的特点 3 一轮加密过程字节代换 -SBox 防止已有的各种密码分析攻击输出位和输入位的相关性很低 b i = b i b (i + 4) mod 8 b (i + 5) mod 8 b (i + 6) mod 8 b (i + 7) mod 8 c i 输出值不不是输入值的线性数学函数乘法逆没有不不动点 H X H X H X H X

27 3 一轮加密过程行行移位 s 0,0 s 0,1 s 0,2 s 0,3 s 1,0 s 1,1 s 1,2 s 1,3 s 2,0 s 2,1 s 2,2 s 2,3 s 3,0 s 3,1 s 3,2 s 3,3 s 0,0 s 0,1 s 0,2 s 0,3 s 1,1 s 1,2 s 1,3 s 1,0 s 2,2 s 2,3 s 2,0 s 2,1 s 3,3 s 3,0 s 3,1 s 3,2 (a) Shift row transformation

28 3 一轮加密过程列列混淆 s 0,0 s 0,1 s 0,2 s 0,3 s 1,0 s 1,1 s 1,2 s 1,3 s 2,0 s 2,1 s 2,2 s 2,3 s 3,0 s 3,1 s 3,2 s 3,3 (b) Mix column transformation s' 0,0 s' 0,1 s' 0,2 s' 0,3 s' 1,0 s' 1,1 s' 1,2 s' 1,3 s' 2,0 s' 2,1 s' 2,2 s' 2,3 s' 3,0 s' 3,1 s' 3,2 s' 3,3

29 3 一轮加密过程列列混淆 s 0, j = (2# s0, j ) (3# s1, j ) s 2, j s 3, j s 1, j = s 0, j (2# s1, j ) (3# s2, j ) s 3, j s 2, j = s 0, j s 1, j (2# s2, j ) (3# s3, j ) s 3, j = (3# s0, j ) s 1, j s 2, j (2# s3, j ) s an example of MixColumns: {02} A =(a 6...a 1 a 0 0), if a 7 =0 {02} A =(a 6...a 1 a 0 0) ( ), if a 7 =1

30 逆变换 3 一轮加密过程列列混淆 TD TD T D 0E 0B 0D E 0B 0D D TD T = D T 0D 09 0E 0B B 0D 09 0E E 0B 0D s 0,0 s 0,1 s 0,2 s 0,3 s 0,0 s 0,1 s 0,2 s 0,3 09 0E 0B 0D s 1,0 s 1,1 s 1,2 s 1,3 s 1,0 s 1,1 s 1,2 s 1,3 D TD TD T = D T 0D 09 0E 0B s 2,0 s 2,1 s 2,2 s 2,3 s 2,0 s 2,1 s 2,2 s 2,3 0B 0D 09 0E s 3,0 s 3,1 s 3,2 s 3,3 s 3,0 s 3,1 s 3,2 s 3,3 加密和解密的运算复杂度 D TD T D T

31 3 一轮加密过程轮秘钥加 A3 4C AC EB 59 8B 1B 37 D4 70 9F 77 FA D1 5C 40 2E A1 C3 94 E4 3A DC = F ED A5 A6 BC F A 1E 84 E7 D6

32 3 一轮加密过程秘钥扩展算法 1 n n

33 k 0 k 4 k 8 k 12 k 1 k 5 k 9 k 13 w k 2 k 6 k 10 k 14 g k 3 k 7 k 11 k 15 B 0 B 1 B 2 B 3 w 0 w 1 w 2 w 3 g B 1 B 2 B 3 B 0 S S S S ' ' ' B 1 B 2 B 3 ' B 0 w 4 w 5 w 6 w 7 RC j w' w 44 w 45 w 46 w 47 (b) Function g

34 3 一轮加密过程秘钥扩展算法 1 n 基本原理理 n 如果已知密钥或轮密钥的部分位, 不不能推算出其他位变换可逆 ( 由任意连续 Nk 个字可推出整个扩展密钥 ) 各种处理理器器均可使用使用轮常量量 RCj, 来消除对称性密钥的很多位能影响到轮密钥的许多位足够的非线性易易于描述

35 4 分析防御能力力雪崩效应当明文改变 1 位, 大约 1 半密文被改变当密钥改变 1 位, 大约 1 半密文被改变

36 4 分析密码学攻击理理论上, 复杂度少于 brute-force( 暴暴力力 ) 攻击的方法都算成功的攻击 2002 年年,XSL attack extended Sparse Linearization (XSL) attack 用于针对分组密码的攻击方式具有攻击 AES 的潜在可能性不不过目前没有找到可行行方案

37 4 分析密码学攻击 -XSL 攻击 XSL 攻击方案 ( 一种已知明文攻击, 且数量量要求较少 ) 分析密文的内部结构解析出一套多元二次方程组 : quadratic simultaneous equations, 如果 AES 为 128 位加密, 则有 8000 个等式 1600 个变量量解方程组, 求出密钥 (extended Sparse Linearization)

38 多元二次方程组求解 : NP 难问题 4 分析密码学攻击 -XSL 攻击 1999 年年,HFE 加密方案, 可以将方程组分解至 Overdetermined system ( 方程数大于变量量数 ) 思路路 :Linearization: 将每个二次项转换为一个独立变量量, 然后求解线性方程组挑战 : 方程数太少方法 :re-linearization:linearization 后, 加入额外的非线性方程, 再次线性化

39 4 分析密码学攻击 -XSL 攻击多元二次方程组求解 : 2000 年年, 改进方案 XL(eXtended Linearization) 思路路 : 增加线性方程的个数方法 : 略略 (multiplying them with all monomials of a certain degree) 缺陷 : 针对 AES 加密无效改进方案 : XSL 思路路 : 利利用这些新增方程的特殊结构

40 4 分析密码学攻击 -XSL 攻击产生 XSL 攻击的主要原因 S-box 的求逆过程过于简单 The method has some merit, and is worth investigating, but it does not break Rijndael as it stands. The XSL attack is not an attack. It is a dream. 1. 初始化 : 构建 16*16 的盒子对第 y 行行, 第 x 列列的位置, 设定初值 {yx} 2. 求 {yx} 在 GF(2^8) 下的逆 3. 矩阵变换 XSL may be a dream. It may also be a very bad dream and turn into a nightmare. 4. 将列列向量量转为字节, 并填充至 (y,x)

41 4 分析密码学攻击 -XSL 攻击产生 XSL 攻击的主要原因 S-box 的求逆过程过于简单 We have one criticism of AES: we don't quite trust the security 1. 初始化 : 构建 16*16 的盒子对第 y 行行, 第 x 列列的位置, 设定初值 {yx} 2. 求 {yx} 在 GF(2^8) 下的逆 What concerns us the most about AES is its simple algebraic structure No other block cipher we know of has such a simple algebraic representation. 3. 矩阵变换 4. 将列列向量量转为字节, 并填充至 (y,x)

42 4 分析密码学攻击 2009 年年攻击复杂度 :2 119 思路路 : 利利用密钥扩展算法的简易易性 2009 年年 12 月攻击复杂度 : 等等上述攻击并不不具备实用性

43 4 分析密码学攻击其他攻击类型 Towards Understanding the Known-Key Security of Block Ciphers known-key distinguishing attack the attacker knows the randomly drawn key the block cipher operates with and aims to find a structural property for the cipher under the known key a property which an ideal cipher (a permutation drawn at random) would not have For an n-bit block cipher with a known key, the goal is to find a plaintext/ciphertext pair with the least s < n/2 significant bits zero. For the ideal cipher, the adversary needs to invest about 2^s encryptions. A cipher that allows one to find such a pair with much less effort than 2^s encryptions is considered insecure in the known-key model. See: Lecture Notes on Cryptography

44 其他攻击类型 4 分析密码学攻击 Key recovery attack Given: The adversary has a sequence of q input-output examples of E T,say (M 1,C 1 ),...,(M q,c q ) where C i = E T (M i ) for i =1,...,q and M 1,...,M q are all distinct n-bit strings. Find: The adversary wants to find the target key T. 注 : 可能有多个 key 都符合条件选择明文攻击, 已知明文攻击 See: Lecture Notes on Cryptography

45 理理想的加密算法抵御所有攻击? 诸多限制分组大小密钥大小理理想分组密码 4 分析密码学攻击

46 4 分析旁路路 (side channel) 攻击计时攻击能量量分析攻击

47 4 分析旁路路 (side channel) 攻击 Cache-timing attack OpenSSL 的 AES 实现需求 : 200milllion 的选择明文多个 cache-timing attack 其中 1 种攻击的需求 : 800 个加密操作, 65ms In April 2005, D.J. Bernstein announced a cache-timing attack that he used to break a custom server that used OpenSSL's AES encryption.[31] The attack required over 200 million chosen plaintexts.[32] The custom server was designed to give out as much timing information as possible (the server reports back the number of machine cycles taken by the encryption operation); however, as Bernstein pointed out, "reducing the precision of the server's timestamps, or eliminating them from the server's responses, does not stop the attack: the client simply uses round-trip timings based on its local clock, and compensates for the increased noise by averaging over a larger number of samples. [31] In October 2005, Dag Arne Osvik, Adi Shamir and Eran Tromer presented a paper demonstrating several cache-timing attacks against AES.[33] One attack was able to obtain an entire AES key after only 800 operations triggering encryptions, in a total of 65 milliseconds. This attack requires the attacker to be able to run programs on the same system or platform that is performing AES.

48 4 分析旁路路 (side channel) 攻击 2009 年年针对某些硬件实现的攻击 Differential fault analysis 复杂度年年 AES 128 位破解特点 : 不不需要明文或密文, 接近实时地破解需求 : 在进行行加密的机器器上运行行无特权的程序 In November 2010 Endre Bangerter, David Gullasch and Stephan Krenn published a paper which described a practical approach to a "near real time" recovery of secret keys from AES-128 without the need for either cipher text or plaintext. The approach also works on AES-128 implementations that use compression tables, such as OpenSSL.[35] Like some earlier attacks this one requires the ability to run unprivileged code on the system performing the AES encryption, which may be achieved by malware infection far more easily than commandeering the root account.[36] In November 2010 Endre Bangerter, David Gullasch and Stephan Krenn published a paper which described a practical approach to a "near real time" recovery of secret keys from AES-128 without the need for either cipher text or plaintext. The approach also works on AES-128 implementations that use compression tables, such as OpenSSL.[35] Like some earlier attacks this one requires the ability to run unprivileged code on the system performing the AES encryption, which may be achieved by malware infection far more easily than commandeering the root account.[36]

49 2016 年年 4 分析旁路路 (side channel) 攻击攻击 128 bit AES 加密需求 : 6-7 个明文 / 密文对标准用户权限运行行 1 分钟时间

50 4 分析旁路路 (side channel) 攻击防范方式 : CPU 专用的 AES 指令集等等 Many modern CPUs have built-in hardware instructions for AES, which would protect against timing-related side-channel attacks.[38][39]

51 作业无

標準 BIG 中文字型碼表 A 0 9 ＢＣＤＥＦ一乙丁七乃九了二人儿入八几刀刁力匕十卜又三下丈上丫丸凡久么也乞于亡兀刃勺千叉口土士夕大女子孑孓寸小尢尸山川工己已巳巾干廾

標準 BIG 中文字型碼表 A 0 9 ＢＣＤＥＦ一乙丁七乃九了二人儿入八几刀刁力匕十卜又三下丈上丫丸凡久么也乞于亡兀刃勺千叉口土士夕大女子孑孓寸小尢尸山川工己已巳巾干廾標準 BIG 中文字型碼表 A 0 9 ＢＣＤＥＦＢＣＤ ± ＥＦ A 0 9 ＢＣＤＥＦ兙兛兞兝兡兣嗧瓩糎 0 Ｂ 9 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ｃ Ⅷ Ⅸ Ⅹ 〡〢〣〤〥〦〧〨〩十卄卅ＤＢＣＤＥＦＧＨＩＪＫＬＭＮＯＰＱＥＲＳＴＵＶＷＸＹＺａｂｃｄｅｆｇＦｈｉ