中科大CTF2018 加密算法和解密算法 WP

(Updated: )
, , , ,

BrainFuck虚拟机翻译优化

近日参加了中科大的CTF，中科大出的题都非常有趣，大概是我玩得最开心的一次比赛了（要是会做的题多点能更开心。）
BrainFuck代码优化的这题本身难度不大，但第一次做这样的虚拟机翻译优化的题目

题目

提示：本题中使用的 base64 编码，采用已被广泛应用于各种场合的 RFC 4648 §5 标准。
小赵听到自己成为了信息安全大赛的创始人后感到非常吃惊：“我一个少院学生会的干事，怎么就成信息安全大赛的创始人了呢？”这也难怪，毕竟小赵后来成为了物理学院的学生。物理和信息安全，通常情况下可都是八杆子打不着的呢。
当然了，小赵作为物理学院的学生，和其他物理学院的学生一样，身上的浮躁劲儿可一点都不少，常常因为一点小成就而沾沾自喜。这不，因为个人安全上的不重视，小赵的某个学弟小郑，很快从小赵暗恋的女孩子手里拿到了小赵和她交流的加密算法的程序。小赵在得知此事后反而没有尽可能地息事宁人，反而公开宣称，由于解密算法目前没有公开，所以拿到了加密算法也没有什么用。看来小赵对于现代密码学，根本没什么全面深入的了解啊。
不过，即使小赵使用的是对称加密算法，分析出解密算法也并非易事——小赵对程序进行了混淆，而混淆的方法是使用 BrainFuck 虚拟机——这也正是小赵的底气所在。现在的任务是分析并读懂一段 BrainFuck 程序，从而将一段密文还原。
现在小郑将这一任务交给了跃跃欲试的你。快来挖掘小赵的黑历史吧！
更多信息请下载题目文件

题目文本没什么好说的，附件主要提供了一个网页，对加密流程进行了补充说明、并给出了一个简单的测试flag的入口，encrypt.bf给出了BrainFuck实现的加密算法。

加密流程

以QUICK_BROWN_FOXES_JUMP_OVER_THE_LAZY_DOG为例。

编码过程如下：

将原文分为四段，每段长度为十： [QUICK_BROW, N_FOXES_JU, MP_OVER_TH, E_LAZY_DOG]
每一段按 Base64 的顺序映射到 0 和 63 之间的数字：
第一段映射后结果为： [16, 20, 8, 2, 10, 63, 1, 17, 14, 22]
第二段映射后结果为： [13, 63, 5, 14, 23, 4, 18, 63, 9, 20]
依此类推
将十个为一组的数字输入 BrainFuck 解释器
解码过程如下：

BrainFuck 解释器一次输出十个数字：
第一段输出后结果为： [154, 76, 209, 202, 232, 37, 165, 180, 251, 165]
第二段输出后结果为： [28, 159, 248, 253, 146, 136, 174, 207, 171, 141]
依此类推
每一段的每一个数字对 64 取模：
第一段取模后结果为： [26, 12, 17, 10, 40, 37, 37, 52, 59, 37]
第二段取模后结果为： [28, 31, 56, 61, 18, 8, 46, 15, 43, 13]
依此类推
每一段按 Base64 的顺序映射后拼接在一起： [aMRKoll07l, cf49SIuPrN, g8v5bMctTk, frQmchaEkF]
将四段拼接后得到密文

