Maojui

CSIE 2019 - Linear cryptoanalysis (Crypto, 300)

2020-01-18

Challenge

題目：

spn.py
task.py
output

Solution

這題的題目名稱，就把告訴我們攻擊的手法了

不知道的人可以先去 Linear Cryptanalysis 這頁看個 ˊˇˋ

首先我們可以先生出一個 LAT

看看這組 SBOX 在哪裡產生出比較大的 Bias

Linear Approximation Table (LAT)

In\Out 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 4 -2 2 -4 0 2 -2 0 0 2 2 0 0 2 2
2 0 0 -2 2 2 2 4 0 -2 2 0 0 0 4 -2 -2
3 0 -4 0 0 -2 2 2 2 2 -2 2 2 4 0 0 0
4 0 0 0 -4 -4 0 0 0 -2 2 -2 -2 2 2 -2 2
5 0 0 -2 2 0 -4 2 2 -2 -2 0 -4 2 -2 0 0
6 0 0 -2 -2 2 -2 0 -4 0 0 2 2 2 -2 -4 0
7 0 0 0 0 -2 2 -2 2 -4 0 4 0 -2 -2 -2 -2
8 0 2 -4 -2 0 2 0 2 0 -2 -4 2 0 -2 0 -2
9 0 -2 -2 -4 0 -2 2 0 0 -2 2 0 -4 2 2 0
A 0 2 2 0 -2 0 0 -2 2 -4 0 -2 0 2 -2 -4
B 0 -2 0 2 -2 -4 -2 0 -2 0 -2 4 0 2 0 -2
C 0 2 0 -2 0 -2 0 2 2 4 2 0 2 0 2 -4
D 0 2 2 0 0 -2 2 4 2 0 0 2 -2 0 -4 2
E 0 2 -2 0 2 0 -4 2 0 -2 2 0 2 4 0 2
F 0 2 4 -2 2 0 2 0 -4 -2 0 2 2 0 2 0

可以看到這幾組 0001->0001 、 0001->0100 、 0100->0100、1000->0010 不但出來的時候沒怎麼變，還很少，是不錯的路線



於是我們就可以找出一條條這種路線，做我們 mask 然後把 1Round 接著1Round 的 KEY 還原出來。

