三顺七的笔记
0%

Differential-Cryptanalysis-Analyse

发表于 更新于 分类于 Valine：

前言：

研究非对称密码就不得不学格理论，而研究对称密码就不得不去学习差分。

本篇同样会从一些比较简单的题目开始上手，一步一步学习差分攻击的本质，以及如何进行差分分析。

在看之前，不需要太多的理论知识，总之欢迎交流讨论。

开干：

  • 首先先认识一下什么是差分，已经他是如何起到作用的？
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
from secret import key,mask
S_BOX = [
    0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c,
    0x05, 0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26, 0x49, 0x86,
    0x06, 0x99, 0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43, 0xed,
    0xcf, 0xac, 0x62, 0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa,
    0x75, 0x8f, 0x3f, 0xa6, 0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c,
    0x19, 0xe6, 0x85, 0x4f, 0xa8, 0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb,
    0x0f, 0x4b, 0x70, 0x56, 0x9d, 0x35, 0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25,
    0x22, 0x7c, 0x3b, 0x01, 0x21, 0x78, 0x87, 0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52,
    0x4c, 0x36, 0x02, 0xe7, 0xa0, 0xc4, 0xc8, 0x9e, 0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38,
    0xb5, 0xa3, 0xf7, 0xf2, 0xce, 0xf9, 0x61, 0x15, 0xa1, 0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34,
    0x1a, 0x55, 0xad, 0x93, 0x32, 0x30, 0xf5, 0x8c, 0xb1, 0xe3, 0x1d, 0xf6, 0xe2, 0x2e, 0x82,
    0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab, 0x0d, 0x53, 0x4e, 0x6f, 0xd5, 0xdb, 0x37, 0x45,
    0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72, 0x6d, 0x6c, 0x5b, 0x51, 0x8d, 0x1b, 0xaf,
    0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41, 0x1f, 0x10, 0x5a, 0xd8, 0x0a, 0xc1,
    0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12, 0xb8, 0xe5, 0xb4, 0xb0, 0x89,
    0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09, 0xc5, 0x6e, 0xc6, 0x84,
    0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e, 0xd7, 0xcb, 0x39,
    0x48,
]

#key = 72
#mask = 41
def S(x,key):return S_BOX[x^key]
def L(x):return x^mask


in1 = ord(b'a')  #97
in2 = ord(b'b')  #98
out1 = L(S(in1,key))
out2 = L(S(in2,key))

print(f'out1={out1}\nout2={out2}')
#out1=125
#out2=34

简单出的一个demo，内容很短，但用来学习入门、了解足够了。

分析公式：

y = L(S(x\bigoplus key))\ 已知x,y

第一想法肯定是去穷举这个key参数，求解x->y这种情况下的key是多少，但遗憾的是存在一个L函数，导致了不能直接暴力穷举。(姑且当做不能吧，这样省事点，一定要在这道题上硬求肯定也是可以的)

这时候就引入了一些概念：

  • 线性组件：直接进行数学操作，比如异或或者按位与等，特点是可以进行数学逆向还原输入输出。不会影响输入和输出的差分值。

  • 非线性组件：具有查表替换的特点，直接置换输入，映射为输出。特点是需要知道输入/输出，才能进行置换。会影响输入和输出的差分值。

  • 差分：研究两个比特之间的异或值，比如：

△=X \bigoplus X’

(小三角就是差分值)

那么回到题目：

  • L函数就是一个线性组件、S函数就是一个非线性组件，保证加密安全性的主要是S函数，因为我们不知道key就无法解密，但是这个L函数一般是可以逆向还原得到输入的（这里图出题省事ban了）。

我们有两份用同一密钥加密的结果，所以直接找到S盒输入和输出的差分值，列出公式：

△_{out}=[L(S(X\bigoplus key))] \bigoplus [L(S(X’\bigoplus key))]\ =[S(X\bigoplus key)]\bigoplus[S(X’\bigoplus key)]\ △_{in}=[X\bigoplus key ]\bigoplus[X’\bigoplus key]\ =X \bigoplus X’\ 两者的差分值是已知的，其中只有key未知

(仔细观察一下in和out的差分值)

这时候我们就可以发现通过研究差分这种办法，直接绕过了L盒的比较，这时候我们发现：

  • 其实我们只要知道输出的差分值，就可以暴力穷举key的值，使得不可能成为可能。

所以到这里就可以写出实验代码了：

1
2
3
4
5
6
7
8
9
10
def get_k(in1,in2,out1,out2):
    diff = out1^out2
	key = []
    for k in range(256):
        if (S_BOX[in1^k]^S_BOX[in2^k]) == diff:
    		key.append(k)        
	return(key)

print(get_k(in1,in2,out1,out2))
#[72, 75]

如果结果的key比较多，建议拿多组试试。

那么到这里就对差分的研究有个初步了解了，那么继续来看看实战的应用，看看这种分析是怎么起到作用的。