加密的主体在于BrainFuck代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
,[->>+++++++>>+++++>>+++>>++>>++++>++++++<<+++<<+++++++++<<++++++++<<
++++++<<++++++++<]>[->>+++++>>+++++++++>>+++++++++>>++>>++++<+++++++++<<++++<<++++<<++<<++<]<,[->>++
+++>>++++++++>>++++++>>+++++++>>+++++++>++++++<<++++++<<++++++++<<+++<<+++<<++++++++<]>[->>++++++++>
>+++>>+++++++>>++++>>+++++++++<++++++<<+++++++++<<++<<+++++++++<<++++++++<]<,[->>++++++++>>+++++++>>
++>>++>>+++++++++>+++<<++++<<+++<<+++++<<++++++++<<++++++++<]>[->>++++>>++++++++>>++++++>>++++++>>++
+++<++++<<+++++++++<<++++++++<<+++++++<<++++<]<,[->>+++++>>+++++++++>>+++>>++++>>++++>+++<<++++++++<
<++++++<<+++++<<++++++<<++++++++<]>[->>++++++>>++++++>>+++++>>++++++++>>+++++++<++++++++<<++++++<<++
+++<<+++<<+++++++<]<,[->>+++++++>>++++>>++++>>+++>>+++++++>+++++++<<+++++++++<<+++++<<+++++<<+++++++
<<++++++++<]>[->>+++>>++++>>++++>>+++++>>++++++<++++<<+++<<++++++++<<+++++++<<+++++<]<,[->>+++++>>++
>>++++>>+++>>++++++>++<<+++++++<<++++<<+++++++++<<+++++++<<++++++++<]>[->>++>>+++++++++>>+++++>>++++
++++>>+++++++++<+++++++<<++<<++++<<+++<<++<]<,[->>++++++>>+++++++>>+++>>++++++>>++++++++>++<<++++<<+
++<<++++++++<<++++++<<++++++++<]>[->>++++++>>++>>+++++++++>>++++>>++++++<+++++<<++++<<++++++++<<++++
<<+++++++<]<,[->>+++++++++>>++++++++>>++++++>>+++++++>>+++++++++>++<<++++++++<<+++++<<+++++<<+++<<++
++++++<]>[->>+++++++++>>+++++++>>+++++++++>>++++>>++<+++++++<<+++++++++<<++<<+++<<++++++++<]<,[->>++
>>++++++++>>++>>++++++>>+++++>++++<<++++<<+++++++<<+++++++<<++++++++<<++++++++<]>[->>+++++++>>++>>++
++++++>>+++++++>>++++<++<<+++<<+++++++<<+++++<<++<]<,[->>+++++++++>>+++++++>>+++++>>++++>>++>+++++<<
+++++<<++<<++<<+++++<<++++++++<]>[->>++++++++>>++++++>>++>>+++++>>+++++++++<++++++++<<++++++++<<++++
<<++++<<+++++++++<]>++.>++++++.>++++++++.>++++++++.>+++.>+++++.>+++++.>+++++++.>++++.>+++++++++.

BrainFuck 简介

众所周知的，BrainFuck作为一门图灵完备的语言，总共有八个操作符，这八个操作符执行的操作和与C语言对应关系如下：

BrainFuck 含义 C
> 指针自增 ++ptr;
< 指针自减 --ptr;
+ 指针指向单元自增 ++*ptr;
- 指针指向单元自减 --*ptr;
. 输出指针指向单元内容 putchar(*ptr);
, 输入内容到指针指向单元 *ptr = getchar();
[ 如果指向单元为零，则跳转到下一个] while (*ptr) {
] 如果指向单元不为零，跳转到上一[ }

翻译BrainFuck

可以看到，BrainFuck的判断和跳转由[]指令实现，一对[]可以翻译为while (*ptr) {}，所以我们先将代码整理成以[]为单位

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
,
[->>+++++++>>+++++>>+++>>++>>++++>++++++<<+++<<+++++++++<<++++++++<<++++++<<++++++++<]
>
[->>+++++>>+++++++++>>+++++++++>>++>>++++<+++++++++<<++++<<++++<<++<<++<]
<,
[->>+++++>>++++++++>>++++++>>+++++++>>+++++++>++++++<<++++++<<++++++++<<+++<<+++<<++++++++<]
>
[->>++++++++>>+++>>+++++++>>++++>>+++++++++<++++++<<+++++++++<<++<<+++++++++<<++++++++<]
<,
[->>++++++++>>+++++++>>++>>++>>+++++++++>+++<<++++<<+++<<+++++<<++++++++<<++++++++<]
>
[->>++++>>++++++++>>++++++>>++++++>>+++++<++++<<+++++++++<<++++++++<<+++++++<<++++<]
<,
[->>+++++>>+++++++++>>+++>>++++>>++++>+++<<++++++++<<++++++<<+++++<<++++++<<++++++++<]
>
[->>++++++>>++++++>>+++++>>++++++++>>+++++++<++++++++<<++++++<<+++++<<+++<<+++++++<]
<,
[->>+++++++>>++++>>++++>>+++>>+++++++>+++++++<<+++++++++<<+++++<<+++++<<+++++++<<++++++++<]
>
[->>+++>>++++>>++++>>+++++>>++++++<++++<<+++<<++++++++<<+++++++<<+++++<]
<,
[->>+++++>>++>>++++>>+++>>++++++>++<<+++++++<<++++<<+++++++++<<+++++++<<++++++++<]
>
[->>++>>+++++++++>>+++++>>++++++++>>+++++++++<+++++++<<++<<++++<<+++<<++<]
<,
[->>++++++>>+++++++>>+++>>++++++>>++++++++>++<<++++<<+++<<++++++++<<++++++<<++++++++<]
>
[->>++++++>>++>>+++++++++>>++++>>++++++<+++++<<++++<<++++++++<<++++<<+++++++<]
<,
[->>+++++++++>>++++++++>>++++++>>+++++++>>+++++++++>++<<++++++++<<+++++<<+++++<<+++<<++++++++<]
>
[->>+++++++++>>+++++++>>+++++++++>>++++>>++<+++++++<<+++++++++<<++<<+++<<++++++++<]
<,
[->>++>>++++++++>>++>>++++++>>+++++>++++<<++++<<+++++++<<+++++++<<++++++++<<++++++++<]
>
[->>+++++++>>++>>++++++++>>+++++++>>++++<++<<+++<<+++++++<<+++++<<++<]
<,
[->>+++++++++>>+++++++>>+++++>>++++>>++>+++++<<+++++<<++<<++<<+++++<<++++++++<]
>
[->>++++++++>>++++++>>++>>+++++>>+++++++++<++++++++<<++++++++<<++++<<++++<<+++++++++<]
>++.>++++++.>++++++++.>++++++++.>+++.>+++++.>+++++.>+++++++.>++++.>+++++++++.