那麼由於這題給的 (明文, 密文) pairs 有點少，所以我再爆第4個 Round 時用了比較多的 mask，來降低找錯 Key 的機率。


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
ROUND_4 = {
    '0_1' : [
        ('0000000010000000000000000000000000000000000000000000000000000000', '1000000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000001000000000000000000000000000000000000000', '0001000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000001000000000000', '0001000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000011000000000000', '0001000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000011100000000', '1000000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000000000010000', '0001000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000000000110000', '0001000000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000000000001000', '0010000000000000000000000000000000000000000000000000000000000000'),
    ],
    '0_2' : [
        ('0000000000000100000000000000000000000000000000000000000000000000', '0000001000000000000000000000000000000000000000000000000000000000'),
        ('0000000000010000000000000000000000000000000000000000000000000000', '0000010000000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000000000010000', '0000100000000000000000000000000000000000000000000000000000000000'),
    ],
    '1_1' : [
        ('0000000000000000000000000000000000000000001100000000000000000000', '0001000000100000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000100000000000000000000000000000000000', '0000000001000000000000000000000000000000000000000000000000000000'),
        ('0000000000000000000100000000000000000000000000000000000000000000', '0000000000010000000000000000000000000000000000000000000000000000'),
    ],
    '1_2' : [
        ('0000010000000000000000000000000000000000000000000000000000000000','0000000000000010000000000000000000000000000000000000000000000000'),
        ('0000010000000000000000000000000000000000000000000000000000000000', '0000000000000010000000000000000000000000000000000000000000000000'),
    ],
    '2_1' : [
        ('0000000000000000011100000000000000000000000000000000000000000000','0000000000000000100000000000000000000000000000000000000000000000'),
        ('0000000000000000111100000000000000000000000000000000000000000000','0000000000000000100000000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000111000000000000000000000000','0000000000000000000100000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000001111000000000000000000000000','0000000000000000000100000000000000000000000000000000000000000000'),
    ],
    '2_2' : [
        ('0000000000000000000000000000000000000000000000000000001100000000','0000000000000000000010000000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000000010000000', '0000000000000000000000100000000000000000000000000000000000000000'),
        ('0000000000001000000000000000000000000000000000000000000000000000', '0000000000000000000001000000000000000000000000000000000000000000'),
        ('0100000000000000000000000000000000000000000000000000000000000000', '0000000000000000000010000000000000000000000000000000000000000000'),
    ],
    '3_1' : [
        ('0000000000000000000000000000000001110000000000000000000000000000', '0000000000000000000000001000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000010000000000000000000000000000000', '0000000000000000000000001000000000000000000000000000000000000000'),
        ('0000000000000000000000000000000011110000000000000000000000000000', '0000000000000000000000001000000000000000000000000000000000000000'),
    ],
    '3_2' : [('0000000000000000000000000000000000000011000000000000000000000000','0000000000000000000000000000000100000000000000000000000000000000'),
            ('0000000000000000000000000000000100000000000000000000000000000000', '0000000000000000000000000000010000000000000000000000000000000000'),
            ('0000000000000000000000000000000000000001000000000000000000000000', '0000000000000000000000000000000100000000000000000000000000000000'),],
    '4_1' : ('0000000000000000000000000000011100000000000000000000000000000000','0000000000000000000000000000000000010000000000000000000000000000'),
    '4_2' : [
        ('0000000000000000010000000000000000000000000000000000000000000000','0000000000000000000000000000000000000010000000000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000100000000000', '0000000000000000000000000000000000000010000000000000000000000000'),
        ('0000000000000000000010000000000000000000000000000000000000000000', '0000000000000000000000000000000000000100000000000000000000000000'),
    ],
    '5_1' : [
        ('0000000000010000000000000000000000000000000000000000000000000000','0000000000000000000000000000000000000000000100000000000000000000'),
        ('0000000000000000000000000000000000000000000001110000000000000000','0000000000000000000000000000000000000000100000000000000000000000'),
        ('0000000000000000000000000000000000000000000011110000000000000000','0000000000000000000000000000000000000000100000000000000000000000'),
        ('0000000001000000000000000000000000000000000000000000000000000000','0000000000000000000000000000000000000000000100000000000000000000'),
        ('0000000001000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000100000000000000000000'),
    ],
    '5_2' : [
        ('0000000000000000000000000000000000000000000000000001000000000000','0000000000000000000000000000000000000000000000010000000000000000'),
        ('0000000000000000000000000000000000000000000000000000000100000000', '0000000000000000000000000000000000000000000001000000000000000000'),
        ('0000000000000000000000000000000000000000000000000000010000000000', '0000000000000000000000000000000000000000000000100000000000000000'),
    ],
    '6_1' : [
        ('0000000000000000000000000000000000000000000000000000000001000000','0000000000000000000000000000000000000000000000000001000000000000'),
        ('0000000000000000000000000000000000000000000001000000000000000000', '0000000000000000000000000000000000000000000000000100000000000000'),
        ('0000000000000000000000000000000000000000000000010000000000000000', '0000000000000000000000000000000000000000000000000100000000000000'),
        ('0000000000000000000000000000000000000000000000000000000000010000', '0000000000000000000000000000000000000000000000000001000000000000'),
        ('0000000000000000100000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000101000000000000'),
    ],
    '6_2' : [
        ('0000000000000000000000001000000000000000000000000000000000000000','0000000000000000000000000000000000000000000000000000010000000000'),
        ('0000000000000000000000000100000000000000000000000000000000000000','0000000000000000000000000000000000000000000000000000000100000000'),
        ('0000000000000000010000000000000000000000000000000000000000000000','0000000000000000000000000000000000000000000000000000100000000000'),
        ('0000000000000000000000000000000000010000000000000000000000000000','0000000000000000000000000000000000000000000000000000010000000000'),
        ('0000000000000000000000000000000000010000000000000000000000000000', '0000000000000000000000000000000000000000000000000000010000000000'),
    ],
    '7_1' : [
        ('0000000000000000000010000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000100000'),
        ('0000000000000000000000000000000000000000000000010000000000000000', '0000000000000000000000000000000000000000000000000000000000010000'),
        ('0000100000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000001000000'),
        ('0000000000000000000000000000000000000000000000110000000000000000', '0000000000000000000000000000000000000000000000000000000000010000'),
    ],
    '7_2' : [
        ('0000000000000000000000010000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000001'),
        ('0000000000000000000000110000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000001'),
        ('0001000000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000100'),
    ],
}