N1CTF2023 SM4：

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import util
import os
FLAG = os.environ.get('FLAG', 'n1ctf{XXXXFAKE_FLAGXXXX}')
key = os.urandom(16)

ct = []
for i in range(5):
    ct.append(util.crypt_ecb(FLAG.encode(), key, 31-i).hex())

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

util函数：

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
from random import sample

i2l = lambda x: [(x >> 24) & 0xff, (x >> 16) & 0xff, (x >> 8) & 0xff, x & 0xff] #将32bytes 置换为列表
l2i = lambda x: (x[0] << 24)|(x[1] << 16)|(x[2] << 8)|x[3] #将列表 置换为32bytes
rotl32 = lambda x, n: ((x << n) & 0xffffffff) | ((x >> (32-n)) & 0xffffffff) #移位寄存,将最高位向后移动
rotl8 = lambda x, n: ((x << n) & 0xff) | ((x >> (8-n)) & 0xff) #单比特移位寄存，同上
xor = lambda x, y: list(map(lambda a, b: a ^ b, x, y))  #异或操作
pad = lambda data, block=16: data + [16 - len(data) % block]*(16 - len(data) % block)


SM4_BOXES_TABLE = [
    0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c,
    0x05, 0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26, 0x49, 0x86,
    0x06, 0x99, 0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43, 0xed,
    0xcf, 0xac, 0x62, 0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa,
    0x75, 0x8f, 0x3f, 0xa6, 0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c,
    0x19, 0xe6, 0x85, 0x4f, 0xa8, 0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb,
    0x0f, 0x4b, 0x70, 0x56, 0x9d, 0x35, 0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25,
    0x22, 0x7c, 0x3b, 0x01, 0x21, 0x78, 0x87, 0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52,
    0x4c, 0x36, 0x02, 0xe7, 0xa0, 0xc4, 0xc8, 0x9e, 0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38,
    0xb5, 0xa3, 0xf7, 0xf2, 0xce, 0xf9, 0x61, 0x15, 0xa1, 0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34,
    0x1a, 0x55, 0xad, 0x93, 0x32, 0x30, 0xf5, 0x8c, 0xb1, 0xe3, 0x1d, 0xf6, 0xe2, 0x2e, 0x82,
    0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab, 0x0d, 0x53, 0x4e, 0x6f, 0xd5, 0xdb, 0x37, 0x45,
    0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72, 0x6d, 0x6c, 0x5b, 0x51, 0x8d, 0x1b, 0xaf,
    0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41, 0x1f, 0x10, 0x5a, 0xd8, 0x0a, 0xc1,
    0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12, 0xb8, 0xe5, 0xb4, 0xb0, 0x89,
    0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09, 0xc5, 0x6e, 0xc6, 0x84,
    0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e, 0xd7, 0xcb, 0x39,
    0x48,
]

SM4_FK = [0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc]

SM4_CK = [
    0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269,
    0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
    0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
    0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
    0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229,
    0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
    0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209,
    0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279
]

box = sample(SM4_BOXES_TABLE, 256)
Dance_Box = [box, sample(box, 256), box, sample(box, 256)]

def dance(): #用D盒的两个比特
    global Dance_Box
    Dance_Box = Dance_Box[2:]+Dance_Box[:2]

def round_key(k): #拓展算法,有点奇怪
    ar = [SM4_BOXES_TABLE[i] for i in i2l(k)]
    b = l2i(ar)
    return b ^ rotl32(b, 13) ^ rotl32(b, 23)

def expand_key(master_key):  #拓展轮密钥
    master_key = list(master_key)
    MK = [l2i(master_key[:4]), l2i(master_key[4:8]),\
           l2i(master_key[8:12]), l2i(master_key[12:])]
    k = [0]*36
    k[0:4] = xor(MK, SM4_FK)
    for i in range(32):
        k[i + 4] = k[i] ^ (round_key(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ SM4_CK[i]))
    return k[4:]

def tfunc(bk):
    ar = [SM4_BOXES_TABLE[i] for i in i2l(bk)]
    b = l2i(ar)
    return b ^ rotl32(b, 2) ^ rotl32(b, 10) ^ rotl32(b, 18) ^ rotl32(b, 24)

def pfunc(bk):
    res = []
    for i in range(4):
        sbox = Dance_Box[i]
        ar = [sbox[_] for _ in i2l(bk[i])]
        b = [rotl8(ar[i], i+3) for i in range(4)]
        res.append(l2i(b))
    return res

def one_round(bk, rk, dt): #一轮加密
    out = []
    buf = [0]*36
    buf[:4] = [l2i(bk[:4]), l2i(bk[4:8]), l2i(bk[8:12]), l2i(bk[12:])]
    for i in range(32):
        if dt == i:
            dance()
        buf[i+4] = buf[i] ^ tfunc(buf[i+1]^buf[i+2]^buf[i+3]^rk[i])
        buf[i+1:i+5] = pfunc(buf[i+1:i+5])
    dance()
    for _ in range(4):
        out += i2l(buf[-1-_])
    return out
    


