DDCTF2020 密码题

2020/09/07 CTF

我参加了滴滴安全部门举办的DDCTF 2020比赛,期间我重点关注其中一道密码题,下面是这道题目的解法以及衍生出来的知识背景。

题目描述

try to decrypt:8ed251b18692697d92901d7c575f64478b002a7252c631be9e617e08c60498e29a6972921fae8df01dcf

点击这里获取题目的源文件。其中包含了加解密算法,以及一组明文、密文对。题目中使用的加密算法是一种基于SPN架构的分组密码,它首先将字符串按每6个字节分成一个块,每个块的大小是48bit,随后将这48bit数据拆分成4个12bit的数据,对这12bit的数据进行加密后拼接得到密文。

我们将这个问题简化为给定一组12bit长度的密文以及对应的明文,需要破解出其加密使用的密钥(5个长度12bit的整数)。按照给定的明密文对,我们可以将其转化为下列形式:

P = [1079, 633, 1799, 1121, 1766, 364, 1943, 873, 1842, 104, 1559, 800, 1590, 3941, 1894, 3948, 1894, 1380, 519, 1135, 1654, 1396, 1670, 1394, 519, 1897, 1862, 2080, 1591, 633, 1799, 1135, 1655, 609, 1798, 2169, 0, 0, 0, 0]

C = [567, 361, 1793, 1001, 3036, 2896, 307, 258, 3884, 2240, 2214, 2489, 993, 2168, 2759, 2361, 2759, 73, 2269, 3421, 3808, 415, 1214, 1260, 2269, 934, 300, 2160, 2209, 361, 1793, 3421, 990, 790, 2503, 2845, 326, 326, 326, 326]

观察上面的内容会发现,相同的明文加密出来的结果是一致的,也就是每个密文与明文之间的映射关系是确定的。假如说我们有足够多的密文明文对,那么就可以在不知道密钥的情况下破解密文了,但是题目中只给出了这些对应关系,所以通过寻找映射关系这种思路是不正确的。

SPN(substitution-permutation network)代换-置换网络是一类特殊的迭代密码,迭代结构如下图所示,其一般包含三个部分,分别是密钥置换、轮加密函数、轮解密函数。

在这道题目里面,轮函数(sbox0、sbox1、ror7)使用了SPN结构,没有使用密钥置换函数。密码算法的大致架构如下图所示。其中sbox0和sbox1虽然是通过伪随机数函数生成的,但是在题目里这两个盒子的映射关系是已知的。ror7这个盒子的作用则是将12bit数据循环右移7位。

解答

首当其冲的想法是暴力破解,无脑循环4096的5次方次寻找密钥,这个算法的速度太慢了。我们可以尝试优化到4096的4次方:

1. randomly pick k0, k1, k2, k3
2. choose one pair (p0, c0)
3. k4 = ror7[sbox0[sbox1[sbox0[p0 ⊕ k0] ⊕ k1] ⊕ k2] ⊕ k3] ⊕ c0
4. choose another pair (pi, ci)
5. test if encrypt(pi, k0, k1, k2, k3, k4) equals to ci

在macbook pro 2016上运行这个算法非常慢,如果算力较强的电脑可能需要几个小时才能破解出来(其实也满足比赛时间要求)。随后我查阅了一些关于SPN结构分组密码的攻击方法,其中提出的一种思路是差分攻击(后面详细补充),我使用差分攻击的脚本去检测sbox0和sbox1未发现有可攻击的漏洞。

紧接着思路转变为能不能对这个SPN架构进行化简,也就是找到一个等价关系的架构,试图通过明文密文对来找到k0~k4这5个密钥之间的关系表达式。经过一番尝试,发现sbox0和sbox1是非线性的映射关系,也就是无法找到一个线性表达式,这就意味着不能用解方程式的思路去解。后来在看差分攻击的文章发现了一句话,差分值经过sbox传递的时候不受到异或的影响,那么这个ror7盒子仅仅是做了移位操作,是否存在可以化简的可能性呢?

实验结果证明是可以的,我们找到了这个关系式成立:ror7(a ⊕ b) = ror7(a) ⊕ ror7(b)。于是我们可以将上面的SPN架构化简为:

通过这个化简后的结构图我们可以得出一个结论,那就是k3和k4总是成双成对出现的,也就是说这道题目求解出来的加密密钥,k0、k1、k2是固定的,但是k3和k4有很多种可能性(4096种可能性)。有了这个条件之后,我们就相当于只需要破解3个密钥即可,加上上面的算法优化,我们只需要暴力循环4096^3次。下面是给出破解的伪代码:

1. suppose T3 equals ror7(k3) ⊕ k4
2. randomly pick k0, k1, k2
3. choose one pair (p0, c0)
4. T3 = ror7[sbox0[sbox1[sbox0[p0 ⊕ k0] ⊕ k1] ⊕ k2]] ⊕ c0
5. choose another pair (pi, ci)
6. test if ror7[sbox0[sbox1[sbox0[pi ⊕ k0] ⊕ k1] ⊕ k2]] = T3 ⊕ ci
7. find only one T3, get (k0, k1, k2)
8. randomly pick k3, k4
9. test if ror7(k3) ⊕ k4 = T3
10. get (k0, k1, k2, k3, k4)

