线性分析法

发表于 | 分类于 |

0x00 概述

线性分析法、差分分析法作为SPN(Substitution Permutation Network)的常用解法，一直让密码学家痴迷。最近也因为0ctf的一些密码学题目，对线性分析法有了一定的了解，并想写篇博客将具体内容详细展示！

0x01 SPN网络介绍

首先我们来看看这个spn网络

spn网络

每轮都包含3个步骤：substitution（代替）、permutation（置换）、key-mixing（轮密钥加）

1.1 substitution

输入4比特，输出4比特。这是一个双射，让集合$0-(2^4-1)$ 与其本身一一对应。

input 0 1 2 3 4 5 6 7 8 9 A B C D E F
output E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7

它起到混淆的作用！

1.2 permutation

输入16比特的数，对其各个比特进行置换。

input 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
output 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16

其实可以看出，这是对上面4组S盒输出的16个比特进行简单的置换。

这是一个可逆的操作！

1.3 轮密钥加

提到轮密钥加，我们不得不提轮密钥的产生。一般的轮密钥产生都是利用一种具有雪崩效应的算法，根据初始密钥，生成每一轮的密钥！比较少见的是给出一段较长的密钥，直接切割出每轮的密钥。

最好不要出现以下几种密钥：

  1. 简单密钥。对于使用的0000....00或者0101..0101类型的密钥，最好不要使用
  2. 可通过某一轮的密钥反解出所有密钥。（前提是你知道某一轮的密钥。。。）
  3. 轮密钥不要相关。如果轮密钥只是简单的进行了固定的循环左移或右移变换，那么所有的密钥将会有相同数量的1，以及相同距离的1。这都是很危险的。Related-key attack

1.4 解密

其实，由于上面的所有变换都是可逆的运算，所以最终都能根据轮密码求解出原文。

0x02 线性分析法简述

线性分析法的基本想法是生成一系列大概可用的线性表达式，如：

$X_{i_1}\oplus X_{i_2} ... X_{i_u} \oplus Y_{j_1} \oplus Y_{j_2} ... Y_{j_v}=0$

其中 $X_i$ 表示第i个比特的输入，$Y_j$ 表示第j个比特的输出

其实当我们比较随机的选取这u+v个比特，最终上述表达式成功的概率大概是1/2。

线性分析法基本原理：如果线性表达式成立的概率距离1/2越远，那么越容易使用线性分析法。若线性表达式发生概率为$p_L$， 那么$|p_L-1/2|$越大越好。

能够使用线性分析法的环境：线性分析可行一般取决于S盒设计，如果S盒导致出现多个线性表达式成立的概率距离1/2很远，那么最终分析结果将会越好；其次就是密钥长度不要太长，轮次不能太多，否则分析难度将会急剧增加。

2.1 Piling-Up Principle（叠加原理）

$$
\begin{equation}
P_r(X_1=i)=\left [
\begin{array}{lr}
p_1, i=0 \newline
1-p_1, i=1 \newline
\end{array}
\right]\
\end{equation}
$$

而
$$
P_r(X_2=i)=\left [
\begin{array} {lr}
p_2, i=0 \newline
1-p_2, i=1 \newline
\end{array}
\right]
$$

于是有：
$$
P_r(X_1 \oplus X_2) = P_r(X_1=X_2)=p_1 p_2 + (1-p_1)(1-p_2)
$$
令 $p_1=1/2+\epsilon_1$， $p_2=1/2+\epsilon_2$

则有 $P_r(X_1 \oplus X_2 = 0)=1/2+2\epsilon_1 \epsilon_2$

我们可以简写 $\epsilon_{1,2} = 2\epsilon_1 \epsilon_2$

根据Piling-Up Lemma (Matsui) ，我们可以快速得到：

$P_r(X_1 \oplus ... \oplus X_n = 0) = 1/2 + 2^{n-1} \prod_{i=1} ^n \epsilon_i$

如果其中某一个$p_i=1/2$， 那么最终的 $P_r(X_1 \oplus ... \oplus X_n = 0) = 1/2$

假设 $X_1 \oplus X_2$ 与 $X_2 \oplus X_3$ 是相互独立的，那么我么有：

$P_r(X_1 \oplus X_3 = 0) = 1/2 +2\epsilon_{1,2} \epsilon_{2,3}$

所以在这种情况下有 $\epsilon_{1,3} = 2\epsilon_{1,2} \epsilon_{2,3}$

2.2 分析S盒

假设S盒输入四位，输出四位，如下图所示：

S盒

假设现在使用的查看的是$X_2 \oplus X_3 \oplus =Y_1 \oplus Y_3 \oplus Y_4$

