【浅谈系列】差分分析与线性分析

12 minute read

Published:

总结一下差分分析与线性分析。

本科时期打 CTF 比赛,与分组密码差分线性分析相关的题目多见于 18-19 年,当时大一大二,只是大概了解会用脚本而对原理了解不够深入;而到大三大四时,差分和线性分析在比赛中不再热门,出现的也不多了。这学期选了密码分析学,看了一些理论方面的书,开文总结一下。

0. 参考资料

1. 差分分析

1.1 基本概念

  • 差分分析

    差分密码分析是目前分析迭代密码的主流方法之一。基本思想是通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。

  • 迭代密码

    迭代密码就是以迭代一个简单的轮函数为基础的密码,即通过选择某个较简单的密码变换,在密钥控制下以迭代方式多次利用它进行加密变换。

  • 差分

    冯登国老师在密码分析学中的定义如下:对分组长度为 $n$ 的 $r$ 轮迭代密码,将两个 $n$ 比特串 $Y_i$ 和 $Y_i^{\ast}$ 的差分定义为 $\Delta Y_i = Y_i \bigotimes Y_i^{\ast -1}$,其中 $\bigotimes$ 表示 $n$ 比特串集上的一个特定群运算,$Y_i^{\ast -1}$ 表示 $Y_i^{\ast}$ 在此群中的逆元。

    一般对迭代密码的差分考虑的是两个输入的异或和对应两个输出的异或。

  • 差分序列和 $r$-轮特征

    $Y_0$ 和 $Y_0^{\ast}$ 是明文对,$Y_i$ 和 $Y_i^{\ast}$ 是第 $i(1 \leq i \leq r)$ 轮的输出,同时也是 $i+1$ 轮的输入。差分序列指 $\Delta Y_0,…,\Delta Y_r$,这也是一个 $r$-轮特征。

  • 串联

    $\Omega^1 = \alpha_0,…,\alpha_m$ 和 $\Omega^2 = \beta_0,…,\beta_l$ 分别是 $m$-轮特征 和 $l$-轮特征,如果 $\alpha_m = \beta_0$,则 $m+l$ 轮特征 $\Omega^3 = \alpha_0,…,\alpha_m,\beta_1,…,\beta_l$ 称为 $\Omega^1$ 和 $\Omega^2$ 的串联。

  • 正确对与错误对

    有 $r$-轮特征 $\Omega = \alpha_0,…,\alpha_r$。对某个明文对 $Y_0 \bigoplus Y_0^{\ast} = \alpha_0$,其第 $i$ 轮输出有 $Y_i \bigoplus Y_i^{\ast} = \alpha_i$,则此明文对为特征 $\Omega$ 的一个正确对。否则称为错误对。

  • 差分概率

    有 $r$-轮特征 $\Omega = \alpha_0,…,\alpha_r$。差分概率 $p_i^{\Omega} = \text{P}(\Delta F(Y) = \alpha_i \mid \Delta Y = \alpha_{i-1})$。$p^{\Omega} = \prod_{i=1}^{r}{p_i^{\Omega}}$。

  • 信噪比

    对某一轮子密钥进行猜解。由生成的明密文对,对密钥投票。信噪比 $S/N$ 指正确密钥获得票数与错误密钥获得票数之比。

    假设 $P$ 为差分概率,$\lambda$ 为过滤密文的比例,$\nu$ 为被计数的每个明密文对所平均递增的计数器个数,简单来说就是平均的拥有的投票选票数量,$k$ 是搜索的子密钥的位数,$N$ 是选择明密文对的对数。

    信噪比 $S/N$ 为正确密钥获得的票数比上每个错误密钥平均获得的票数。正确对会为正确密钥和错误密钥投票,错误对只会为错误密钥投票。所以正确密钥可以从正确对获得一票,而正确密钥有且只有一个,即为 $NP$。错误密钥从正确对获得 $NP(\nu - 1)$ 票,从错误对获得 $N(\lambda-P)\nu$ 票,总共有 $2^k - 1$ 个错误对,所以平均每个错误对获得 $\frac{NP(\nu-1)+N\nu(\lambda-P)}{2^k-1}$ 票。

    因此信噪比为:

    \[S/N = \frac{P(2^k-1)}{\lambda \nu - P}\]

    如果差分攻击可以成功,必须信噪比 $S/N \gg 1$,这样才能让正确密钥在投票中获得明显多于错误密钥的票数。

  • 有效明文对个数

    有效即为通过过滤,参与最终投票的明密文对个数。这个问题在 BilhamShamir 当年的论文中给出结论。这里不给出推导,直接给出计算公式: $P_{\Omega} = c \cdot \frac{1}{p}$,其中 $c$ 是一个很小的常数,$p$ 是你用的差分特征的差分概率。