参考代码

下面这段程序使用了5组明密文对,在MBP 2016(Core i5 6267U 2.90GHz)上运行需要约10分钟时间,将求解出来的一组密钥输入到上面的python文件中即可。这个解法不是最优解,但暴力破解时间控制在10分钟内也是可以接受的了,我总是觉得这个题目是可以使用差分攻击来秒解的,等后续正式writeup出来后再更新。

进一步的,代码中我们不妨假设k3=0,此时k4 = T3 ^ ror7(k3) = T3。

#include <iostream>
using namespace std;

#define MAX_VALUE 4096

int _rand_start = 0;
int sbox0[MAX_VALUE], sbox1[MAX_VALUE];
int P[5] = {1079, 633, 1799, 1121, 1766};
int C[5] = {567, 361, 1793, 1001, 3036};
int K[5] = {0};
int T3 = 0;

int my_rand() {
    if(!_rand_start)
        _rand_start=123459876;
    int hi = _rand_start / 127773;
    int lo = _rand_start % 127773;
    long long x = 16807*(long long)lo - 2836*(long long)hi;
    if(x<0)
        x+=0x7fffffff;
    _rand_start = (x % 2147483648);
    return _rand_start;
}

void generate_boxes(int seed,int sbox[]) {
    _rand_start=seed;
    for(int i=0; i<MAX_VALUE; i++){
        int r = my_rand() % MAX_VALUE;
        int t = sbox[i];
        sbox[i] = sbox[r];
        sbox[r] = t;
    }
}

void init_boxes() {
    for(int i=0; i<MAX_VALUE; i++){
        sbox0[i] = i;
        sbox1[i] = i;
    }
    generate_boxes(106,sbox0);
    generate_boxes(81,sbox1);
}

int ror7(int b){
    return ((b >> 7) | (b << 5)) & 0xfff;
}

int fun(int p, int k0, int k1, int k2) {
    return ror7(sbox0[sbox1[sbox0[p ^ k0] ^ k1] ^ k2]);
}

void crack() {
    for (int k0=0; k0<MAX_VALUE; k0++) {
        for (int k1=0; k1<MAX_VALUE; k1++) {
            for (int k2=0; k2<MAX_VALUE; k2++) {
                T3 = fun(P[0], k0, k1, k2) ^ C[0];
                if ((T3 ^ fun(P[1], k0, k1, k2)) == C[1]
                    && (T3 ^ fun(P[2], k0, k1, k2)) == C[2]
                    && (T3 ^ fun(P[3], k0, k1, k2)) == C[3]
                    && (T3 ^ fun(P[4], k0, k1, k2)) == C[4]) 
                {
                    K[0] = k0;
                    K[1] = k1;
                    K[2] = k2;
                    return;
                }
            }
        }
    }
}

int main() {
    init_boxes();
    crack();

    K[3] = 0;
    K[4] = T3;

    cout << "(" << K[0] << "," << K[1] << "," << K[2] << "," << K[3] << "," << K[4] << ")" << endl;
    return 0;
}

差分攻击

上面的算法中,循环次数是4096的3次方,速度还是比较慢的。经过同学的提示,我发现了一个差分攻击的实例,下面是这个结构图的进一步简化:

我们可以遍历k0和k1,结合1个明文P可以求解出TP,此时TP与C形成一组明密文对,k2和T3看做是两个需要求解的密钥。这是一个非常标准的sbox模型,使用典型的二元差分攻击即可爆破出k2和T3,它的思路是:

1. get (TP0,C0) and (TP1,C1).
2. diffX = TP0 ⊕ TP1, diffY = C0 ⊕ C1.
3. find all (x0,x1) which satisfies x0 ⊕ x1 = diffX and sbox2[x0] ⊕ sbox2[x1] = diffY.
4. suppose any two value in x[] and y[] satisfies x[i] ⊕ x[j] = diffX and y[i] ⊕ y[j] = diffY.
5. let k2 = TP0 ⊕ x[i], T3 = C0 ⊕ y[i].
6. choose another TPi and Ci, test whether sbox2[TPi ⊕ k2] ⊕ T3 equal to Ci.

参考代码如下,这个程序不到1秒就找出密钥了,它只需要\(4096^2 \times pairSize[diff]\)次循环,空间开销是\(2 \times 4096^2\),典型的空间换时间策略。下面的代码删除了部分函数的内容,与上文一致。

#include <iostream>
using namespace std;

#define MAX_VALUE 4096

int _rand_start = 0;
int sbox0[MAX_VALUE], sbox1[MAX_VALUE], sbox2[MAX_VALUE];
int P[5] = {1079, 633, 1799, 1121, 1766};
int C[5] = {567, 361, 1793, 1001, 3036};
int K[5] = {0};
int T3 = 0;

