从一道 CTF 题了解密码学中的 Meet-in-the-middle 攻击
本文首发于先知
在家里无聊打了 nullcon, 其中有一题用到了 Meet-in-the-middle 这种攻击方式,
在这里分享给大家.
题目
124 bit key space is brute forceable so how about 48 bit key space? flag is hackim19{decrypted flag}
2
316 bit plaintext: b'0467a52afa8f15cfb8f0ea40365a6692' flag: b'04b34e5af4a1f5260f6043b8b9abb4f8'
1from hashlib import md5
2from binascii import hexlify, unhexlify
3from secret import key, flag
4BLOCK_LENGTH = 16
5KEY_LENGTH = 3
6ROUND_COUNT = 16
7
8sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54,
9 217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107,
10 91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221,
11 63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81,
12 201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15,
13 151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119,
14 123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99,
15 82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129,
16 131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48,
17 97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125,
18 106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200,
19 70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153,
20 174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65,
21 176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83,
22 223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246,
23 169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117,
24 100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231,
25 0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222,
26 20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215,
27 50, 148, 159, 93, 80, 45, 17, 205, 95]
28p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14]
29
30
31def xor(a, b):
32 return bytearray(map(lambda s: s[0] ^ s[1], zip(a, b)))
33
34
35def fun(key, pt):
36 assert len(pt) == BLOCK_LENGTH
37 assert len(key) == KEY_LENGTH
38 key = bytearray(unhexlify(md5(key).hexdigest()))
39 ct = bytearray(pt)
40 for _ in range(ROUND_COUNT):
41 ct = xor(ct, key)
42 for i in range(BLOCK_LENGTH):
43 ct[i] = sbox[ct[i]]
44 nct = bytearray(BLOCK_LENGTH)
45 for i in range(BLOCK_LENGTH):
46 nct[i] = ct[p[i]]
47 ct = nct
48 return hexlify(ct)
49
50
51def toofun(key, pt):
52 assert len(key) == 2 * KEY_LENGTH
53 key1 = key[:KEY_LENGTH]
54 key2 = key[KEY_LENGTH:]
55
56 ct1 = unhexlify(fun(key1, pt))
57 ct2 = fun(key2, ct1)
58
59 return ct2
60
61print("16 bit plaintext: %s" % toofun(key, b"16 bit plaintext"))
62print("flag: %s" % toofun(key, flag))
解题思路
我们的目标就是通过给出的明文 16 bit plaintext 和对应的密文 0467a52afa8f15cfb8f0ea40365a6692
算出 key, 从而解密 flag 密文 04b34e5af4a1f5260f6043b8b9abb4f8
根据加密代码和题目描述, 很显然方法只有爆破一种, 但是爆破 6 位 key 的 2**48(281,474,976,710,656) 种可能是不现实的.
但正如题目中所说, 爆破 2**24(16,777,216) 还是非常简单的.
现在我们的问题变成如何简化这个爆破过程, 这里就要用到一开始说的 Meet-in-the-middle 攻击,
加密主要是这两个函数,
1def fun(key, pt):
2 assert len(pt) == BLOCK_LENGTH
3 assert len(key) == KEY_LENGTH
4 key = bytearray(unhexlify(md5(key).hexdigest()))
5 ct = bytearray(pt)
6 for _ in range(ROUND_COUNT):
7 ct = xor(ct, key)
8 for i in range(BLOCK_LENGTH):
9 ct[i] = sbox[ct[i]]
10 nct = bytearray(BLOCK_LENGTH)
11 for i in range(BLOCK_LENGTH):
12 nct[i] = ct[p[i]]
13 ct = nct
14 return hexlify(ct)
15
16
17def toofun(key, pt):
18 assert len(key) == 2 * KEY_LENGTH
19 key1 = key[:KEY_LENGTH]
20 key2 = key[KEY_LENGTH:]
21
22 ct1 = unhexlify(fun(key1, pt))
23 ct2 = fun(key2, ct1)
24
25 return ct2
发现其实真正的加密函数是 fun, 在 toofun 中调用了两次
而且这里并没有将 6 位长的 key 一次性使用, 而是将其从中间分开, 先用前 3 位加密一次, 再用后 3 位加密一次.
也就是说实际的加密过程是用两个 3 位的 key 连续加密二次.
这就让我们的攻击有了可能性.
虽然也是爆破, 但是与一开始的最先能想到的爆破 6 位 key 不同的是
我们先遍历所有 3 位长的 key, 算出 16 bit plaintext 对应的所有第一次加密结果, 将其保存起来,
然后再遍历一次 key, 将密文解密, 如果能在第一次加密的结果中找到, 那么对应的两个 3 位 key 拼起来就是一开始的 6 位 key.
然后用这个 key 就可以解密出 flag 了~
现在能感觉到这个攻击的名字取的还是非常切题的, 一边加密, 一边解密, 在中间碰头得到秘钥.
与一开始的解法相比, 我们成功的将 2**48 降到 2*2**24, 不过对应的是需要一个哈希表来保存所有第一次加密的结果,
相当于用空间换时间了, 好在现在内存都比较大, 应付起来很轻松.
题解
因为 python 不太适合这种大量数据的爆破, 所以就用 C++ 写了, 写的比较烂请见谅
1#include "md5.cpp"
2#include <iostream>
3#include <unordered_map>
4#include <string>
5
6const int BLOCK_LENGTH = 16;
7const int ROUND_COUNT = 16;
8typedef unsigned char uchar;
9
10uchar sbox[] = {210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54,
11 217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107,
12 91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221,
13 63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81,
14 201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15,
15 151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119,
16 123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99,
17 82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129,
18 131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48,
19 97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125,
20 106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200,
21 70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153,
22 174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65,
23 176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83,
24 223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246,
25 169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117,
26 100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231,
27 0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222,
28 20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215,
29 50, 148, 159, 93, 80, 45, 17, 205, 95
30 };
31
32int p[] = {3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14};
33
34uchar dbox[] = {221, 62, 140, 111, 5, 213, 225, 242, 157, 167, 40, 80, 121,
35 83, 93, 64, 219, 253, 123, 147, 234, 212, 49, 115, 131, 35,
36 160, 191, 42, 204, 175, 21, 202, 96, 205, 238, 19, 32, 126,
37 164, 193, 36, 41, 46, 76, 252, 31, 69, 116, 23, 247, 201, 84,
38 70, 12, 184, 44, 154, 185, 30, 165, 171, 172, 39, 236, 168,
39 57, 79, 24, 228, 143, 107, 100, 196, 63, 109, 211, 206, 95,
40 170, 251, 51, 91, 181, 136, 99, 239, 230, 87, 227, 128, 26,
41 50, 250, 6, 255, 106, 117, 108, 90, 208, 124, 166, 192, 43,
42 141, 130, 25, 97, 114, 173, 174, 150, 138, 68, 2, 240, 207,
43 232, 77, 112, 243, 4, 78, 33, 129, 125, 110, 58, 103, 237,
44 104, 18, 188, 28, 244, 229, 144, 217, 122, 178, 163, 151,
45 86, 183, 190, 158, 61, 248, 214, 161, 65, 145, 155, 149, 45,
46 14, 186, 92, 249, 198, 48, 59, 22, 7, 146, 148, 153, 179, 195,
47 72, 137, 60, 187, 156, 81, 169, 17, 3, 197, 152, 210, 216, 54,
48 37, 34, 134, 119, 89, 245, 135, 189, 101, 241, 159, 226,
49 180, 177, 98, 8, 142, 52, 15, 71, 215, 254, 162, 133, 56,
50 231, 0, 218, 16, 1, 55, 246, 127, 13, 176, 88, 105, 38, 233,
51 182, 203, 200, 74, 66, 73, 53, 9, 220, 139, 209, 118, 132,
52 102, 10, 222, 75, 82, 94, 29, 113, 120, 20, 194, 67, 11,
53 235, 47, 27, 224, 199, 223, 85
54 };
55
56int q[] = {2, 3, 7, 0, 12, 8, 9, 5, 4, 1, 11, 14, 13, 10, 15, 6};
57
58inline void mxor(uchar* a, uchar* b, uchar* tmp) {
59 for(int i = 0; i < BLOCK_LENGTH; i++) {
60 tmp[i] = a[i] ^ b[i];
61 }
62}
63
64inline void copy(uchar* from, uchar* to) {
65 for(int i = 0; i < BLOCK_LENGTH; i++) {
66 to[i] = from[i];
67 }
68}
69
70void fun(uchar* key, uchar* ct, uchar* tmp) {
71 for(int i = 0; i < ROUND_COUNT; i++) {
72 mxor(ct, key, tmp);
73 copy(tmp, ct);
74 for(int i = 0; i < BLOCK_LENGTH; i++) {
75 ct[i] = sbox[ct[i]];
76 }
77 uchar nct[BLOCK_LENGTH];
78 for(int i = 0; i < BLOCK_LENGTH; i++) {
79 nct[i] = ct[p[i]];
80 }
81 copy(nct, ct);
82 }
83}
84
85void dec(uchar* key, uchar* ct, uchar* tmp) {
86 for(int i = 0; i < ROUND_COUNT; i++) {
87 uchar nct[BLOCK_LENGTH];
88 for(int i = 0; i < BLOCK_LENGTH; i++) {
89 nct[i] = ct[q[i]];
90 }
91 copy(nct, ct);
92
93 for(int i = 0; i < BLOCK_LENGTH; i++) {
94 ct[i] = dbox[ct[i]];
95 }
96 mxor(ct, key, tmp);
97 copy(tmp, ct);
98 }
99}
100
101int main() {
102 std::unordered_map<std::string, std::string> map;
103 uchar* md5key = new uchar[BLOCK_LENGTH];
104 uchar tmp[BLOCK_LENGTH];
105 uchar hexkey[] = {0, 0, 0};
106
107 for(int i = 0; i < 256; i++) { // 爆破明文所有 key 加密的结果
108 for(int j = 0; j < 256; j++) {
109 for(int k = 0; k < 256; k++) {
110 uchar pt[] = "16 bit plaintext";
111 copy(MD5((char*)hexkey, 3).digest, md5key);
112 fun(md5key, pt, tmp);
113
114 std::string s1((char*)pt, 16);
115 std::string s2((char*)hexkey, 3);
116
117 map[s1] = s2;
118 hexkey[2] += 1;
119 }
120 hexkey[1] += 1;
121 }
122 std::cout << i << std::endl;
123 hexkey[0] += 1;
124 }
125
126 for(int i = 0; i < 256; i++) { // 爆破密文所有 key 解密的结果, 如果在 map 中找到一样的, 用这两个 key 拿来解密 flag
127 for(int j = 0; j < 256; j++) {
128 for(int k = 0; k < 256; k++) {
129 uchar pt[] = "\x04g\xa5*\xfa\x8f\x15\xcf\xb8\xf0\xea@6Zf\x92"; // "0467a52afa8f15cfb8f0ea40365a6692".decode('hex')
130 copy(MD5((char*)hexkey, 3).digest, md5key);
131 dec(md5key, pt, tmp);
132
133 std::string s1((char*)pt);
134 auto ptr = map.find(s1);
135
136 if(ptr != map.end()) {
137 std::cout << "Key found" << std::endl;
138 uchar key[3];
139 uchar flag[] = "\x04\xb3NZ\xf4\xa1\xf5&\x0f`C\xb8\xb9\xab\xb4\xf8"; // "04b34e5af4a1f5260f6043b8b9abb4f8".decode('hex')
140 key[0] = (*ptr).second.c_str()[0];
141 key[1] = (*ptr).second.c_str()[1];
142 key[2] = (*ptr).second.c_str()[2];
143 copy(MD5((char*)hexkey, 3).digest, md5key);
144 dec(md5key, flag, tmp);
145 copy(MD5((char*)key, 3).digest, md5key);
146 dec(md5key, flag, tmp);
147 std::cout << std::string((char*)flag, 16) << std::endl;
148 return 0;
149 }
150 hexkey[2] += 1;
151 }
152 hexkey[1] += 1;
153 }
154 std::cout << i << std::endl;
155 hexkey[0] += 1;
156 }
157 return 0;
158}
其中 dbox 和 q 可以这样生成
1dbox = [0 for i in range(len(sbox))]
2q = [0 for i in range(len(p))]
3for i in range(len(sbox)):
4 dbox[sbox[i]] = i
5for i in range(len(p)):
6 q[p[i]] = i
大约需要 3g 内存和几分钟时间得到 flag
编译的时候别忘记带上 -O3
1Key found
21337_1n_m1ddl38f
总结
密码学博大精深, Meet-in-the-middle 只是其中一种攻击技术, 但其中的思路还是非常值得学习的,
有时候爆破不可避免, 我们能做的是如何让爆破最简化, 至少不那么暴力 233.
想要了解更多关于 Meet-in-the-middle 的知识可以去看对应的 WIKI