1.2 具体步骤

  • 第一步:寻找优质的 $r-1$ 轮特征,一般使其概率达到最大或几乎最大。或者可以满足信噪比远大于 $1$ 的要求也行。若不满足信噪比要求则无法使用差分攻击。

  • 第二步:均匀随机地选取明文,根据上一步的差分特征计算明密文对。过滤显然不满足条件的错误对,得到过滤后的正确对和部分错误对。要求过滤后的明密文对数满足 ShamirBilham 论文中的 $P_{\Omega} = c \cdot \frac{1}{p^{\Omega}}$,其中 $c$ 是一个很小的常数。

  • 第三步:对最后一轮子密钥的所有可能值进行投票,投票结束后明显高于其他计数器的,即为正确的子密钥(或部分比特)。

1.3 更多推广

下面是对差分分析的更多推广,本质还是差分,细节可参考冯登国老师的《密码分析学》。

  • 截断差分

    对某些密码体制,寻找高概率的差分特征是不可能的,但知道几比特的差分特性就足够解决问题,其他未知比特可以非常短的时间内穷搜出来。

  • 高阶差分

    1994 年由上交的来学嘉老师首次引入此概念。高阶差分分析是差分分析的高阶推广,又是积分分析的一个特例。差分分析研究的是迭代密码中一个明密文差分对的概率分布,而高阶差分分析和积分分析研究的是迭代密码中多个差分对的密码特性。高阶差分分析和积分分析的不同之处在于前者是对一组线性子空间中的明文所对应的密文求和,而后者对这个集合没有硬性要求,前者具有普遍性,而后者依赖于迭代密码的结构。

  • 不可能差分

    利用概率非常小的差分特征,排除必不可能的那些候选密钥。

2. 线性分析

3. 实例:CipherFour

密码分析学课程布置的作业,出处是 The Block Cipher Companion,作为例子来说明差分分析还是很简单易懂的。

我的解法如下,当时代码写的比较丑陋,后来做完了也懒得修好看了:

3.1 题目

分析如下的加密方案:

  • 五轮的一个加密方案

  • 其中 S 盒与 P 置换如下图:

  • 密钥生成:

    主密钥 50 比特,密钥生成算法每轮左循环移动 19 位,取密钥寄存器最左端 16 比特作为轮密钥。

用下面的代码对此加密方案进行实现。

# CipherFour


from Crypto.Util.number import long_to_bytes, bytes_to_long
import random


def sub_key_generate(global_key_length, rounds):
    global_key = random.getrandbits(global_key_length)
    str_global_key = bin(global_key)[2:]
    str_global_key = (global_key_length-len(str_global_key))*'0' + str_global_key
    assert len(str_global_key) == global_key_length
    sub_key = []
    for i in range(rounds):
        tmp_key = str_global_key[:16]
        str_global_key = str_global_key[19:]+str_global_key[:19]
        sub_key.append(int("0b"+tmp_key, 2))
    return sub_key
    

def S(x, Sbox):
    return Sbox[x]


def inv_S(x, Sbox):
    inv_Sbox = {x:y for y,x in Sbox.items()}
    return inv_Sbox[x]


def P(x, Permutation):
    tmp = [0]*len(x)
    assert len(x) == len(Permutation)
    for i in range(len(Permutation)):
        tmp[i] = x[Permutation[i]]
    res = "".join(j for j in tmp)
    return int("0b" + res, 2)
    

