2024NCTF复现

发表于 更新于 阅读次数： 本文字数： 12k 阅读时长 ≈ 21 分钟

owo

爆零，不嘻嘻。

Arcahv

一道大杂烩题目，其实赛后复现感觉自己应该也能做，可惜赛中没耐心细细分析代码。

题目：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from Crypto.Util.number import *
from os import urandom,getenv
from functools import reduce
from Crypto.Cipher import AES

class LCG:
    def __init__(self,seed:int) -> None:
        self.p = getPrime(1024)
        self.a = getPrime(1023)
        self.b = getPrime(1023)
        self.status = seed

    def next(self) -> int:
        ret = self.status
        self.status = (self.status * self.a + self.b) % self.p
        return ret
    
def crystal_trick(m:bytes) -> bytes:
    m = bytearray(m)
    for i in range(len(m)):
        m[i] = reduce(lambda x,y: x^y^urandom(1)[0],m[:i],m[i])
    return m

class RSA:
    def __init__(self):
        p = getStrongPrime(1024)
        q = getStrongPrime(1024)
        self.p = p
        self.N = p * q
        self.e = 65537
        self.d = pow(self.e, -1, (p-1)*(q-1))

    def encrypt(self,m:int) -> int:
        return pow(m,self.e,self.N)
    
    def decrypt(self,c:int) -> int:
        return pow(c,self.d,self.N) 

class MyRSA1(RSA):
    def encrypt(self,m:bytes) -> bytes:
        return super().encrypt(int.from_bytes(m)).to_bytes(256)
    
    def decrypt(self,c:bytes) -> bytes:
        return super().decrypt(int.from_bytes(c)).to_bytes(256)

class MyRSA2(RSA):
    def encrypt(self,m:bytes) -> bytes:
        return pow(int.from_bytes(m),self.e,self.N).to_bytes(256,'little')
    
    def decrypt(self,c:bytes) -> bytes:
        m = pow(int.from_bytes(c),self.d,self.N).to_bytes(256,'little')
        print('Hibiscus is here to trick your decryption result!!')
        return crystal_trick(m)

menu = '''
Welcome to NCTF 2025 arcahv challenge!

--- Menu ---
[1] View encrypted flag and hint
[2] Play with the decryption orcale
[3] Get some random numbers for fun
[4] Exit

Your Option > '''