ROUND_3 = {
    '0_1' : ('0000000000010000000000000000000000000000000000000000000000000000', '0001000000000000000000000000000000000000000000000000000000000000'),
    '0_2' : ('0000000000000000000000000000000000000000000001000000000000000000', '0000010000000000000000000000000000000000000000000000000000000000'),
    '1_1' : ('0000000000000000000000000000000000000000000000000000000100000000', '0000000000010000000000000000000000000000000000000000000000000000'),
    '1_2' : ('0000000000000000011100000000000000000000000000000000000000000000', '0000000000000100000000000000000000000000000000000000000000000000'),
    '2_1' : ('0000000000000000000000000100000000000000000000000000000000000000', '0000000000000000000100000000000000000000000000000000000000000000'),
    '2_2' : ('0000000000000000000000000000000100000000000000000000000000000000', '0000000000000000000001000000000000000000000000000000000000000000'),
    '3_1' : ('0000000000000000000100000000000000000000000000000000000000000000', '0000000000000000000000001000000000000000000000000000000000000000'),
    '3_2' : ('0000000000000000000000000000000000000000000000000000100000000000', '0000000000000000000000000000010000000000000000000000000000000000'),
    '4_1' : ('0000000000000000000000000000100000000000000000000000000000000000', '0000000000000000000000000000000000010000000000000000000000000000'),
    '4_2' : ('0000000000000000000000000000000000000000000000000000010000000000', '0000000000000000000000000000000000000100000000000000000000000000'),
    '5_1' : ('0000000000000000000010000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000100000000000000000000'),
    '5_2' : ('0000000000000000000000001000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000001000000000000000000'),
    '6_1' : ('1000000000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000101000000000000'),
    '6_2' : ('0000000001000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000010000000000'),
    '7_1' : ('0000000000000000000000000000000000000000000000000001000000000000', '0000000000000000000000000000000000000000000000000000000001000000'),
    '7_2' : ('0000010000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000100'),
}

ROUND_2 = {
    '0_1' : ('0000000000000000100000000000000000000000000000000000000000000000', '1000000000000000000000000000000000000000000000000000000000000000'),
    '0_2' : ('1000000000000000000000000000000000000000000000000000000000000000', '0000001000000000000000000000000000000000000000000000000000000000'),
    '1_1' : ('0000000000000000000000001000000000000000000000000000000000000000', '0000000000010000000000000000000000000000000000000000000000000000'),
    '1_2' : ('0000000010000000000000000000000000000000000000000000000000000000', '0000000000000100000000000000000000000000000000000000000000000000'),
    '2_1' : ('0000000000000100000000000000000000000000000000000000000000000000', '0000000000000000100000000000000000000000000000000000000000000000'),
    '2_2' : ('0000000001000000000000000000000000000000000000000000000000000000', '0000000000000000000010000000000000000000000000000000000000000000'),
    '3_1' : ('0000000000000000000000000000000000000000000000000000000100000000', '0000000000000000000000001000000000000000000000000000000000000000'),
    '3_2' : ('0000000000001000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000100000000000000000000000000000000'),
    '4_1' : ('0000000000000000000000000100000000000000000000000000000000000000', '0000000000000000000000000000000010000000000000000000000000000000'),
    '4_2' : ('0000000000000000000000000000000000000000000100000000000000000000', '0000000000000000000000000000000000000100000000000000000000000000'),
    '5_1' : ('0000000100000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000001000000000000000000000'),
    '5_2' : ('0000000000010000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000001000000000000000000'),
    '6_1' : ('0000010000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000100000000000000'),
    '6_2' : ('0000000000000000000100000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000100000000'),
    '7_1' : ('0000000000000000000000010000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000010000000'),
    '7_2' : ('0000000000000000000000000000000000000000100000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000001'),
}

