2025-阿里云CTF-wp-crypto

这次阿里云CTF还是和r3一起打，又一次拿到亚军，有点可惜，不过同源那道我确实是目前无论如何做不出来的TT

LinearCasino

题目

题目描述：

1	Are you Super Guesser 🍀

题目：

alarm(120)
n, d1, d2 = 100, 60, 50
FLAG = "aliyunctf{REDACTED}"
print("😊 LinearCasino is the Game 4 Super Guesser.")
for _ in range(100):
    D1 = random_matrix(GF(2), d1, n)
    D2 = random_matrix(GF(2), d2, n)
    A = random_matrix(GF(2), d1+d2, d1+d2)
    B = [random_matrix(GF(2), d1+d2, 2*n), block_matrix([[D1, D1],[0, D2]])]
    C = Permutations(2*n).random_element().to_matrix()
    ct = [A*B[0]*C, A*B[1]*C]
    decision = randint(0,1)
    a = int(''.join(map(str, ct[decision].list())),2)
    print("🎩", int(''.join(map(str, ct[decision].list())),2))
    assert input("🎲 ") == str(decision)
print(f"🚩 Real Super Guesser! {FLAG}")

题目生成以下两个不同的矩阵：

${B_0}_{(d_1+d_2) \times 2n}$ $B_1 = \left(\matrix{ {D_1}_{d_1\times n} & {D_1}_{d_1\times n}\\ 0 & {D_2}_{d_2\times n} }\right)$

然后分别计算如下两个密文矩阵：

$enc_0 = AB_0C$ $enc_1 = AB_1C$

其中$A_{(d_1+d_2)\times (d_1+d_2)}$是随机矩阵，$C_{2n\times 2n}$是随机置换矩阵，给出其中一个密文矩阵，我们需要判断他是$enc_0$还是$enc_1$，连续成功100轮就可以获得flag。

思路

这个题是第一天晚上上的，还没来得及看题@dbt和@rec他们就很快做掉了，所以就赛后来复现一下。

由于接触过一点点编码，所以看到这题很容易联想到编码里$SGP$的情况，其中$S$就是题目中的$A$，是随机矩阵，而$P$则是题目中的$C$也就是置换矩阵，而我们需要区分的是$SGP$中的$G$，这可能就和具体的编码结构有关系，也就是题目里的：

$B_1 = \left(\matrix{ {D_1} & {D_1}\\ 0 & {D_2} }\right)$

但是印象里@dbt他们的做法似乎很简单，和编码关系也不是特别大，所以直接问了下@hashhash知道了这样一个思路：

由于$enc_0$和纯随机矩阵没什么区别，所以主要关注$enc_1$，由于$C$是置换矩阵，所以有下面这样一个事实：

$CC^T = E$

这很容易想通，因为只有在对角线上的位置，置换矩阵当前行的1才能和他转置矩阵当前列的1恰好“碰上”

所以对于整个$enc_1$有：

$AB_1C(AB_1C)^T = AB_1(CC^T)B_1^TA^T = AB_1B_1^TA^T$

而$B_1$的结构是：

$B_1 = \left(\matrix{ {D_1} & {D_1}\\ 0 & {D_2} }\right)$

所以有：

$B_1B_1^T = \left(\matrix{ {D_1} & {D_1}\\ 0 & {D_2} }\right) \left(\matrix{ {D_1}^T & 0\\ {D_1}^T & {D_2}^T }\right) = \left(\matrix{ 2D_1{D_1}^T & D_1D_2^T\\ D_2{D_1}^T & D_2{D_2}^T }\right)$

因为矩阵是$GF(2)$下的，所以左上的部分是0，也就有：

$B_1B_1^T = \left(\matrix{ 0 & D_1D_2^T\\ D_2{D_1}^T & D_2{D_2}^T }\right)$

此时关注以下矩阵维数：

$B_1B_1^T = \left(\matrix{ 0 & {D_1D_2^T}_{d_1\times d_2}\\ {D_2{D_1}^T}_{d_2\times d_1} & {D_2{D_2}^T}_{d_2\times d_2} }\right)_{(d_1+d_2)\times (d_1+d_2)}$

左下角的矩阵是$d_2 \times d_1$的，因此整个矩阵左半部分的秩最多只有$d_2$，这会导致$B_1B_1^T$的秩最多也只有$2d_2$，而$AB_1B_1^TA^T$的秩显然是小于等于$B_1B_1^T$的秩的，所以$enc_1 \cdot enc_1^T$的秩最多也只有$2d_2$。

exp

from tqdm import *
from pwn import *