我们首先输入16个可能的输入作为X，然后检查对应的可能输出作为Y。我们发现这16个中有12个符合上面的等式。所以上式发生的概率偏差为 $12/16-1/2=1/4$

假设现在使用的查看的是$X_1 \oplus X_4 \oplus =Y_2$

我们首先输入16个可能的输入作为X，然后检查对应的可能输出作为Y。我们发现这16个中有8个符合上面的等式。所以上式发生的概率偏差为 $8/16-1/2=0$

近似值

上述讲述了通常意义上的方法，那么我们如何运用算法来求解呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
# sbox from the tutorial
sbox = [0xe, 4, 0xd, 1, 2, 0xf, 0xb, 8, 3, 0xa, 6, 0xc, 5, 9, 0, 7]
#sbox = [0xf, 3, 0xa, 6, 4, 1, 0xb, 9, 0xe, 5, 0, 0xd, 2, 0xc, 7, 8]
SIZE_SBOX = len(sbox)
linear_approx_table = [0]*SIZE_SBOX*SIZE_SBOX
# compute the linear approximation for a given "input = output" equation
def linearApprox(input_int, output_int):
    total = 0
    # range over the input
    for ii in range(SIZE_SBOX):
        # get input and output of our equations
        input_masked = ii & input_int
        output_masked = sbox[ii] & output_int
        # same result?
        if (bin(input_masked).count("1") - bin(output_masked).count("1")) % 2 == 0:
            total += 1
    # get the number of results compared to 8/16
    result = total - (SIZE_SBOX//2)
    if result > 0:
        result = "+" + str(result)
    else:
        result = str(result)
    return result
def main():
    # rows
    sys.stdout.write( "     | ")
    for i in range(SIZE_SBOX):
        sys.stdout.write(str(i).rjust(4) + " ")
    print ""
    print " " + "-" * (SIZE_SBOX * 5 + 5)
    for row in range(SIZE_SBOX):
        sys.stdout.write(str(row).rjust(4) +  " | ")
        # cols
        for col in range(SIZE_SBOX):
            # print the linear approx
            r = linearApprox(row,col)
            sys.stdout.write(r.rjust(4) + " ")
            linear_approx_table[row*SIZE_SBOX+col]=(int(r))
        print ""
    print linear_approx_table
if __name__ == "__main__":
    main()

根据上述算法，我们得到下面这张表linear Approximation Table：

我们来讲一讲这张表的含义：

Input sum代表的是所有比特位的累加和，output sum表示所有比特位的累加和。而在表中的数字代表的是：输入和的2进制表达式对应的输入与输出和的2进制表达式对应的输出组成的线性表达式，其成立的次数减去所有可能数的一半。

例如：$X_2 \oplus X_3 \oplus =Y_1 \oplus Y_3 \oplus Y_4$ 对应的就是$(2^2+2^1,2^3+2+2^0)=(6,11)=+4$，概率偏差就是1/4

$X_1 \oplus X_4 \oplus =Y_2$ 对应的就是$(2^3+1,2^2)=(9,4)=0$ 其概率偏差为0

几个常用的引理：

  1. 任何输出位的线性组合，在遍历ii，求得sbox[ii] & output_sum后，必定具有相同数量的0和1
  2. 所有无输出比特的线性组合与所有无输入的线性组合相等，都是1/2，即左上角（0,0）是sbox_size/2，而(0,i)=(i,0)=0， 其中i不为0。
  3. 所有行和的绝对值为sbox_size/2，所有列和的绝对值为sbox_size/2。

2.3 引理的证明

根据算法，我们可以写出下列表达式

我们首先看一下input_sum确定的情况：
$$
\sum_{j=0} ^n \sum_{i=0} ^n P(output_{mask},input_{mask})=\sum_{j=0} ^n \sum_{i=0} ^n P(i \& input_{sum}, sbox[i] \& j)
= \sum_{i=0} ^n \sum_{j=0} ^n P(i \& input_{sum}, sbox[i] \& j) = \sum_{sbox[i]=0} P(i \& input_{sum}, sbox[i] \& j) = -sbox_{size}/2 或者 +sbox_{size}/2
$$

0x03 线性分析法整体分析

3.1 具体步骤

根据上面那种线性分析表格，我们有：

$S_{12}: X_1 \oplus X_3 \oplus X_4 = Y_2; 概率12/16, 偏差1/4$

$S_{22}: X_2= Y_2 \oplus Y_4; 概率4/16, 偏差-1/4$

$S_{32}: X_2= Y_2 \oplus Y_4; 概率4/16, 偏差-1/4$

$S_{34}: X_2= Y_2 \oplus Y_4; 概率416, 偏差-1/4$

设 $U_{i,j}(V_{i,j})$ 表示第i轮的16比特中的第j比特输入或输出，$P_i$ 代表16位明文的第i位输入

于是我们有：

第一轮： $V_{1,6} = U_{1,5} \oplus U_{1,7} \oplus U_{1,8} = (P_5 \oplus K_{1,5}) \oplus (P_7 \oplus K_{1,7}) \oplus (P_8 \oplus K_{1,8})$ (2)

第二轮：$V_{2,6} \oplus V_{2,8} = U_{2,6} = V_{1,6} \oplus K_{2,6}$

带入第一轮的数据，有：$V_{2,6} \oplus V_{2,8} \oplus P_5 \oplus P_7 \oplus P_8 \oplus K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} =0 $ (3)

