Explore SPN

Notes
CTFSeason2
发布日期:   2021-02-26

huangx607087学习SPN加密的笔记

0.简介

一个密码学fw的学习笔记，很菜

BUUCTF上做了一道SPN的题目，挺复杂的，得认真做亿点点笔记，wp上讲的非常简单，自己摸了半天才做出来。

1.什么是SPN

SPN加密是分组密码的一种，其中包括一个$S$盒和一个$P$盒，$S$盒的作用是将某个数对应地变成另一个数，而$P$盒的作用是置换比特位。其英文全称叫Substitution-Permutation Network，翻译成中文就是代换-置换网络。

SPN加密网络中大概分为这三个过程。

第一步，准备这一次加密的密钥$k$，将输入的明文与$k$异或。

第二步，将第一步得到的所有的结果通过$S$盒，进行数字的代换。

第三步，对已知的比特位进行修改位置，不修改其值的置换。

因此根据上面的观察，可以得出结论：只有$S$盒的代换是一个非线性的过程，似乎没有什么规律，其他的步骤都是可逆的。

例如：已知一个SPN的$S$盒和$P$盒如下：

$x$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$ $14$ $15$
$S(x)$ $6$ $14$ $5$ $12$ $1$ $7$ $11$ $2$ $0$ $4$ $15$ $8$ $13$ $10$ $3$ $9$
$P(x)$ $1$ $3$ $0$ $5$ $6$ $7$ $2$ $4$ / / / / / / / /

很显然，这个$S$盒一个单位是$8$个比特值，其中每$4$比特进行一次置换。