然后可以对每个循环块简要分析。首先要确定每个循环块每次循环的判断依据，这题简单就简单在每个循环块中指针自增和指针自减的数量是相同的，也就是说循环次数只由一个变量决定，而且每次循环都是对相同的单元进行相同的操作。
既然如此，那我们翻译代码的难度大大降低了。写一个脚本进行第一次翻译，将所有的指针增减操作简化掉：

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
ptr = 0
p = 0
code = 'balabala'
f = open('a', 'w')

w = lambda x: f.write(x + '\n')
# w = print
while p < len(code):
    if code[p] == '.':
        w('put(ptr[{}]);'.format(ptr))
    elif code[p] == ',':
        w('ptr[{}] = get();'.format(ptr))
    elif code[p] == '<':
        ptr -= 1
    elif code[p] == '>':
        ptr += 1
    elif code[p] == '+':
        w('ptr[{}] += 1;'.format(ptr))
    elif code[p] == '-':
        w('ptr[{}] -= 1;'.format(ptr))
    elif code[p] == '[':
        w('while (ptr[{}]) {{'.format(ptr))
        op = {}
        while code[p] != ']':
            x = code[p]
            if x == '>':
                ptr += 1
            elif x == '<':
                ptr -= 1
            elif x == '+':
                if op.get(ptr) is None:
                    op[ptr] = 0
                op[ptr] += 1
            elif x == '-':
                if op.get(ptr) is None:
                    op[ptr] = 0
                op[ptr] -= 1
            p += 1
        for x in sorted(op.keys()):
            if op[x] == 0:
                pass
            elif op[x] > 0:
                w('ptr[{}] += {};'.format(x, op[x]))
            elif op[x] < 0:
                w('ptr[{}] -= {};'.format(x, -op[x]))
        w('}')
    p += 1
f.close()

输出结果如下(有删减)：

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
ptr[0] = get();
while (ptr[0]) {
	ptr[0] -= 1;
	ptr[1] += 8;
    // balabala
}
while (ptr[1]) {
	ptr[1] -= 1;
    // balabala
}
ptr[0] = get();
while (ptr[0]) {
	ptr[0] -= 1;
	ptr[1] += 8;
    // balabala
}
while (ptr[1]) {
	ptr[1] -= 1;
	ptr[2] += 8;
    // balabala
}
ptr[0] = get();
while (ptr[0]) {
	ptr[0] -= 1;
	ptr[1] += 8;
    // balabala
}
while (ptr[1]) {
	ptr[1] -= 1;
    // balabala
}
// 略
// balabala
put(ptr[2]);
// balabala
put(ptr[3]);
// balabala
// balabala
put(ptr[11]);

代码的思路很q夸克，首先接受输入保存在ptr[0]，之后第一块循环块就以ptr[0]作为循环停止的判断依据，每次循环将ptr[0]减1，并对其他变量进行简单的加减法；之后第二个循环块以ptr[1]作为判断依据，每次循环也会将ptr[1]减1。两次循环块结束后再次接受输入、重复上述操作，重复10次后又对ptr[2:12]进行了一些简单的加减，然后依次输出ptr[2:12]。
分析后我们发现，循环块一的循环次数是完全由输入决定的，循环块二的循环次数由循环块一决定，且两个循环快进行的都是简单的加减运算，那么我们就可以将循环块一、二合并并展开，即将其整理为ptr[x] = a*input的形式。进一步的,我们可以将所有的循环块以及循环块外的操作合并，整理为ptr[x] = a0*input[0] + a1*input[1] + ... + a9*input[9] + b的形式。ptr[0] ptr[1]作为循环的临时变量抛弃掉，最后我们整理得到如下代码（转换代码略）：