(2)式的概率偏差是1/4，概率为3/4，带入(3)式有其概率为： 1/2+2(3/4-1/2)(1/4-1/2)=3/8 (偏差-1/8)

第三轮：$V_{3,6} \oplus V_{3,8} = U_{3,6} = V_{2,6} \oplus K_{3,6}$

$V_{3,14} \oplus V_{3,16} = U_{3,14} = V_{2,8} \oplus K_{3,14}$

带入之后有： $V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \oplus V_{2,6} \oplus K_{3,6} \oplus V_{2,8} \oplus K_{3,14} = 0$ (4)

(4)式的概率为 1/2+2(1/4-1/2)(1/4-1/2) = 5/8 (偏差为1/8)

结合(3)、(4)式，我们有： $V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \oplus P_5 \oplus P_7 \oplus P_8 \oplus K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,14} = 0$

第四轮：由$U_{4,6} = V_{3,6} \oplus K_{4,6}$，$U_{4,8} = V_{3,14} \oplus K_{4,8}$， $U_{4,14}=V_{3,8} \oplus K_{4,14}$ ，$U_{4,16} = V_{3,16} \oplus K_{4,16}$

我们有：$U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} \oplus P_5 \oplus P_7 \oplus P_8 \oplus \sum_K = 0$

其中：$\sum_K = K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,14} \oplus K_{4,6} \oplus K_{4,8} \oplus K_{4,14} \oplus K_{4,16}$

其中$\sum_K$ 的值为0或1，并且由叠加原理，有其概率为 $1/2+2^3(3/4-1/2)(1/4-1/2)^3=15/32$ （偏差-1/32）

$U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} \oplus P_5 \oplus P_7 \oplus P_8 = 0$ （5）

第5轮：

3.2 获取Key的各比特位的值

上面之所以不进行第5轮的计算，是因为若R-1轮线性分析后，从密文反推会更为容易。

对于给出对应位置的部分目标子密钥$[K_{5,5} ... K_{5,8}, K_{5,13} ... K_{5,16}]$，解密出对应的密文得到$[V_{4,5} ... V_{4,8}, V_{4,13} ... V_{4,16}]$。通过S和的逆变换，我们可以求解出$[U_{4,5} ... U_{4,8}, U_{4,13} ... U_{4,16}]$ 。然后依据（5）式，可以算出符合该线性表达式的次数。

之所以可以使用这种方法，是因为如果部分目标子密钥正确，那么（5）式成立的概率将会与1/2有很大不同。而其他不正确的子密钥，将会造成（5）式概率接近于1/2。

(5)式影响S盒$S_{42}$ 和 $S_{44}$ 的输入。对于每对明密文对，我们将会尝试256种可能的部分目标子密钥$[K_{5,5} ... K_{5,8}, K_{5,13} ... K_{5,16}]$ 。对于每种可能的部分子密钥，我们都会求出(5)式为真时的次数。这些次数偏离最远的就是正确的解，当然不用管这些次数是正向偏移还是逆向偏移（其取决于$\sum_K$）。

当$\sum_K=0$ 时，（5）式成立的概率 < 1/2

当$\sum_K=1$ 时，（5）式成立的概率 > 1/2

我们测试了10000组已知明密文对，用下列公式计算偏移：

$|bias| = |count - 5000|/10000$

最终得到下面的表格：

根据表格可以看出$[K_{5,5} ... K_{5,8}]=0010, [K_{5,13} ... K_{5,16}]=0100$ 时，偏移概率最大，为0.0336。其实1/32=0.03125。注意到这些之后，我们可以肯定这两部分的密钥值就是这些。

而直到这两部分的值之后，我们完全可以爆破求解另外两部分的密钥（如果密钥是可以反向求解的！）

3.3 攻击的复杂度

成功原因：如果S盒偏差越大，线性分析的偏差也会越大。

设$\epsilon$ 为线性表达式距离1/2的偏差，Matsui表示要使攻击成功，那么已知明文的数量要与$\epsilon^-2$ 的数量成正比。

