首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[原创] 看雪 2023 KCTF 年度赛 第二题 CN星际基地
2023-9-5 04:57 8168

[原创] 看雪 2023 KCTF 年度赛 第二题 CN星际基地

mb_mgodlfyn 活跃值
12
2023-9-5 04:57
8168

全部逻辑都在main函数sub_140001790中，IDA F5静态分析 + x64dbg动态调试确定各部分的逻辑：（函数太长，伪代码不贴了）

第一步：读入serial，检查长度为156
第二步：serial的每四个字符一组（四个字符的位置相差39，即把156长度的输入变成4*39的数组，然后取每列的四个字符组成一组），转换成十进制数字。另外，如果这4个字符中没有'2'，则要求能按二进制转换成功且值不为15。注意15的二进制表示是1111，这里的限制暂可认为是检查一组四个字符组成的字符串不为"1111"
第三步：一些multibyte的转换，没有实质意义
第四步：继续检查一组四个字符，如果其中有'2'，则不能有4个'2'。相当于检查四个字符组成的字符串不为"2222"
第五步：把第二部分转出的十进制数再转回了字符串，没有实质意义
第六步：（0x140001DF2）第二步得到了39个十进制数，检查它们是递增的，且最小的数大于0
第七步：（0x140001EF1）检查156个原始字符只能是'0'、'1'、'2'之一，并把'0'转换为0，'1'转换为1，'2'转换为-1，存入0x1400098A8的4*39矩阵中。回顾第二步，其每四个字符组成的字符串实际上只能包含'0''1''2'三种字符，且不为"0000""1111""2222"。
第八步：给0x1400098C0的矩阵赋值，没有实质意义。
第九步：对第七步得到的0x1400098A8矩阵，从0到38遍历，对每一行，如果对应位置的数是1，则计数器1加一，如果对应位置的数是-1，则计数器2加一；然后，根据计数器1和2的大小关系将1、0、-1存入0x1400098B8（实际上，最终存入的值一定等于0x1400098A8矩阵对应列的值）；四行遍历完成后，再检查0x1400098B8的值与0x1400098A8矩阵的对应列的值相等。这是一个很奇怪的检查，代码很复杂但实际上没有任何效果，检查一定会无条件通过。另外，第七步的'2'->-1的转换也并没有实质效果
第十步：（0x140002512）在第九步的遍历中，对每一行，将该行的39个数求和，检查结果为0（当且仅当行内1和-1的个数相等时才满足）

以上是程序对serial的所有逻辑校验。如果都通过，则最后检查156字节的serial的md5值为"aac82b7ad77ab00dcef90ac079c9490d"。

举个例子总结一下校验逻辑：例如输入的serial为 000000000000011111111111112222222222222000011111111100001122222220000011222222011100011122200120200112220112202001122101201201201212001212020120121202010201 （这是题目的正确输入）
serial只能包含'0''1''2'三种字符。先转成4*39矩阵：

1
2
3
4
000000000000011111111111112222222222222
000011111111100001122222220000011222222
011100011122200120200112220112202001122
101201201201212001212020120121202010201

每一行的1和2的个数必须相等（第十步）（注意，这里对0的具体个数没有要求，第十步不要求0（或者1或2）的个数恰好占1/3）
按列重组：

1
2
3
4
5
6
7
8
9
0001
0010
0011
0012
...
2210
2212
2220
2221

把按列重组的每一行当做十进制数字，则这些数字要求严格单调递增、且不能等于0000、1111、2222（第二步、第四步、第六步）

仅此而已

可以看到，这些校验条件过于宽松，不足以缩小md5的爆破范围

后续作者给了两个提示：

1
2
1、列向量组里不存在相反值，如[1,-1,1,0]与[-1,1,-1,0]不能同时存在
2、每个行向量里的 0 的数量 占 1/3

说是提示并不合理，实际上是在修正题目的缺陷。这两个约束条件本就应该写进程序中，按理应当在开赛前的验题流程中被发现。