def crypt_ecb(pt, key, dance_time=-1):#pt = plaintext
    pt = pad(list(pt))
    rk = expand_key(key) #拓展密钥
    block = [ pt[_:_+16] for _ in range(0, len(pt), 16)] #分组处理
    result = b''
    for i in block:
        result += bytes(one_round(i, rk, dt=dance_time)) #一轮一密钥
    return result

题目比较长，但是这里也不会直接去讲解SM4算法是怎么进行的。

这里给出32轮加密时的流程图：大致组件和操作都是按照图里的内容进行：

SM4.png

(第32轮加密时的流程图)

如图所示：SM4算法每次处理一个块(16bytes)，一个块分4字节(4 bytes)处理(这里记作X)，所以每轮加密的结构就是上图。

回到开头我们所学过的，这里简单概括一下这些结构的特点：

  • P盒：pfunc函数，是个非线性处理的操作，但是我们可以逆向这个函数，通过输出得到输入的状态(每轮)。
  • T盒：tfunc函数，是线性处理操作，不可以通过输出逆向得到输入，但是每次处理都会保留差分特征。

注意到SM4的程序中还有一个Dance函数和Dance盒，用来影响P盒的操作，相当于故障注入，正是这一步使得差分分析的可能性存在：

那么一个很简单、自然的想法由此而生：

  • 能不能用开头的操作去求解每一轮的轮密钥，然后推出主密钥？

接下来开始推理：

X35=X31\bigoplus T(S(X32\bigoplus X33\bigoplus X34\bigoplus rK_{31}))\ 其中除了rK_{31}全部已知！\ 得：X35\bigoplus X35’=T(S(X32\bigoplus X33\bigoplus X34\bigoplus rK_{31}))\bigoplus T(S(X32\bigoplus X33\bigoplus X34\bigoplus rK_{31}))

式子看的很复杂，但是不管怎么样我们可以发现，这整个式子里面只有一个未知数——rK_31 !

而其中的输入（等式右边的变量）在异或、经过S盒之后，T盒与T盒之间的异或值，是等于S盒与S盒之间的异或值的。

所以我们可以通过：爆破rK_31的单字节(256种可能性)，重复4次，从而得到本轮的轮密钥。

上述的这种推理分析线性、非线性得到子秘钥的过程就是叫做差分分析（只可意会不好言传）

接下来就是反复执行上面的关键部4轮，恢复四个子秘钥，就可以推出完整的密钥，从而得到flag。

知道怎么利用差分之后，现在整理一下思路：

  • 在固定的某一轮，去求解子秘钥
  • 逆推会上一轮，重复上一步
  • 求解四轮子秘钥之后，倒推回主密钥
  • 解密

EXP：

补写了解密算法的SM4脚本：

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
134
135
136
137
138
139
from random import sample

i2l = lambda x: [(x >> 24) & 0xff, (x >> 16) & 0xff, (x >> 8) & 0xff, x & 0xff] #将32bytes 置换为列表
l2i = lambda x: (x[0] << 24)|(x[1] << 16)|(x[2] << 8)|x[3] #将列表 置换为32bytes
rotl32 = lambda x, n: ((x << n) & 0xffffffff) | ((x >> (32-n)) & 0xffffffff) #移位寄存,将最高位向后移动
rotl8 = lambda x, n: ((x << n) & 0xff) | ((x >> (8-n)) & 0xff) #单比特移位寄存，同上
xor = lambda x, y: list(map(lambda a, b: a ^ b, x, y))  #异或操作
pad = lambda data, block=16: data + [16 - len(data) % block]*(16 - len(data) % block)
rotr8 = lambda x, n: ((x >> n) & 0xff) | ((x << (8-n)) & 0xff) #单比特移位寄存，同上


SM4_BOXES_TABLE = [
    0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c,
    0x05, 0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26, 0x49, 0x86,
    0x06, 0x99, 0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43, 0xed,
    0xcf, 0xac, 0x62, 0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa,
    0x75, 0x8f, 0x3f, 0xa6, 0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c,
    0x19, 0xe6, 0x85, 0x4f, 0xa8, 0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb,
    0x0f, 0x4b, 0x70, 0x56, 0x9d, 0x35, 0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25,
    0x22, 0x7c, 0x3b, 0x01, 0x21, 0x78, 0x87, 0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52,
    0x4c, 0x36, 0x02, 0xe7, 0xa0, 0xc4, 0xc8, 0x9e, 0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38,
    0xb5, 0xa3, 0xf7, 0xf2, 0xce, 0xf9, 0x61, 0x15, 0xa1, 0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34,
    0x1a, 0x55, 0xad, 0x93, 0x32, 0x30, 0xf5, 0x8c, 0xb1, 0xe3, 0x1d, 0xf6, 0xe2, 0x2e, 0x82,
    0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab, 0x0d, 0x53, 0x4e, 0x6f, 0xd5, 0xdb, 0x37, 0x45,
    0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72, 0x6d, 0x6c, 0x5b, 0x51, 0x8d, 0x1b, 0xaf,
    0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41, 0x1f, 0x10, 0x5a, 0xd8, 0x0a, 0xc1,
    0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12, 0xb8, 0xe5, 0xb4, 0xb0, 0x89,
    0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09, 0xc5, 0x6e, 0xc6, 0x84,
    0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e, 0xd7, 0xcb, 0x39,
    0x48,
]