int my_rand() {
}

void generate_boxes(int seed,int sbox[]) {
}

int ror7(int b){
}

void init_boxes() {
    for (int i=0; i<MAX_VALUE; i++) {
        sbox0[i] = i;
        sbox1[i] = i;
    }
    generate_boxes(106,sbox0);
    generate_boxes(81,sbox1);
    for (int i=0; i<MAX_VALUE; i++) {
        sbox2[i] = ror7(sbox0[i]);
    }
}

int pairSize[MAX_VALUE] = {0};
int inputX[MAX_VALUE][MAX_VALUE] = {0};
int inputY[MAX_VALUE][MAX_VALUE] = {0};

int main() {
    init_boxes();
    int TP[5] = {0};
    int k2 = 0, T3 = 0;
    int TT = C[0] ^ C[1];

    for (int PiP=0; PiP<MAX_VALUE; PiP++) {
        int index = 0;
        for (int i=0; i<MAX_VALUE; i++) {
            int j = sbox2[i];
            if (sbox2[i ^ PiP] == (j ^ TT)) {
                inputX[PiP][index] = i;
                inputY[PiP][index] = j;
                index++;
            }
        }
        pairSize[PiP] = index;
    }

    for (int k0=0; k0<MAX_VALUE; k0++) {
        for (int k1=0; k1<MAX_VALUE; k1++) {
            for (int i=0; i<5; i++)
                TP[i] = sbox1[sbox0[P[i] ^ k0] ^ k1];
            int diff = TP[0] ^ TP[1];
            for (int i=0; i<pairSize[diff]; i++) {
                k2 = TP[0] ^ inputX[diff][i];
                T3 = C[0] ^ inputY[diff][i];
                if ((sbox2[TP[1] ^ k2] ^ T3) == C[1] 
                    && (sbox2[TP[2] ^ k2] ^ T3) == C[2] 
                    && (sbox2[TP[3] ^ k2] ^ T3) == C[3] 
                    && (sbox2[TP[4] ^ k2] ^ T3) == C[4]) 
                {
                    cout << "Key is ";
                    cout << "(" << k0 << "," << k1 << "," << k2 << "," << 0 << "," << T3 << ")" << endl;
                    return 0;
                }
            }
        }
    }
}

进一步地通过实验结果发现,这个代码中pairSize[diff]的值其实很小,所以inputX和inputY两张二维表实际被使用的部分是很小的,因此我们可以用一些STL数据结构来优化下代码,让空间占用率减少点。一开始我拒绝使用STL是担心速度的问题,下面的代码运行结果显示,速度的影响微乎其微。通过结果分析可以得出时间开销是\(4096^2\),空间开销是\(4096*1.5\)左右。下面的代码删除了部分函数的内容,与上文一致。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_VALUE 4096

int _rand_start = 0;
int sbox0[MAX_VALUE], sbox1[MAX_VALUE], sbox2[MAX_VALUE];

int my_rand() {
}

void generate_boxes(int seed,int sbox[]) {
}

int ror7(int b){
}

void init_boxes() {
}

int main() {
    init_boxes();
    int TP[5] = {0};
    int P[5] = {1079, 633, 1799, 1121, 1766};
    int C[5] = {567, 361, 1793, 1001, 3036};
    int k2 = 0, T3 = 0, TT = C[0] ^ C[1];
    vector<vector<pair<int, int> > > diffPair(4096);

    for (int PiP=0; PiP<MAX_VALUE; PiP++)
        for (int i=0; i<MAX_VALUE; i++)
            if (sbox2[i ^ PiP] == (sbox2[i] ^ TT))
                diffPair[PiP].push_back(make_pair(i, sbox2[i]));

    for (int k0=0; k0<MAX_VALUE; k0++) {
        for (int k1=0; k1<MAX_VALUE; k1++) {
            for (int i=0; i<5; i++)
                TP[i] = sbox1[sbox0[P[i] ^ k0] ^ k1];
            int diff = TP[0] ^ TP[1];
            for (auto item:diffPair[diff]) {
                k2 = TP[0] ^ (item.first);
                T3 = C[0] ^ (item.second);
                if ((sbox2[TP[1] ^ k2] ^ T3) == C[1] 
                    && (sbox2[TP[2] ^ k2] ^ T3) == C[2] 
                    && (sbox2[TP[3] ^ k2] ^ T3) == C[3] 
                    && (sbox2[TP[4] ^ k2] ^ T3) == C[4]) 
                {
                    cout << "Key is ";
                    cout << "(" << k0 << "," << k1 << "," << k2 << "," << 0 << "," << T3 << ")" << endl;
                    return 0;
                }
            }
        }
    }
}

感想

这篇博客的“差分攻击”部分的两段代码,是我将博文分享出去后,收到了两位同学的建议下,重新做实验探索出来的,这让我很感触。学习的道路上永远不可能是闭门造车,只有将自己的思考分享出去,才能得到新的思考、新的回响,这也是我坚持写博客的原因之一。

Search

    Table of Contents