sh = process(["sage", "task.sage"])
sh.recvuntil(b"LinearCasino is the Game 4 Super Guesser.")

n, d1, d2 = 100, 60, 50
for _ in trange(100):
    sh.recvuntil(b"\xf0\x9f\x8e\xa9 ")
    enc = Matrix(GF(2), d1+d2, 2*n, list(map(int, bin(int(sh.recvline().strip().decode()))[2:].zfill((d1+d2)*(2*n)))))
    if((enc*enc.T).rank() <= 100):
        sh.sendline(b"1")
    else:
        sh.sendline(b"0")
print(sh.recvline())

PRFCasino

题目

题目描述：

1	Are you Super Guesser 🍀

题目：

from Crypto.Util.strxor import strxor
from Crypto.Util.number import *
from hashlib import md5
import random, os
__import__("signal").alarm(100)
FLAG = "aliyunctf{REDACTED}"

lrot = lambda X,t: (X<<t|X>>(64-t))&(2**64-1)
sbox = lambda X,Sbox: bytes([Sbox[i] for i in X])
pad = lambda X: X+b'\x00'*(block_size-len(X)%block_size)
block_size = 16

class PRF:
    def __init__(self):
        self.key = os.urandom(16)
        self.RK = [self.key]
        self.Sbox = list(range(256))
        random.shuffle(self.Sbox)
        self.round_key()

    def round_key(self, round=30):
        for _ in range(round):
            next_rk = md5(self.RK[-1]).digest()
            self.RK.extend([next_rk[:8], next_rk[8:]])

    def encrypt(self, block, round=30):
        L, R = block[:8], block[8:]
        for i in range(1, 2*round+1, 2):
            T = bytes_to_long(strxor(sbox(L, self.Sbox), self.RK[i]))
            T = (i*T+lrot(T, 17)+bytes_to_long(self.RK[i+1]))%2**64
            L, R = long_to_bytes((T+lrot(T, 20)+bytes_to_long(R))%2**64, 8), L
        return L+R
    
    def cbc_encrypt(self, msg):
        blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
        result = b'\x00'*16
        for block in blocks:
            result += self.encrypt(strxor(block, result[-16:]))
        return result[16:]

print("😊 PRFCasino is the Game 4 Super Guesser.")
for _ in range(100):
    prf = PRF()
    msg = pad(bytes.fromhex(input("💵 ")))
    ct = [prf.cbc_encrypt(msg), os.urandom(len(msg))]
    decision = random.randint(0,1)
    print("🎩", ct[decision].hex())
    assert input("🎲 ") == str(decision)
print(f"🚩 Real Super Guesser! {FLAG}")

题目基于一个Feistel结构的PRF，我们可以输入任意长度的明文，之后靶机生成两个密文串，一个是PRF对输入明文进行CBC模式加密的结果，另一个是纯随机字节串。我们需要判断给出的串究竟是其中哪个，依然需要连续成功100轮拿到flag。

思路

先不管CBC模式，就假如初始的$L,R$两部分都是0，关注一下encrypt的过程：

def encrypt(self, block, round=30):
    L, R = block[:8], block[8:]
    for i in range(1, 2*round+1, 2):
        T = bytes_to_long(strxor(sbox(L, self.Sbox), self.RK[i]))
        T = (i*T+lrot(T, 17)+bytes_to_long(self.RK[i+1]))%2**64
        L, R = long_to_bytes((T+lrot(T, 20)+bytes_to_long(R))%2**64, 8), L
    return L+R

其中最重要的无疑是$T$这个值，每一轮代码一共三行，由于轮密钥$RK$的值完全不知道，所以前两行结束后，$T$可以看成是一个随机变量，因此最后一行才是关键：

1	L, R = long_to_bytes((T+lrot(T, 20)+bytes_to_long(R))%2**64, 8), L

记第i轮中进入第三行代码的$T$为$T_i$，那么用前几轮简单看一下Feistel网络的迭代过程：

$Round_1 :\quad L_1 = T_1 + lrot(T_1,20) \quad R_1 = 0$ $Round_2 :\quad L_2 = T_2 + lrot(T_2,20) \quad R_2 = T_1 + lrot(T_1,20)$ $Round_3 :\quad L_3 = T_1 + lrot(T_1,20) + T_3 + lrot(T_3,20) \quad R_3 = T_2 + lrot(T_2,20)$ $Round_4 :\quad L_4 = T_2 + lrot(T_2,20) + T_4 + lrot(T_4,20) \quad R_4 = T_1 + lrot(T_1,20) + T_3 + lrot(T_3,20)$ $...$

可以看出第三十轮的$L,R$分别是：