SM4_FK = [0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc]

SM4_CK = [
    0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269,
    0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
    0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
    0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
    0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229,
    0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
    0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209,
    0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279
]

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

Dance_Box_inv = []
def dance(): #用D盒的两个比特
    global count
    count += 1
    global Dance_Box
    Dance_Box = Dance_Box[2:]+Dance_Box[:2]

def round_key(k): #拓展算法
    ar = [SM4_BOXES_TABLE[i] for i in i2l(k)]
    b = l2i(ar)
    return b ^ rotl32(b, 13) ^ rotl32(b, 23)

def expand_key():  #拓展轮密钥
    k = [0]*36
    MK = [525810282, 1377439330, 2607913931, 3878460273]
	'''注意这一步的主密钥是恢复之后我手动填进去的，详细原脚本得看上面'''
    k[0:4] = xor(MK, SM4_FK)
    for i in range(32):
        k[i + 4] = k[i] ^ (round_key(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ SM4_CK[i]))
    return k[4:]

def tfunc(bk):
    ar = [SM4_BOXES_TABLE[i] for i in i2l(bk)]
    b = l2i(ar)
    return b ^ rotl32(b, 2) ^ rotl32(b, 10) ^ rotl32(b, 18) ^ rotl32(b, 24)

def pfunc(bk):
    res = []
    for i in range(4):
        sbox = Dance_Box[i]
        ar = [sbox[_] for _ in i2l(bk[i])]
        b = [rotl8(ar[i], i+3) for i in range(4)]
        res.append(l2i(b))
    return res

def pfunc_inv(bk):#逆
	res = []
	for i in range(4):
		sbox = Dance_Box[i]
		tmp = i2l(bk[i])
		b = [rotr8(tmp[i],i+3) for i in range(4)]
		ar = [sbox.index(_) for _ in b]
		res.append(l2i(ar))
	return res

def one_round(bk, rk, dt): #一轮解密
    out = []
    buf = [l2i(bk[:4]), l2i(bk[4:8]), l2i(bk[8:12]), l2i(bk[12:])]
    dance()
    for i in range(32):
        if dt == 32-i:
            dance()
        buf[:4] = pfunc_inv(buf[:4][::-1])[::-1]
        result = buf[0] ^ tfunc(buf[1]^buf[2]^buf[3]^rk[31-i])
        buf =  buf[1:]+buf[:1]
        buf[3] = result
    for _ in range(4):
        out += i2l(buf[-1-_])
    return out

def one_round_(bk, rk, dt): #一轮加密
    out = []
    buf = [l2i(bk[:4]), l2i(bk[4:8]), l2i(bk[8:12]), l2i(bk[12:])]
    for i in range(32):
        if dt == i:
            dance()
        result = buf[0] ^ tfunc(buf[1]^buf[2]^buf[3]^rk[i])
        buf =  buf[1:]+buf[:1]
        buf[3] = result
        buf[:4] = pfunc(buf[:4])
    dance()
    for _ in range(4):
        out += i2l(buf[-1-_])
    return out

def decrypt_ecb(ct,dance_time=-1):
	block = [ct[_:_+16] for _ in range(0, len(ct), 16)] #分组处理
	block_count = len(block)
	rk = expand_key()
	result = b''
	for i in block:
		result += bytes(one_round(i,rk,dt=dance_time))
	return result

def encrypt_ecb(pt, dance_time=-1):#pt = plaintext
    pt = pad(list(pt))
    rk = expand_key() #拓展密钥
    block = [ pt[_:_+16] for _ in range(0, len(pt), 16)] #分组处理
    result = b''
    for i in block:
        result += bytes(one_round_(i, rk, dt=dance_time)) #一轮一密钥
    return result

真正用来研究差分的脚本：

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#目标是恢复轮密钥rk
#通过找到S盒之间的差分d，恢复当前的轮密钥
#思路是：先找到已知的p1,p2,p3、故障，
#然后找到输入S盒之前的值，那么我们就可以得到rk
from collections import Counter
from Crypto.Util.number import long_to_bytes,bytes_to_long
import exp