如果$N_L$ 表示线性表达式需要的已知明文数量，则有 $N_L \approx 1/\epsilon^2$

由于偏差使用线性叠加的方式来计算的，所以很容易看出偏差依赖于S盒的线性近似表达式和触发的S盒数量。

0x04 范例

既然讲到了线性分析法，那么我们就必须使用其进行解题。下面是2018 0ctf的一道题，zer0SPN

zer0SPN.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/usr/bin/env python
# coding=utf-8
#from secret import secret
rcon = [0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a]
sbox = [62, 117, 195, 179, 20, 210, 41, 66, 116, 178, 152, 143, 75, 105, 254, 1, 158, 95, 101, 175, 191, 166, 36, 24, 50, 39, 190, 120, 52, 242, 182, 185, 61, 225, 140, 38, 150, 80, 19, 109, 246, 252, 40, 13, 65, 236, 124, 186, 214, 86, 235, 100, 97, 49, 197, 154, 176, 199, 253, 69, 88, 112, 139, 77, 184, 45, 133, 104, 15, 54, 177, 244, 160, 169, 82, 148, 73, 30, 229, 35, 79, 137, 157, 180, 248, 163, 241, 231, 81, 94, 165, 9, 162, 233, 18, 85, 217, 84, 7, 55, 63, 171, 56, 118, 237, 132, 136, 22, 90, 221, 103, 161, 205, 11, 255, 14, 122, 47, 71, 201, 99, 220, 83, 74, 173, 76, 144, 16, 155, 126, 60, 96, 44, 234, 17, 215, 107, 138, 159, 183, 251, 3, 198, 0, 89, 170, 131, 151, 219, 29, 230, 32, 187, 125, 134, 64, 12, 202, 164, 247, 25, 223, 222, 119, 174, 67, 147, 146, 206, 51, 243, 53, 121, 239, 68, 130, 70, 203, 211, 111, 108, 113, 8, 106, 57, 240, 21, 93, 142, 238, 167, 5, 128, 72, 189, 192, 193, 92, 10, 204, 87, 145, 188, 172, 224, 226, 207, 27, 218, 48, 33, 28, 123, 6, 37, 59, 4, 102, 114, 91, 23, 209, 34, 42, 2, 196, 141, 208, 181, 245, 43, 78, 213, 216, 232, 46, 98, 26, 212, 58, 115, 194, 200, 129, 227, 249, 127, 149, 135, 228, 31, 153, 250, 156, 168, 110]
ptable = [
    0, 8, 16, 24, 32, 40, 48, 56,
    1, 9, 17, 25, 33, 41, 49, 57,
    2, 10, 18, 26, 34, 42, 50, 58,
    3, 11, 19, 27, 35, 43, 51, 59,
    4, 12, 20, 28, 36, 44, 52, 60,
    5, 13, 21, 29, 37, 45, 53, 61,
    6, 14, 22, 30, 38, 46, 54, 62,
    7, 15, 23, 31, 39, 47, 55, 63
]
sbox_inv = [143, 15, 224, 141, 216, 191, 213, 98, 182, 91, 198, 113, 156, 43, 115, 68, 127, 134, 94, 38, 4, 186, 107, 220, 23, 160, 237, 207, 211, 149, 77, 250, 151, 210, 222, 79, 22, 214, 35, 25, 42, 6, 223, 230, 132, 65, 235, 117, 209, 53, 24, 169, 28, 171, 69, 99, 102, 184, 239, 215, 130, 32, 0, 100, 155, 44, 7, 165, 174, 59, 176, 118, 193, 76, 123, 12, 125, 63, 231, 80, 37, 88, 74, 122, 97, 95, 49, 200, 60, 144, 108, 219, 197, 187, 89, 17, 131, 52, 236, 120, 51, 18, 217, 110, 67, 13, 183, 136, 180, 39, 255, 179, 61, 181, 218, 240, 8, 1, 103, 163, 27, 172, 116, 212, 46, 153, 129, 246, 192, 243, 175, 146, 105, 66, 154, 248, 106, 81, 137, 62, 34, 226, 188, 11, 126, 201, 167, 166, 75, 247, 36, 147, 10, 251, 55, 128, 253, 82, 16, 138, 72, 111, 92, 85, 158, 90, 21, 190, 254, 73, 145, 101, 203, 124, 164, 19, 56, 70, 9, 3, 83, 228, 30, 139, 64, 31, 47, 152, 202, 194, 26, 20, 195, 196, 241, 2, 225, 54, 142, 57, 242, 119, 157, 177, 199, 112, 168, 206, 227, 221, 5, 178, 238, 232, 48, 135, 233, 96, 208, 148, 121, 109, 162, 161, 204, 33, 205, 244, 249, 78, 150, 87, 234, 93, 133, 50, 45, 104, 189, 173, 185, 86, 29, 170, 71, 229, 40, 159, 84, 245, 252, 140, 41, 58, 14, 114]
def s2b(s):
    return map(int, format(int(str(s).encode('hex'), 16), '0{}b'.format(8*len(s))))