ROUND_1 = {
    '0_1' : ('0100000000000000000000000000000000000000000000000000000000000000', '0100000000000000000000000000000000000000000000000000000000000000'),
    '0_2' : ('0000010000000000000000000000000000000000000000000000000000000000', '0000010000000000000000000000000000000000000000000000000000000000'),
    '1_1' : ('0000000001000000000000000000000000000000000000000000000000000000', '0000000001000000000000000000000000000000000000000000000000000000'),
    '1_2' : ('0000000000000100000000000000000000000000000000000000000000000000', '0000000000000100000000000000000000000000000000000000000000000000'),
    '2_1' : ('0000000000000000010000000000000000000000000000000000000000000000', '0000000000000000010000000000000000000000000000000000000000000000'),
    '2_2' : ('0000000000000000000001000000000000000000000000000000000000000000', '0000000000000000000001000000000000000000000000000000000000000000'),
    '3_1' : ('0000000000000000000000000100000000000000000000000000000000000000', '0000000000000000000000000100000000000000000000000000000000000000'),
    '3_2' : ('0000000000000000000000000000010000000000000000000000000000000000', '0000000000000000000000000000010000000000000000000000000000000000'),
    '4_1' : ('0000000000000000000000000000000001000000000000000000000000000000', '0000000000000000000000000000000001000000000000000000000000000000'),
    '4_2' : ('0000000000000000000000000000000000000100000000000000000000000000', '0000000000000000000000000000000000000100000000000000000000000000'),
    '5_1' : ('0000000000000000000000000000000000000000010000000000000000000000', '0000000000000000000000000000000000000000010000000000000000000000'),
    '5_2' : ('0000000000000000000000000000000000000000000001000000000000000000', '0000000000000000000000000000000000000000000001000000000000000000'),
    '6_1' : ('0000000000000000000000000000000000000000000000000100000000000000', '0000000000000000000000000000000000000000000000000100000000000000'),
    '6_2' : ('0000000000000000000000000000000000000000000000000000010000000000', '0000000000000000000000000000000000000000000000000000010000000000'),
    '7_1' : ('0000000000000000000000000000000000000000000000000000000001000000', '0000000000000000000000000000000000000000000000000000000001000000'),
    '7_2' : ('0000000000000000000000000000000000000000000000000000000000000100', '0000000000000000000000000000000000000000000000000000000000000100'),
}

那因為我寫到快氣死了，所以我的小工具多了以下功能

1
2
3
4
5
6
7
8
9
from cytro.sym.spn import *

sbox = [14, 2, 6, 13, 7, 8, 10, 3, 15, 9, 12, 5, 0, 11, 4, 1]
pbox = [18, 30, 38, 45, 47, 3, 2, 56, 16, 35, 46, 26, 17, 10, 61, 52, 13, 39, 32, 34, 9, 54, 63, 44, 55, 36, 0, 40, 28, 21, 48, 14, 25, 4, 33, 1, 50, 43, 29, 8, 58, 20, 7, 53, 15, 11, 37, 57, 62, 5, 60, 6, 31, 22, 27, 19, 23, 59, 41, 51, 24, 49, 12, 42]

atable = LAT(sbox,len(sbox),len(sbox))
bruteRoute(atable,pbox,'SPSPSP') # Round 4
bruteRoute(atable,pbox,'SPSP') # Round 3
bruteRoute(atable,pbox,'SP') # Round 2

他可以直接生成簡單的路線

那如果複雜一點可能要像上圖那樣，自行手動找了 Q_Q

那有了這些 MASK 就是一直跑一直解密，把 bias 不一樣的 key 取出來，這題就結束了。

Script : solve.py

Tags: Linear cryptanalysis SPN
← 線性密碼分析 | Linear Cryptanalysis AIS3 2020 EOF - train (Crypto, 334) →