介绍了一些块密码的相关概念、分组模式及经典算法,一些简单的攻击方法。
对称之美,似锦繁花。
块加密
块加密就是每次加密一块明文,它是一种对称加密。
常见的块加密算法:
- IDEA 加密
- DES 加密
- AES 加密
我们也可以把块加密理解一种特殊的替代密码,但是其每次替代的是一大块,明文空间巨大,对于不同的密钥几乎无法打表查询,因此必须得有复杂的加解密算法来加解密明密文。
而与此同时,明文往往可能很长也可能很短,因此在块加密时往往需要两个辅助
- padding,即 padding 到指定分组长度
- 分组加密模式,即明文分组加密的方式。
基本策略
香农老爷子提出的
混淆
混淆,Confusion,将密文与密钥之间的统计关系变得尽可能模糊,使得攻击者即使获取了密文的一些统计特性,也无法推测密钥。一般使用复杂的非线性变换可以得到很好的混淆效果
- S盒
- 乘法
扩散
扩散,Diffusion,为了隐藏明文的统计属性而将一个明文符号的影响扩散到多个密文符号的加密操作。
- 线性变换
- 置换
- 移位,循环移位
常见加解密结构
迭代结构
便于设计与实现,同时方便安全性评估
一般包括三个部分:
- 密钥置换
- 轮加密函数
- 轮解密函数
目前,密钥扩展的方法有很多,没有见到什么完美的密钥扩展方法,基本原则是使得密钥的每一个比特尽可能影响多轮的轮密钥。
分组模式
分组加密会将明文消息划分为固定大小的块,每块明文分别在密钥控制下加密为密文。当然并不是每个消息都是相应块大小的整数倍,所以我们可能需要进行填充。
明文分组($M_n$):指分组密码算法中作为加密对象的明文,明文分组的长度与分组密码算法的分组长度是等长的。
密文分组($C_n$):指使用分组密码算法将明文分组加密之后所生成的密文。
填充
-
ZeroPadding
数据长度不对齐时使用0填充,否则不填充。
-
PKCS7Padding
假设数据长度需要填充 n (n>0)个字节才对齐,那么填充n个字节,每个字节都是n;如果数据本身就已经对齐了,则填充一块长度为块大小的数据,每个字节都是块大小。
-
PKCS5Padding
PKCS7Padding基础上,块大小固定为8字节。
电子密码本模式(ECB)
加、解密过程都是一次对一个分组解密,而且每次加、解密都使用同一密钥。
密码分组链接模式(CBC)
-
IV 不要求保密,但必须是不可预测的,而且要保证完整性。
-
问题在于:接收端如何知道所使用的IV呢?
一种方法是在不安全的通道上发送该IV,并且该IV只使用一次,永不重复。 另外一种方法就是基于唯一数的概念。唯一数是一个唯一的数字,永远不重复使用 的密钥,它不一定非得保密,它可以是消息的数目等。用块加密法将唯一数加密后 生成IV。如果唯一数附加到密文前面,接收端就可以还原IV。
-
-
错误有限传播:如果加密后的某一分组某一位出现内容错误(指我们接收到的 $C_i$ 中的某一位),那么解密的时候最多只会让2个分组内容受到数据损坏的影响。
字节翻转攻击
控制解密后任意明文(用于服务端)
只能改一个 $Block$ 中的明文
知 $M_{i+1}=C_i\ xor\ f(C_{i+1} ),f(C_{i+1} )\ is\ before\ E_k,which\ means\ (M_{i+1} \ xor\ C_i)$
则可以构造 $C_i’=C_i\ xor\ M_{i+1} \ xor\ A$,则解密出的 $M_{i+1}’ = A$
- 这样会使得 $M_i$ 改变,若此为第一个Block可以通过改变 $IV$ 构造 $M_i$
Padding Oracle Attack
条件:知道密文以及 $IV$,并能够触发密文的解密过程,知道解密结果是否符合 $Padding$
原理
分组密码需要确保每组的长度都是分组长度的整数倍。若明文的最后一个分组长度不足,普遍的做法是在其后填充某固定的值,这个值的大小为填充的字节总数。如:最后还差3个字符,则填充3个0×03
则可以通过反复构造 $IV’/C’_{i-1}$ 的值,使得解密后最后一个分组的 $Padding$ 合法,从而一位一位得到 $M_i $
第 $k$ 次构造后使得最后 $k\ Bytes$ 都为 0x0k,即可获取该位字节的中间值 $E_ {i_k} = 0x0k \oplus IV_k’$,从而得到 $M_{i_k} = E_{i_k} \oplus IV_k$
攻击步骤
解密任意明文
枚举 $IV’_n$ ,直到解密成功得到合法填充即 0x01
令 $IV_n’ = IV_n’ \oplus 0x01 \oplus IV_n \oplus 0x02$,枚举 $IV_{n-1}’$,使得倒数第二位也为 0x02,从而得到 $E_{n-1}$
以此类推得到最后一组所有中间值与明文,然后去掉最后一组密文,只提交第一组到倒数第二组密文,构造倒数第三组密文得到倒数第二组密文的明文,以此类推,最终获得全部明文。
构造任意明文的密文
得知 $E_i$ 后构造 $IV’_i=E_i \oplus A$
然后通过解密任意明文得到 改变 $IV’_i$ 后,前一组的 $E’_i$,继续构造,以此类推则可构造。
例子
-
HGAME2019 WEEK4 CBCBC
这里摘取部分关键代码:
BLOCKS = lambda data: [data[16*i:16*(i+1)] for i in range(len(data)//16)] XOR = lambda s1, s2: bytes([x^y for x,y in zip(s1, s2)]) BLOCKSIZE = 16 IV = os.urandom(32) KEY = os.urandom(2 * BLOCKSIZE) def pad(data): pad_len = BLOCKSIZE - (len(data) % BLOCKSIZE) return data + bytes( [pad_len] * pad_len ) def unpad(data): pad_len = data[-1] _data = data[:-pad_len] if pad(_data) != data: raise ValueError('Padding is incorrect.') return _data def encrypt(data): assert len(data) > 2*BLOCKSIZE data = pad(data) iv_1, iv_2 = BLOCKS(data)[0], BLOCKS(data)[1] mid_1, mid_2 = iv_1, iv_2 cipher = b'' for block in BLOCKS(data)[2:]: block = XOR(block, mid_1) block = enc(block) mid_1 = block block = XOR(block, mid_2) block = enc(block) mid_2 = block cipher += block return iv_1 + iv_2 + cipher def decrypt(data): assert len(data) > 2*BLOCKSIZE assert len(data) % BLOCKSIZE == 0 iv_1, iv_2 = BLOCKS(data)[0], BLOCKS(data)[1] mid_1, mid_2 = iv_1, iv_2 plain = b'' for block in BLOCKS(data)[2:]: mid_2_n = block block = dec(block) block = XOR(block, mid_2) mid_1_n = block block = dec(block) # we define the block here as mid_3 block = XOR(block, mid_1) mid_1, mid_2 = mid_1_n, mid_2_n plain += block return unpad(iv_1 + iv_2 + plain) # we can get encrypt(flag) and the checking result of padding every time.
可以发现:
c[0] 是最容易获取的,只需要逐位篡改 IV1 进行 Padding Oracle Attack 即可。
那么之后的 c 如何获取呢:因为已知 mid_2 也即 c[i - 1],观察到只要获取 mid_1, 进行 Padding Oracle Attack 即可拿到 m.
- 逐位构造 IV1 to decrypt(IV1’ + c[i - 1] + c[i]) s.t. m = 0x0k 来得到正确的 mid_3.
- 逐位篡改 c[i - 2] to decrypt(IV1 + c’[i - 2] + c[i - 1] + c[i]) s.t. m = 0x0k, 则 mid_1 = mid_3 xor m xor c’[i - 2] xor c[i - 2]
- 已知 mid_1, mid_2, 进行 Padding Oracle Attack 即可.
然而事后看大佬的 WP 发现有更简单的做法= =:
逐位篡改 c’[i - 1] = c[i - 1] xor j to decrypt s.t m’ = 0x0k, then m = m’ xor j.
Because: m = mid_3 xor c[i - 1], 0x0k = c[i - 1] xor j xor mid_3.
明文密码块链接(PCBC)
和 $CBC$ 差不多,也是在 $Encryption$ 前将 $M_i$ 与 $IV$ 异或,但这里的 $IV$ 是 $M_{i-1} \oplus C_{i-1}$
密文反馈模式(CFB)
一种类似于流加密的分组密码
- 适应于不同数据格式的要求
- 错误有限传播
- 自同步
- 加、解密不能并行化
加、解密
加密过程:$C_i=M_i\oplus f(C_{i-1}, Key)$。
解密算法与加密算法相同。
重放攻击
条件:key 相同,中间人获得密文
A向B发送了两次消息,假设这两次消息都是由四个密文块组成。若攻击者将第二次接收到的最后三个密文块替换为第一次的三个,那么:
B解密第二次消息时,因为 $IV$ 没有变化,第一组密文可正确解密;
而第二组密文与第一组不匹配,故不可正确解密;
第三、四组密文可正确解密,不过得到的是第一次消息中的明文。
同样可以进行字节翻转攻击。
但这里要注意的是:其实 CFB 模式的真实情况如下图:(OFB 也差不多)
前提:知道原 plaintext, 同时能拿到每一次 Decrypt(C_i) 的对应结果。
一般来说,这里的 n = 8, 也就是 1 byte, 同时因为我们更改了 C_i, C_i 会被存放进寄存器, 根据 Encrypt() 就可能影响到接下来 k bytes 的明文解密。(例如 AES: 128/8 = 16 bytes)
所以这里需要逐位进行翻转。
测试代码如下:
from Crypto.Cipher import AES
from os import urandom
from Crypto.Util.number import *
class AES_CFB:
def __init__(self):
self.key = urandom(16)
self.iv = urandom(16)
def encrypt(self, plain):
aes = AES.new(self.key, AES.MODE_CFB, self.iv)
return aes.encrypt(plain)
def decrypt(self, cipher):
aes = AES.new(self.key, AES.MODE_CFB, self.iv)
return aes.decrypt(cipher)
plain = b'1'*32
aes = AES_CFB()
cipher = aes.encrypt(plain)
print(aes.decrypt(cipher))
for i in range(32):
pt = aes.decrypt(cipher)
cipher = cipher[:i]+long_to_bytes(ord(cipher[i:i+1])^ord(pt[i:i+1])^ord(b'2'))+cipher[i+1:]
print(aes.decrypt(cipher))
参考链接:对字节反转攻击的深入研究
输出反馈模式(OFB)
类似于 $CFB$,只不过 $IV_i=Enc(IV_{i-1},key)$。也就是说知道了初始 $IV$ 且能触发加密过程,就可解密所有密文。
- 不具有错误传播特性
- IV 无需保密,但是对每个消息必须选择不同的 IV
- 不具有自同步能力
- 适用于一些明文冗余度比较大的场景,如图像加密和语音加密
同样可以进行字节翻转攻击。
计数器模式(CTR)
-
计数器的生成方法:每次加密都会生成一个不同的值(nonce)来作为计数器的初始值。
例如:当分组长度为128比特(16字节)时,计数器的初始值可能是如下形式。其中,前8个字节为nonce,在每次加密时必须不同。后8个字节为分组序号,这个部分在加密过程中逐次累加。
对于 CTR Mode 来讲,也是有字节翻转攻击的。
Feistel 结构
加密
输入是分组长为 $2w$ 的明文和密钥 $K$
将每组明文分成左右两半 $L_0,R_0$,在进行完n轮迭代后,左右两半再合并到一起以产生密文分组。
其中第 $i$ 轮迭代的输入为: \(L_i = R_{i-1} \\Ri=L_{i-1} \oplus f(R_{i-1},K_i)\) $K_i$ 是第 $i$ 轮的子密钥,由加密密钥K得到。通常,各轮子密钥彼此不同,与 $K$ 也不同。
解密
\(R_{i-1} = L_i\\L_{i-1}=R_i \oplus f(L_i,K_i)\)
DES
介绍
- 输入 64 位
- 输出 64 位
- 密钥 64 位,使用 64 位密钥中的 56 位,剩余的 8 位要么丢弃,要么作为奇偶校验位。
- 尽管DES密钥有 64 位,但用户只能定义其中的 56 位,其余的 8 位由算法提供。分别 放在 8、16、24、32、40、48、56、64 位上,这样做是为了让每 8 位的块都有奇数个 1
- Feistel 迭代结构
- 明文经过 16 轮迭代得到密文。
- 密文经过类似的 16 轮迭代得到明文。
过程详解
以上是对 $DES$ 加密过程的简单图示,但其中还有很多细节问题尚待说明。
这里给出一个更加繁杂的图示:
接下来,先解释左边,再解释右边。
-
$IP(x),IP^{-1}(x)$
-
$f$ 函数
-
E 扩展置换
将32比特分为8个4位的分组,再将4位的分组拓展为6位,变成8个6位分组。
-
$E_i \oplus K_i$
-
S 盒
8 个 S 盒,每个对应 6 bits
对于每 6 bits,第 1 位和第 6 位形成一个二进制数,表示行数;其余四位组成的二进制数表示列数。行和列选定后,得到其交叉位置的十进制数,将这个数表示为4位二进制数即得这一 S 盒的输出。
-
P 盒
子密钥生成
- 用置换表 PC-1 进行置换操作,同时去除奇偶校验位。
- 将密钥分为 C0 和 D0 两个部分,并进行左位移(循环移位)操作,生成 C1 和 C2。
- C1 和 C2 根据置换表 PC-2 再次进行置换操作生成子密钥 k1。
- C1 和 C2 进行左位移操作,生成 C3 和 C4 ······
-
$PC-1$
在置换表中忽略第8、16、24、32、40、48、56、64位。(去掉奇偶校验位)
- 左位移操作
- 当 i = 1,2,9,16 轮时,左右两部分向左移动一位。
- 当 i ≠ 1,2,9,16 轮时,左右两个部分向左移动两位。
- 有趣的属性:$C_0=C_{16},D_0=D_{16}$
-
$PC-2$
从 56 位置换得到 48 位的子密钥
-
若有 $k_1’=k_{16},k_2’=k_{15},…,k_8’=k_9$,则这样的密钥对叫(半)弱密钥。
-
产生原因:
64 位的密钥经 PC-1 之后,变为 56 位,分为高 28 位和低 28 位,分别进行移位。
若高 28 位和低 28 位为全 0 或全 1,则经过移位后不变,16 个子密钥都相同。
移位是独立进行的,组合可以得到:
K1=…=K16=0x000000000000 K1=…=K16=0xFFFFFFFFFFFF K1=…=K16=0x000000FFFFFF K1=…=K16=0xFFFFFF000000
所以至少有四个弱密钥。
弱密钥
定义
$E_k(E_k(M))=M$
例子
0x0101010101010101
0xFEFEFEFEFEFEFEFE
0xE0E0E0E0F1F1F1F1
0x1F1F1F1F0E0E0E0E
若不考虑校验位以下四组也为弱密钥
0x0000000000000000
0xFFFFFFFFFFFFFFFF
0xE1E1E1E1F0F0F0F0
0x1E1E1E1E0F0F0F0F
半弱密钥
定义
$E_{k_1}(E_{k_2}(M))=M$
例子
0x011F011F010E010E 和 0x1F011F010E010E01
0x01E001E001F101F1 和 0xE001E001F101F101
0x01FE01FE01FE01FE 和 0xFE01FE01FE01FE01
0x1FE01FE00EF10EF1 和 0xE01FE01FF10EF10E
0x1FFE1FFE0EFE0EFE 和 0xFE1FFE1FFE0EFE0E
0xE0FEE0FEF1FEF1FE 和 0xFEE0FEE0FEF1FEF1
衍生
-
2DES
-
3DES
- 加、解密
攻击方法
- 差分攻击
- 线性攻击
AES
Attacks
线性攻击
mainly refer to 0xDktb
诸多密码系统中(如SPN网络),均有非线性变换的存在(如S盒)。线性攻击基于概率统计,其基本思想就是通过寻找一个给定密码系统算法的有效的近似线性表达式 $P[i_1,…,i_a] \oplus C[j_1,…,j_b] = K[k_1,…,k_c]$ 来破译密码系统(其中 i,j,k 都为固定比特位)。其利用了近似线性表达式的概率偏差。
前置知识
设 $X_1,…,X_K$ 是取值于集合 {0,1} 的独立随机变量。设 $p_i\in [0,1]$ 为实数,$Pr(x_i=0)=p_i,Pr(x_i=1)=1-p_i$。则设随机变量 $X_i$ 的分布偏差为 $\varepsilon_i = p_i - 1/2$。
堆积引理
$Pr(X_1\oplus … \oplus X_n = 0) = {1\over 2} + 2^{n-1} \Pi_{i=1}^n \varepsilon_i$,也即 $\varepsilon_{1,…,n}=2^{n-1} \Pi_{i=1}^n \varepsilon_i$。通过数学归纳法证明即可。
利用堆积引理,我们可以将每轮变换中偏差最大的线性逼近式进行组合,组合后的所有轮变换的线性逼近式,也将拥有最佳的偏差,即寻找分组密码的最佳线性逼近式。由于 SPN 网络中,仅有 S盒 为非线性变换,所以每轮线性逼近式的寻找,只需要寻求 S盒 部分的即可。
那么,怎么找呢,具体方法如下:
假设 S盒大小为 256 (2\^8)。那么,将输入的线性表达式写作 $P[i_1,…,i_a] = a_1·X_1 \oplus … \oplus a_8·X_8(a\in {0,1} )$;相应地,我们将S盒变换后的输出表示为 $C[j_1,…,j_a] = b_1·Y_1 \oplus … \oplus b_8·Y_8(b\in {0,1} )$。穷举(所有)(a, b),找出所有 $P[i_1,…,i_a] \oplus C[j_1,…,j_b] = 0$ 的概率。若该概率越偏离 0.5,越说明该对 (a, b) 不够均衡,故易作攻击之用。$\varepsilon(a,b) = (N_L(a,b)-128)/256$($N_L(a,b)$ 表示选定 $a,b$ 时满足以上关系的数量),选取 $\arrowvert \varepsilon(a,b) \arrowvert_{max}$ 的表达式,将其作为该S盒 下的最佳线性估计。基于足够多的数据对密钥进行枚举、逆向时,若密钥正确,则有 $\arrowvert bias \arrowvert \approx \varepsilon(a,b)$。
例题
-
0ctf 2019 zer0spn
-
EzSPN
差分攻击
也是 S 盒有缺陷导致的攻击,大概的攻击路径为找到一条差分路径,然后利用 filter 进行筛选。(不可能差分是一种特例)具体的我忘记了。。