对称之美,似锦繁花。

块加密就是每次加密一块明文,它是一种对称加密。

常见的块加密算法:

我们也可以把块加密理解一种特殊的替代密码,但是其每次替代的是一大块,明文空间巨大,对于不同的密钥几乎无法打表查询,因此必须得有复杂的加解密算法来加解密明密文。

而与此同时,明文往往可能很长也可能很短,因此在块加密时往往需要两个辅助

基本策略

香农老爷子提出的

混淆

混淆,Confusion,将密文与密钥之间的统计关系变得尽可能模糊,使得攻击者即使获取了密文的一些统计特性,也无法推测密钥。一般使用复杂的非线性变换可以得到很好的混淆效果

扩散

扩散,Diffusion,为了隐藏明文的统计属性而将一个明文符号的影响扩散到多个密文符号的加密操作。

常见加解密结构

迭代结构

便于设计与实现,同时方便安全性评估

一般包括三个部分:

目前,密钥扩展的方法有很多,没有见到什么完美的密钥扩展方法,基本原则是使得密钥的每一个比特尽可能影响多轮的轮密钥。

分组模式

分组加密会将明文消息划分为固定大小的块,每块明文分别在密钥控制下加密为密文。当然并不是每个消息都是相应块大小的整数倍,所以我们可能需要进行填充。

明文分组($M_n$):指分组密码算法中作为加密对象的明文,明文分组的长度与分组密码算法的分组长度是等长的。

密文分组($C_n$):指使用分组密码算法将明文分组加密之后所生成的密文。

填充

电子密码本模式(ECB)

img

1mg

加、解密过程都是一次对一个分组解密,而且每次加、解密都使用同一密钥。

密码分组链接模式(CBC)

CBC

字节翻转攻击

控制解密后任意明文(用于服务端)

只能改一个 $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$

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

1

2

令 $IV_n’ = IV_n’ \oplus 0x01 \oplus IV_n \oplus 0x02$,枚举 $IV_{n-1}’$,使得倒数第二位也为 0x02,从而得到 $E_{n-1}$

以此类推得到最后一组所有中间值与明文,然后去掉最后一组密文,只提交第一组到倒数第二组密文,构造倒数第三组密文得到倒数第二组密文的明文,以此类推,最终获得全部明文。

3

4

构造任意明文的密文

得知 $E_i$ 后构造 $IV’_i=E_i \oplus A$

然后通过解密任意明文得到 改变 $IV’_i$ 后,前一组的 $E’_i$,继续构造,以此类推则可构造。

例子

明文密码块链接(PCBC)

和 $CBC$ 差不多,也是在 $Encryption$ 前将 $M_i$ 与 $IV$ 异或,但这里的 $IV$ 是 $M_{i-1} \oplus C_{i-1}$

pcbc_encryption

密文反馈模式(CFB)

一种类似于流加密的分组密码

加、解密

加密过程:将 $IV$ 与 $key$ 加密后,与 $M_i$ 异或得到 $C_i$,再将 $C_i$ 与 $key$ 加密后,与 $M_{i+1}$ 异或得到 $C_{i+1}$,以此类推。

cfb_encryption

解密算法与加密算法相同。

重放攻击

条件:key 相同,中间人获得密文

A向B发送了两次消息,假设这两次消息都是由四个密文块组成。若攻击者将第二次接收到的最后三个密文块替换为第一次的三个,那么:

B解密第二次消息时,因为 $IV$ 没有变化,第一组密文可正确解密;

而第二组密文与第一组不匹配,故不可正确解密;

第三、四组密文可正确解密,不过得到的是第一次消息中的明文。

同样可以进行字节翻转攻击

但这里要注意的是:其实 CFB 模式的真实情况如下图:(OFB 也差不多)

cfb_encryption

前提:知道原 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$ 且能触发加密过程,就可解密所有密文。

ofb_encryption

同样可以进行字节翻转攻击。

计数器模式(CTR)

ctr_encryption

ctr_example

对于 CTR Mode 来讲,也是有字节翻转攻击的。

乘积加密法

加密

basis_enc

输入是分组长为 $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$ 也不同。

解密

basis \(R_{i-1} = L_i\\L_{i-1}=R_i \oplus f(L_i,K_i)\)

DES

介绍

des

过程详解

以上是对 $DES$ 加密过程的简单图示,但其中还有很多细节问题尚待说明。

这里给出一个更加繁杂的图示:

further_des

接下来,先解释左边,再解释右边。

f-function

子密钥生成

Key_generate

弱密钥

定义

$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

加、解密

\[C=E_{k3}(D_{k2}(E_{k1}(M)))\\M=D_{k1}(E_{k2}(D_{k3}(C)))\]

攻击方法

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盒部分的即可。

这jb堆积引理到底用在哪了 或许是多轮的时候用

那么,怎么找呢,具体方法如下:

假设 S盒大小为 256。那么,将输入的线性表达式写作 $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)$。

待补充

例题

差分攻击

插值攻击

积分攻击