SM4_BOXES_TABLE = [
    0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c,
    0x05, 0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26, 0x49, 0x86,
    0x06, 0x99, 0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43, 0xed,
    0xcf, 0xac, 0x62, 0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa,
    0x75, 0x8f, 0x3f, 0xa6, 0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c,
    0x19, 0xe6, 0x85, 0x4f, 0xa8, 0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb,
    0x0f, 0x4b, 0x70, 0x56, 0x9d, 0x35, 0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25,
    0x22, 0x7c, 0x3b, 0x01, 0x21, 0x78, 0x87, 0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52,
    0x4c, 0x36, 0x02, 0xe7, 0xa0, 0xc4, 0xc8, 0x9e, 0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38,
    0xb5, 0xa3, 0xf7, 0xf2, 0xce, 0xf9, 0x61, 0x15, 0xa1, 0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34,
    0x1a, 0x55, 0xad, 0x93, 0x32, 0x30, 0xf5, 0x8c, 0xb1, 0xe3, 0x1d, 0xf6, 0xe2, 0x2e, 0x82,
    0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab, 0x0d, 0x53, 0x4e, 0x6f, 0xd5, 0xdb, 0x37, 0x45,
    0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72, 0x6d, 0x6c, 0x5b, 0x51, 0x8d, 0x1b, 0xaf,
    0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41, 0x1f, 0x10, 0x5a, 0xd8, 0x0a, 0xc1,
    0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12, 0xb8, 0xe5, 0xb4, 0xb0, 0x89,
    0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09, 0xc5, 0x6e, 0xc6, 0x84,
    0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e, 0xd7, 0xcb, 0x39,
    0x48,
]
Dance_Box = [[46, 38, 43, 106, 114, 176, 12, 69, 1, 21, 82, 27, 184, 109, 170, 0, 179, 25, 4, 145, 33, 61, 66, 223, 85, 238, 22, 23, 59, 64, 19, 174, 180, 240, 111, 128, 187, 65, 72, 35, 77, 221, 157, 172, 13, 197, 44, 229, 226, 130, 220, 49, 198, 24, 103, 76, 39, 211, 191, 115, 165, 206, 30, 7, 98, 156, 205, 181, 89, 252, 58, 138, 253, 104, 212, 236, 54, 224, 166, 155, 118, 8, 93, 140, 28, 95, 225, 248, 80, 182, 112, 63, 192, 116, 47, 217, 91, 84, 144, 53, 124, 117, 16, 73, 218, 254, 188, 18, 11, 107, 222, 5, 52, 129, 194, 173, 81, 9, 137, 246, 242, 143, 175, 147, 74, 195, 41, 133, 207, 120, 92, 17, 164, 169, 171, 48, 241, 57, 31, 83, 55, 96, 29, 185, 68, 232, 70, 148, 243, 209, 100, 214, 37, 244, 219, 131, 203, 139, 126, 183, 167, 199, 101, 159, 50, 230, 168, 45, 149, 123, 119, 87, 134, 75, 127, 67, 250, 228, 247, 135, 113, 60, 62, 177, 150, 121, 162, 227, 142, 34, 178, 42, 15, 160, 161, 216, 235, 234, 163, 186, 154, 141, 233, 208, 78, 151, 204, 190, 86, 152, 245, 239, 108, 196, 158, 210, 99, 237, 251, 3, 40, 90, 125, 132, 36, 215, 193, 71, 255, 200, 102, 56, 32, 136, 146, 79, 97, 110, 249, 20, 202, 231, 122, 88, 94, 6, 153, 105, 14, 10, 2, 201, 189, 213, 51, 26], [246, 56, 103, 21, 181, 105, 216, 118, 145, 183, 169, 211, 27, 242, 190, 162, 237, 179, 244, 199, 206, 35, 120, 38, 95, 133, 25, 231, 3, 70, 40, 238, 223, 45, 127, 245, 4, 15, 250, 11, 52, 215, 142, 129, 167, 191, 61, 241, 188, 226, 249, 146, 221, 184, 104, 109, 157, 39, 176, 114, 236, 240, 254, 253, 251, 158, 198, 37, 42, 19, 87, 230, 153, 43, 77, 76, 208, 26, 32, 18, 150, 195, 122, 90, 80, 148, 197, 44, 83, 51, 166, 75, 88, 73, 64, 252, 20, 119, 46, 201, 196, 121, 222, 115, 22, 128, 164, 102, 97, 5, 217, 172, 177, 81, 58, 234, 168, 60, 29, 124, 147, 101, 224, 151, 130, 65, 98, 225, 155, 91, 108, 152, 140, 219, 9, 24, 189, 203, 138, 160, 59, 48, 193, 14, 69, 159, 233, 53, 135, 143, 33, 165, 41, 132, 57, 187, 227, 93, 200, 1, 0, 149, 137, 194, 23, 117, 170, 247, 17, 255, 92, 205, 47, 213, 136, 66, 2, 209, 6, 110, 78, 63, 28, 74, 235, 229, 30, 139, 154, 94, 131, 49, 86, 185, 163, 79, 68, 8, 72, 174, 99, 111, 141, 107, 210, 34, 207, 239, 106, 144, 228, 186, 89, 204, 55, 54, 171, 161, 100, 16, 13, 7, 50, 182, 112, 173, 212, 31, 214, 85, 156, 180, 175, 116, 248, 243, 36, 82, 134, 123, 220, 10, 125, 96, 67, 62, 12, 202, 126, 71, 84, 113, 232, 178, 192, 218], [46, 38, 43, 106, 114, 176, 12, 69, 1, 21, 82, 27, 184, 109, 170, 0, 179, 25, 4, 145, 33, 61, 66, 223, 85, 238, 22, 23, 59, 64, 19, 174, 180, 240, 111, 128, 187, 65, 72, 35, 77, 221, 157, 172, 13, 197, 44, 229, 226, 130, 220, 49, 198, 24, 103, 76, 39, 211, 191, 115, 165, 206, 30, 7, 98, 156, 205, 181, 89, 252, 58, 138, 253, 104, 212, 236, 54, 224, 166, 155, 118, 8, 93, 140, 28, 95, 225, 248, 80, 182, 112, 63, 192, 116, 47, 217, 91, 84, 144, 53, 124, 117, 16, 73, 218, 254, 188, 18, 11, 107, 222, 5, 52, 129, 194, 173, 81, 9, 137, 246, 242, 143, 175, 147, 74, 195, 41, 133, 207, 120, 92, 17, 164, 169, 171, 48, 241, 57, 31, 83, 55, 96, 29, 185, 68, 232, 70, 148, 243, 209, 100, 214, 37, 244, 219, 131, 203, 139, 126, 183, 167, 199, 101, 159, 50, 230, 168, 45, 149, 123, 119, 87, 134, 75, 127, 67, 250, 228, 247, 135, 113, 60, 62, 177, 150, 121, 162, 227, 142, 34, 178, 42, 15, 160, 161, 216, 235, 234, 163, 186, 154, 141, 233, 208, 78, 151, 204, 190, 86, 152, 245, 239, 108, 196, 158, 210, 99, 237, 251, 3, 40, 90, 125, 132, 36, 215, 193, 71, 255, 200, 102, 56, 32, 136, 146, 79, 97, 110, 249, 20, 202, 231, 122, 88, 94, 6, 153, 105, 14, 10, 2, 201, 189, 213, 51, 26], [206, 165, 193, 37, 187, 108, 248, 246, 44, 139, 152, 201, 173, 214, 77, 72, 97, 35, 70, 24, 3, 79, 178, 175, 30, 66, 18, 198, 114, 125, 32, 210, 180, 224, 235, 28, 62, 136, 149, 227, 82, 147, 90, 119, 85, 199, 126, 121, 51, 20, 88, 4, 75, 101, 38, 151, 109, 115, 110, 223, 43, 17, 146, 249, 226, 26, 222, 232, 87, 195, 200, 131, 245, 81, 113, 157, 220, 12, 16, 184, 204, 192, 84, 31, 197, 215, 129, 94, 93, 181, 218, 194, 65, 148, 158, 112, 221, 34, 25, 33, 243, 78, 10, 67, 209, 6, 252, 196, 237, 42, 172, 164, 161, 244, 111, 191, 46, 170, 128, 69, 183, 212, 60, 99, 8, 122, 49, 86, 247, 96, 179, 57, 135, 106, 0, 58, 100, 202, 55, 98, 1, 254, 53, 155, 156, 83, 132, 9, 19, 171, 48, 95, 166, 68, 22, 104, 7, 14, 142, 211, 213, 50, 150, 234, 182, 203, 217, 64, 185, 163, 73, 45, 41, 118, 103, 134, 186, 230, 241, 250, 52, 207, 162, 124, 140, 116, 167, 228, 92, 63, 47, 176, 239, 238, 5, 216, 225, 188, 137, 160, 80, 231, 102, 11, 89, 91, 59, 23, 240, 105, 153, 177, 138, 219, 174, 123, 36, 159, 76, 21, 56, 242, 61, 107, 133, 143, 154, 130, 233, 15, 145, 255, 13, 189, 120, 251, 236, 117, 208, 190, 169, 168, 74, 229, 54, 2, 39, 127, 29, 253, 141, 71, 205, 40, 144, 27]]