def CipherFour_Enc(plain, sub_key, rounds):
    plain = bytes_to_long(plain)
    assert len(bin(plain)) <= 18
    Sbox = {'0':'6', '1':'4', '2':'c', '3':'5', '4':'0', '5':'7', '6':'2', '7':'e', '8':'1', '9':'f', 'a':'3', 'b':'d', 'c':'8', 'd':'a', 'e':'9', 'f':'b'}
    Permutation = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
    assert len(sub_key) == rounds+1
    u = []
    u.append(plain)
    
    for i in range(rounds-1):
        tmp_a = u[i] ^^ sub_key[i]
        tmp_A = hex(tmp_a)[2:]
        tmp_A = (4-len(tmp_A))*'0' + tmp_A
        tmp_y = ""
        y = []
        for j in tmp_A:
            tmp_y += S(j, Sbox)
        y = bin(int("0x"+tmp_y, 16))[2:]
        y = (16-len(y))*'0' + y
        y = list(y)
        round_result = P(y, Permutation)
        u.append(round_result)
    
    assert len(u) == rounds
    tmp_a = u[rounds-1] ^^ sub_key[rounds-1]
    tmp_A = hex(tmp_a)[2:]
    tmp_A = (4-len(tmp_A))*'0' + tmp_A
    tmp_y = ""
    y = []
    for j in tmp_A:
        tmp_y += S(j, Sbox)
    y = int("0x"+tmp_y, 16)
    cipher = y ^^ sub_key[rounds]
    
    return long_to_bytes(cipher)


def CipherFour_Dec(cipher, sub_key):
    rounds = len(sub_key)-1
    cipher = bytes_to_long(cipher)
    assert len(bin(cipher)) <= 18
    Sbox = {'0':'6', '1':'4', '2':'c', '3':'5', '4':'0', '5':'7', '6':'2', '7':'e', '8':'1', '9':'f', 'a':'3', 'b':'d', 'c':'8', 'd':'a', 'e':'9', 'f':'b'}
    Permutation = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
    u = []
    u.append(cipher)
    
    tmp_y = cipher ^^ sub_key[rounds]
    tmp_y = hex(tmp_y)[2:]
    tmp_y = (4-len(tmp_y))*'0' + tmp_y
    tmp_a = ""
    for i in tmp_y:
        tmp_a += inv_S(i, Sbox)
    tmp_a = int("0x" + tmp_a, 16)
    tmp_u = tmp_a ^^ sub_key[rounds-1]
    u.append(tmp_u)
    
    for j in range(rounds-1):
        tmp_y = u[j+1]
        tmp_y = bin(tmp_y)[2:]
        tmp_y = (16-len(tmp_y))*'0' + tmp_y
        tmp_y = list(tmp_y)
        tmp_y = P(tmp_y, Permutation)
        tmp_y = hex(tmp_y)[2:]
        tmp_y = (4-len(tmp_y))*'0' + tmp_y
        tmp_a = ""
        for k in tmp_y:
            tmp_a += inv_S(k, Sbox)
        tmp_a = int("0x" + tmp_a, 16)
        tmp_u = tmp_a ^^ sub_key[rounds-2-j]
        u.append(tmp_u)
    
    return long_to_bytes(u[-1])
    

if __name__ == "__main__":
    plain = b"ha"
    global_key_length = 50
    rounds = 5
    sub_key = sub_key_generate(global_key_length, rounds+1)
    cipher = CipherFour_Enc(plain, sub_key, rounds)
    print (cipher)
    print (sub_key)
    dec_plain = CipherFour_Dec(cipher, sub_key)
    print (dec_plain)

随便选择一个明文进行验证,验证成功,说明我写的加密解密代码没有问题。

b'\xa0\xe4'
[49128, 41477, 59947, 62522, 750, 5631]
b'ha'

3.2 思路

整个加密方案看起来和一般的分组密码很像。

整个加密过程中总共有五轮,根据密钥生成算法,从主密钥生成了六个子密钥。除最后一轮外,每一轮明文先与轮密钥异或,再经过 S 盒,再经过一次 P 置换,然后进入下一轮。最后一轮没有 P 置换,与轮密钥异或后,经过 S 盒,再与最后的第六个密钥异或后输出密文。

整个流程中的非线性部分只有 S 盒。因此对这个加密方案的分析的关键就在于 S 盒。

我决定尝试使用差分分析来分析 S 盒。

Sbox = {'0':'6', '1':'4', '2':'c', '3':'5', '4':'0', '5':'7', '6':'2', '7':'e', '8':'1', '9':'f', 'a':'3', 'b':'d', 'c':'8', 'd':'a', 'e':'9', 'f':'b'}

differential_table = matrix(16)

for i in range(16):
    for j in range(16):
        input_diff = i ^^ j
        output_diff = int("0x"+S(hex(i)[2:], Sbox), 16) ^^ int("0x"+S(hex(j)[2:], Sbox), 16)
        differential_table[input_diff, output_diff] += 1