（所以，是验题人疏忽了，还是，根本就没有验过题？？？）

将程序中的约束和作者提示给出的约束综合在一起，可以直观的翻译为z3：

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
from z3 import *
 
def build_integer(a, b, c, d):
    return a*1000 + b*100 + c*10 + d
 
def check_inverse(x, y):
    conds = [Or(And(x[i]==0, y[i]==0), And(x[i]==1, y[i]==2), And(x[i]==2, y[i]==1)) for i in range(4)]
    return And(conds)
 
v = [Int(f"{i}") for i in range(156)]
s = Solver()
for bad in badvalues:
    s.add(Not(And([v[i] == bad[i] for i in range(156)])))
for n in v:
    s.add(Or(n == 0, n == 1, n == 2))
integers = [build_integer(v[i], v[39+i], v[39*2+i], v[39*3+i]) for i in range(39)]
s.add(integers[0] > 0)
s.add(integers[38] != 1111)
s.add(integers[38] < 2222)
for i in range(39-1):
    s.add(integers[i] < integers[i+1])
    s.add(integers[i] != 1111)
for i in range(39):
    for j in range(i+1, 39):
        s.add(Not(check_inverse([v[i], v[39+i], v[39*2+i], v[39*3+i]], [v[j], v[39+j], v[39*2+j], v[39*3+j]])))
 
for k in range(4):
    sum_minus_1 = Sum([If(v[39*k+i] == 2, 1, 0) for i in range(39)])
    sum_1 = Sum([If(v[39*k+i] == 1, 1, 0) for i in range(39)])
    sum_0 = Sum([If(v[39*k+i] == 0, 1, 0) for i in range(39)])
    s.add(sum_minus_1 == sum_1)
    s.add(sum_0 == 13)
 
s.check()    // sat

解出单个满足条件的答案非常轻松，但是，加上作者提示补充的约束条件后仍然过于宽松，满足所有条件的答案数量仍然非常多。由于要爆破哈希，必须要求出所有的答案。
z3可以通过把先前求出的答案作为反向约束加入求解器中找到新的解，但是题目的答案太多，性能显然不足。

合理的解法似乎只能是正向遍历生成所有的解。如果直接按照原始的约束，写遍历并不容易。

实际上，做一个抽象，题目的约束可以转换如下：一个立方体，抽离一些方块后，剩下各个截面的方块数量相同。

这里的立方体可以是任意维度，相应的截面是低一维的维度。

举一些例子：
先从二维开始，“立方体”是3*3的平面，截面是3*1的三条横线和1*3的三条竖线。

1
2
3
4
5
   -1 0 1
    - - -
 1| o o o
 0| o o o
-1| o o o

这9个方块的坐标分别为：（这里用2代替-1）

1
2
3
4
5
6
7
8
9
0, 0
0, 1
0, 2
1, 0
1, 1
1, 2
2, 0
2, 1
2, 2

转置一下：

1
2
000111222
012012012

这个转置矩阵有两行，每行的0、1、2的个数恰好占1/3，并且如果把每列的两个数组合成十进制，9个列恰好是单调递增的。

我们现在从9个方块中抽走6个，剩余3个，并且要求3*3方格中，每行每列剩下的方块个数都相等。一种抽离方法如下：（o是保留的方块，x是抽离的方块。对角线的坐标为00，11，22，所以首先被抽离掉）

1
2
3
4
5
   -1 0 1
    - - -
 1| x o x
 0| o x x
-1| x x o

剩下的三个节点的坐标，转置后是：（仍然用2代替-1）

1
2
012
120

注意到，每行的0、1、2的个数仍然恰好占1/3，且任何关于中心方块00对称的一对方块，最后只留下了一个（例如01和02，12和21，20和10，都只留下了前者）

二维的例子已经与题目serial的格式有一些相似了，但仍然不太明确

下面将示例扩展到三维，对应关系会变得非常清晰
三维立方体共有27个方块，每个面有9个，这27个方块的坐标如下：（用2代替-1，转置）

