首页
论坛
课程
招聘
[原创]KCTF2022春季赛第二题分析(4qwerty7)
2022-5-12 03:27 6144

[原创]KCTF2022春季赛第二题分析(4qwerty7)

2022-5-12 03:27
6144

分析代码可知,首先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)
 
"""
output:
1
12
123
321
123654
321654
38165472
381654729
"""

根据前文,这里很可能选取 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。


看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回