$L_{30} = \sum_{i=1}^{15}[T_{2i} + lrot(T_{2i}, 20)] \quad(mod\;2^{64})$ $R_{30} = \sum_{i=1}^{15}[T_{2i-1} + lrot(T_{2i-1}, 20)] \quad(mod\;2^{64})$

观察一下$T+lrot(T,20)$这个结构，不妨把$T$的高20bit记为$a$，低44bit记为$b$，那么就有：

$T+lrot(T,20) = 2^{44}a + b + a + 2^{20}b = (2^{44}+1)a + (2^{20}+1)b \quad(mod\;2^{64})$

那么比如对于$L_{30}$，他累加起来是：

$L_{30} = \sum_{i=1}^{15}[(2^{44}+1)a_{2i} + (2^{20}+1)b_{2i}] \quad(mod\;2^{64})$

这里需要注意到：

$gcd(2^{44}+1, 2^{20}+1) = 17$

这还真只能“注意到”XD，实际上是尝试了下LLL发现总有个奇怪的短向量，才知道这个公约数的

而累加只有15次，因此整个式子有：

$L_{30} = \sum_{i=1}^{15}[(2^{44}+1)a_{2i} + (2^{20}+1)b_{2i}] <= 15[(2^{44}+1)a_{max} + (2^{20}+1)b_{max}]$

因为17是大于15的，因此将17提取出来，并将他的逆乘至左边会有：

$\frac{L_{30}}{17} <= 15[\frac{(2^{44}+1)}{17}a_{max} + \frac{(2^{20}+1)}{17}b_{max}] \quad(mod\;2^{64})$

此时要注意到一个事实，由于$a_{max},b_{max}$也不过只是20bit、44bit的量，所以不等式实际上还满足：

$\frac{L_{30}}{17} <= 15[\frac{(2^{44}+1)}{17}a_{max} + \frac{(2^{20}+1)}{17}b_{max}] < 15[\frac{(2^{44}+1)}{17}2^{20} + \frac{(2^{20}+1)}{17}2^{44}] = \frac{15}{17}(2^{65}+2^{44}+2^{20}) \approx \frac{15}{17}2^{65}$

这里的不等式是没有模$2^{64}$下的实际值，可以看出，如果不取max而取平均值，那么这个平均值显然会比较接近于$\frac{15}{17}2^{64}$，至少比$2^{63}$要大。但如果是随机串，那么显然乘17的逆之后也是个随机变量，他的均值就该是$2^{63}$，这就导致加密密文和随机密文在统计意义上出现了差别。

依据此我们完全可以申请足够多组的明文，然后做统计就可以了。

CBC模式影响不大，把上一组密文对应减掉之后就可以得到上述结构的$L$和$R$

exp

from Crypto.Util.number import *
from tqdm import *
from pwn import *

#sh = process(["python", "task.py"])
sh = remote("121.41.238.106", 34257)
sh.recvuntil(b"PRFCasino is the Game 4 Super Guesser.")

n = 2**64
for _ in trange(100):
    nums = 100
    msg = b"\x00"*nums*16
    sh.sendline(msg.hex().encode())
    sh.recvuntil(b"\xf0\x9f\x8e\xa9 ")
    enc = bytes.fromhex(sh.recvline().strip().decode())[:nums*16]

    c = [[enc[16*i:16*i+8], enc[16*i+8:16*i+16]] for i in range(nums)]
    Ti = [bytes_to_long(c[0][0])] + [(bytes_to_long(c[i][0])-bytes_to_long(c[i-1][0])) % n for i in range(1, nums)]
    if(int(sum([i*inverse(17,n)%n for i in Ti]) / nums) > 11000000000000000000):
        sh.sendline(b"0")
    else:
        sh.sendline(b"1")
print(sh.recvline())
sh.close()


#aliyunctf{Th15_PRF_n0t_r4ndom_3nough}

哈基游

题目

题目描述：

1	A simple hash game.

这题是misc题，不过做前面部分的师傅和dbt交流之后把题目转化成了一个密码题，然后交给我做完了他，这里也就记录一下。

这一部分题意可以概括为，已知：

1	RUN echo "aliyunctf{`head /dev/urandom \| tr -dc A-Za-z0-9 \| head -c 15`}" > /flag

也就是说flag文件的结构为：

“aliyunctf{}”包裹
中间有15个字符，由”A-Za-z0-9”组成
由于是echo，所以最后会多一个”\x0a”

之后可以拿到对该文件的三个哈希值：

1
2
3

c1 = crc32(flag)
c2 = crc32b(flag)
c3 = crc32c(flag)