SM4_FK = [0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc]

SM4_CK = [
    0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269,
    0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9,
    0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
    0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9,
    0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229,
    0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
    0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209,
    0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279
]
i2l = lambda x: [(x >> 24) & 0xff, (x >> 16) & 0xff, (x >> 8) & 0xff, x & 0xff] #将32bytes 置换为列表
l2i = lambda x: (x[0] << 24)|(x[1] << 16)|(x[2] << 8)|x[3] #将列表 置换为32bytes
rotl32 = lambda x, n: ((x << n) & 0xffffffff) | ((x >> (32-n)) & 0xffffffff) #移位寄存,将最高位向后移动
rotl8 = lambda x, n: ((x << n) & 0xff) | ((x >> (8-n)) & 0xff) #单比特移位寄存，同上
xor = lambda x, y: list(map(lambda a, b: a ^ b, x, y))  #异或操作
pad = lambda data, block=16: data + [16 - len(data) % block]*(16 - len(data) % block)
rotr8 = lambda x, n: ((x >> n) & 0xff) | ((x << (8-n)) & 0xff) #单比特移位寄存，同上

def invL(A):return A ^ rotl32(A,2) ^ rotl32(A,4) ^ rotl32(A,8) ^ rotl32(A,12) ^ rotl32(A,14) ^ rotl32(A,16) ^ rotl32(A,18) ^  rotl32(A,22) ^ rotl32(A,24) ^ rotl32(A,30)
def L(b):return b ^ rotl32(b, 2) ^ rotl32(b, 10) ^ rotl32(b, 18) ^ rotl32(b, 24)

