-
-
[原创]KCTF2022春季赛第二题分析(4qwerty7)
-
2022-5-12 03:27
9429
-
[原创]KCTF2022春季赛第二题分析(4qwerty7)
分析代码可知，首先flag被做了两个hash
首先是在 GF(2^8) 上的类 BKDR hash：
1 2 3 4 5 6 7 8 9 10 | v5 = 0
for i in flag:
v5 ^= i
for _ in range(8):
v9 = 2 * v5
if v9 > 127:
v9 ^= 128 + 7
v5 = v9
xv = v5
|
然后是 CRC32：
1 2 3 4 5 6 7 8 9 10 11 12 | import numpy as np
ht = []
for i in range(256):
v = np.int32(i)
for _ in range(8):
v = (v >> 1) ^ (np.int32(-0x12477CE0) if (v & 1) != 0 else 0)
ht.append(v)
hv = np.int32(-1)
for k in flag:
hv = ht[np.uint8(np.int8(k) ^ hv)] ^ (hv >> 8)
hv = ~hv
|
接下来 flag 的每一位通过下面的方法转为数字
1 2 3 4 | def dec(c):
if c >= 0x3a:
return c - 55
return c - 48
|
然后根据 xv 通过 3x+1猜想 的过程计算出 v17 的值：
1 2 3 4 5 6 7 8 9 | v33 = [0]
for i in range(1, 200):
if (xv & 1) != 0:
xv = 3 * xv + 1
else:
xv >>= 1
v33.append(xv)
v17 = v33[198] | v33[197] | v33[196]
|
容易验证对于非0 xv 输入的 v17 值均为 7.
然后要求 flag 的前 3 位的异或和为 v17，接下来4位是KCTF。
而长度为 v17+2 的第二部分被要求：
1 2 3 4 5 | p2_len = v17 + 2
u = sorted(ID[7:7+p2_len])
dst = b'1234567890_ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for i in range(p2_len):
assert dec(dst[i]) == u[i]
|
容易发现第二部分的值均为 1~9 的数字。
同时，还要求
1 2 3 4 5 6 7 8 | p2_len = v17 + 2
v37 = 0
for i in range(p2_len):
v23 = ID[7 + i] + 10 * v37
v23 &= 0xffffffff
v37 = v23 if v23 <= 0x4B435445 else v23 - 0x37373737
v37 &= 0xffffffff
assert v37 % (i + 1) == 0
|
由于 987654321 <= 0x4B435445，容易验证此条件无效，即要求数字前 i 位被 i 整除，可搜索出全部满足此要求的数字：
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 | def check(uu):
def dfs(cur, leng):
if leng != 0 and cur % leng != 0:
return
if leng == uu:
print(cur)
return
u = str(cur)[:leng]
for i in range(1, uu + 1):
if str(i) in u:
continue
dfs(cur * 10 + i, leng + 1)
dfs(0, 0)
for i in range(10):
check(i)
|
根据前文，这里很可能选取 381654729。
如果第二部分后还有多余内容，则要求经过加密操作后与两段文本的异或结果相等。
可以验证，如果加密，则此处是无解的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | d1 = bytes.fromhex('CED2B1B2B6C1CAE9C8CBD2BBC9FACBF9C7F3B2BBB9FDCBC4CAC23ACEAACCECB5D8C1A2D0C4A3ACCEAAC9FAC3F1C1A2C3FCA3ACCEAACDF9CAA5BCCCBEF8D1A7A3ACCEAACDF2CAC0BFAACCABC6BD2E00002083B8ED')
d2 = bytes.fromhex('CED22CBAABC1A22CD7F7CEAAD2BBC3FBB9E2C8D9B5C4B3CCD0F2D4B12CD4C2C1C1B2BBCBAFCED2B2BBCBAF2CCCABD1F4C3BBC6F0CED2BECDC6F02CD2B9D2D4BCCCC8D52CD6D5D3DAB0D1C8E2C9EDD0DEC1B6B8AFD0E0C1CB2E2E2EC8BBBAF32CB4A9D4BDC1CB2E2E2E')
xd = [x ^ y for x, y in zip(d1, d2)][:44-7-9]
from z3 import *
flag = [BitVec(f'x{i}', 8) for i in range(8)]
x = flag.copy()
for i in range(0, 8, 8):
st = flag[i]
for j in range(7):
v10 = (flag[i + j] << (7 - j)) | (flag[i + j + 1] >> (j + 1))
flag[i + j] = st ^ (2 * v10 + 1)
flag[i + 7] = st ^ (2 * flag[i + 7] + 1)
sol = Solver()
sol.add(x[0] == 0)
for i in range(8):
sol.add(flag[i] == xd[i])
print(sol.check())
|
如果不加密，则至多增补两个 0。
综上所述，开头3个字符尚未确定，爆破CRC32即可：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | import numpy as np
ht = []
for i in range(256):
v = np.int32(i)
for _ in range(8):
v = (v >> 1) ^ (np.int32(-0x12477CE0) if (v & 1) != 0 else 0)
ht.append(v)
def enc(c):
if c < 10:
return c + 48
return c + 55
for i in range(0, 40):
for j in range(0, 40):
flag = bytes([enc(i), enc(j), enc(7 ^ i ^ j)]) + b'KCTF381654729'
hv = np.int32(-1)
for k in flag:
hv = ht[np.uint8(np.int8(k) ^ hv)] ^ (hv >> 8)
hv = ~hv
if hv == 0xF52E0765 or hv == -181532827:
print('bingo', flag)
|
得到结果为 421KCTF381654729。
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
