前言
这学期选了一门网安的科研课堂。第一节课就给了我一个下马威，直接阅读全英论文。好在我借助翻译读了一遍后，又听教授和同学们讲了一次，总算是把33页论文的第一部分，也就是Linear Cryptanalysis理解完了。
当然理解归一回事儿，实现是另一回事，所以昨天晚上（也就是9月13日下午），我就把论文中的例子基本复现出来了。
分组密码
什么是分组密码？简而言之就是把数据分组，一组一组的加密。论文中的例子是一个非常简单的分组加密，数据每16bit为一组，采用的是SPN结构（即Substitution-Permutation Network）。这个加密会经过若干轮，每轮有如下步骤：
Substitution 置换
我们把16bit数据分成4bit一组，一共4组。将每组的4bit的值传入对应S-box中，S-box也会传出一个4bit的值。每个S-box的逻辑都可以查表得到。通常4个S-box应当不一样，但是作为例子，论文中选取了同样的S-box。其映射表如下：
| 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 |
上表以16进制数表示4bit的值。
Permutation 排列
排列就是一个连线的操作，当然也可以理解为一种映射。本步骤的输出就是输入的一种排列。下表是例子选用的排列：
| 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 |
上表中input=3, output=9表示输出中第9比特的值来自输入中第3比特的值。
Key Mixing 密钥加密
所谓Key Mixing其实异常简单，就是给一个16bit的密钥，然后和16bit的输入进行异或，就得到了16bit的输出。
图示
本图是从 A Tutorial on Linear and Differential Cryptanalysis 中摘下来的。
线性分析
我原以为，我们可以直接从明密文对获取加密信息，并且破译密码。结果，我发现我们能做的不过是在Substitution和Permutation都已知的情况下去推测Subkey的值。但即便如此，也并非易事。
堆积引理
$X_1,X_2,\cdots,X_n$是二值分布，在它们相互独立的情况下，若$p_1=\frac12+\epsilon_1,\cdots,p_n=\frac12+\epsilon_n$，则有：
$$
Pr(X_1 \oplus \cdots \oplus X_n = 0) = \frac12 + 2^{n-1}\prod_{i=1}^{n}\epsilon_i
$$
或者说：
$$
\epsilon_{1,2,\cdots,n} = 2^{n-1}\prod_{i=1}^{n}\epsilon_i
$$
我们称$\epsilon$为bias，偏差，$\epsilon=Pr-\frac12$。
线性拟合S-box
由于S-box是整个加密过程中唯一的非线性过程，也是本加密方法的安全性所在。为了破译密码，我们不得不对S-box进行线性拟合。
假设S-box的输入是$X_1,X_2,X_3,X_4$，输出是$Y_1,Y_2,Y_3,Y_4$，列出一组线性表达式，我们就可以算出输入随机的时候，该线性表达式成立的概率。譬如：$X_2 \oplus X_3 = Y_1 \oplus Y_3 \oplus Y_4$，穷举后可知16个不同输入中有12个使得这个式子成立。则成立概率是$\frac34$，偏差是$\frac14$。
子密钥分析
我们选取偏差较大的线性方程，然后模拟该方程所涉及到的输入的加密路劲，沿途应用堆积引理，最终可以得到一个明文和倒数第二轮的输出的一个线性表示的成立的概率的偏差的绝对值。
然后，穷举最后一个subkey的有涉及的位，根据密文逆推得到倒数第二轮输出，然后和明文一起，记录线性表达式成立的次数。选取很多组明文对（论文是1万组，我实测是10万组才能得到好的结果），计算线性表示成立概率。对于穷举到的每一个subkey，最后偏差绝对值最大的那一个就高概率是密钥，而且这个偏差和线性表达式的偏差的非常接近。
复现
加密过程复现
最开始是打算用Python的，后来发现Python位运算并不方便，所以就用C++了。贴个代码吧。
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned char u8, u4;
typedef unsigned short u16;
const u4 sbox[] = {
0xE, 0x4, 0xD, 0x1,
0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC,
0x5, 0x9, 0x0, 0x7,
};
const u4 wire[] = {
0x0, 0x4, 0x8, 0xc,
0x1, 0x5, 0x9, 0xd,
0x2, 0x6, 0xa, 0xe,
0x3, 0x7, 0xb, 0xf,
};
const u16 KEYS[] = {
0xed52,
0x3799,
0xac27,
0x47fc,
0x72b4,
// 0xacbd, 密钥随便改
};
inline u16 permutation(u16);
inline u16 substitution(u16);
inline u16 key_mixing(u16, u16);
inline u16 halfWordFunc(u16&, const u16*, int);
int main()
{
freopen("1.data.in", "rb", stdin);
freopen("1.data.out", "wb", stdout);
int ch1, ch2;
while(~(ch1 = getchar()))
{
ch2 = getchar();
if(ch2 == EOF) ch2 = 0;
u16 data = ch1 << 8 | ch2; // 两个字节16bit为一组
halfWordFunc(data, KEYS, 4);
ch1 = data >> 8;
ch2 = data & 0xff;
putchar(ch1);
putchar(ch2);
}
return 0;
}
inline u16 substitution(u16 data)
{
const u16 p1 = 0xf000, p2 = 0x0f00, p3 = 0x00f0, p4 = 0x000f;
u16 d1 = (data & p1) >> 12, d2 = (data & p2) >> 8, d3 = (data & p3) >> 4, d4 = data & p4;
d1 = sbox[d1] << 12;
d2 = sbox[d2] << 8;
d3 = sbox[d3] << 4;
d4 = sbox[d4];
return d1 | d2 | d3 | d4;
}
inline u16 permutation(u16 data)
{
bitset<16> bst = data, out;
for(int i = 0; i < 16; i++)
{
out[i] = bst[wire[i]];
}
return (u16) out.to_ulong();
}
inline u16 key_mixing(u16 data, u16 key)
{
return data ^ key;
}
inline u16 halfWordFunc(u16& data, const u16* keys, int round)
{
for(int i = 1; i < round; i++)
{
data = key_mixing(data, keys[i-1]);
data = substitution(data);
data = permutation(data);
}
data = key_mixing(data, keys[round-1]);
data = substitution(data);
data = key_mixing(data, keys[round]);
return data;
}密码分析
这次用的Python，虽然我还是觉得Python的位运算真的有些别扭……
import pandas as pd
'U4,6 ^ U4,8 ^ U4,14 ^ U4,16 ^ P5 ^ P7 ^ P8 = 0'
SBOX = (
0xE, 0x4, 0xD, 0x1,
0x2, 0xF, 0xB, 0x8,
0x3, 0xA, 0x6, 0xC,
0x5, 0x9, 0x0, 0x7,
)
WIRE = (
0x0, 0x4, 0x8, 0xc,
0x1, 0x5, 0x9, 0xd,
0x2, 0x6, 0xa, 0xe,
0x3, 0x7, 0xb, 0xf,
)
INV_SBOX = (
0xe, 0x3, 0x4, 0x8,
0x1, 0xc, 0xa, 0xf,
0x7, 0xd, 0x9, 0x6,
0xb, 0x2, 0x0, 0x5,
)
'明文对个数'
DATA_GROUP = 100000
if __name__ == '__main__':
anlysis = pd.DataFrame(columns=['partial subkey', '|bias|'])
# print(anlysis.info())
for k in range(256):
fp = open('1.data.in', 'rb')
fe = open('1.data.out', 'rb')
k2 = k >> 4
k4 = k & 0xf
key = k2 << 8 | k4
count_of_equal = 0
for i in range(DATA_GROUP):
p = ord(fp.read(1)) << 8 | ord(fp.read(1))
e = ord(fe.read(1)) << 8 | ord(fe.read(1))
# print('%X->%X'%(p,e))
v = key ^ e
u2 = INV_SBOX[(v&0x0f00)>>8]
u4 = INV_SBOX[(v&0x000f)>>0]
u_4_6 = (u2 & 0b0100) >> 2
u_4_8 = (u2 & 0b0001) >> 0
u_4_14 = (u4 & 0b0100) >> 2
u_4_16 = (u4 & 0b0001) >> 0
p_5 = (p & 0x0800) >> 11
p_7 = (p & 0x0200) >> 9
p_8 = (p & 0x0100) >> 8
if u_4_14 ^ u_4_6 ^ u_4_8 ^ u_4_16 == p_5 ^ p_7 ^ p_8:
count_of_equal += 1
anlysis = anlysis.append({'partial subkey':'%x %x'%(k2,k4), '|bias|':'%.04f'%(abs(count_of_equal - DATA_GROUP / 2) / DATA_GROUP)}, ignore_index=True)
fp.close()
fe.close()
anlysis.to_csv('1.data.csv', index=False)分析结果
可见第五轮subkey的第5-9bit是0b0010，第13-16bit是0b0100，还是十分准确的，而且bias是0.0308和论文给的理论值$\frac1{32}=0.03125$还是十分接近的。
参考资料
[1]Heys, Howard M . A Tutorial on Linear and Differential Cryptanalysis[J]. Cryptologia, 2002, 26(3):189-221.
–3e21d02a14a849f477b88b14859f1ee2–