其中三种crc32的python源码为：

def crc32(data):  
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^= byte << 24
        for _ in range(8):
            if crc & 0x80000000:
                crc = ((crc << 1) ^ 0x04C11DB7) & 0xFFFFFFFF
            else:
                crc = (crc << 1) & 0xFFFFFFFF
    
    crc = ~crc & 0xFFFFFFFF
    return bytes([
        crc & 0xFF,
        (crc >> 8) & 0xFF,
        (crc >> 16) & 0xFF,
        (crc >> 24) & 0xFF
    ])

def crc32b(data): 
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^= byte
        for _ in range(8):
            if crc & 1:
                crc = (crc >> 1) ^ 0xEDB88320
            else:
                crc = crc >> 1
    
    crc = ~crc & 0xFFFFFFFF
    return bytes([
        (crc >> 24) & 0xFF,
        (crc >> 16) & 0xFF,
        (crc >> 8) & 0xFF,
        crc & 0xFF
    ])

def crc32c(data): 
    if isinstance(data, str):
        data = data.encode('utf-8')
        
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^= byte
        for _ in range(8):
            if crc & 1:
                crc = (crc >> 1) ^ 0x82F63B78
            else:
                crc = crc >> 1
    
    crc = ~crc & 0xFFFFFFFF
    return bytes([
        (crc >> 24) & 0xFF,
        (crc >> 16) & 0xFF,
        (crc >> 8) & 0xFF,
        crc & 0xFF
    ])
 
if __name__ == "__main__":
    test_data = b"1"
    
    print(f"CRC32:  {crc32(test_data).hex()}")
    print(f"CRC32B: {crc32b(test_data).hex()}")
    print(f"CRC32C: {crc32c(test_data).hex()}")

要求还原flag。

思路

转化到这一步，这题目就很密码学了，首先可以知道三种crc显然都是线性结构。也就是说如果把flag文件做二进制展开，展开成一个长$m$的向量$\textbf{x}$，那么对于三种crc32都有(运算在$GF(2)$下)：

$crc32(\textbf{x}) = \textbf{x}A_{m\times 32} + C_{1\times 32}$

而对于三种crc32，其不同点也就在于$A,C$不同而已，但是都是随着$m$固定的。

对于题目来说，首先$m$的值就是flag文件的二进制长度，算上末尾的”\x0a”，一共是$27\times 8=216$。那么有了$m$之后，$A,C$的值也就固定下来了，接下来的步骤就是要求解出三种crc32分别对应的$A,C$。这很简单，只需要将crc32的过程当作黑盒调用，然后收集足够的输入输出对去求解即可。

记三种crc32得到的$A,C$分别为$A_1,A_2,A_3,C_1,C_2,C_3$如此一来我们就得到了三组方程：

$crc32(\textbf{x}) = \textbf{x}{A_1}_{216\times 32} + {C_1}_{1\times 32}$ $crc32b(\textbf{x}) = \textbf{x}{A_2}_{216\times 32} + {C_2}_{1\times 32}$ $crc32c(\textbf{x}) = \textbf{x}{A_3}_{216\times 32} + {C_3}_{1\times 32}$

这其实就相当于对于216个变量的$\textbf{x}$，收集到了96个方程。

而实际上方程可以有更多：

已知flag的其中12个字符为”aliyunctf{}\x0a”，这96个已知bit对应96个方程
中间的15个字符由”A-Za-z0-9”组成，MSB均为0，这15个MSB对应15个方程

因此实际上我们拥有$96+96+15=207$个方程，只有9维的kernel需要小爆一下，检查输出的flag中间15个字符是否满足上述形式就可以了。

exp

from Crypto.Util.number import *

def rev(a):
    return a ^^ 0xFFFFFFFF

def crc32(data):  
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^^= byte << 24
        for _ in range(8):
            if crc & 0x80000000:
                crc = ((crc << 1) ^^ 0x04C11DB7) & 0xFFFFFFFF
            else:
                crc = (crc << 1) & 0xFFFFFFFF
    
    crc = rev(crc) & 0xFFFFFFFF
    res = bytes([
        crc & 0xFF,
        (crc >> 8) & 0xFF,
        (crc >> 16) & 0xFF,
        (crc >> 24) & 0xFF
    ])
    return bytes_to_long(res)

def crc32b(data): 
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^^= byte
        for _ in range(8):
            if crc & 1:
                crc = (crc >> 1) ^^ 0xEDB88320
            else:
                crc = crc >> 1
    
    crc = rev(crc) & 0xFFFFFFFF
    res = bytes([
        (crc >> 24) & 0xFF,
        (crc >> 16) & 0xFF,
        (crc >> 8) & 0xFF,
        crc & 0xFF
    ])
    return bytes_to_long(res)