1
2
3
000000000111111111222222222
000111222000111222000111222
012012012012012012012012012

第一行为0、1、2的列分别代表从垂直x轴方向切分得到的三个平面的方块
第二行为0、1、2的列分别代表从垂直y轴方向切分得到的三个平面的方块
第三行为0、1、2的列分别代表从垂直z轴方向切分得到的三个平面的方块

排除主对角线上的三个方块（000、111、222），还有24个方块。我们抽离一半，那么只剩下12个方块，平均到每个面上是4个。剩余12个方块坐标如下：（其中前4列、中间4列、后4列分别表示一个平面）

1
2
3
000011112222
????????????
????????????

?表示待定，但是我们要保证无论沿着与哪个坐标轴垂直的方向切分，得到的平面都要恰好只剩4个方块，所以第二行的0、1、2的个数必须相等，第三行同理。

题目需要求解四维的情况。

四维立方体共81个方块，每个面(四维立方体的面是三维立方体)有27个方块。
排除主对角线方块3个（坐标0000、1111、2222），剩余78个方块抽离一半，剩余39个，平均到每个面上是13个。
剩余的39个方块，每个方块的坐标要用4个维度表示，恰好是main函数第七步存入0x140001EF1的矩阵。
矩阵的每一行要求0、1、-1 (2) 的个数都是1/3，即13个，恰好等于平均到每个面上的方块数量。
排除主对角线（第二步、第四步、第六步的约束）后，剩余的78方块恰好是两两关于中心点0000对称的。抽离的数量是一半，而作者提示的补充约束1指明相反的值不能同时存在，结合二者，实际上抽离时不能随意选择一半的方块，而是要求从每对关于中心点对称的方块中抽走一个留下另一个。

定义81个变量表示81个方块，取值0表示被抽离走，取值1表示最终留存，则所有的约束可以精确的等价为方程：

  • 方块只有抽离和留存两种状态 -> 每个变量的取值只有0和1两种可能
  • 0000、1111、2222不存在 -> 主对角线一定被抽离 -> 代表主对角线的三个变量取值等于0
  • 列向量组里不存在相反值 + 抽离数量是一半 -> 坐标关于0000中心点对称的一对两个方块保留一个 -> 坐标关于中心点对称的两个方块所代表的变量之和为1
  • 每个行向量里的0的数量占1/3且1和-1(2)的数量相等(即13个) -> 抽离后立方体每个面的剩余方块数量都是13 -> 某一维度坐标分量相同的所有方块所代表的变量之和为13

最终，我们有81个变量以及一个线性方程组，只需要在满足方程组约束的前提下找到所有变量的所有可能取值，即可反推出所有可能的serial。