def b2s(b):
    return bytearray.fromhex(format(reduce(lambda x,y: 2*x+y, b), '0{}x'.format(len(b)/4)))
def addkey(a, b):
    global flag
    return bytearray(i^j for i,j in zip(a, b))
def substitute(a):
    return bytearray(sbox[i] for i in a)
def permutation(a):
    assert len(a) == 8
    bits = s2b(a)
    bits = [bits[ptable[i]] for i in xrange(64)]
    return b2s(bits)
def substitute_inv(a):
    return bytearray(sbox_inv[i] for i in a)
class zer0SPN(object):
    '''0ops Substitution–Permutation Network'''
    def __init__(self, key, key_size=8, rounds=4):
        assert len(key) == key_size
        self.key = key
        self.key_size = key_size
        self.rounds = rounds
        self.key_schedule()
    def key_schedule(self):
        roundkey = bytearray(self.key)
        tmp = roundkey[-4:]
        for i in xrange(1, self.rounds+1):
            tmp = tmp[1:] + tmp[:1]
            tmp = bytearray(sbox[i] for i in tmp)
            tmp[0] ^= rcon[i]
            for j in range(self.key_size/4):
                for k in range(4):
                    tmp[k] ^= roundkey[-self.key_size+k]
                roundkey += tmp
        self.roundkey = roundkey
    def get_roundkey(self, k):
        assert k <= self.rounds
        return self.roundkey[self.key_size*k:self.key_size*(k+1)]
    def encrypt(self, plain):
        assert len(plain) == self.key_size
        block = bytearray(plain)
        for i in xrange(self.rounds):
            block = addkey(block, self.get_roundkey(i))
            block = substitute(block)
            if i != self.rounds - 1:
                # Permutation in the last round is of no purpose.
                block = permutation(block)
        block = addkey(block, self.get_roundkey(i+1))
        return block
def key_schedule(key):
    rounds = 4
    key_size = 8
    roundkey = bytearray(key)
    tmp = roundkey[-4:]
    for i in xrange(1, rounds+1):
        tmp = tmp[1:] + tmp[:1]
        tmp = bytearray(sbox[i] for i in tmp)
        tmp[0] ^= rcon[i]
        for j in range(key_size/4):
            for k in range(4):
                tmp[k] ^= roundkey[-key_size+k]
            roundkey += tmp
    roundkey = roundkey
    return roundkey
def key_schedule_inv(last_key):
    rounds = 4
    key_size = 8
    roundkey = bytearray(last_key)
    for i in xrange(rounds, 0, -1):
        tmp = roundkey[4:8]
        for k in range(0,4):
            tmp[k] ^= roundkey[k]
        roundkey = tmp+roundkey
        tmp = roundkey[0:4]
        tmp = tmp[1:] + tmp[:1]
        tmp = bytearray(sbox[i] for i in tmp)
        tmp[0] ^= rcon[i]
        for k in range(0,4):
            tmp[k] ^= roundkey[4+k]
        roundkey = tmp + roundkey
    roundkey = roundkey
    return roundkey
for i in range(255):
    print sbox[i]^sbox[i+1]
exit(0)
if __name__ == '__main__':
    from os import urandom
    from struct import pack
    import binascii
    print "Your flag is flag{%s}" % secret.encode('hex')
    f = open('data', 'wb')
    for _ in xrange(65536):
        c = zer0SPN(secret)
        plaintext = bytearray(urandom(8))
        f.write(pack('8B', *plaintext))
        ciphertext = c.encrypt(plaintext)
        f.write(pack('8B', *ciphertext))
    f.close()

使用下面脚本获取S盒的缺陷表达式：(find_linear_approxmation)

1
2
3
4
5
6
7
for insum in xrange(256):
    for outsum in xrange(256):
        if insum&(insum-1) and outsum&(outsum-1):
            continue
        bias = sum((bin(x&insum).count('1') + bin(sbox[x]&outsum).count('1')) % 2 for x in xrange(256)) - 128
        if abs(bias) > 40:
            print '+'.join(['X'+str(i) for i in xrange(8) if insum&(2**i)] + ['Y'+str(i) for i in xrange(8) if outsum&(2**i)])

