ByteCTF 2021 Crypto

本文最后更新于：2022年3月15日 晚上

easyxor

shift函数是个常见的移位异或操作，convert是对一个数字使用不同的key和mask进行4次移位异或，这个函数在已知key的情况下是可逆的。

encrypt函数是对明文块进行两种模式（CBC和OFB）的块加密，块长度为8，对于每一块的加密使用的就是上面的convert函数。

首先通过密文的长度可以得知一共被分成了6块；前3块明文使用OFB模式，后三块明文使用CBC模式；keys是一个长度为4的列表，列表中每个值的范围是(-32, 32)，64464^4爆破也是可以接受的。

读完题目代码之后可以想到其实我们已经知道第一块明文了，就是flag的格式ByteCTF{，而OFB模式实际上是加密的key，最终结果和明文块异或，所以第一个明文块异或第一个密文块就可以知道第一个key加密的结果，也就是cur_c = convert(last, k)的cur_c，这样就可以得到第二块的last。

现在对于第二块，已知IV（last），未知keys，已知明文是可显示字符，所以可以爆破keys了，把能解出可显示字符明文的keys都保留出来，发现有4836个keys是满足的，那么我们还要借助第三块再筛一次，最终只得到一组keys。

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
from itertools import product
from tqdm import tqdm
from Crypto.Util.number import bytes_to_long, long_to_bytes
def check(s):
    return min([((i<129) and (i>31)) for i in s])

c = "89b8aca257ee2748f030e7f6599cbe0cbb5db25db6d3990d3b752eda9689e30fa2b03ee748e0da3c989da2bba657b912"
c_list = [int(c[i*16:i*16+16], 16) for i in range(len(c)//16)]
known_m = bytes_to_long(b'ByteCTF{')
range64 = list(range(-32, 33))
cur_c = known_m^c_list[0]
print(cur_c)
k_cnt = 0
for a,b,c,d in tqdm(product(range64, range64, range64, range64)):
    last = cur_c
    k = [a, b, c, d]
    try_cur_c = convert(last, k)
    m1 = long_to_bytes(try_cur_c ^ c_list[1])
    if check(m1): # 只筛选这第一轮的话，4836个k是满足条件的，所以得筛第二轮
        last = try_cur_c
        try_cur_c = convert(last, k)
        m2 = long_to_bytes(try_cur_c ^ c_list[2])
        if check(m2):
            k_cnt += 1
            try:
                print(m1.decode() + m2.decode(), k)
            except:
                print("error")
print(k_cnt)
# keys = [-12, 26, -3, -31]
# ByteCTF{5831a241s-f30980

现在已经得到了keys和前三块的明文，可以接着解后三块明文了。

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
from Crypto.Util.number import bytes_to_long, long_to_bytes

k = [-12, 26, -3, -31]
c = "89b8aca257ee2748f030e7f6599cbe0cbb5db25db6d3990d3b752eda9689e30fa2b03ee748e0da3c989da2bba657b912"
cl = [int(c[i*16:i*16+16], 16) for i in range(len(c)//16)]
cur_c = bytes_to_long(b'ByteCTF{') ^ cl[0]

def shift(m, k, c):
    if k < 0:
        return m ^ m >> (-k) & c
    return m ^ m << k & c

def convert(m, key):
    c_list = [0x37386180af9ae39e, 0xaf754e29895ee11a, 0x85e1a429a2b7030c, 0x964c5a89f6d3ae8c]
    for t in range(4):
        m = shift(m, key[t], c_list[t])
    return m

def unshift_right(value, key, mask=None, nbits=32):
    if not mask: mask = (1 << (nbits + 1)) - 1
    i = 0
    while i * key < nbits:
        part_mask = ((((1 << nbits)-1) << (nbits - key)) & ((1 << nbits)-1)) >> (i * key)
        part = value & part_mask
        value ^= (part >> key) & mask
        i += 1
    return value

def unshift_left(value, key, mask=None, nbits=32):
    if not mask: mask = (1 << (nbits + 1)) - 1
    i = 0
    while i * key < nbits:
        part_mask = ((((1 << nbits)-1) >> (nbits - key)) & ((1 << nbits)-1)) << (i * key)
        part = value & part_mask
        value ^= (part << key) & mask
        i += 1
    return value

def my_unshift(m, k, c):
    if k < 0:
        tmp = unshift_right(m, -k, c, 64)
        return tmp
    tmp = unshift_left(m, k, c, 64)
    return tmp

def re_convert(m, key):
    c_list = [0x37386180af9ae39e, 0xaf754e29895ee11a, 0x85e1a429a2b7030c, 0x964c5a89f6d3ae8c]
    for t in range(3, -1, -1):
        m = my_unshift(m, key[t], c_list[t])
    return m

IV = re_convert(cur_c, k)
assert IV.bit_length() == 64

last = IV
cur = re_convert(cl[3], k)
m3 = long_to_bytes(cur ^ last)
print(m3)

last = cl[3]
cur = re_convert(cl[4], k)
m4 = long_to_bytes(cur ^ last)
print(m4)

last = cl[4]
cur = re_convert(cl[5], k)
m5 = long_to_bytes(cur ^ last)
print(m5)
print(m3 + m4 + m5)
# q535af-2156547475u2t}$$$

拼接起来得到完整flag: ByteCTF{5831a241s-f30980q535af-2156547475u2t}$$$

abusedkey

首先把用到的数据放在了task_data.py，方便些其他脚本时直接导入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
URL = "http://39.105.181.182:30000"
msg11 = URL+"/abusedkey/server/msg11"
msg13 = URL+"/abusedkey/server/msg13"
msg21 = URL+"/abusedkey/server/msg21"
msg23 = URL+"/abusedkey/ttp/msg23"
msg25 = URL+"/abusedkey/server/msg25"

# -------------------------------- Secp256k1 --------------------------------
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a, b = 0, 7
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
# ------------------ https://en.bitcoin.it/wiki/Secp256k1 -------------------

Pc = (0xb5b1b07d251b299844d968be56284ef32dffd0baa6a0353baf10c90298dfd117,
      0xea62978d102a76c3d6747e283091ac5f2b4c3ba5fc7a906fe023ee3bc61b50fe)

协议2的部分，想要拿到hint很简单，只要按照描述实现出来，就拿到了hint，hint.sage:

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
import requests, os, random
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from task_data import p, a, b, G, msg21, msg23, msg25
from hashlib import sha256

E = EllipticCurve(IntegerModRing(p), [a, b])
G = E(G)

# sid2 = hex(random.getrandbits(256))[2:]
sid2 = "8d1a95ce724141a0ea7c8ffa7eddc48605b3117c8aa886bcc2aff3b0c2175b56"
msg22 = requests.get(msg21, data=sid2).text
Qs_hex = msg22

rc = 1 # random.randint(1, p)
Rc = rc*G

Pic = long_to_bytes(int('FFFF', 16))
hc = int(sha256(Pic).hexdigest(), 16)
Qc = hc*Rc
Qc_hex = hex(Qc[0])[2:].rjust(64) + hex(Qc[1])[2:].rjust(64)
assert len(Qc_hex) == 128

msg24 = requests.get(msg23, data=Qc_hex+Qs_hex).text
assert len(msg24) == 256
Yc_hex, Ys_hex = msg24[:128], msg24[128:]

msg26 = requests.get(msg25, data=sid2+Yc_hex).text

Ys = E((int(Ys_hex[:64], 16), int(Ys_hex[64:], 16)))
Zcs = rc*Ys
Zcsx = long_to_bytes(int(Zcs[0]))
sk2 = sha256(Zcsx).digest()

msg26 = bytes.fromhex(msg26)
iv, ciphertext, mac = msg26[:12], msg26[12:-16], msg26[-16:]
cipher = AES.new(sk2, mode=AES.MODE_GCM, nonce=iv)
try:
    m = cipher.decrypt_and_verify(ciphertext, mac)
    print(m.decode())
except ValueError:
    print("MAC check failed")
# off-line guessing on protocol_II, and key compromise impersonation on protocol_I

Hint: off-line guessing on protocol_II, and key compromise impersonation on protocol_I

hint和题目描述都在说明，两个协议共用一个Server端的key，那么大概思路就是通过协议2拿到key，再将这个key用于解协议1的flag，可以先简单分析一下：

1
2
3
4
5
6
7
8
9
已知 rc-(随机), hc-H(c口令)
未知 rs-(随机), hs-H(s口令)
Qc = rc * hc * G --- 已知
Qs = rs * hs * G --- 已知

Yc = rc * rt * G --- 已知
Ys = rs * rt * G --- 已知

Zcs = rc * rs * rt * G --- 已知 公共密钥

这里面的rc是我们可以控制的，所以可以令rc=1让问题看起来简单一点。

1
2
3
4
5
6
7
8
rc = 1 时：

Qc = hc * G --- 已知
Qs = rs * hs * G --- 已知

Yc  =      rt * G --- 已知
Ys  = rs * rt * G --- 已知
Zcs = rs * rt * G --- 已知 公共密钥

hshs是两个字节的sha256结果，显然是让我们爆破的，也就是说我们需要得到一组形式为hs⋅Poinths\cdot Point和PointPoint的数据，这样去爆两个字节就可以了，为了得到这样的数据，我们需要构造一下发送的数据。

1
2
3
4
5
发送假的 Qc = hc * rs * hs * G = hc * Qs
得到    Yc = hs * rs * rt * G

发送 Qs = rs * hs * G
得到 Ys = rs * rt * G

这样以来，YsYs和YcYc刚好是我们需要的一组数据，Yc=hs⋅YsYc=hs\cdot Ys，然后爆破一下两个字节的哈希，如果某两个字节的sha256乘YsYs等于YcYc，那么这个sha256的值就是hshs：

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
import requests, os, random, tqdm
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from task_data import p, a, b, G, msg21, msg23, msg25
from hashlib import sha256

E = EllipticCurve(IntegerModRing(p), [a, b])
G = E(G)

sid2 = "8d1a95ce724141a0ea7c8ffa7eddc48605b3117c8aa886bcc2aff3b0c2175b56"
msg22 = requests.get(msg21, data=sid2).text
Qs = E((int(msg22[:64], 16), int(msg22[64:], 16)))


rc = 1 # random.randint(1, p)
Rc = rc*G

Pic = long_to_bytes(int('FFFF', 16))
hc = int(sha256(Pic).hexdigest(), 16)
fake_Qc = hc * Qs # hc * rs * hs * G
fake_Qc_hex = hex(fake_Qc[0])[2:].rjust(64) + hex(fake_Qc[1])[2:].rjust(64)

msg24 = requests.get(msg23, data=fake_Qc_hex+msg22).text
assert len(msg24) == 256
Yc_hex, Ys_hex = msg24[:128], msg24[128:]

# hs * rs * rt * G
Yc = E((int(Yc_hex[:64], 16), int(Yc_hex[64:], 16)))
#      rs * rt * G
Ys = E((int(Ys_hex[:64], 16), int(Ys_hex[64:], 16)))

for pis in tqdm.tqdm(range(0xff, 0xffff+1)):
    hs = int(sha256(long_to_bytes(pis)).hexdigest(), 16)
    if ((hs*Ys) == Yc):
        print(f'pis = {pis}\nhs = {hs}')
        break

'''
pis = 36727
hs = 67294392667457530634966084521984708026794776225602296684920633502274376489620
'''

协议2搞到了hshs，也就是协议1中的服务端私钥ds，所以服务端的公钥也很容易得到，这样就有了(dS,PS)(d_S,P_S)，还有题目给我们的PCP_C，一旦计算出KCSK_{CS}就可以解出flag了，那么问题是看起来我们必须知道tSt_S和dCd_C中的一个，所以需要想办法把它消掉，在要求上传TCT_C的时候，上传−TC-T_C就可以了。

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
import requests, random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from task_data import p, a, b, G, msg11, msg13, Pc
from hashlib import sha256


E = EllipticCurve(IntegerModRing(p), [a, b])
G = E(G)
sid1 = "8d1a95ce724141a0ea7c8ffa7eddc48605b3117c8aa886bcc2aff3b0c2175b56"

msg12 = requests.get(msg11, data=sid1).text
ds = 67294392667457530634966084521984708026794776225602296684920633502274376489620
Ps = ds*G
Pc = E(Pc)
invPc = -1*Pc
print(invPc)
invPc_hex = hex(invPc[0])[2:].rjust(64) + hex(invPc[1])[2:].rjust(64)
msg14 = requests.get(msg13, data=sid1+invPc_hex).text

Kcs = ds*invPc
sk1 = sha256(long_to_bytes(int(Kcs[0]))).digest()

msg26 = bytes.fromhex(msg14)
iv, ciphertext, mac = msg26[:12], msg26[12:-16], msg26[-16:]
cipher = AES.new(sk1, mode=AES.MODE_GCM, nonce=iv)
try:
    m = cipher.decrypt_and_verify(ciphertext, mac)
    print(m.decode())
except ValueError:
    print("MAC check failed")

JustDecrypt

和美团CTF决赛的secret_decryption_system几乎一样的题，不同的地方是给的交互次数不够，最后unpad不一定会被截断到什么地方，所以用一样的脚本跑出结果的概率是1/256

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
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
def main():
    r = remote('39.105.181.182', '30001')
    plaintext = b"Hello, I'm a Bytedancer. Please give me the flag!"+b"\x0f"*15

    def my_XOR(a, b):
        assert len(a) == len(b)
        return b''.join([long_to_bytes(a[i]^b[i]) for i in range(len(a))])

    def proof_of_work():
        rev = r.recvuntil(b"sha256(XXXX+")
        suffix = r.recv(28).decode()
        rev = r.recvuntil(b" == ")
        tar = r.recv(64).decode()

        def f(x):
            hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
            return hashresult == tar

        prefix = util.iters.mbruteforce(f, string.digits + string.ascii_letters, 4, 'upto')
        r.recvuntil(b'Give me XXXX > ')
        r.sendline(prefix.encode())

    def decrypt(msg):
        newmsg = msg + b'\x00'*(256+64-len(msg))
        r.recvuntil(b'Please enter your cipher in hex > ')
        r.sendline(newmsg.hex().encode())
        r.recvline()
        result = r.recvline().decode().strip()
        return bytes.fromhex(result)

    def decrypt_(msg):
        newmsg = msg + b'\x00'*(256-len(msg))
        r.recvuntil(b'Please enter your cipher in hex > ')
        r.sendline(newmsg.hex().encode())
        r.recvline()
        result = r.recvline().decode().strip()
        return bytes.fromhex(result)
    
    proof_of_work()
    msg = b'\x00'*16
    decrypt(msg)
    c = b""
    for i in range(50):
        t = decrypt(c)[i]
        c += long_to_bytes(t^plaintext[i])

    decc = decrypt_(c)
    print(decc)
    res = r.recvline()+r.recvline()
    if b"Here is your flag" in res:
        print(r.recvline())
        print(r.recvline())
        r.close()
        return (True, len(decc))
    r.close()
    return (False, len(decc))

ll = []
while True:
    ss = main()
    ll.append(ss[1])
    if ss[0]: break
    print(len(ll), ll)


Overheard

相当于一个Oracle，给返回pow(msg, b, p)的高位，可以想办法利用coppersmith定理。先后发送Alice和pow(Alice, 2, p)的值，然后得到x1，x2，那么在模p的多项式f(x)=(x1+a)2−x2−bf(x) = (x1 + a)^2 - x2 - b 的值为0，所以解这个方程的small roots就可以得到被舍弃的值（小于64bit）。

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
from pwn import remote
from Crypto.Util.number import *
import itertools

r = remote('39.105.38.192', 30000)
p = 62606792596600834911820789765744078048692259104005438531455193685836606544743
g = 5

r.sendlineafter(b"$ ", b"1")
Alice = int(r.recvline().decode().strip()) 

r.sendlineafter(b"$ ", b"2")
Bob = int(r.recvline().decode().strip()) 


r.sendlineafter(b"$ ", b"3")
r.sendlineafter(b"To Bob: ", str(Alice).encode())
x1 = int(r.recvline().decode().strip()) 

r.sendlineafter(b"$ ", b"3")
r.sendlineafter(b"To Bob: ", str(pow(Alice, 2, p)).encode())
x2 = int(r.recvline().decode().strip()) 

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()
	R = f.base_ring()
	N = R.cardinality()
	f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)
	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)
	B, monomials = G.coefficient_matrix()
	monomials = vector(monomials)
	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)
	B = B.dense_matrix().LLL()
	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)
	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots
	return []

PR.<a,b> = PolynomialRing(Zmod(p))
f = (x1 + a)**2 - x2 - b
ans = small_roots(f, (2**64, 2**64), m=8)
print("ans =", ans)
r.sendlineafter(b'$ ', b'4')
r.sendlineafter(b'secret: ', str(x1 + ans[0][0]).encode())
print(r.recvline().decode().strip())
r.close()
'''
ans = [(275016199582168079, 3988784878785365375)]
b'ByteCTF{0fcca5ab-c7dc-4b9a-83f0-b24d4d004c19}'
'''