这里使用了sympy对线性方程组做符号化简：

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
from pprint import pprint
from sympy import Symbol, symbols, solve
 
 
def i2abcd(i):
    a, b, c, d = (i // 27) % 3, (i // 9) % 3, (i // 3) % 3, i % 3
    return a, b, c, d
 
 
def abcd2i(a, b, c, d):
    return a*27 + b*9 + c*3 + d
 
 
def i2n(i):
    a, b, c, d = i2abcd(i)
    return a*1000 + b*100 + c*10 + d
 
 
def n2i(n):
    a, b, c, d = (n // 1000) % 10, (n // 100) % 10, (n // 10) % 10, n % 10
    return abcd2i(a, b, c, d)
 
 
def opposite(i):
    a, b, c, d = i2abcd(i)
    a, b, c, d = (3-a) % 3, (3-b) % 3, (3-c) % 3, (3-d) % 3
    return abcd2i(a, b, c, d)
 
 
def build_all_opposite_pairs():
    pairs = []
    known = set()
    for i in range(81):
        if i in known:
            continue
        if i2n(i) in [0, 1111, 2222]:
            continue
        ii = opposite(i)
        assert ii not in known
        known.add(i)
        known.add(ii)
        pairs.append((i, ii))
    return pairs
 
 
def build_row_parts(row):
    parts = ([], [], [])
    for i in range(81):
        abcd = i2abcd(i)
        parts[abcd[row]].append(i)
    return parts
 
row0_parts = build_row_parts(0)
row1_parts = build_row_parts(1)
row2_parts = build_row_parts(2)
row3_parts = build_row_parts(3)
 
all_opposite_pairs = build_all_opposite_pairs()
 
 
x = list(symbols('x:81'))
 
 
equations = []
 
for i in range(81):
    if i2n(i) in [0, 1111, 2222]:
        equations.append(x[i])
 
for a, b in all_opposite_pairs:
    equations.append(x[a]+x[b]-1)
 
for i in range(3):
    equations.append(sum(x[c] for c in row0_parts[i])-13)
for i in range(3):
    equations.append(sum(x[c] for c in row1_parts[i])-13)
for i in range(3):
    equations.append(sum(x[c] for c in row2_parts[i])-13)
for i in range(3):
    equations.append(sum(x[c] for c in row3_parts[i])-13)
 
# print(equations)
 
r = solve(equations)
for k, v in r.items():
    print(k, "=", v)

得到的输出如下：

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
x0 = 0
x1 = 2*x20 - x22 + x23 + 2*x24 + x25 + 3*x26 - x55 + x56 - x57 - 2*x58 + x6 + x60 + 2*x62 - x63 - 2*x64 - 2*x66 - 3*x67 - x68 - x70 + x71 + x72 + 2*x74 - x76 + x77 + 2*x78 + x79 + 2*x8 - x9 - 3
x10 = 1 - x20
x11 = x20 + 2*x24 + 2*x25 + 2*x26 - x57 - x58 - x59 + x6 + x60 + x61 + x62 - x63 - x64 - x65 - 2*x66 - 2*x67 - 2*x68 + x7 + x72 + x73 + x74 + 2*x78 + 2*x79 + x8 - x9 - 3
x12 = 1 - x24
x13 = 1 - x26
x14 = 1 - x25
x15 = x22 + x23 - x24 - x25 - x26 + x57 + x58 + x59 - x6 - x60 - x61 - x62 + x66 + x67 + x68 - x69 - x7 - x70 - x71 + x75 + x76 + x77 - x78 - x79 - x8 + 2
x16 = 1 - x23
x17 = 1 - x22
x18 = 1 - x9
x19 = -x20 - 2*x24 - 2*x25 - 2*x26 + x57 + x58 + x59 - x6 - x60 - x61 - x62 + x63 + x64 + x65 + 2*x66 + 2*x67 + 2*x68 - x7 - x72 - x73 - x74 - 2*x78 - 2*x79 - x8 + x9 + 4
x2 = -2*x20 + x22 - x23 - 2*x24 - x25 - 3*x26 + x55 - x56 + x57 + 2*x58 - x6 - x60 - 2*x62 + x63 + 2*x64 + 2*x66 + 3*x67 + x68 + x70 - x71 - x72 - 2*x74 + x76 - x77 - 2*x78 - x79 - 2*x8 + x9 + 4
x21 = -x22 - x23 + x24 + x25 + x26 - x57 - x58 - x59 + x6 + x60 + x61 + x62 - x66 - x67 - x68 + x69 + x7 + x70 + x71 - x75 - x76 - x77 + x78 + x79 + x8 - 1
x27 = x55 + x56 + x57 + x58 + x59 + x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 + x68 + x69 + x70 + x71 + x72 + x73 + x74 + x75 + x76 + x77 + x78 + x79 - 12
x28 = 1 - x56
x29 = 1 - x55
x3 = 1 - x6
x30 = 1 - x60
x31 = 1 - x62
x32 = 1 - x61
x33 = 1 - x57
x34 = 1 - x59
x35 = 1 - x58
x36 = 1 - x72
x37 = 1 - x74
x38 = 1 - x73
x39 = 1 - x78
x4 = 1 - x8
x40 = 0
x41 = 1 - x79
x42 = 1 - x75
x43 = 1 - x77
x44 = 1 - x76
x45 = 1 - x63
x46 = 1 - x65
x47 = 1 - x64
x48 = 1 - x69
x49 = 1 - x71
x5 = 1 - x7
x50 = 1 - x70
x51 = 1 - x66
x52 = 1 - x68
x53 = 1 - x67
x54 = -x55 - x56 - x57 - x58 - x59 - x60 - x61 - x62 - x63 - x64 - x65 - x66 - x67 - x68 - x69 - x70 - x71 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x79 + 13
x80 = 0

总共81个变量，有46个方程，也就是只有81-46=35个变量是自由的，只要这35个变量的值是确定的，即可计算出全部81个变量的值。

从上面46个方程的右边找到这35个自由变量，分别是：x6, x7, x8, x9, x20, x22, x23, x24, x25, x26, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79

2**35的量级，用C/C++语言完全能够在分钟量级遍历完成。
当35个自由变量确定值后，可以解出全部81个变量，而唯一这46个方程没能体现的约束则是每个变量只取0和1两个值。观察上面的46个方程，只需要对x1、x11、x15、x19、x2、x21、x27、x54做额外检验即可。再进一步，注意到x1+x2==1、x11+x19==1、x15+x21==1、x27+x54==1恒成立，实际上只需要额外检验四个变量。

（在64位Linux下运行，保证long是8个字节）

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
#include <stdio.h>
 
#define BIT(n, i)  (((n) >> (i)) & 1)
#define is_zero_or_one(x)  (((x) == 0) || ((x) == 1))
 
int main(void) {
        long i;
        for (i = 0; i < (1L<<35); i++) {
                long x6 = BIT(i, 0);
                long x7 = BIT(i, 1);
                long x8 = BIT(i, 2);
                long x9 = BIT(i, 3);
                long x20 = BIT(i, 4);
                long x22 = BIT(i, 5);
                long x23 = BIT(i, 6);
                long x24 = BIT(i, 7);
                long x25 = BIT(i, 8);
                long x26 = BIT(i, 9);
                long x55 = BIT(i, 10);
                long x56 = BIT(i, 11);
                long x57 = BIT(i, 12);
                long x58 = BIT(i, 13);
                long x59 = BIT(i, 14);
                long x60 = BIT(i, 15);
                long x61 = BIT(i, 16);
                long x62 = BIT(i, 17);
                long x63 = BIT(i, 18);
                long x64 = BIT(i, 19);
                long x65 = BIT(i, 20);
                long x66 = BIT(i, 21);
                long x67 = BIT(i, 22);
                long x68 = BIT(i, 23);
                long x69 = BIT(i, 24);
                long x70 = BIT(i, 25);
                long x71 = BIT(i, 26);
                long x72 = BIT(i, 27);
                long x73 = BIT(i, 28);
                long x74 = BIT(i, 29);
                long x75 = BIT(i, 30);
                long x76 = BIT(i, 31);
                long x77 = BIT(i, 32);
                long x78 = BIT(i, 33);
                long x79 = BIT(i, 34);
 
                long x1 = 2*x20 - x22 + x23 + 2*x24 + x25 + 3*x26 - x55 + x56 - x57 - 2*x58 + x6 + x60 + 2*x62 - x63 - 2*x64 - 2*x66 - 3*x67 - x68 - x70 + x71 + x72 + 2*x74 - x76 + x77 + 2*x78 + x79 + 2*x8 - x9 - 3;
                long x11 = x20 + 2*x24 + 2*x25 + 2*x26 - x57 - x58 - x59 + x6 + x60 + x61 + x62 - x63 - x64 - x65 - 2*x66 - 2*x67 - 2*x68 + x7 + x72 + x73 + x74 + 2*x78 + 2*x79 + x8 - x9 - 3;
                long x15 = x22 + x23 - x24 - x25 - x26 + x57 + x58 + x59 - x6 - x60 - x61 - x62 + x66 + x67 + x68 - x69 - x7 - x70 - x71 + x75 + x76 + x77 - x78 - x79 - x8 + 2;
                long x27 = x55 + x56 + x57 + x58 + x59 + x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 + x68 + x69 + x70 + x71 + x72 + x73 + x74 + x75 + x76 + x77 + x78 + x79 - 12;
 
                if (is_zero_or_one(x1) && is_zero_or_one(x11) && is_zero_or_one(x15) && is_zero_or_one(x27)) {
                        // printf("hit %ld %ld\n", i, 1L<<35);
                        fprintf(stderr, "%ld\n", i);
                }
 
                if ((i & 0xffffffff) == 0) {
                        printf("checkpoint %ld %ld\n", i, 1L<<35);
                }
        }
        return 0;
}

gcc -O3编译，单线程大约19min跑完，stderr的输出（stderr.txt，3.22GB！）即为合法的35个自由变量的取值，共计 294511600 个！（2.9亿，这也是实际满足题目所有约束(除了哈希)的所有解的个数）

最后一步，将这294511600个结果反推为serial，逐一计算md5，检查是否满足预设值。

（下面的python脚本要用pypy3跑，单线程大约十几到二十几分钟（当然，可以拆分输入开多进程加速）。普通的cpython不行，速度太慢）

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
import sys
import hashlib
 
def i2abcd(i):
    a, b, c, d = (i // 27) % 3, (i // 9) % 3, (i // 3) % 3, i % 3
    return a, b, c, d
 
 
def BIT(n, i):
    return (n>>i) & 1
 
 
def build_input(n):
    x6 = BIT(n, 0)
    x7 = BIT(n, 1)
    x8 = BIT(n, 2)
    x9 = BIT(n, 3)
    x20 = BIT(n, 4)
    x22 = BIT(n, 5)
    x23 = BIT(n, 6)
    x24 = BIT(n, 7)
    x25 = BIT(n, 8)
    x26 = BIT(n, 9)
    x55 = BIT(n, 10)
    x56 = BIT(n, 11)
    x57 = BIT(n, 12)
    x58 = BIT(n, 13)
    x59 = BIT(n, 14)
    x60 = BIT(n, 15)
    x61 = BIT(n, 16)
    x62 = BIT(n, 17)
    x63 = BIT(n, 18)
    x64 = BIT(n, 19)
    x65 = BIT(n, 20)
    x66 = BIT(n, 21)
    x67 = BIT(n, 22)
    x68 = BIT(n, 23)
    x69 = BIT(n, 24)
    x70 = BIT(n, 25)
    x71 = BIT(n, 26)
    x72 = BIT(n, 27)
    x73 = BIT(n, 28)
    x74 = BIT(n, 29)
    x75 = BIT(n, 30)
    x76 = BIT(n, 31)
    x77 = BIT(n, 32)
    x78 = BIT(n, 33)
    x79 = BIT(n, 34)
 
    x0 = 0
    x1 = 2*x20 - x22 + x23 + 2*x24 + x25 + 3*x26 - x55 + x56 - x57 - 2*x58 + x6 + x60 + 2*x62 - x63 - 2*x64 - 2*x66 - 3*x67 - x68 - x70 + x71 + x72 + 2*x74 - x76 + x77 + 2*x78 + x79 + 2*x8 - x9 - 3
    x10 = 1 - x20
    x11 = x20 + 2*x24 + 2*x25 + 2*x26 - x57 - x58 - x59 + x6 + x60 + x61 + x62 - x63 - x64 - x65 - 2*x66 - 2*x67 - 2*x68 + x7 + x72 + x73 + x74 + 2*x78 + 2*x79 + x8 - x9 - 3
    x12 = 1 - x24
    x13 = 1 - x26
    x14 = 1 - x25
    x15 = x22 + x23 - x24 - x25 - x26 + x57 + x58 + x59 - x6 - x60 - x61 - x62 + x66 + x67 + x68 - x69 - x7 - x70 - x71 + x75 + x76 + x77 - x78 - x79 - x8 + 2
    x16 = 1 - x23
    x17 = 1 - x22
    x18 = 1 - x9
    x19 = -x20 - 2*x24 - 2*x25 - 2*x26 + x57 + x58 + x59 - x6 - x60 - x61 - x62 + x63 + x64 + x65 + 2*x66 + 2*x67 + 2*x68 - x7 - x72 - x73 - x74 - 2*x78 - 2*x79 - x8 + x9 + 4
    x2 = -2*x20 + x22 - x23 - 2*x24 - x25 - 3*x26 + x55 - x56 + x57 + 2*x58 - x6 - x60 - 2*x62 + x63 + 2*x64 + 2*x66 + 3*x67 + x68 + x70 - x71 - x72 - 2*x74 + x76 - x77 - 2*x78 - x79 - 2*x8 + x9 + 4
    x21 = -x22 - x23 + x24 + x25 + x26 - x57 - x58 - x59 + x6 + x60 + x61 + x62 - x66 - x67 - x68 + x69 + x7 + x70 + x71 - x75 - x76 - x77 + x78 + x79 + x8 - 1
    x27 = x55 + x56 + x57 + x58 + x59 + x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 + x68 + x69 + x70 + x71 + x72 + x73 + x74 + x75 + x76 + x77 + x78 + x79 - 12
    x28 = 1 - x56
    x29 = 1 - x55
    x3 = 1 - x6
    x30 = 1 - x60
    x31 = 1 - x62
    x32 = 1 - x61
    x33 = 1 - x57
    x34 = 1 - x59
    x35 = 1 - x58
    x36 = 1 - x72
    x37 = 1 - x74
    x38 = 1 - x73
    x39 = 1 - x78
    x4 = 1 - x8
    x40 = 0
    x41 = 1 - x79
    x42 = 1 - x75
    x43 = 1 - x77
    x44 = 1 - x76
    x45 = 1 - x63
    x46 = 1 - x65
    x47 = 1 - x64
    x48 = 1 - x69
    x49 = 1 - x71
    x5 = 1 - x7
    x50 = 1 - x70
    x51 = 1 - x66
    x52 = 1 - x68
    x53 = 1 - x67
    x54 = -x55 - x56 - x57 - x58 - x59 - x60 - x61 - x62 - x63 - x64 - x65 - x66 - x67 - x68 - x69 - x70 - x71 - x72 - x73 - x74 - x75 - x76 - x77 - x78 - x79 + 13
    x80 = 0
 
    x = [x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80]
 
    ans = bytearray(156)
    j = 0
    for i in range(81):
        if x[i]:
            a, b, c, d = i2abcd(i)
            ans[j] = 48+a
            ans[39+j] = 48+b
            ans[39*2+j] = 48+c
            ans[39*3+j] = 48+d
            j += 1
    return ans
             
 
f = open("stderr.txt", "r")
 
# 294511600 lines
 
for i, line in enumerate(f):
    n = int(line)
    sss = build_input(n)
    md5value = hashlib.md5(sss).hexdigest()
    if md5value == "aac82b7ad77ab00dcef90ac079c9490d":
        print("success!", i, n, sss)
        print(sss.decode())
        break
    if i % 1000000 == 0:
        print("checkpoint", i, n, sss)
 
f.close()

最后，在 i = 281453140、n = 31608758280 的时候爆破成功，正确的serial为：

1
000000000000011111111111112222222222222000011111111100001122222220000011222222011100011122200120200112220112202001122101201201201212001212020120121202010201

按照题目程序的校验却无法反推出唯一的serial，只能作为约束减少爆破的范围，使得题目最后变成了哈希爆破的游戏，不得不说是一个巨大的遗憾，完全失去了题目算法原本的优雅。

（虽然爆破时间可以控制在30分钟内不违反规则，但显然规则也明确不鼓励爆破。而且，作为逆向题，如果多解需要依靠哈希校验才能控制住，是不是说明本身程序的逻辑是不完备的呢？）


[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。

收藏
点赞・6
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回