BkP-CTF 2013 MITM
前两天BkP的CTF练习赛中的一道题,crypto 200,题目如下
message 1: QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=
encrypted: THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=
message 2: RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=
encrypted: 01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=
ciphertext: s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=
看到最后的等号首先就想到了base64编码,decode之后得到
message1: AES-256 ECB mode twice, two keys
message2: Each key zero until last 24 bits
两轮AES-256加密,padding=ECB,key不一样,但是前面都是0x00,只有最后24位需要破解
密文都是2进制不可读,不贴了
题目提示了是256位(32字节的key),前29个字节都是0,需要破解两个key的后3个字节,纯暴力方式需要尝试224 * 224 = 248 ≈ 2.81e14种可能,这么大的计算量,显然是不现实的。
暴力破解,估计要用到hadoop集群了。
其实,当时忽略了一个细节,就是题目:MITM,google一下出来的都是Man-in-the-middle Attack(中间人攻击),似乎跟这个题目半毛钱关系都没有,换用wikipedia得到了我们想要的东西:
- Man-in-the-middle attack, a computer networking attack method
- Meet-in-the-middle attack, a cryptographic attack method
很显然,Meet-in-the-middle attack应该就是我们想找的东西了
Assume the attacker knows a set of plaintext P and ciphertext C that satisfies the following:
- C=ENCk2(ENCk1(P))
- P=DECk1(DECk2©
where ENC is the encryption function, DEC the decryption function defined as ENC-1 (inverse mapping) and k1 and k2 are two keys.
The attacker can then compute ENCk1(P) for all possible keys k1. Afterwards he can decrypt the ciphertext by computing DECk2© for each k2. Any matches between these two resulting sets are likely to reveal the correct keys. (To speed up the comparison, the ENCk1(P) set can be stored in an in-memory lookup table, then each DECk2© can be matched against the values in the lookup table to find the candidate keys)
这个模型跟题目所设的是完全一样的,思路给的很清楚了,先穷举key1,计算出明文经过所有可能的key1加密后的结果,将结果存于内存中,然后穷举key2,计算密文经过key2解密后的结果,与内存中的结果集进行比对(因为AES是对称加密,加密跟解密是用的相同的key),如果有一致的,就表明破解成功了,这样算起来,时间复杂度只有224 + 224 = 225
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 |
|
大概5分钟左右就跑完了,缓存key1的加密结果用了1.65G内存,如果内存不够,可以对key1分段跑,不过时间就要相应变长。
key1:
\x9a\xe8\x07
key2:
\xff?E
message is:
This time I didn’t include sol’n