print(differential_table)

用上面的代码得到 S 盒的差分分布表,如下。

[16  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  6  0  0  0  0  2  0  2  0  0  2  0  4  0]
[ 0  6  6  0  0  0  0  0  0  2  2  0  0  0  0  0]
[ 0  0  0  6  0  2  0  0  2  0  0  0  4  0  2  0]
[ 0  0  0  2  0  2  4  0  0  2  2  2  0  0  2  0]
[ 0  2  2  0  4  0  0  4  2  0  0  2  0  0  0  0]
[ 0  0  2  0  4  0  0  2  2  0  2  2  2  0  0  0]
[ 0  0  0  0  0  4  4  0  2  2  2  2  0  0  0  0]
[ 0  0  0  0  0  2  0  2  4  0  0  4  0  2  0  2]
[ 0  2  0  0  0  2  2  2  0  4  2  0  0  0  0  2]
[ 0  0  0  0  2  2  0  0  0  4  4  0  2  2  0  0]
[ 0  0  0  2  2  0  2  2  2  0  0  4  0  0  2  0]
[ 0  4  0  2  0  2  0  0  2  0  0  0  0  0  6  0]
[ 0  0  0  0  0  0  2  2  0  0  0  0  6  2  0  4]
[ 0  2  0  4  2  0  0  0  0  0  2  0  0  0  0  6]
[ 0  0  0  0  2  0  2  0  0  0  0  0  0 10  0  2]

发现差分分布表中,差分特征分布并不均匀,所以对于 S 盒可以采用差分攻击。

而画出 P 置换的置换层的图如下,观察可以发现,在五轮的情况下,轮数较少,P 置换的扩散并不是很好。所以我们可以对于每个 S 盒寻找四轮差分特征,进行差分攻击。

本次作业只给出对于最后一轮子密钥的攻击。因为最后一轮需要找四轮差分特征,是相对而言最麻烦的,具有典型性。当最后一轮子密钥被破解后,前面的每一轮只要对照最后一轮的攻击,依葫芦画瓢就行。前面的每一轮的攻击就相当于重复的体力劳动了,只是多了一个 P 置换,P 置换先逆回去就行,没什么意义,所以我就没做。

3.3 寻找差分特征

首先,我们可以知道,非线性的部分只有 S 盒。所以说,对于某个输入差分,它经过 S 盒有一定概率得到某个输出差分,但之后经过 P 置换是 100% 概率的,一定能得到这个输出差分经过 P 置换后的值。

但是 P 置换会让总共四个十六进制位中的某一位的差分,扩散到其他位上,激活其他位的 S 盒。所以我寻找差分特征的时候,尽可能找那种一条路直线走到底,不激活其他 S 盒的,即使找不到一条直线走到底的,而必须要激活其他 S 盒,也一定要到最后一轮再激活。

因此,综合上述分析,对于四个 S 盒,分别寻找四轮差分特征如下。

对于每轮的第一个 S 盒,观察整个加密的图,我们可以发现如果最左边的这条线是一条路走到底,如下图所示。

那最左边这条路行得通吗?观察之前我们输出的差分分布表,可以发现 0x8000 满足要求。四轮下来是:

\[\text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000}\]

所以概率为 $(\frac{1}{4})^4$。

对于每轮的第三个 S 盒,可以类似地找到一个一条路走到底的差分路径,如下图所示。

发现 0x0020 满足要求,四轮下来是:

\[\text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020}\]

概率为 $(\frac{3}{8})^4$。

但是对于每轮的第二个和第四个 S 盒,并没有找到恰好的能一条直线走到底的。所以我采用之前第一个和第三个 S 盒的那两个一条直线走到底的,试图在第四轮经过 P 置换找到一条激活第二个和第四个 S 盒的差分路径。由于题目并不复杂,最后也幸运的找到了。

对于第四个 S 盒我找的差分路径如下图所示。

四轮下来是:

\[\text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0020} \overset{S,P}{\Longrightarrow} \text{0x0002}\]

对于第二个 S 盒我找的差分路径如下图所示。

四轮下来是:

\[\text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x8000} \overset{S,P}{\Longrightarrow} \text{0x0808}\]

3.4 如何过滤错误对

正确对和错误对的定义如课堂上或一般教科书上所讲。