得到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
X0+Y0+Y1+Y2+Y7
X1+Y0+Y1+Y3+Y4+Y7
X2+Y0+Y1+Y2+Y3+Y4+Y6+Y7
X3+Y1+Y4+Y5+Y7
X4+Y0+Y2+Y4+Y5+Y6
X0+X3+X4+Y6
X0+X1+X2+X3+X4+Y2
X5+Y0+Y1+Y2+Y3+Y4
X0+X2+X3+X4+X5+Y7
X6+Y1+Y7
X1+X2+X3+X4+X6+Y0
X0+X2+X3+X4+X5+X6+Y1
X7+Y0+Y4
X1+X2+X4+X7+Y5
X1+X6+X7+Y3
X1+X2+X3+X4+X6+X7+Y4

然后我们来获得到第四轮时的表达式（未亦或）：(这里选择性地用了几组开始数据)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import sympy
rcon = [0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a]
sbox = [62, 117, 195, 179, 20, 210, 41, 66, 116, 178, 152, 143, 75, 105, 254, 1, 158, 95, 101, 175, 191, 166, 36, 24, 50, 39, 190, 120, 52, 242, 182, 185, 61, 225, 140, 38, 150, 80, 19, 109, 246, 252, 40, 13, 65, 236, 124, 186, 214, 86, 235, 100, 97, 49, 197, 154, 176, 199, 253, 69, 88, 112, 139, 77, 184, 45, 133, 104, 15, 54, 177, 244, 160, 169, 82, 148, 73, 30, 229, 35, 79, 137, 157, 180, 248, 163, 241, 231, 81, 94, 165, 9, 162, 233, 18, 85, 217, 84, 7, 55, 63, 171, 56, 118, 237, 132, 136, 22, 90, 221, 103, 161, 205, 11, 255, 14, 122, 47, 71, 201, 99, 220, 83, 74, 173, 76, 144, 16, 155, 126, 60, 96, 44, 234, 17, 215, 107, 138, 159, 183, 251, 3, 198, 0, 89, 170, 131, 151, 219, 29, 230, 32, 187, 125, 134, 64, 12, 202, 164, 247, 25, 223, 222, 119, 174, 67, 147, 146, 206, 51, 243, 53, 121, 239, 68, 130, 70, 203, 211, 111, 108, 113, 8, 106, 57, 240, 21, 93, 142, 238, 167, 5, 128, 72, 189, 192, 193, 92, 10, 204, 87, 145, 188, 172, 224, 226, 207, 27, 218, 48, 33, 28, 123, 6, 37, 59, 4, 102, 114, 91, 23, 209, 34, 42, 2, 196, 141, 208, 181, 245, 43, 78, 213, 216, 232, 46, 98, 26, 212, 58, 115, 194, 200, 129, 227, 249, 127, 149, 135, 228, 31, 153, 250, 156, 168, 110]
ptable = [
    0, 8, 16, 24, 32, 40, 48, 56,
    1, 9, 17, 25, 33, 41, 49, 57,
    2, 10, 18, 26, 34, 42, 50, 58,
    3, 11, 19, 27, 35, 43, 51, 59,
    4, 12, 20, 28, 36, 44, 52, 60,
    5, 13, 21, 29, 37, 45, 53, 61,
    6, 14, 22, 30, 38, 46, 54, 62,
    7, 15, 23, 31, 39, 47, 55, 63
]
sbox_inv = [143, 15, 224, 141, 216, 191, 213, 98, 182, 91, 198, 113, 156, 43, 115, 68, 127, 134, 94, 38, 4, 186, 107, 220, 23, 160, 237, 207, 211, 149, 77, 250, 151, 210, 222, 79, 22, 214, 35, 25, 42, 6, 223, 230, 132, 65, 235, 117, 209, 53, 24, 169, 28, 171, 69, 99, 102, 184, 239, 215, 130, 32, 0, 100, 155, 44, 7, 165, 174, 59, 176, 118, 193, 76, 123, 12, 125, 63, 231, 80, 37, 88, 74, 122, 97, 95, 49, 200, 60, 144, 108, 219, 197, 187, 89, 17, 131, 52, 236, 120, 51, 18, 217, 110, 67, 13, 183, 136, 180, 39, 255, 179, 61, 181, 218, 240, 8, 1, 103, 163, 27, 172, 116, 212, 46, 153, 129, 246, 192, 243, 175, 146, 105, 66, 154, 248, 106, 81, 137, 62, 34, 226, 188, 11, 126, 201, 167, 166, 75, 247, 36, 147, 10, 251, 55, 128, 253, 82, 16, 138, 72, 111, 92, 85, 158, 90, 21, 190, 254, 73, 145, 101, 203, 124, 164, 19, 56, 70, 9, 3, 83, 228, 30, 139, 64, 31, 47, 152, 202, 194, 26, 20, 195, 196, 241, 2, 225, 54, 142, 57, 242, 119, 157, 177, 199, 112, 168, 206, 227, 221, 5, 178, 238, 232, 48, 135, 233, 96, 208, 148, 121, 109, 162, 161, 204, 33, 205, 244, 249, 78, 150, 87, 234, 93, 133, 50, 45, 104, 189, 173, 185, 86, 29, 170, 71, 229, 40, 159, 84, 245, 252, 140, 41, 58, 14, 114]
def s2b(s):
    return map(int, format(int(str(s).encode('hex'), 16), '0{}b'.format(8*len(s))))