def dance(): 
    global Dance_Box
    Dance_Box = Dance_Box[2:]+Dance_Box[:2]

def tfunc(bk):
    ar = [SM4_BOXES_TABLE[i] for i in i2l(bk)]
    b = l2i(ar)
    #print(b)
    return b ^ rotl32(b, 2) ^ rotl32(b, 10) ^ rotl32(b, 18) ^ rotl32(b, 24)

def pfunc_inv(bk):#逆
	res = []
	for i in range(4):
		sbox = Dance_Box[i]
		tmp = i2l(bk[i])
		b = [rotr8(tmp[i],i+3) for i in range(4)]
		ar = [sbox.index(_) for _ in b]
		res.append(l2i(ar))
	return res

def pfunc(bk):
    res = []
    for i in range(4):
        sbox = Dance_Box[i]
        ar = [sbox[_] for _ in i2l(bk[i])]
        b = [rotl8(ar[i], i+3) for i in range(4)]
        res.append(l2i(b))
    return res

def decry_one(bk,dt=0):
	dance()
	result = pfunc_inv(bk)
	dance()
		#result = pfunc(result)
	return result

def one_round(bk, rk): #一轮解密
    '''把当前轮的轮密钥传进来，和是否故障传进来就能获得上轮的密文'''
    buf = bk
    result = buf[3] ^ tfunc(buf[0]^buf[1]^buf[2]^rk)
    buf =  buf[3:]+buf[:3]
    buf[0] = result

    return buf

def find_out(outX1,outX2):#唯密文分析
	in1 = i2l(outX1[0]^outX1[1]^outX1[2])
	in2 = i2l(outX2[0]^outX2[1]^outX2[2])
	#print(l2i(in1))
	diff = long_to_bytes(invL(outX1[3]^outX2[3]))
	rk = []
	for _ in range(4):
		for k in range(256):
			if(SM4_BOXES_TABLE[(in1[_]^k)] ^ SM4_BOXES_TABLE[(in2[_]^k)]) == diff[_]:
				rk += [(k,_)]
	return rk

def round_key(k): #拓展算法
    ar = [SM4_BOXES_TABLE[i] for i in i2l(k)]
    b = l2i(ar)
    return b ^ rotl32(b, 13) ^ rotl32(b, 23)

def expand_key_inv(MK):  #拓展轮密钥
    k = [0]*32
    k = MK + k
    for i in range(32):
        k[i + 4] = k[i] ^ (round_key(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ SM4_CK[31-i]))
    return xor(k[::-1][:4],SM4_FK)


def getC(c):#处理前16bytes的差分
	tmp = bytes.fromhex(c)
	result = [bytes_to_long(tmp[:4]),bytes_to_long(tmp[4:8]),bytes_to_long(tmp[8:12]),bytes_to_long(tmp[12:16])]
	return result[::-1]
#得在头部做一轮倒序处理，然后输入逆盒，就是那么奇怪

def getC_(c):#处理后16bytes的差分
	tmp = bytes.fromhex(c)
	result = [bytes_to_long(tmp[16:16+4]),bytes_to_long(tmp[16+4:16+8]),bytes_to_long(tmp[16+8:16+12]),bytes_to_long(tmp[16+12:16+16])]
	return result[::-1]

ct = [
'e5a304ea2ffc53a1ff94337c2b2ae5368b46c6da3cc37f8438eb967b29249d4e', 
'6733baa353d4cfc4ff94337c58dc7fdbd6df83f4fbf6e5e838eb967b98d7e8d3', 
'e77dbfe7868701fbd7072e6358dc7fdba067d296707bad1b0f4541dc98d7e8d3', 
'54b772d532556d5573a6ab667c9ff76857b5efc3b62130668e46a79b163138e4', 
'47339f6738dd9f4c9581fbd496dde76ea320d95b457e0373cddb910acc41fe35'
]

rk = []