if __name__=='__main__':
    print('Loading, please wait...')
    
    flag = open('flag.txt').read().strip().encode()
    #flag = getenv('FLAG').encode()
    attempts = 75
    r1 = MyRSA1()
    r2 = MyRSA2()
    hint1 = r2.encrypt(r1.p.to_bytes(128))

    key = urandom(16)
    hint2 = AES.new(key,AES.MODE_ECB).encrypt(r1.N.to_bytes(256))

    def flag_and_hint():
        print(f'Encrypted flag: {r1.encrypt(flag).hex()}')
        print(f'Hint1: {hint1.hex()}')
        print(f'Hint2: {hint2.hex()}')

    def rsachal(): 
        global attempts

        print("Since you didn't v Hibiscus 50 on crazy thursday, Hibiscus decided to do some trick on your decryption result!")
        print(f'Your pubkey:({hex(r2.N)[2:]},{hex(r2.e)[2:]})')

        while attempts > 0:
            if input('Do you still want to try decryption(y/[n])?') != 'y':
                break

            c = bytes.fromhex(input(f'You have {attempts} remaining access to decryption orcale!\nYour ciphertext(in hex):'))
            print(f'Result: {r2.decrypt(c).hex()}')
            attempts -= 1
        
        if attempts == 0:
            print('Unfortunately, you are out of decryption attempts! Come back again on nctf2026 ~')

    
    def lcgchal():
        lcg = LCG(int.from_bytes(key))

        print('Tempering with LCG generator, please wait...')
        while urandom(1)[0] & 0xff:
            lcg.next()
        
        hexnums = ''.join(hex(lcg.next())[2:] for _ in range(5))
        if len(hexnums) % 16:
            hexnums = hexnums.zfill((len(hexnums) // 16 + 1) * 16)
        
        idx = 0
        while input('Do you want another unsigned long long number(y/[n])?') == 'y':
            print(int(''.join(hexnums[idx:idx+16]),16))
            idx = (idx + 16) % len(hexnums)

    def bye():
        print('Hope you have fun during the challenge XD:)')
        exit(0)

    fundc = {1:flag_and_hint,2:rsachal,3:lcgchal,4:bye}

    while True:
        opt = input(menu)
        if len(opt) == 0 or opt not in '1234':
            opt = '4'
        fundc[int(opt)]()

首先选项一交互得到密文，hint1，hint2.并且由

1
2
3
4
hint1 = r2.encrypt(r1.p.to_bytes(128))

    key = urandom(16)
    hint2 = AES.new(key,AES.MODE_ECB).encrypt(r1.N.to_bytes(256))

不难看出，hint1是对p进行RSA加密得到的结果，那么很明显我们要通过后面的rsachall函数来对p进行解密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rsachal(): 
        global attempts

        print("Since you didn't v Hibiscus 50 on crazy thursday, Hibiscus decided to do some trick on your decryption result!")
        print(f'Your pubkey:({hex(r2.N)[2:]},{hex(r2.e)[2:]})')

        while attempts > 0:
            if input('Do you still want to try decryption(y/[n])?') != 'y':
                break

            c = bytes.fromhex(input(f'You have {attempts} remaining access to decryption orcale!\nYour ciphertext(in hex):'))
            print(f'Result: {r2.decrypt(c).hex()}')
            attempts -= 1
        
        if attempts == 0:
            print('Unfortunately, you are out of decryption attempts! Come back again on nctf2026 ~')

值得注意的是这并不是一个普通的RSA加密，因为r2涉及到了一个混淆函数

1
2
3
4
5
def crystal_trick(m:bytes) -> bytes:
    m = bytearray(m)
    for i in range(len(m)):
        m[i] = reduce(lambda x,y: x^y^urandom(1)[0],m[:i],m[i])
    return m

我们试一下该函数的输出可以发现每次混淆之后第一个字节是不变的，根据此我们就可以通过多次交互来逐步还原p，一个字节8位，题目限定了75次交互，也就是我们最多只能还原高600位，此时未知424位，就可以用coppersmith去打。还原高600位涉及到的一个攻击思想是RSA LSB Orcale,我们需要逐步还原其高位。通过在 Z$_p$下将密文乘以 C$^e$，我们解密得到的明文即为 m′=Cm modN。显然存在等式 m′+kN=Cm。本题中由于我们可以得到 m′mod256，因而亦令 C=256。从另一个角度理解就是为了保证一次爆尽可能多的字节，选256就是刚好爆一个字节(8位)，本质就是把范围缩小到1/256.

不过我们看到给定的交互次数只有75次，在交互次数有限的情况下，应选择跳过前127次交互，因为已知这127次交互必定会得到 k=0。接下来详细解释一下。

此时RSA素数 p，其位数为1024位，N位数就为2048位已知m′=Cm−kN(k∈Z)。若 Cm≥N，则 m′=Cm−kN≥0，且 k≥1。但根据参数选择 C=256$^{127}$，实际有 Cm<N，

则m′=Cm modN=Cm−0⋅N=Cm。

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
m = enc_hint
omit_count = 127
io.sendlineafter(b'>', b'2')
io.recvuntil(b'(')
rn = int(io.recvuntil(b',', drop=True).strip().decode(), 16)
re = int(io.recvuntil(b')', drop=True).strip().decode(), 16)

upper_bound = reduce(lambda x, y: floor(x / 256), range(omit_count), rn)

lower_bound = 0
single_mul = pow(256, re, rn)
inv = pow(rn, -1, 256)

m = m * pow(single_mul, omit_count, rn) % rn

for i in range(75):
    m = int(m * single_mul % rn)

    io.sendlineafter(b'?', b'y')
    io.sendlineafter(b':', hexify_send(m))
    io.recvuntil(b':')
    this = int(io.recvline().strip().decode()[:2], 16)

    k = int(-this * inv % 256)
    ttl = (upper_bound - lower_bound) / 256

    lower_bound += ceil(k * ttl)
    upper_bound = lower_bound + floor(ttl)

res_pp = lower_bound
print(f'res_pp={res_pp}')

第二部分是一个lcg。这就是一个很普通的逆推求key的过程。首先需要找到五个连续的输出，因为可以发现5个连续随机数是LCG参数完全未知时下还原 p 所需的最小数目。随后就是一个很基本的还原参数然后逆向求key。从任意输出 Xi开始，反向计算前驱状态，直至状态值的位长 ≤ 128位（即16字节），此时即为初始种子 key。

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
io.sendlineafter(b'>',b'3')
ls = []
for _ in range(80):
    io.sendlineafter(b'?',b'y')
    ls.append(int(io.recvline().strip().decode()))


hexstr = ''.join(hex(i)[2:].zfill(16) for i in ls)
lcgnums = [int(hexstr[i:i+256],16) for i in range(0,len(hexstr),256)]


A = [lcgnums[i+1]-lcgnums[i] for i in range(4)]
p = gcd(A[1]^2 - A[2]*A[0],A[2]^2 - A[3]*A[1])

if not isPrime(p):
    p = factor(p)[-1][0]

assert isPrime(p)

a = int(A[1] * int(pow(A[0],-1,p)) % p)
b = int((lcgnums[1] - a * lcgnums[0]) % p)

cur = Zmod(p)(lcgnums[0])
count = 0
while int(cur).bit_length() > 128:
    cur = (cur - b) * pow(a,-1,p)
    count += 1

key = int(cur).to_bytes(16,'big')
res_n = int.from_bytes(AES.new(key,AES.MODE_ECB).decrypt(enc_hint2),'big')

现在我们已经得到了p的600位高位和n，那么很明显接下来就是coppersmith在已知p高位下分解n，最后解密即可

1
2
3
4
5
6
7
8
9
10
P.<x> = Zmod(res_n)[]
rt = (res_pp + x).small_roots(X=2^453,beta=0.4)[0]

p0 = int(res_pp + rt)

assert res_n % p0 == 0
q0 = res_n // p0

d0 = int(pow(65537,-1,(p0-1)*(q0-1)))
print(long_to_bytes(int(pow(enc_flag,d0,res_n))))

sign

题目

srv.py

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
from Crypto.Util.number import *
from util import *
from os import getenv
from Crypto.Util.Padding import pad
from random import Random
from Crypto.Cipher import AES
from hashlib import md5

string = open('secret.txt').read().strip().encode()
flag = getenv('FLAG').encode()

if __name__=='__main__':
    Keys = []
    for m in string:
        f = FHE()
        s = long_to_bytes(Random().getrandbits(20000))
        for i in s[4:]:
            Keys.extend(f.encrypt([i]))

        for i in s[:4]:
            Keys.extend(f.encrypt([i * (m & 0x03) % 0x101]))
            m >>= 2
        
    assert len(Keys) == 30000

    print(f'[+] Your ciphertext: {AES.new(md5(string).digest(),AES.MODE_ECB).encrypt(pad(flag,16)).hex()}')
    input(f'[+] The keys to retrieve the global internet connection are as follows:')
    for i in range(30000):
        print(f'[+] {Keys[i]}')

util.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from os import urandom
from Crypto.Util.number import *

def getrandint(n:int):
    return int.from_bytes(urandom(n//8+1)) % pow(2,n)

class FHE:
    def __init__(self):
        self.p = getPrime(77)
        self.pubkeys = []
        for _ in range(16):
            self.pubkeys.append(self.p * getrandint(177) + (getrandint(17) << 8))

    def encrypt(self,msg:list[int] | bytes):
        result = []
        for m in msg:
            tmp = 0
            shuffle_base = urandom(16)
            for i in shuffle_base:
                x,y = divmod(i,16)
                tmp += x*self.pubkeys[y] + y*self.pubkeys[x]
            result.append(tmp + m)
        return result

沟槽的MT19937还在追我，但是先来看看这个FHE,重点看self.pubkeys.append(self.p * getrandint(177) + (getrandint(17) << 8))，公钥组的生成p$*k_i$=p$*a_i$+b$_i$<<8,对移位操作比较熟悉不难发现左移8位相当于乘上256，即p$*k_i$=p$*a_i$+b$_i$*256，那很明显就是一个agcd的问题，把加号后面的看作一个整体就行。首先agcd构造格求出p。结果可以简化为result=p*A+256*B+m，分析得出m=result%p%256，那么流程就很清晰了，使用agcd解密得到生成随机数的后19968位，随后用MT19937在已知后19968位的前提下预测前32位。然后用自定义的加解密方式还原m。

agcd部分ref：AGCD近似最大公约数问题 | 独奏の小屋

MT19937逆向预测其实就是逆向其twist()函数，回头开篇文章专门写一下关于MT19937的，最近碰到的这类题蛮多了。

ref：NCTF 2024 - SeanDictionary | 折腾日记

记录一下，逆向预测的脚本

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
def MT19937_re(state):
    try:
        # 构造目标向量R
        R = []
        for i in state:
            R += list(map(int, bin(i)[2:].zfill(8)))

        R = vector(GF(2), R)
        s = L.solve_left(R)  # 这里可能会抛出异常

        # 将解转换为二进制字符串
        init = "".join(list(map(str, s)))
        state = []
        # 将解重新分割成624个32位整数
        for i in range(624):
            state.append(int(init[32 * i:32 * i + 32], 2))

            # 创建新的RNG并设置恢复出的状态
        RNG1 = Random()
        RNG1.setstate((3, tuple(state + [624]), None))

        return RNG1

    except Exception as e:
        print(f"[-]{e}")
        pass

完整exp

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
from Crypto.Util.number import *
from random import *
import json
from pwn import *
from Crypto.Cipher import AES
from hashlib import md5
from tqdm import *



def construct_a_row(RNG):
    row = []
    for _ in range(19968 // 32):
        tmp = RNG.getrandbits(32)
        row = list(map(int, bin(tmp)[2:].zfill(32))) + row
    return row


# 构造线性方程组的矩阵
L = []
for i in trange(19968):
    state = [0] * 624  # MT19937使用624个32位整数作为状态
    # 构造一个只有一位为1,其他都为0的序列
    temp = "0" * i + "1" * 1 + "0" * (19968 - 1 - i)
    # 将这个序列分成624段,每段32位,转换为整数
    for j in range(624):
        state[j] = int(temp[32 * j:32 * j + 32], 2)

    RNG = Random()
    RNG.setstate((3, tuple(state + [624]), None))
    L.append(construct_a_row(RNG))

# 将L转换为GF(2)上的矩阵（二进制域）
L = Matrix(GF(2), L)
print(L.nrows(), L.ncols())
def AGCD(xs, rho):
    # reference:https://hasegawaazusa.github.io/agcd-note.html
    k = len(xs)
    A = ZZ(pow(2, rho + 1))
    B = matrix(xs[1:])
    C = matrix.diagonal([-xs[0]] * (k - 1))
    M = matrix.block([[A, B], [ZZ(0), C]])
    L = M.LLL()
    q0 = ZZ(L[0, 0] / A).abs()
    e0 = ZZ(xs[0] % q0)
    p = ZZ((xs[0] - e0) / q0)
    return p


def MT19937_re(state):
    try:
        # 构造目标向量R
        R = []
        for i in state:
            R += list(map(int, bin(i)[2:].zfill(8)))

        R = vector(GF(2), R)
        s = L.solve_left(R)  # 这里可能会抛出异常

        # 将解转换为二进制字符串
        init = "".join(list(map(str, s)))
        state = []
        # 将解重新分割成624个32位整数
        for i in range(624):
            state.append(int(init[32 * i:32 * i + 32], 2))

            # 创建新的RNG并设置恢复出的状态
        RNG1 = Random()
        RNG1.setstate((3, tuple(state + [624]), None))

        return RNG1

    except Exception as e:
        print(f"[-]{e}")
        pass


ciphertext = long_to_bytes(0xb34b04966970e822ff73a6d1d1e6f2a3778e38330d8b8660f66f713d9fd9a536dde82daeb1c2d6e8d8dbd7c8f80178a2)
Keys = json.loads(open(r"sign1.txt", "r").read())

string = b""
for i in range(30000 // 2500):
    xs = Keys[i * 2500:(i + 1) * 2500]
    p = AGCD(xs[:40], 23)
    print(f"[+]found p:{p}")
    es = [(x % p) % 256 for x in xs]
    RNG = MT19937_re(es[:-4])
    print("[+]reverse MT19937")
    heads = [int(i) for i in long_to_bytes(RNG.getrandbits(20000))[:4]]
    m = 0
    for i in range(4)[::-1]:
        tmp = (pow(heads[i], -1, 0x101) * es[-4:][i]) % 0x101
        assert int(tmp).bit_length() <= 2
        m = (m << 2) + tmp
    m = long_to_bytes(int(m))
    string += m
    print(f"[+]get:{m}")
print(f"[+]string:{string}")
print(f"[+]flag: {AES.new(md5(string).digest(), AES.MODE_ECB).decrypt(ciphertext)}")