def b2s(b):
    return bytearray.fromhex(format(reduce(lambda x,y: 2*x+y, b), '0{}x'.format(len(b)/4)))
def addkey(a, b):
    global flag
    return bytearray(i^j for i,j in zip(a, b))
def substitute(a):
    return bytearray(sbox[i] for i in a)
def permutation(a):
    assert len(a) == 8
    bits = s2b(a)
    bits = [bits[ptable[i]] for i in xrange(64)]
    return b2s(bits)
def substitute_inv(a):
    return bytearray(sbox_inv[i] for i in a)
# Some precomputations of the P-box to use (byte,bit) indexing
pt = [[None for i in xrange(8)] for j in xrange(8)]
for i in xrange(8):
    for j in xrange(8):
        c = bytearray('\0'*8)
        c[i] = chr(2**j)
        d = permutation(c)
        i2 = None
        for k in xrange(8):
            if d[k] != 0:
                assert i2 is None
                i2 = k
        j2 = None
        for k in xrange(8):
            if (d[i2]&(2**k)) != 0:
                assert j2 is None
                j2 = k
        pt[i][j] = (i2,j2)
K = sympy.IndexedBase('K')
P = sympy.IndexedBase('P')
U4 = sympy.IndexedBase('U4')
def k(i, j, b):
    # not interested in which key bits are involved
    return 0
def p(i, b):
    # plain-text bits
    return P[i, b]
def u(i, j, b):
    if i == 4:
        # this is the input of the last S-box, leave it as it is
        return U4[j, b]
    # These numbers are from the S-box biases where there is only a single input bit involved, map them to output bits
    return sum(map(lambda x: v(i, j, x), [[0,1,2,7], [0,1,3,4,7], [0,1,2,3,4,6,7], [1,4,5,7], [0,2,4,5,6], [0,1,2,3,4], [1,7], [0,4]][b]))
def v(i, j, b):
    # From the output of an S-box we can get to the input of the next S-box by using the permutations (and some key bits)
    return k(i+1, pt[j][b][0], pt[j][b][1])+u(i+1, pt[j][b][0], pt[j][b][1])
def x(i):
    # Input of the first S-box is the plaintext bit ^ a key bit
    return p(0, i)+k(1, 0, i)
def y(i):
    # Output of the first S-box
    return v(1, 0, i)
print x(1)+x(2)+x(3)+x(4)+x(6)+y(0)
print x(0)+x(2)+x(3)+x(4)+x(5)+x(6)+y(1)
print x(0)+x(1)+x(2)+x(3)+x(4)+y(2)
print x(1)+x(6)+x(7)+y(3)
print x(1)+x(2)+x(3)+x(4)+x(6)+x(7)+y(4)
print x(1)+x(2)+x(4)+x(7)+y(5)
print x(0)+x(3)+x(4)+y(6)
print x(0)+x(2)+x(3)+x(4)+x(5)+y(7)

获得表达式：

1
2
3
4
5
6
7
8
P[0, 1] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 6] + U4[0, 0] + U4[0, 4] + U4[5, 0] + U4[5, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 0] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 5] + P[0, 6] + U4[0, 0] + U4[0, 4] + U4[3, 0] + U4[3, 4] + U4[4, 0] + U4[4, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 0] + P[0, 1] + P[0, 2] + P[0, 3] + P[0, 4] + U4[0, 0] + U4[0, 4] + U4[1, 0] + U4[1, 4] + U4[3, 0] + U4[3, 4] + U4[4, 0] + U4[4, 4] + U4[5, 0] + U4[5, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 1] + P[0, 6] + P[0, 7] + U4[0, 0] + U4[0, 4] + U4[2, 0] + U4[2, 4] + U4[3, 0] + U4[3, 4] + U4[6, 0] + U4[6, 4]
P[0, 1] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 6] + P[0, 7] + U4[1, 0] + U4[1, 4] + U4[2, 0] + U4[2, 4] + U4[3, 0] + U4[3, 4] + U4[5, 0] + U4[5, 4] + U4[7, 0] + U4[7, 4]
P[0, 1] + P[0, 2] + P[0, 4] + P[0, 7] + U4[3, 0] + U4[3, 4] + U4[4, 0] + U4[4, 4] + U4[5, 0] + U4[5, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 0] + P[0, 3] + P[0, 4] + U4[0, 0] + U4[0, 4] + U4[6, 0] + U4[6, 4]
P[0, 0] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 5] + U4[3, 0] + U4[3, 4] + U4[7, 0] + U4[7, 4]