如果到某一轮为止,中间每一轮的输出差分是我们想要的,都走了我们想要这个差分特征走的路,那就是正确对;如果在某个 S 盒路走错了走到了其他输出差分,不是我们想要的,那就是错误对。

差分特征往往差分概率不是一个很大的概率,如果我们不过滤错误对,那么大量的错误对给错误密钥投票,会导致下一个部分说的信噪比过高。

那如何过滤呢?很简单,比如第四轮我需要输出差分是 $0020$,那么最后一轮,也就是第五轮经过 S 盒后的输出只可能是 $0010,0020,0090,00a0$,如果输出不在这四个里面,那第四轮怎么也不可能是 $0020$,作为错误对过滤掉就好了。

比如这次实验,以第三个 S 盒为例,我们选取差分特征 $\text{0x0020}$,随机生成 $65536$ 个明密文对,看看其中有多少正确对和错误对,以及有多少可以通过过滤的错误对。运行如下代码:

# Differential characteristics related 2


def Enc_without_last_round(plain, sub_key, rounds):
    plain = bytes_to_long(plain)
    assert len(bin(plain)) <= 18
    Sbox = {'0':'6', '1':'4', '2':'c', '3':'5', '4':'0', '5':'7', '6':'2', '7':'e', '8':'1', '9':'f', 'a':'3', 'b':'d', 'c':'8', 'd':'a', 'e':'9', 'f':'b'}
    Permutation = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]
    assert len(sub_key) == rounds+1
    u = []
    u.append(plain)
    
    for i in range(rounds-1):
        tmp_a = u[i] ^^ sub_key[i]
        tmp_A = hex(tmp_a)[2:]
        tmp_A = (4-len(tmp_A))*'0' + tmp_A
        tmp_y = ""
        y = []
        for j in tmp_A:
            tmp_y += S(j, Sbox)
        y = bin(int("0x"+tmp_y, 16))[2:]
        y = (16-len(y))*'0' + y
        y = list(y)
        round_result = P(y, Permutation)
        u.append(round_result)
    
    assert len(u) == rounds
    tmp_a = u[rounds-1] ^^ sub_key[rounds-1]
    tmp_A = hex(tmp_a)[2:]
    tmp_A = (4-len(tmp_A))*'0' + tmp_A
    tmp_y = ""
    y = []
    for j in tmp_A:
        tmp_y += S(j, Sbox)
    y = int("0x"+tmp_y, 16)
    cipher = y ^^ sub_key[rounds]
    
    return tmp_a, cipher


characteristics = 0x0020
test_amount = 2^16
output_differential = []

global_key_length = 50
rounds = 5
sub_key = sub_key_generate(global_key_length, rounds+1)
test_filter_pass_cnt = 0
test_possible_last_round = [0x10, 0x20, 0x90, 0xa0]

for i in tqdm(range(test_amount)):
    plain_1 = random.randint(0, 0xffff)
    plain_2 = plain_1 ^^ characteristics
    tmp_1, cipher_1 = Enc_without_last_round(long_to_bytes(plain_1), sub_key, rounds)
    tmp_2, cipher_2 = Enc_without_last_round(long_to_bytes(plain_2), sub_key, rounds)
    output_differential.append(tmp_1 ^^ tmp_2)
    if cipher_1 ^^ cipher_2 in test_possible_last_round:
        test_filter_pass_cnt += 1

correct_pair_test_amount = Counter(output_differential)[characteristics]

print (correct_pair_test_amount, float(correct_pair_test_amount/test_amount))
print (test_filter_pass_cnt, float(correct_pair_test_amount/test_filter_pass_cnt))

结果如下:

100%|██████████| 65536/65536 [00:04<00:00, 15282.43it/s]
5488 0.083740234375
7992 0.6866866866866866

我们可以发现,如果不过滤,$65536$ 个明密文对中,正确对只有 $5488$ 个。而经过过滤之后,只剩下 $7992$ 个,$5488$ 个正确对在其中占比就很大了,就满足下文分析的信噪比的要求了。

3.5 整体代码

对最后一轮子密钥的攻击代码如下:

# Last round decrypt difference

