CSIE 2019 - Linear cryptoanalysis (Crypto, 300)

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->00010001->01000100->01001000->0010 不但出來的時候沒怎麼變,還很少,是不錯的路線



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

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


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'),
}

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

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