最后我们看看上面的表达式，我们能够爆破的只有两个字节，因此应该选择合适的表达式进行展开。

由于性能的要求，这里使用的是c语言（这里用的是倒数第2个表达式）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
int sbox_inv[256] = {143, 15, 224, 141, 216, 191, 213, 98, 182, 91, 198, 113, 156, 43, 115, 68, 127, 134, 94, 38, 4, 186, 107, 220, 23, 160, 237, 207, 211, 149, 77, 250, 151, 210, 222, 79, 22, 214, 35, 25, 42, 6, 223, 230, 132, 65, 235, 117, 209, 53, 24, 169, 28, 171, 69, 99, 102, 184, 239, 215, 130, 32, 0, 100, 155, 44, 7, 165, 174, 59, 176, 118, 193, 76, 123, 12, 125, 63, 231, 80, 37, 88, 74, 122, 97, 95, 49, 200, 60, 144, 108, 219, 197, 187, 89, 17, 131, 52, 236, 120, 51, 18, 217, 110, 67, 13, 183, 136, 180, 39, 255, 179, 61, 181, 218, 240, 8, 1, 103, 163, 27, 172, 116, 212, 46, 153, 129, 246, 192, 243, 175, 146, 105, 66, 154, 248, 106, 81, 137, 62, 34, 226, 188, 11, 126, 201, 167, 166, 75, 247, 36, 147, 10, 251, 55, 128, 253, 82, 16, 138, 72, 111, 92, 85, 158, 90, 21, 190, 254, 73, 145, 101, 203, 124, 164, 19, 56, 70, 9, 3, 83, 228, 30, 139, 64, 31, 47, 152, 202, 194, 26, 20, 195, 196, 241, 2, 225, 54, 142, 57, 242, 119, 157, 177, 199, 112, 168, 206, 227, 221, 5, 178, 238, 232, 48, 135, 233, 96, 208, 148, 121, 109, 162, 161, 204, 33, 205, 244, 249, 78, 150, 87, 234, 93, 133, 50, 45, 104, 189, 173, 185, 86, 29, 170, 71, 229, 40, 159, 84, 245, 252, 140, 41, 58, 14, 114};
int cnt[256][256];
int bit(int n, int k)
{
    return (n & (1 << k)) != 0;
}
int main()
{
    auto f = fopen("data", "rb");
    for (int i = 0; i < 65536; i++) {
        uint8_t p[8], c[8];
        fread(&p, 8, 1, f);
        fread(&c, 8, 1, f);
        for (int a = 0; a < 256; a++) {
            for (int b = 0; b < 256; b++) {
                int u4b0 = sbox_inv[(int)c[0] ^ a], u4b6 = sbox_inv[(int)c[6] ^ b];
                if (bit(p[0], 0) ^ bit(p[0], 3) ^ bit(p[0], 4) ^ bit(u4b0, 0) ^ bit(u4b0, 4)
                  ^ bit(u4b6, 0) ^ bit(u4b6, 4)) {
                    cnt[a][b]++;
                }
            }
        }
    }
    for (int a = 0; a < 256; a++) {
        for (int b = 0; b < 256; b++) {
            int bias = abs(cnt[a][b] - 32768);
            if (bias > 1000)
                cout << a << " " << b << " " << bias << endl;
        }
    }
}

结果为：

1
2
3
4
5
6
130 103 1068
130 118 1044
130 194 2220
130 196 1111
130 213 1068
149 194 1045

于是我们可以认为最后1轮中，第0字节为130，第6个字节是194。

当然我们可用类似的办法求出另外一些字节：

1
2
3
4
5
6
7
8
9
10
11
def inv(rnd, r5):
    r4b = bytearray(r5[i]^r5[4+i] for i in xrange(4))
    r4a = bytearray(r5[i]^sbox[r4b[(i+1)%4]] ^ (rcon[rnd] if i == 0 else 0) for i in xrange(4))
    return r4a + r4b
r5 = bytearray([130, 167, 150, 65, 235, 239, 194, 40])
r4 = inv(4, r5)
r3 = inv(3, r4)
r2 = inv(2, r3)
r1 = inv(1, r2)
print 'flag{%s}'%(str(r1).encode('hex'))

最终的flag为flag{48667ec1a5fb3383}

0x05 引用

https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

https://gist.github.com/ngg/f534e51c14a832d69c41289837078773