c1 = decry_one(getC(ct[0]))
c2 = decry_one(getC(ct[1]))
c1_=decry_one(getC_(ct[0]))
c2_=decry_one(getC_(ct[1]))
print(find_out(c1,c2))
print(find_out(c1_,c2_))
#[(69, 0), (167, 0), (168, 1), (248, 1), (68, 2), (150, 2), (191, 3), (236, 3)]
#[(60, 0), (167, 0), (167, 1), (248, 1), (68, 2), (104, 2), (112, 3), (191, 3)]
rk1 = [167,248,68,191]
rk1 = bytes_to_long(bytes(rk1))
#rk.append(find_out(c1,c2))

c2_= decry_one(one_round(c2_,rk1))
c2 = decry_one(one_round(c2,rk1))
c3 = decry_one(getC(ct[2]))
c3 = decry_one(one_round(c3,rk1))
c3_= decry_one(getC_(ct[2]))
c3_= decry_one(one_round(c3_,rk1))

print(find_out(c2,c3))
print(find_out(c2_,c3_))
#[(89, 0), (224, 0), (46, 1), (115, 1), (96, 2), (122, 2), (172, 3), (209, 3)]
#[(68, 0), (89, 0), (46, 1), (87, 1), (0, 2), (96, 2), (71, 3), (172, 3)]
rk2 = [89,46,96,172]
rk2 = bytes_to_long(bytes(rk2))


c3_= decry_one(one_round(c3_,rk2))
c3 = decry_one(one_round(c3,rk2))

c4_=decry_one(getC_(ct[3]))
c4_ = decry_one(one_round(c4_,rk1)) #1
c4_ = decry_one(one_round(c4_,rk2))

c4 = decry_one(getC(ct[3]))
c4 = decry_one(one_round(c4,rk1)) #1
c4 = decry_one(one_round(c4,rk2))
print(find_out(c3,c4))
print(find_out(c3_,c4_))
#[(132, 0), (153, 0), (189, 1), (221, 1), (51, 2), (117, 2), (74, 3), (187, 3)]
#[(153, 0), (205, 0), (183, 1), (189, 1), (51, 2), (189, 2), (78, 3), (187, 3)]
rk3 = [153,189,51,187]
rk3 = bytes_to_long(bytes(rk3))


c4_= decry_one(one_round(c4_,rk3))
c4 = decry_one(one_round(c4,rk3))

c5_ = decry_one(getC_(ct[4]))
c5_ = decry_one(one_round(c5_,rk1))
c5_ = decry_one(one_round(c5_,rk2))
c5_ = decry_one(one_round(c5_,rk3))

c5 = decry_one(getC(ct[4]))
c5 = decry_one(one_round(c5,rk1))
c5 = decry_one(one_round(c5,rk2))
c5 = decry_one(one_round(c5,rk3))
print(find_out(c4,c5))
print(find_out(c4_,c5_))

#[(29, 0), (159, 0), (42, 1), (226, 1), (12, 2), (97, 2), (109, 3), (145, 3)]
rk4 = [159,42,97,109]
rk4 = bytes_to_long(bytes(rk4))


tmp = [rk1,rk2,rk3,rk4]
recover = expand_key_inv(tmp)
#print(tmp)
print(recover)#从这里得到主密钥


c31 = long_to_bytes(0xe5a304ea2ffc53a1ff94337c2b2ae5368b46c6da3cc37f8438eb967b29249d4e)
print(exp.decrypt_ecb(c31,31))
#b'n1ctf{Go0d_j0b_u_h4ck_th3_6ox}\x02\x02'

总之想说的和做的都在里面了。

如果脚本太长懒得看：

这里给出一些难点说明和耗时间的地方，以及为什么我要一段一段地去写这个差分而不是全自动(因为真的很麻烦)。

  • 这是一种唯密文分析的攻击办法
  • 首先在上面的思路当中，差分的办法我已经给出了，那是一个关键步，其次最重要的就是找对位置的密文
  • 一组密文只对应一组差分的解，而题目给的一份密文有两组块，可以利用这个去缩小差分的解
  • 一组密文解密之后还要逆推回到上一组的密文状态，这步写脚本真的很麻烦（可以想象一下）

如果你想尝试去独立完成这道题，这里给出一些细节提醒和建议：

  • 算法流程和我绘出的流程图是一样的（别担心我画错，照着看就行）
  • 但是在合并密文输出的时候题目进行了一次**倒置，**所以把密文输入回算法的时候务必倒过来一次
  • 至于故障轮，也就是对应p盒dance的地方，注意开始和结束的时候，一次加密结束故障恢复，但是每次加密必定会出现故障（写的时候就知道这句话有多重要了）
  • 恢复轮密钥的算法和加密的算法类似，很容易推出来的，别担心还要再考虑逆向一轮轮密钥恢复的复杂度。

DES差分：

推荐看NCTF2023 Fault Milestone，写得很详细啦

AES差分：

见文章末尾：三顺七的强基计划-AES

未完待续，一系列差分分析技巧和题目在路上中……