def crc32c(data): 
    if isinstance(data, str):
        data = data.encode('utf-8')
        
    crc = 0xFFFFFFFF
    
    for byte in data:
        crc ^^= byte
        for _ in range(8):
            if crc & 1:
                crc = (crc >> 1) ^^ 0x82F63B78
            else:
                crc = crc >> 1
    
    crc = rev(crc) & 0xFFFFFFFF
    res = bytes([
        (crc >> 24) & 0xFF,
        (crc >> 16) & 0xFF,
        (crc >> 8) & 0xFF,
        crc & 0xFF
    ])
    return bytes_to_long(res)

import os

length = 15 + len(b"aliyunctf{}\x0a")
m = length * 8
n = 32

def construct_linear_crc(crc, m, n):
    nums = m + 100
    L = Matrix(GF(2), nums, m)
    R = Matrix(GF(2), nums, n)
    temp = os.urandom(length)
    fixed_lv = vector(GF(2), list(map(int, bin(bytes_to_long(temp))[2:].zfill(m))))
    fixed_rv = vector(GF(2), list(map(int, bin(crc(temp))[2:].zfill(n))))
    for i in range(nums):
        temp = os.urandom(length)
        lv = vector(GF(2), list(map(int, bin(bytes_to_long(temp))[2:].zfill(m))))
        rv = vector(GF(2), list(map(int, bin(crc(temp))[2:].zfill(n))))
        L[i] = lv - fixed_lv
        R[i] = rv - fixed_rv

    A = L.solve_right(R)
    C = fixed_rv - fixed_lv*A
    return A, C

A1, C1 = construct_linear_crc(crc32, m, n)
A2, C2 = construct_linear_crc(crc32b, m, n)
A3, C3 = construct_linear_crc(crc32c, m, n)

#test
msg = os.urandom(length)
v = vector(GF(2), list(map(int, bin(bytes_to_long(msg))[2:].zfill(m))))
assert v*A1 + C1 == vector(GF(2), list(map(int, bin(crc32(msg))[2:].zfill(n))))
assert v*A2 + C2 == vector(GF(2), list(map(int, bin(crc32b(msg))[2:].zfill(n))))
assert v*A3 + C3 == vector(GF(2), list(map(int, bin(crc32c(msg))[2:].zfill(n))))

A = block_matrix(GF(2), [
    [A1, A2, A3]
])
C = vector(GF(2), C1.list() + C2.list() + C3.list())
assert v*A + C == vector(GF(2), list(map(int, bin(crc32(msg))[2:].zfill(n) + bin(crc32b(msg))[2:].zfill(n) + bin(crc32c(msg))[2:].zfill(n))))

ans = (int("2fe72772", 16) << 64) + (int("81e868d8", 16) << 32) + int("a795a60d", 16)
ans = vector(GF(2), list(map(int, bin(ans)[2:].zfill(n*3))))
ans = ans - C
ans = ans.list()

prefix = list(map(int, bin(bytes_to_long(b"aliyunctf{"))[2:].zfill(80)))
for i in range(80): #prefix: aliyunctf{
    temp_v = vector(GF(2), [0]*i + [1] + [0]*(m-i-1))
    A = A.augment(temp_v)
    ans.append(prefix[i])

suffix = list(map(int, bin(bytes_to_long(b"}\x0a"))[2:].zfill(16)))
for i in range(16): #suffix: }
    temp_v = vector(GF(2), [0]*(25*8+i) + [1] + [0]*(15-i))
    A = A.augment(temp_v)
    ans.append(suffix[i])

for i in range(15): #MSB
    temp_v = vector(GF(2), [0]*(10*8) + [0]*(8*i) + [1] + [0]*7 + [0]*(14*8 - 8*i) + [0]*16)
    A = A.augment(temp_v)
    ans.append(0)

1
2
3

x = A.solve_left(vector(GF(2), ans))
ker = A.left_kernel().basis()
print(len(ker))

from itertools import *
import string

for i in product([0,1],repeat=len(ker)):
    temp = 0
    for j in range(len(i)):
        temp += i[j]*ker[j]
    final = x + temp
    flag = ""
    for i in final:
        flag += str(i)
    flag = long_to_bytes(int(flag, 2)).decode()[:-1]
    if(all([j in (string.ascii_letters+string.digits+"aliyunctf{}") for j in flag])):
        print(flag)


#aliyunctf{JIIpJ3eztwoo22K}