当数字$186(11,10)$先通过$S$盒再通过$P$盒时，变换是这样的：首先，先通过$S$盒置换，$11$变成$8$，$10$变成$15$。数字的值从$186(\text{BAH})$改为了$143(\text{8FH})$。其比特为$10001111\text{B}$。然后进行置换：首位(下标$0$）的$1$被换到第三位(下标$1$）,以此类推，最终数字变成了$01101011\text{B}$也就是$107(\text{6BH})$。

2.对非线性S盒的分析——线性处理

所谓线性分析，就是寻找一个给定的密码系统下，具有如下的线性表达式，其中所有的小写字母取值都在$0,1$内。

$$
P[p_1,p_2,…,p_n] \text{ xor } C[c_1,c_2,…,c_n]=K[k_1,k_2,…,k_n]
$$
因此，线性分析的基本思想就是通过寻找一个给定密码算法有效的线性近似表达式来破译密码系统。因为每个密码系统均为非线性系统，因此只能寻找线性近似的表达式。

其中，对于一个随机给定的明文$P$和相对应的密文$C$，上面的等式成立的概率不等于$0.5$。一般情况下，会构造一个关于明文和倒数第二轮输入的线性表达式，就有可能会付出最后一轮加密使用的子密钥的一个子集，达到攻击的目的。

因此，如果我们向对一个$S$盒进行线性处理的时候，就要考虑考虑其是否存在线性优势，以及如何求单轮和多轮的线性优势。因此，我们可以设$e=p-0.5$为偏差值，因此等式的有效性可以用$|\delta|$来衡量。

下面我们引入堆积引理，表达式如下，其中所有的$x$取值范围均为$0,1$。
$$
Pr(\sum_{i=1}^n x_i \equiv 0 \pmod 2\text{ }) =0.5+2^{n-1}\prod_{i=1}^n\delta_i
$$
很显然，如果某一个$\delta$值为$0$，那么整个算式的$\delta$值也为$0$。

因此，利用堆积引理，我们可以将每轮变换中偏差最大的线性逼近式进行组合。而组合后的线性逼近式也会有最大的偏差值。

而线性组合使用的式子则为，其中$x$值为通过$S$盒的输入值
$$
f\equiv \sum_{i=1}^n a_ix_i \pmod 2
$$
当然，我们也可以找出$S$盒的输出值$y$进行一次线性组合。
$$
g\equiv \sum_{i=1}^n b_iy_i \pmod 2
$$
最后计算一下$f+g \equiv 0 \pmod 2$的概率，并与$0.5$进行比较，偏差越大越好。

以我们上面的那个例子为例，假如我们决定使用的组合表达式为$f\equiv 1x_1+1x_2+1x_3+1x_4\pmod 2$，$g \equiv 0y_1+1y_2+0y_3+0y_4$，我们通过枚举$0$到$15$的每个值可以求出$f+g\equiv 0 \pmod 2$的情况有$10$种，概率$0.625$，偏差$\delta=0.625-0.5=0.125=12.5\text{percent}$。为了能够给出一个符号，我们直接组合$f$的所有系数为$1111\text{B}=7$，和$g$的系数$0100\text B=4$，记作$\delta_{(7,4)}=0.125$。

如果我们对所有的可能性都枚举一次，可以得到这样一张表，其中$i$循环用于枚举输入数字，$j$循环用于枚举输入的线性组合的系数，$k$循环用于枚举输出的线性组合的系数。因此我们只需要开一个二维计数数组就可以了。最后这个数组中的$256$个数值构成了一个线性逼近表。而这个线性逼近表的不均匀性，也就提供了线性分析的可能性，因此我们只要选择出最佳线性逼近式来进行线性攻击。

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<bits/stdc++.h>
using namespace std;
const int s[16]={6,14,5,12,1,7,11,2,0,4,15,8,13,10,3,9};
double p[16][16];
int sumbitpros(int a,int x)
{
	int c=a&x,d=0;
	while(c)
	{
		d+=c&1;
		c>>=1;
	}
	return d&1;
}
int main()
{
	int i,j,k;
	for(i=0;i<=15;i++)
	{
		for(j=0;j<=15;j++)
			for(k=0;k<=15;k++)
			{
				int a=sumbitpros(j,i),b=sumbitpros(k,s[i]);
				p[j][k]+=(a==b);
			}
	}
	for(i=0;i<=15;i++)
	{
		for(j=0;j<=15;j++)
			printf("%.2lf ",abs(p[i][j]-8)/16);
		printf("\n");
	}
	return 0;
}

输出结果如下，红色数字标出了每一行出现得最大值。

1

然后我们就可以得到一个系数数组[0,1,11,2,1,5,5,3,11,12,6,7,12,8,2,4]。

归纳一下线性攻击的过程为:假如我们能够在一个明文比特子集和最后一轮即将进行代换的输入状态比特子集之间找到一个概率线性关系，换句话说，即存在一个比特子集使得其中元素的异或表现出非随机的分布(即明文和最后一轮输入的最佳线性逼近
式)，再假设一个攻击者拥有大量的用同一未知密钥加密的明文密文对.

对每一个明文密文对，将用所有的(最后一轮)候选密钥来对最后一轮解密密文.对每一个候选密钥，计算包含在线性关系式中的相关比特的异或的值，然后确定上述的线性关系式是否成立。如果成立，就在对应于特定候选密钥的计数器上加$1$.

在这个过程的最后，我们希望计数频率离明密文对数的一半最远的候选密钥含有那些密钥比特的正确值.
可以看到，线性攻击成功只依赖于明文的个数$N$和$|p- 0.5|$, 并且随着$N$或$|p -0.5|$的增加而增加。

需要说明的是:在选择从一轮到多轮线性逼近式时，除了考虑有效性外，还需使得得到的最后关系式中，只包含明文、密文和最后一轮的密钥比特，才能实施有效攻击。

3. CTF实战——以[NPUCTF2020]EzSPN为例

Step 1 阅读代码看懂题目

我们首先来看一下这个加密代码

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
import os
from binascii import hexlify, unhexlify
import Crypto.Random.random as random
from secret import flag
coef = [239, 163, 147, 71, 163, 75, 219, 73]
sbox = list(range(256))
random.shuffle(sbox)
sboxi = []
for i in range(256):
    sboxi.append(sbox.index(i))
def doxor(l1,l2):
    return [x[0]^x[1] for x in zip(l1,l2)]
def trans(blk):
    res = []
    for k in range(0, 8, 8):
        bits = [bin(x)[2:].rjust(8,'0') for x in blk[k:k+8]]
        for i in range(8):
            res.append(int(''.join([x[(i+1) % 8] for x in bits]),2))
        res[k:k+8] = [(coef[i] * res[k+i]) % 256 for i in range(8)]
    return res
def encrypt_block(pt, ks):
    cur = doxor(pt, ks[:8])
    cur = [sbox[x] for x in cur]
    cur = trans(cur)
    cur = [sboxi[x] for x in cur]
    cur = doxor(cur, ks[8:])
    return cur
def encrypt(pt, k):
    x = 0 if len(pt)%8==0 else (8-len(pt)%8)
    pt += [x]*x
    ct = ''
    for i in range(0, len(pt), 8):
        res = encrypt_block([x for x in pt[i:i+8]], k)
        ct += ''.join(["{:02x}".format(xx) for xx in res])
    return ct
def doout(x):
    if len(x) % 16:
        x = (16 - len(x) % 16) * "0" + x
    return x
def doin(x):
    return list(unhexlify(x))
def genkeys():
    return list(os.urandom(2*8))
if __name__ == "__main__":
    print(sbox)
    key = genkeys()
    ct = encrypt(flag, key)
    print(ct)
    while True:
        pt = doin(input())
        print(doout(encrypt(pt, key)))

简单分析一下代码就可以知道，每$8$个字符为一组，共$64$个比特值进行加密。其中$S$盒的容量是$8$比特，包含一个字节，题目一开始给出了$S$盒和flag的密文。代换有了，不过还没有置换。

不过我们可以看到trans函数似乎给出了比特位的置换规则。自己内测一下+分析一下，可以给出$P$盒的置换规则是：一组$8$个$8$比特数字中，遍历下标$-1$到$6$，先取最高位构成第一个新数字，然后取次高位构成第二个新数字，以此类推。最后还乘上了对应位的一个coef常数。

1
2
3
4
5
6
7
8
def trans(blk):
    res = []
    for k in range(0, 8, 8):
        bits = [bin(x)[2:].rjust(8,'0') for x in blk[k:k+8]]
        for i in range(8):
            res.append(int(''.join([x[(i+1) % 8] for x in bits]),2))
        res[k:k+8] = [(coef[i] * res[k+i]) % 256 for i in range(8)]
    return res

当我们找出$S$盒和$P$盒的时候，考虑一些每一次加密的过程：先是将待加密数据与密钥异或，然后将数据通过$S$盒，然后进行$P$盒附带乘上coef常数置换，，最后再来一次$S^{-1}$盒以及与后半段密钥异或进行的加密

1
2
3
4
5
6
7
def encrypt_block(pt, ks):
    cur = doxor(pt, ks[:8])
    cur = [sbox[x] for x in cur]
    cur = trans(cur)
    cur = [sboxi[x] for x in cur]
    cur = doxor(cur, ks[8:])
    return cur

每次我们可以任意选取一段明文，然后发送给服务器，服务器会反馈给我们加密结果。

根据刚才的分析，很显然，一旦我们知道了第二轮的密钥，就很容易将整个过程逆回去。所以我们要考虑求出第二轮密钥。

Step 2 分析题目，分部解决

这里的分组对称密码中出现了S盒，因此我们必然是要考虑考虑S盒的线性攻击的。故我们选择分别对应Sbox八个输出的八个Sbox的最大偏差线性估计，来进行八个第二轮子密钥的猜测，时间复杂度为$O(256×8)=O(2048)$。

而我们猜测这个密钥，同样地也可以用线性分析。不过这里我们就需要大量学习数据，就跟机器学习一样。按道理说，当数据足够大的时候，每个数字的结果应该都不相同，因此我们很容易就能找到那个偏差最大的数字，然后就是我们需要找到的第二轮密钥。

而整个过程，可以分为这么几个部分：

[1] 初始化部分

初始化部分主要包括了：将接收到的$S$盒由字符串形式转化成数组、将十六位长的字符串转化成八个$0-255$内的数字、补位十六进制填充和二进制填充、返回两数组中对应位置异或的值，以及构建形如以下式子的线性组合，其中$A,X$是八比特数字，$a,x$是对应比特数。
$$
f(A,X)\equiv\sum _{i=1}^8 a_ix_i \pmod 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
def getboxinv(s):
    S,Q=[],[0]*256
    cntint,endex=0,False
    for i in s:
        if ord(i) in range(48,58):
            endex=True
            cntint=cntint*10+ord(i)-48
        else:
            if endex==True:
                endex=False
                S.append(cntint)
                Q[cntint]=len(S)-1
                cntint=0
    return S,Q
def s32tol8(s16):
    L8=[]
    for i in range(0,len(s16),2):
        L8.append(int(s16[i:i+2],16))
    return L8
def padhex(x,b):
    x=hex(x)[2:]
    return (b-len(x))*'0'+x
def padbin(x,b):
    x=bin(x)[2:]
    return (b-len(x))*'0'+x
def doxor(l1,l2):
    return [x[0]^x[1] for x in zip(l1,l2)]
def sumbitpros(a,x):
    c,d=a&x,0
    while c:
        d+=c&1
        c>>=1
    return d&1

[2] 初始化部分

线性化$S$盒的函数，可以发现，我们类比于上面$\text{16 x 16}$的表格，列举出一个$\text{256 x 256}$的表格，其中$i$是我们列举的输入数字，$j$是带入上面的线性组合对应的比特系数，$k$是$S$盒输出结果构造线性函数的比特系数。最后我们得到的offset序列，例如：offser[115]就是数字$115$通过$S$盒时的最佳逼近系数。这一部分已经在一开始有了讲解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def linersbox(sbox):
    lnipt=[]
    offset=[[0 for _ in range(256)] for __ in range(256)]
    for i in range(256):
        if i%15==0:
            print('[lnrsbox]:'+str(i+1)+'/256')
        si=sbox[i]
        for j in range(256):
            for k in range(256):
                a=sumbitpros(j,i)
                b=sumbitpros(k,si)
                if a==b:
                    offset[j][k]+=1
    for i in range(256):
        offset[i]=[abs(x-128)/256.0 for x in offset[i]]
    for i in range(256): 
        cur=[x[i] for x in offset] 
        lnipt.append(cur.index(max(cur)))
    return offset,lnipt

[3] 猜测第二段密钥部分

当我们想要获取密钥比特的时候，如果我们有了$r$轮加密过程的算法和前$r-1$轮的线性近似表达式，且表达式的线性可能性偏移量足够大，那么我们恢复最后一轮的子密钥攻击时可行的。把从最后一个子密钥中恢复出的密钥的一部分成为局部目标子密钥。而局部目标子密钥来自于最后一轮$S$盒相关联的子密钥。

特别地，对于所有可能的局部目标子密钥，相应的密文比特与其进行异或运算，结果就会继续通过最后一轮对应的$S$盒进行计算。

如果使用的是不正确的子密钥，那么这就会跟随机猜测输入产生的结果近似差不多，使得最后程序输出的概率接近于$0.5$，偏移量接近于$0$。

如果一个子密钥的计数值与明文-密文的数目一半相差最多，就会被认为是正确的子密钥。因为一个正确的子密钥会使得线性近似表达式成立的概率偏离于$0.5$。

所以我们可以产生大量的随机明文，并让服务器给我们进行加密获得密文，然后利用我们手上的明文和密文，通过大量数据的分析 ，最后我们就可以找出一个正确的子密钥了。在这里，我选择接收$16384$组附加明文和密文。（实际上$7000+$组的规模就够用了）

所以猜测密钥部分，我们可以用如下的代码，通过getkey8f函数中枚举$8$个部分，每个部分$256$中可能的取值，共$16384$组附加明文和附加密文。我们只需要不断地判断最后两个线性组合的相等概率与$0.5$相差多少就可以了，相差最大的那个，就一定是第二轮密钥了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def guess(pt,ct,loc,gus,lnipt,coefinv):
    pt,ct=s32tol8(pt),s32tol8(ct)
    ct[loc]^=gus
    ct[loc]=sbox[ct[loc]]
    ct[loc]=ct[loc]*coefinv[loc]&255
    tmp1=sumbitpros(pt[0],lnipt[1<<((14-loc)&7)])
    tmp2=sumbitpros(ct[loc],128)
    return tmp1==tmp2
def getkey8f(Tl,Cl,lnipt,coefinv,scale):
    k8f=[]
    for i in range(8):
        print('[GettingKey]:ID='+str(i+8))
        kount=[0 for _ in range(256)]
        for gskey in range(256):
            for j in range(scale):
                if guess(Tl[j],Cl[j],i,gskey,lnipt,coefinv):
                    kount[gskey]+=1
        beta=[abs(x-scale//2+0.0)/(scale+0.0) for x in kount]
        k8f.append(beta.index(max(beta)))
    return k8f

[4] 通过第二段密钥恢复第一段密钥和解密明文

当第二段密钥得到之后，我们就可以通过一组附加密文和附加明文，进而求得第一段密钥，第一段密钥求出后，直接模仿加密的形式，写出所有步骤的逆，flag就出来了。

以下是求第一段密钥和对密文进行解密的过程，这一过程很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def getkey07(pt,ct,k8f,coefinv,sbox,sinv):
    pt,ct=s32tol8(pt),s32tol8(ct)
    cur=ct
    cur=doxor(cur,k8f)
    cur=[sbox[i] for i in cur]
    cur=transinv(cur)
    cur=[sinv[i] for i in cur]
    k07=doxor(pt,cur)
    return k07
def decrypt(ct,k07,k8f,sbox,sinv):
    ct=s32tol8(ct)
    cur=ct
    cur=doxor(cur,k8f)
    cur=[sbox[i] for i in cur]
    cur=transinv(cur)
    cur=[sinv[i] for i in cur]
    m=doxor(cur,k07)
    return m

[5] 完整代码

整个解题过程中，步骤还是很多的，是自己目前写的最长的脚本

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
from Crypto.Util.number import *
from pwn import *
from os import urandom
def getboxinv(s):
    S,Q=[],[0]*256
    cntint,endex=0,False
    for i in s:
        if ord(i) in range(48,58):
            endex=True
            cntint=cntint*10+ord(i)-48
        else:
            if endex==True:
                endex=False
                S.append(cntint)
                Q[cntint]=len(S)-1
                cntint=0
    return S,Q
def s32tol8(s16):
    L8=[]
    for i in range(0,len(s16),2):
        L8.append(int(s16[i:i+2],16))
    return L8
def padhex(x,b):
    x=hex(x)[2:]
    return (b-len(x))*'0'+x
def padbin(x,b):
    x=bin(x)[2:]
    return (b-len(x))*'0'+x
def doxor(l1,l2):
    return [x[0]^x[1] for x in zip(l1,l2)]
def sumbitpros(a,x):
    c,d=a&x,0
    while c:
        d+=c&1
        c>>=1
    return d&1
def transinv(blk):
    res=[]
    blk=[(coefinv[i]*blk[i])&255 for i in range(8)]
    blk=[padbin(i,8)for i in blk]
    for i in range(8):
        s=""
        for j in range(-1,7):
            s+=blk[j][i]
        res.append(int(s,2))
    return res
def linersbox(sbox):
    lnipt=[]
    offset=[[0 for _ in range(256)] for __ in range(256)]
    for i in range(256):
        if i%15==0:
            print('[lnrsbox]:'+str(i+1)+'/256')
        si=sbox[i]
        for j in range(256):
            for k in range(256):
                a=sumbitpros(j,i)
                b=sumbitpros(k,si)
                if a==b:
                    offset[j][k]+=1
    for i in range(256):
        offset[i]=[abs(x-128)/256.0 for x in offset[i]]
    for i in range(256): 
        cur=[x[i] for x in offset] 
        lnipt.append(cur.index(max(cur)))
    return offset,lnipt
def guess(pt,ct,loc,gus,lnipt,coefinv):
    pt,ct=s32tol8(pt),s32tol8(ct)
    ct[loc]^=gus
    ct[loc]=sbox[ct[loc]]
    ct[loc]=ct[loc]*coefinv[loc]&255
    tmp1=sumbitpros(pt[0],lnipt[1<<((14-loc)&7)])
    tmp2=sumbitpros(ct[loc],128)
    return tmp1==tmp2
def getkey8f(Tl,Cl,lnipt,coefinv,scale):
    k8f=[]
    for i in range(8):
        print('[GettingKey]:ID='+str(i+8))
        kount=[0 for _ in range(256)]
        for gskey in range(256):
            for j in range(scale):
                if guess(Tl[j],Cl[j],i,gskey,lnipt,coefinv):
                    kount[gskey]+=1
        beta=[abs(x-scale//2+0.0)/(scale+0.0) for x in kount]
        k8f.append(beta.index(max(beta)))
    return k8f
def getkey07(pt,ct,k8f,coefinv,sbox,sinv):
    pt,ct=s32tol8(pt),s32tol8(ct)
    cur=ct
    cur=doxor(cur,k8f)
    cur=[sbox[i] for i in cur]
    cur=transinv(cur)
    cur=[sinv[i] for i in cur]
    k07=doxor(pt,cur)
    return k07
def decrypt(ct,k07,k8f,sbox,sinv):
    ct=s32tol8(ct)
    cur=ct
    cur=doxor(cur,k8f)
    cur=[sbox[i] for i in cur]
    cur=transinv(cur)
    cur=[sinv[i] for i in cur]
    m=doxor(cur,k07)
    return m
#----------MAIN BELOW----------#
sh=remote("node3.buuoj.cn",29170)
sbox=sh.recvline(keepends=False)
C=sh.recvline(keepends=False)
print(C)
sbox,sinv=getboxinv(sbox)
Tl,Cl=[],[]
coefinv=[15,11,155,119,11,99,83,249]
for i in range(16384):
    if i%45==0:
        print('[Recving]:'+str(i+1)+'/16384')
    cntsend=padhex(bytes_to_long(urandom(8)),16)
    Tl.append(cntsend)
    sh.sendline(cntsend)
    Cl.append(sh.recvline(keepends=False))
offset,lnipt=linersbox(sbox)
k8f=getkey8f(Tl,Cl,lnipt,coefinv,16384)
print(k8f)
k07=getkey07(Tl[0],Cl[0],k8f,coefinv,sbox,sinv)
print(k07)
flag=[]
for i in range(0,len(C),16):
    m=decrypt(C[i:i+16],k07,k8f,sbox,sinv)
    flag+=m
print(flag)
#[110, 112, 117, 99, 116, 102, 123, 55, 105, 110, 121, 83, 80, 78, 45, 99, 52, 110, 45, 98, 51, 45, 51, 64, 115, 105, 49, 121, 45, 99, 114, 52, 99, 107, 51, 100, 33, 33, 125, 1]
文章作者: huangx607087
文章链接: http://example.com/2021/02/26/Explore-SPN/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
Notes
赏
  目录