def last_round_decrypt_difference(cipher_1, cipher_2, last_round_subkey):
    Sbox = {'0':'6', '1':'4', '2':'c', '3':'5', '4':'0', '5':'7', '6':'2', '7':'e', '8':'1', '9':'f', 'a':'3', 'b':'d', 'c':'8', 'd':'a', 'e':'9', 'f':'b'}
    Permutation = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]

    tmp_y_1 = cipher_1 ^^ last_round_subkey
    tmp_y_1 = hex(tmp_y_1)[2:]
    tmp_y_1 = (4-len(tmp_y_1))*'0' + tmp_y_1
    tmp_a_1 = ""
    for i in tmp_y_1:
        tmp_a_1 += inv_S(i, Sbox)
    tmp_a_1 = int("0x" + tmp_a_1, 16)
    
    tmp_y_2 = cipher_2 ^^ last_round_subkey
    tmp_y_2 = hex(tmp_y_2)[2:]
    tmp_y_2 = (4-len(tmp_y_2))*'0' + tmp_y_2
    tmp_a_2 = ""
    for i in tmp_y_2:
        tmp_a_2 += inv_S(i, Sbox)
    tmp_a_2 = int("0x" + tmp_a_2, 16)
    
    return tmp_a_1 ^^ tmp_a_2


# Attack last round key's xxx th hex number

def attack_last_round_key_xth_hexnum(xth_key, differential_characteristics, output_difference, probability, possible_last_round, sub_key, total_rounds):

    # initialize
    
    c = 3
    efficient_pair_amount = 10*int(1/probability)
    pair_amount = efficient_pair_amount

    rounds = total_rounds
    change_range = int("0x" + (5-xth_key)*'f', 16)

    plain_pair_list = []
    cipher_pair_list = []

    # filtering
    
    for i in tqdm(range(pair_amount)):
        plain_1 = random.randint(0, 0xffff)
        plain_2 = plain_1 ^^ differential_characteristics
        cipher_1 = bytes_to_long(CipherFour_Enc(long_to_bytes(plain_1), sub_key, rounds))
        cipher_2 = bytes_to_long(CipherFour_Enc(long_to_bytes(plain_2), sub_key, rounds))
        if cipher_1 ^^ cipher_2 in possible_last_round:
            plain_pair_list.append((plain_1, plain_2))
            cipher_pair_list.append((cipher_1, cipher_2))

    # vote
    
    key_vote = [0]*change_range
    vote_length = len(cipher_pair_list)
    # print (vote_length)
    max_vote = []

    for i in tqdm(range(change_range)):
        for j in range(vote_length):
            tmp_cipher_1, tmp_cipher_2 = cipher_pair_list[j]
            last_round_diff = last_round_decrypt_difference(tmp_cipher_1, tmp_cipher_2, i)
            if last_round_diff == output_difference:
                key_vote[i] += 1

    max_vote_cnt = max(key_vote)

    for i in tqdm(range(change_range)):
        if key_vote[i] == max_vote_cnt:
            max_vote.append(i)

    # print (max_vote_cnt)
    # print (max_vote)
    
    return (hex(max_vote[0])[xth_key-5])


def attack_last_round(sub_key, total_rounds):  
    attack_subkey = []
    tmp_subkey = ""
    
    # first hexnum
    
    xth_key = 1
    differential_characteristics = 0x8000
    output_difference = 0x8000
    probability = 0.003
    possible_last_round = [0x5000, 0x7000, 0x8000, 0xb000, 0xd000, 0xf000]
    tmp_subkey += attack_last_round_key_xth_hexnum(xth_key, differential_characteristics, output_difference, probability, possible_last_round, sub_key, total_rounds)
    
    # second hexnum
    
    xth_key = 2
    differential_characteristics = 0x8000
    output_difference = 0x0808
    probability = 0.003
    possible_eight = ['5', '7', '8', 'b', 'd', 'f']
    possible_last_round = []

    for i in range(len(possible_eight)):
        for j in range(len(possible_eight)):
            possible_last_round.append(int("0x" + possible_eight[i] + '0' +possible_eight[j], 16))
    
    tmp_subkey += attack_last_round_key_xth_hexnum(xth_key, differential_characteristics, output_difference, probability, possible_last_round, sub_key, total_rounds)

    # third hexnum
    
    xth_key = 3
    differential_characteristics = 0x0020
    output_difference = 0x0020
    probability = 0.02
    possible_last_round = [0x10, 0x20, 0x90, 0xa0]
    tmp_subkey += attack_last_round_key_xth_hexnum(xth_key, differential_characteristics, output_difference, probability, possible_last_round, sub_key, total_rounds)
    
    # fourth hexnum
    
    xth_key = 4
    differential_characteristics = 0x0020
    output_difference = 0x0002
    probability = 0.02
    possible_last_round = [0x1, 0x2, 0x9, 0xa]
    tmp_subkey += attack_last_round_key_xth_hexnum(xth_key, differential_characteristics, output_difference, probability, possible_last_round, sub_key, total_rounds)
    
    return int("0x"+tmp_subkey, 16)
    