1
2
ptr[0] = 23*input[0] + 69*input[1] + 40*input[2] + 61*input[3] + 47*input[4] + 21*input[5] + 62*input[6] + 73*input[7] + 18*input[8] + 81*input[9] + 2;
// balabala

考虑到附件中对算法的补充，我们对算法进行最后调整，得到：

1
2
3
4
5
6
7
8
9
10
out[0] = (23*in[0] + 69*in[1] + 40*in[2] + 61*in[3] + 47*in[4] + 21*in[5] + 62*in[6] + 73*in[7] + 18*in[8] + 81*in[9] + 2) % 64;
out[1] = (46*in[0] + 67*in[1] + 40*in[2] + 54*in[3] + 31*in[4] + 23*in[5] + 54*in[6] + 75*in[7] + 64*in[8] + 69*in[9] + 6) % 64;
out[2] = (21*in[0] + 80*in[1] + 63*in[2] + 33*in[3] + 60*in[4] + 26*in[5] + 39*in[6] + 32*in[7] + 48*in[8] + 39*in[9] + 8) % 64;
out[3] = (80*in[0] + 27*in[1] + 69*in[2] + 53*in[3] + 37*in[4] + 81*in[5] + 24*in[6] + 61*in[7] + 23*in[8] + 50*in[9] + 8) % 64;
out[4] = (35*in[0] + 22*in[1] + 66*in[2] + 43*in[3] + 68*in[4] + 36*in[5] + 67*in[6] + 22*in[7] + 58*in[8] + 37*in[9] + 3) % 64;
out[5] = (81*in[0] + 64*in[1] + 51*in[2] + 46*in[3] + 37*in[4] + 44*in[5] + 75*in[6] + 77*in[7] + 71*in[8] + 18*in[9] + 5) % 64;
out[6] = (34*in[0] + 79*in[1] + 74*in[2] + 52*in[3] + 27*in[4] + 19*in[5] + 38*in[6] + 79*in[7] + 30*in[8] + 68*in[9] + 5) % 64;
out[7] = (19*in[0] + 38*in[1] + 52*in[2] + 72*in[3] + 49*in[4] + 71*in[5] + 36*in[6] + 40*in[7] + 60*in[8] + 45*in[9] + 7) % 64;
out[8] = (76*in[0] + 55*in[1] + 41*in[2] + 68*in[3] + 39*in[4] + 62*in[5] + 48*in[6] + 65*in[7] + 21*in[8] + 66*in[9] + 4) % 64;
out[9] = (38*in[0] + 78*in[1] + 43*in[2] + 59*in[3] + 55*in[4] + 74*in[5] + 50*in[6] + 18*in[7] + 36*in[8] + 77*in[9] + 9) % 64;

解一次线性同余方程组

out已知，in未知，这样我们就得到了带模运算的十元一次方程组。额，这就触及到知识盲区了.png，尝试使用神器z3，居然也绝妙的被卡死了。。。
查阅资料这被称为一次线性同余方程组，解法参考链接。
看完之后发现里面提供的解法都有一定条件限制，我们得到的方程组哪种解法都不满足。
然后又找到这个，不得不说线性代数正是个强大的工具。

最后将附件中提供的密文JzRVPiVpqo4iDM8celyueIs4ff4DKeG3EMKihzuH转换为四组已知数，解四组方程然后经转换即得到明文。最后要注意的是题目用的是这套Base64标准

    Table 2: The "URL and Filename safe" Base 64 Alphabet

Value Encoding  Value Encoding  Value Encoding  Value Encoding
    0 A            17 R            34 i            51 z
    1 B            18 S            35 j            52 0
    2 C            19 T            36 k            53 1
    3 D            20 U            37 l            54 2
    4 E            21 V            38 m            55 3
    5 F            22 W            39 n            56 4
    6 G            23 X            40 o            57 5
    7 H            24 Y            41 p            58 6
    8 I            25 Z            42 q            59 7
    9 J            26 a            43 r            60 8
   10 K            27 b            44 s            61 9
   11 L            28 c            45 t            62 - (minus)
   12 M            29 d            46 u            63 _
   13 N            30 e            47 v            (underline)
   14 O            31 f            48 w
   15 P            32 g            49 x
   16 Q            33 h            50 y            (pad) =

看完大佬的WP才知道这是希尔密码，果然还是我太菜了。
看完官方WP我都不好意思发之篇文章了（虽然发了也没人看。。