imaginaryCTF-round45

imaginaryCTF Round45 Crypto Writeup

以Ciprocamin的名义solo的比赛,预计以后每个月都会写一次Crypto方向的wp,姑且鞭策下自己.

time

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/local/bin/python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random
import time

def encrypt(message, key):
    cipher = AES.new(key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(pad(message, AES.block_size))
    return ciphertext

flag = open('flag.txt','rb').read().strip()
random.seed(int(time.time()))
key = random.randbytes(16)

encrypted_flag = encrypt(flag, key)
print("Encrypted flag (in hex):", encrypted_flag.hex())

nc连上之后会根据服务器端的时间设置seed,简单爆破一下就可以获得AES key.

time2

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/local/bin/python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random
import time
import os

def encrypt(message, key):
    cipher = AES.new(key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(pad(message, AES.block_size))
    return ciphertext

flag = open('flag.txt','rb').read().strip()
random.seed(int(os.urandom(64).hex(),16)) # super secure!
key = b''
x=random.randbytes(1)
for i in range(16):
	key += x
	random.seed(int(x.hex(),16))
	x = random.randbytes(1)
encrypted_flag = encrypt(flag, key)
print("Encrypted flag (in hex):", encrypted_flag.hex())

# Encrypted flag (in hex): 04b5b9e11ee236a1c0784882d3f8efe9cc28b2993971a83413907e9833190e2a99e611c748966d61489f84ea2f331c7c

爆破key的首字节即可.

python
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
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes

def decrypt(ciphertext, key):
    cipher = AES.new(key, AES.MODE_ECB)
    plaintext = unpad(cipher.decrypt(ciphertext), AES.block_size)
    return plaintext


ciphertext = long_to_bytes(0x04b5b9e11ee236a1c0784882d3f8efe9cc28b2993971a83413907e9833190e2a99e611c748966d61489f84ea2f331c7c)
for i in range(0,256):
	key = b''
	x = bytes([i])
	for j in range(16):
		key += x
		random.seed(int(x.hex(),16))
		x=random.randbytes(1)
	try:
		flag = decrypt(ciphertext,key)
		if(b'ictf' in flag):
			print(flag)
	except:
		continue


crack

python
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
#!/usr/local/bin/python
import random
flag = open('flag.txt').read()
print("Welcome! Let's play a game!")
def print_menu():
	print("""1) Get random bits
2) Guess number
3) Exit	""")

while True:
	print_menu()
	x = int(input("Choice: "))
	if x == 1:
		print("How many random numbers do you want?")
		r = int(input())
		arr = []
		for i in range(r):
			arr.append(random.getrandbits(32))
		print(f'Here you go: {arr}')
	if x == 2:
		to_guess = random.randint(0,65535*65537)
		guess = int(input("Enter guess: "))
		if guess == to_guess:
			print(f"Wow! Here's your flag: {flag}")
		else:
			print('Incorrect!')
			exit()
	if x == 3:
		exit()

可以选择获取的随机数的数量,然后要求预测一个随机数.Python默认内置的随机数发生器是MT19937,只要获取连续输出的624个32-bit随机数就可以预测随后的随机数序列.这里使用randcrack一把梭.

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import random, time
from randcrack import RandCrack
from pwn import *

io = remote('34.72.43.223','49133')
io.sendline(b'1')
io.sendline(b'624')
io.readuntil(b'Here you go: ')
arr = (io.readline().strip())
x = b'arr = ' + arr
exec(x)

rc = RandCrack()

for i in range(624):
	rc.submit(arr[i])

answer = rc.predict_randint(0, 65535*65537)
io.sendline(b'2')
io.sendline(str(answer).encode())
io.readuntil(b"Wow! Here's your flag: ")
print(io.readline().strip())

Scissor

python
1
2
3
4
5
6
7
flag = 'REDACTED'
ciphertext = b''
for i in flag:
	ciphertext += chr(ord(i)+0x1337).encode()
print(f'ciphertext = {ciphertext.hex()}')

# ciphertext = e18ea0e18e9ae18eabe18e9de18eb2e18e9ae18daae18ea9e18daee18da8e18e9de18da8e18daae18e9be18e96e18da8e18daae18daae18daee18e96e18e9fe18dabe18eafe18da7e18ea9e18d98e18eb4

观察输出的密文可以发现每6字节一组,每组减去0x1337即可.

python
1
2
3
4
5
6
from Crypto.Util.number import *
c_list = [0xe18ea0,0xe18e9a,0xe18eab,0xe18e9d,0xe18eb2,0xe18e9a,0xe18daa,0xe18ea9,0xe18dae,0xe18da8,0xe18e9d,0xe18da8,0xe18daa,0xe18e9b,0xe18e96,0xe18da8,0xe18daa,0xe18daa,0xe18dae,0xe18e96,0xe18e9f,0xe18dab,0xe18eaf,0xe18da7,0xe18ea9,0xe18d98,0xe18eb4]
s = ""
for i in c_list:
    s+=chr(ord(long_to_bytes(i).decode())-0x1337)
print(s)

Moonjump

lua
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
72
73
74
75
76
77
78
79
function u(s)
    local r = 0

    for i = #s, 1, -1 do
        r = r * 256
        r = r + string.byte(string.sub(s, i, i))
    end

    return r
end

function sw(t, a, b)
    local x = t[a]
    t[a] = t[b]
    t[b] = x
end

function s(k)
    local r = {}

    for i = 0, 255 do
        r[i] = i
    end

    local j = 0
    local idx = 0

    for i = 0, 255 do
        idx = (i % #k) + 1
        j = (j + r[i] + k:sub(idx, idx):byte()) % 256
        sw(r, i, j)
    end

    return r
end

function e(p, k)
    local i = 0
    local j = 0
    local r = ""

    for l = 1, 3072 do
        i = (i + 1) % 256
        j = (j + k[i]) % 256
        sw(k, i, j)
        t = (k[i] + k[j]) % 256
    end

    for l = 1, #p do
        i = (i + 1) % 256
        j = (j + k[i]) % 256
        sw(k, i, j)
        t = (k[i] + k[j]) % 256
        r = r .. string.char(p:sub(l, l):byte() ~ k[t])
    end

    return r
end

local f = assert(io.open("moon.bmp", "r"))
local d = f:read("*all")
f:close()

local t = os.time()
math.randomseed(t)

local o = u(string.sub(d, 11, 14)) + 1
local p = string.sub(d, o, #d)

for i = 1, 1000000000000000 do
    math.random()
end

local ks = s(tostring(math.random(0, 2^32 - 1)))
local ct = e(p, ks)

f = assert(io.open("chall.bmp", "w"))
f:write(string.sub(d, 0, o - 1) .. ct .. os.date("!%d %h %Y, %H:%M", t))
f:close()

使用随机数生成密钥后对位图的一部分像素做了RC4加密.给出了时间戳,随机数的种子是可以爆破的,无非就60种情况;但是PRNG的中间状态不少于1000000000000000种,直接从头输出的话,耗时是不可接受的.

通过搜索了解到Lua4.2之后内置的随机数发生器为Xorshiro256**,其提供了一个jump操作,执行一次可以跳过 \(2^{128}\) 个状态,不过简单推演就能知道不适用于本题.

能不能仿照jump操作,自行实现一个更小步长的jump呢?审了审Lua中Xorshiro256**的源码,发现其实是个linear的PRNG,最后输出时做了个truncate.是线性的就能算出个矩阵,这样转化到了对矩阵做幂运算,用上快速幂之后时间复杂度直接就可以下来.

最终exp如下:

python
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
# sage
from Crypto.Cipher import ARC4
from datetime import datetime

def rotl(x, n, nbits=64):
    return ((x << n) % (2**nbits)) | (x >> (64 - n))


class LuaXoshiro:
    def __init__(self, seed=0):
        self.seed(seed)

    def seed(self, seed):
        self.state = [seed, 0xff, 0, 0]

    def raw_seed(self, state):
        self.state = [state >> 192, (state >> 128) % (2**64), (state >> 64) % (2**64), state % (2**64)]

    def next(self):
        [s0, s1, s2, s3] = self.state
        s2 ^^= s0
        s3 ^^= s1
        res = rotl((s1 * 5) % (2**64), 7) * 9 % (2**64)
        self.state[0] = s0 ^^ s3
        self.state[1] = s1 ^^ s2
        self.state[2] = s2 ^^ ((s1 << 17) % (2**64))
        self.state[3] = rotl(s3, 45)
        return res

    def raw_state(self):
        [s0, s1, s2, s3] = self.state
        return (s0 << 192) + (s1 << 128) + (s2 << 64) + s3

    def next_state(self):
        self.next()
        return self.raw_state()


def n_to_bit_list(n, nbits=256):
    F = GF(2)
    result = [None for _ in range(nbits)]
    for i in range(nbits):
        result[i] = F((n >> (nbits - i - 1)) % 2)
    return result

def bit_list_to_n(bl):
    result = 0
    for b in bl:
        result *= 2
        result += int(b)
    return result


def transition_matrix(engine, nbits=256):
    state = engine.state
    columns = []
    # calculate the standard matrix
    for i in range(nbits):
        seed = 1 << (nbits - i - 1)
        engine.raw_seed(seed)
        columns.append(n_to_bit_list(engine.next_state()))

    engine.state = state
    return matrix(GF(2), columns).transpose()


def jump(engine, num_steps, mat=None):
    if mat is None:
        mat = transition_matrix(engine)

    state = engine.raw_state()
    v = vector(n_to_bit_list(state))
    v2 = mat^num_steps * v
    newstate = bit_list_to_n(v2)
    engine.raw_seed(newstate)


def lua_nth_random(e, n, mat=None):
    # lua advances the state 16 times after setting the seed in math.randomseed
    jump(e, n + 16, mat)
    return e.next() & (2**32 - 1)


def solve():
    with open('chall.bmp', 'rb') as f:
        data = f.read()
    header = data[:0x8a]
    enc = data[0x8a:]
    dt = datetime.strptime('31 Jan 2020, 20:38 +0000', '%d %b %Y, %H:%M %z')
    e = LuaXoshiro()
    mat = transition_matrix(e)
    for i in range(60):
        seed = int(dt.timestamp() + i)
        e.seed(seed)
        key = str(lua_nth_random(e, 1_000_000_000_000_000)).encode()
        cipher = ARC4.new(key, drop=3072)
        dec = cipher.decrypt(enc)
        with open(f'decrypted/{i:02}.bmp', 'wb') as f:
            f.write(header + dec)


if __name__ == '__main__':
    solve()

# ictf{xoshiro_jumps_in_lua_like_a_pro}

Writeups
#CTF #Crypto
imaginaryCTF-round45
https://eupho.me/1cbd8855.html
作者
Lambert Swizzer
发布于
2024年5月3日
许可协议