if __name__ == "__main__":
    sub_key = [24190, 48858, 21109, 16139, 27989, 15091]
    attack_subkey = []
    total_rounds = 5
    
    last_round_key = attack_last_round(sub_key, total_rounds)
    print (last_round_key)
    attack_subkey.append(last_round_key)

运行结果如下:

100%|██████████| 3330/3330 [00:00<00:00, 7395.27it/s]
100%|██████████| 65535/65535 [00:18<00:00, 3623.58it/s]
100%|██████████| 65535/65535 [00:00<00:00, 2745278.08it/s]
100%|██████████| 3330/3330 [00:00<00:00, 10131.17it/s]
100%|██████████| 4095/4095 [00:01<00:00, 3569.54it/s]
100%|██████████| 4095/4095 [00:00<00:00, 3023886.42it/s]
100%|██████████| 500/500 [00:00<00:00, 10447.63it/s]
100%|██████████| 255/255 [00:00<00:00, 1094.38it/s]
100%|██████████| 255/255 [00:00<00:00, 1328630.46it/s]
100%|██████████| 500/500 [00:00<00:00, 9799.46it/s]
100%|██████████| 15/15 [00:00<00:00, 2105.22it/s]
100%|██████████| 15/15 [00:00<00:00, 99391.09it/s]
15091

显然,运行后得到 $15091$,和本次实验自己定义的轮密钥 $[24190, 48858, 21109, 16139, 27989, 15091]$ 中的最后一轮子密钥显然一致。

因此差分攻击成功,实验完成。

4. 实例:PRESENT

PRESENT 是一个知名的轻量级分组密码。CTF 中感觉见的不多,不过 Google 可以找到一些攻击,感兴趣可以自己深入了解。很巧的是,Google 出来的第一篇文章是本科时教我模电的老师。

PRESENT 密码的差分故障攻击 - 陈伟健

5. 实例:DES

DES 是最为知名的分组密码之一。在 CTF 比赛中也多次出现。

比如有魔改的六轮 DES 的差分分析。详见 WMCTF 2020 idiot box

比如有八轮 DES 的差分分析。详见 0CTF Quals 2019 zer0des

更多和 DES 相关的可以去看 Shamir 那篇经典的论文。

6. 实例:Feal-4

也是很经典的一个分组密码,四轮 Feistel 结构。在 CTF 比赛中也多次出现。

差分或是线性分析对它都很有效。

具体例子比如 VolgaCTF 2016 Quals Five Blocks

比如 starCTF 2019 notfeal

7. 实例:SM4

中国的国密算法。

相关的文献不是很多,我搜索到的只有一个差分故障攻击。比赛中被出过题,详见 强网杯 2020 fault

8. 实例:AES

AES 是美国新一代对称分组密码算法标准,于 2001 年 11 月 26 日公布。开发 AES 算法的是两位来自比利时的密码专家:Proton World InternationalJoan Daemen 博士和 Katholieke Universiteit Leuven 电子工程系的 Vincent Rijmen 博士。在选为标准之前,AES 被称为 Rijndael 算法。它采用的是代替置换网络。每一轮由三层组成,线性混合层确保多轮之后的高度扩散,非线性层由 $16$ 个 $S$ 盒并置而成,起到混淆的作用;密钥加层则简单地将子密钥异或到中间状态上。$S$ 盒选取的是有限域 $\text{GF}(2^8),\;m(x)=x^8+x^4+x^3+x+1$ 中的乘法逆运算,它的差分均匀性和线性偏差都达到了最佳。

它也是最知名的分组密码之一。CTF 比赛中很常见,且不局限于密码学,逆向等题目中也会出现。

例子比如 魔改版简易 AES

比如 GoogleCTF 2020 oracle writeup 1GoogleCTF 2020 oracle writeup 2

9. 实例:SPN toycipher

线性分析的经典例子,详见 0CTF 2018 zer0SPN,题目是一个用了 SPN 结构的玩具密码。


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.