Grey Cat The Flag 2024 Qualifiers

發表於 2024-04-21

分類於 CTF

This article is LLM-translated by GPT-4o, so the translation may be inaccurate or complete. If you find any mistake, please let me know.

This week I soloed this event using nyahello, solved all the crypto problems, and found some of the problems quite interesting, so I’m writing a writeup.

Filter Ciphertext

from Crypto.Cipher import AES
import os

with open("flag.txt", "r") as f:
    flag = f.read()

BLOCK_SIZE = 16
iv = os.urandom(BLOCK_SIZE)

xor = lambda x, y: bytes(a^b for a,b in zip(x,y))

key = os.urandom(16)

def encrypt(pt):
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    blocks = [pt[i:i+BLOCK_SIZE] for i in range(0, len(pt), BLOCK_SIZE)]
    tmp = iv
    ret = b""
    
    for block in blocks:
        res = cipher.encrypt(xor(block, tmp))
        ret += res
        tmp = xor(block, res)
        
    return ret

    
def decrypt(ct):
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    blocks = [ct[i:i+BLOCK_SIZE] for i in range(0, len(ct), BLOCK_SIZE)]

    for block in blocks:
        if block in secret_enc:
            blocks.remove(block)
    
    tmp = iv
    ret = b""
    
    for block in blocks:
        res = xor(cipher.decrypt(block), tmp)
        ret += res
        tmp = xor(block, res)
    
    return ret
    
secret = os.urandom(80)
secret_enc = encrypt(secret)

print(f"Encrypted secret: {secret_enc.hex()}")

print("Enter messages to decrypt (in hex): ")

while True:
    res = input("> ")

    try:
        enc = bytes.fromhex(res)

        if (enc == secret_enc):
            print("Nice try.")
            continue
        
        dec = decrypt(enc)
        if (dec == secret):
            print(f"Wow! Here's the flag: {flag}")
            break

        else:
            print(dec.hex())
        
    except Exception as e:
        print(e)
        continue

In short, it has a decryption oracle, and when dividing into blocks, if it detects that a certain block is part of secret_enc, it will remove it. However, upon closer inspection, you will find that it seems a bit off:

for block in blocks:
	if block in secret_enc:
		blocks.remove(block)

Here, it is iterating blocks while simultaneously modifying blocks, which will cause issues in Python. Specifically, when i=0, it will remove blocks[0], and the data originally in blocks[1] will move to blocks[0], causing blocks[1] to be unchecked. So, assuming each block meets block in blocks, it means that blocks 0,2,4,6,... will be removed, while blocks 1,3,5,7,... will be retained.

Therefore, to solve this problem, divide secret_enc into blocks, repeat each block twice, and then join them together:

secret_enc = bytes.fromhex(input())
blks = [secret_enc[i : i + 16] for i in range(0, len(secret_enc), 16)]
new_blks = sum([[blk] * 2 for blk in blks], [])
new_secret_enc = b"".join(new_blks)
print(new_secret_enc.hex())
# grey{00ps_n3v3r_m0d1fy_wh1l3_1t3r4t1ng}

Filter Plaintext

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
import os

with open("flag.txt", "r") as f:
    flag = f.read()

BLOCK_SIZE = 16
iv = os.urandom(BLOCK_SIZE)

xor = lambda x, y: bytes(a^b for a,b in zip(x,y))

key = os.urandom(16)

def encrypt(pt):
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    blocks = [pt[i:i+BLOCK_SIZE] for i in range(0, len(pt), BLOCK_SIZE)]
    tmp = iv
    ret = b""
    
    for block in blocks:
        res = cipher.encrypt(xor(block, tmp))
        ret += res
        tmp = xor(block, res)
        
    return ret

    
def decrypt(ct):
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    blocks = [ct[i:i+BLOCK_SIZE] for i in range(0, len(ct), BLOCK_SIZE)]

    
    tmp = iv
    ret = b""
    
    for block in blocks:
        res = xor(cipher.decrypt(block), tmp)
        if (res not in secret):
            ret += res
        tmp = xor(block, res)
        
    return ret
    
secret = os.urandom(80)
secret_enc = encrypt(secret)

print(f"Encrypted secret: {secret_enc.hex()}")

secret_key = md5(secret).digest()
secret_iv = os.urandom(BLOCK_SIZE)
cipher = AES.new(key = secret_key, iv = secret_iv, mode = AES.MODE_CBC)
flag_enc = cipher.encrypt(pad(flag.encode(), BLOCK_SIZE))

print(f"iv: {secret_iv.hex()}")

print(f"ct: {flag_enc.hex()}")

print("Enter messages to decrypt (in hex): ")

while True:
    res = input("> ")

    try:
        enc = bytes.fromhex(res)
        dec = decrypt(enc)
        print(dec.hex())
        
    except Exception as e:
        print(e)
        continue

This problem implements AES-PCBC mode, and during decryption, if the plaintext is in secret, it will be skipped; otherwise, it functions as a normal decryption oracle.

AES-PCBC encryption

AES-PCBC decryption

First, since there is no iv, we need to find a way to get the iv. We know that $ct_0=E(iv \oplus pt_0)$ , and if we send $(ct_0,ct_0)$ into the decryption oracle, the first block will be $pt_0$ , so it will be filtered out. However, $iv_1=ct_0 \oplus pt_0$ , so the output of the second block given by the oracle will be $o=(pt_0 \oplus ct_0) \oplus (iv \oplus pt_0)=ct_0 \oplus iv$ , thus we can get the iv by XORing.

Next, to get the first block of plaintext $pt_0$ , I sent $(ct_0,ct_1,ct_1)$ in, the first and second blocks will be filtered, but we only need to focus on the last block. The output will be $o=(pt_1 \oplus ct_1) \oplus (iv_1 \oplus pt_1)=iv_1 \oplus ct_1$ , where $iv_1$ is the iv used to encrypt the second block, which is $iv_1=pt_0 \oplus ct_0$ , so by XORing, we can get $pt_0$ .

After obtaining $pt_0$ , decrypting the subsequent blocks is not as complicated. Just send the $ct_i, i>0$ to the oracle in sequence. Note that $ct_i=E(pt_i \oplus iv_i)=E(pt_i \oplus ct_{i-1} \oplus pt_{i-1})$ , so the output will be $o=iv \oplus pt_i \oplus ct_{i-1} \oplus pt_{i-1}$ , and by XORing with the known information from the previous block, we can get $pt_i$ .

from pwn import process, remote
from Crypto.Cipher import AES
from hashlib import md5

# io = process(["python", "filter_plaintext.py"])
io = remote("challs.nusgreyhats.org", 32223)
io.recvuntil(b"secret: ")
secret_enc = bytes.fromhex(io.recvlineS().strip())
io.recvuntil(b"iv: ")
secret_iv = bytes.fromhex(io.recvlineS().strip())
io.recvuntil(b"ct: ")
flag_enc = bytes.fromhex(io.recvlineS().strip())


def decrypt(m: bytes):
    io.sendlineafter(b"> ", m.hex().encode())
    return bytes.fromhex(io.recvlineS().strip())


xor = lambda x, y: bytes(a ^ b for a, b in zip(x, y))
ct = [secret_enc[i : i + 16] for i in range(0, len(secret_enc), 16)]
iv0 = xor(decrypt(b"".join([ct[0]] * 2))[-16:], ct[0])
iv1 = xor(decrypt(b"".join([ct[0]] + [ct[1]] * 2))[-16:], ct[1])
pt0 = xor(iv1, ct[0])
pt1 = xor(xor(xor(decrypt(ct[1]), iv0), pt0), ct[0])
pt2 = xor(xor(xor(decrypt(ct[2]), iv0), pt1), ct[1])
pt3 = xor(xor(xor(decrypt(ct[3]), iv0), pt2), ct[2])
pt4 = xor(xor(xor(decrypt(ct[4]), iv0), pt3), ct[3])
secret_rec = pt0 + pt1 + pt2 + pt3 + pt4
assert len(secret_rec) == 80

secret_key = md5(secret_rec).digest()
cipher = AES.new(key=secret_key, iv=secret_iv, mode=AES.MODE_CBC)
flag = cipher.decrypt(flag_enc)
print(flag)
# grey{pcbc_d3crypt10n_0r4cl3_3p1c_f41l}

AES

from secrets import token_bytes
from aes import AES

FLAG = 'REDACTED'
password = token_bytes(16)
key = token_bytes(16)

AES = AES(key)
m = bytes.fromhex(input("m: "))
if (len(m) > 4096): exit(0)
print("c:", AES.encrypt(m).hex())

print("c_p:", AES.encrypt(password).hex())
check = input("password: ")
if check == password.hex():
    print('flag:', FLAG)

This AES problem is a modified version of AES, where the mix columns have been turned into a NO-OP, meaning that each input byte does not affect the others. Each input byte index corresponds to an output byte index, and each byte on the input has a fixed transformation to the output byte.

Therefore, by sending a $16 \times 256$ bytes input to the encryption oracle, covering all possible bytes at all positions, we can build an encryption and decryption table, and then use the table for encryption and decryption.

from secrets import token_bytes
from aes import AES
from pwn import process, remote

# io = process(["python", "server.py"])
io = remote("challs.nusgreyhats.org", 35100)


key = token_bytes(16)
aes = AES(key)

idx_map = {}
for i in range(16):
    pt = bytearray(b"a" * 16)
    ct1 = aes.encrypt(pt)
    pt[i] ^= 1
    ct2 = aes.encrypt(pt)
    diff_idx = next(i for i, (a, b) in enumerate(zip(ct1, ct2)) if a != b)
    idx_map[i] = diff_idx
print(idx_map)


pts = [bytes([i]) * 16 for i in range(256)]
pt = b"".join(pts)
io.sendline(pt.hex().encode())
io.recvuntil(b"c: ")
ct = bytes.fromhex(io.recvlineS().strip())
cts = [ct[i : i + 16] for i in range(0, len(ct), 16)]

enc_map = {}  # (idx, val) -> (idx, val)
dec_map = {}  # (idx, val) -> (idx, val)
for pt, ct in zip(pts, cts):
    for i, a in enumerate(pt):
        j = idx_map[i]
        b = ct[j]
        enc_map[(i, a)] = (j, b)
        dec_map[(j, b)] = (i, a)


def encrypt(enc_map, pt):
    ct = [0] * 16
    for i, a in enumerate(pt):
        j, b = enc_map[(i, a)]
        ct[j] = b
    return bytes(ct)


def decrypt(dec_map, ct):
    pt = [0] * 16
    for j, b in enumerate(ct):
        i, a = dec_map[(j, b)]
        pt[i] = a
    return bytes(pt)


io.recvuntil(b"c_p: ")
pwd_ct = bytes.fromhex(io.recvlineS().strip())
pwd_ct_blks = [pwd_ct[i : i + 16] for i in range(0, len(pwd_ct), 16)]
pwd_pt_blks = [decrypt(dec_map, cblk) for cblk in pwd_ct_blks]
pwd = b"".join(pwd_pt_blks)[:16]
io.sendline(pwd.hex().encode())
io.interactive()
# grey{mix_column_is_important_in_AES_ExB3Hf9q9I3m}

PRG

from secrets import token_bytes, randbits
from param import A 
import numpy as np

FLAG = 'REDACTED'

A = np.array(A)

def print_art():
    print(r"""
            />_________________________________
    [########[]_________________________________>
            \>
    """)
    
def bytes_to_bits(s):
    return list(map(int, ''.join(format(x, '08b') for x in s)))

def bits_to_bytes(b):
    return bytes(int(''.join(map(str, b[i:i+8])), 2) for i in range(0, len(b), 8))

def prg(length):
    x = token_bytes(8); r = token_bytes(8); k = token_bytes(8)
    x = np.array(bytes_to_bits(x)); r = np.array(bytes_to_bits(r)); k = np.array(bytes_to_bits(k))
    output = []
    for i in range(length * 8):
        output.append(sum(x) % 2)
        if (i % 3 == 0): x = (A @ x + r) % 2
        if (i % 3 == 1): x = (A @ x + k) % 2
        if (i % 3 == 2): x = (A @ x + r + k) % 2
    output = output
    return bits_to_bytes(output).hex()
    
def true_random(length):
    return token_bytes(length).hex()

def main():
    try:
        print_art()
        print("I try to create my own PRG")
        print("This should be secure...")
        print("If you can win my security game for 100 times, then I will give you the flag")
        for i in range(100):
            print(f"Game {i}")
            print("Output: ", end="")
            game = randbits(1)
            if (game): print(prg(16))
            else: print(true_random(16))
            guess = int(input("What's your guess? (0/1): "))
            if guess != game:
                print("You lose")
                return
        print(f"Congrats! Here is your flag: {FLAG}")
    except Exception as e:
        return

if __name__ == "__main__":
    main()

The above param.A is a $64 \times 64$ binary matrix, and the goal is to distinguish the output generated by prg and true_random.

Since prg looks very linear, my idea is to directly simulate its function symbolically, and then get a system $M [x \, r \, k]^T = output$ , and see if it has a solution. Although the output is only 128 bits, and there are 192 unknowns in $x,r,k$ , so it might seem that $\operatorname{span}(M) = \mathbb{F}_2^{128}$ and it might not be distinguishable, in reality, $\operatorname{rank}(M)=63$ , so the probability of a wrong distinction is $2^{-61}$ .

from sage.all import *
from pwn import process, remote
from param import A

# quick fix: https://github.com/sagemath/sage/issues/37837
from sage.rings.polynomial.multi_polynomial_sequence import (
    PolynomialSequence_generic,
    PolynomialSequence_gf2,
)

PolynomialSequence_gf2.coefficients_monomials = (
    PolynomialSequence_generic.coefficients_monomials
)


def bytes_to_bits(s):
    return list(map(int, "".join(format(x, "08b") for x in s)))


F = GF(2)
Asage = matrix(F, A)
PR = PolynomialRing(
    F,
    [f"x{i}" for i in range(64)]
    + [f"r{i}" for i in range(64)]
    + [f"k{i}" for i in range(64)],
)
x = vector(PR.gens()[:64])
r = vector(PR.gens()[64:128])
k = vector(PR.gens()[128:192])
syms = []
for i in range(16 * 8):
    syms.append(sum(x))
    if i % 3 == 0:
        x = Asage * x + r
    if i % 3 == 1:
        x = Asage * x + k
    if i % 3 == 2:
        x = Asage * x + r + k
M, _ = Sequence(syms).coefficients_monomials(sparse=False)
print(M.dimensions())
print(M.rank())

# io = process(["python", "server.py"])
io = remote("challs.nusgreyhats.org", 35101)
for rnd in range(100):
    print(rnd)
    io.recvuntil(b"Output: ")
    out = bytes.fromhex(io.recvlineS().strip())
    vs = vector(F, bytes_to_bits(out))
    try:
        M.solve_right(vs)
        io.sendline(b"1")
    except Exception:
        io.sendline(b"0")
io.interactive()
# grey{Not_so_easy_to_construct_a_secure_PRG_LaQSqprzmTjBZs8ygMkGuw}

IPFE

server.py:

from IPFE import IPFE, _FeDDH_C
from secrets import randbits

FLAG = 'REDACTED'

# Prime from generate_prime()
# To save server resource, we use a fix prime
p = 16288504871510480794324762135579703649765856535591342922567026227471362965149586884658054200933438380903297812918052138867605188042574409051996196359653039
q = (p - 1) // 2

n = 5
key = IPFE.generate(n, (p, q))
print("p:", key.p)
print("g:", key.g)
print("mpk:", list(map(int, key.mpk)))

while True:
    '''
    0. Exit
    1. Encrypt (You can do this yourself honestly)
    2. Generate Decryption Key
    3. Challenge
    '''
    option = int(input("Option: "))
    if (option == 0):
        exit(0)
    elif (option == 1):
        x = list(map(int, input("x: ").split()))
        c = IPFE.encrypt(x, key)
        print("g_r:", c.g_r)
        print("c:", list(map(int, c.c)))
    elif (option == 2):
        y = list(map(int, input("y: ").split()))
        g_r = int(input("g_r: "))
        dummy_c = _FeDDH_C(g_r, [])
        dk = IPFE.keygen(y, key, dummy_c)
        print("s_k:", int(dk.sk))
    elif (option == 3):
        challenge = [randbits(40) for _ in range(n)]
        c = IPFE.encrypt(challenge, key)
        print("g_r:", c.g_r)
        print("c:", list(map(int, c.c)))
        check = list(map(int, input("challenge: ").split()))
        if (len(check) == n and all([x == y for x, y in zip(challenge, check)])):
            print("flag:", FLAG)
        exit(0)

IPFE.py:

from Crypto.Util.number import getPrime, isPrime, inverse
from secrets import randbelow
from gmpy2 import mpz
from typing import List, Tuple

# References:
# https://eprint.iacr.org/2015/017.pdf

def generate_prime():
    while True:
        q = getPrime(512)
        p = 2 * q + 1
        if isPrime(p):
            return mpz(p), mpz(q)
        
def discrete_log_bound(a, g, bounds, p):
    cul = pow(g, bounds[0], p)
    for i in range(bounds[1] - bounds[0] + 1):
        if cul == a:
            return i + bounds[0]
        cul = (cul * g) % p
    raise Exception(f"Discrete log for {a} under base {g} not found in bounds ({bounds[0]}, {bounds[1]})")

class _FeDDH_MK:
    def __init__(self, g, n: int, p: int, q: int, mpk: List[int], msk: List[int]=None):
        self.g = g
        self.n = n
        self.p = p
        self.q = q
        self.msk = msk
        self.mpk = mpk

    def has_private_key(self) -> bool:
        return self.msk is not None

    def get_public_key(self):
        return _FeDDH_MK(self.g, self.n, self.p, self.q, self.mpk)
    
class _FeDDH_SK:
    def __init__(self, y: List[int], sk: int):
        self.y = y
        self.sk = sk

class _FeDDH_C:
    def __init__(self, g_r: int, c: List[int]):
        self.g_r = g_r
        self.c = c

    
class IPFE:
    @staticmethod
    def generate(n: int, prime: Tuple[int, int] = None):
        if (prime == None): p, q = generate_prime()
        else: p, q = prime
        g = mpz(randbelow(p) ** 2) % p
        msk = [randbelow(q) for _ in range(n)]
        mpk = [pow(g, msk[i], p) for i in range(n)]

        return _FeDDH_MK(g, n, p, q, mpk=mpk, msk=msk)

    @staticmethod
    def encrypt(x: List[int], pub: _FeDDH_MK) -> _FeDDH_C:
        if len(x) != pub.n:
            raise Exception("Encrypt vector must be of length n")
        
        r = randbelow(pub.q)
        g_r = pow(pub.g, r, pub.p)
        c = [(pow(pub.mpk[i], r, pub.p) * pow(pub.g, x[i], pub.p)) % pub.p for i in range(pub.n)]

        return _FeDDH_C(g_r, c)
    
    @staticmethod
    def decrypt(c: _FeDDH_C, pub: _FeDDH_MK, sk: _FeDDH_SK, bound: Tuple[int, int]) -> int:
        cul = 1
        for i in range(pub.n):
            cul = (cul * pow(c.c[i], sk.y[i], pub.p)) % pub.p
        cul = (cul * inverse(sk.sk, pub.p)) % pub.p
        return discrete_log_bound(cul, pub.g, bound, pub.p)
    
    @staticmethod
    def keygen(y: List[int], key: _FeDDH_MK, c: _FeDDH_C) -> _FeDDH_SK:
        if len(y) != key.n:
            raise Exception(f"Function vector must be of length {key.n}")
        if not key.has_private_key():
            raise Exception("Private key not found in master key")
        
        t = sum([key.msk[i] * y[i] for i in range(key.n)]) % key.q
        sk = pow(c.g_r, t, key.p)
        return _FeDDH_SK(y, sk)
    
if __name__ == "__main__":
    n = 10
    key = IPFE.generate(n)
    x = [i for i in range(n)]
    y = [i + 10 for i in range(n)]
    c = IPFE.encrypt(x, key)
    sk = IPFE.keygen(y, key, c)
    m = IPFE.decrypt(c, key.get_public_key(), sk, (0, 1000))
    expected = sum([a * b for a, b in zip(x, y)])
    assert m == expected

In short, this problem uses IPFE, a functional encryption scheme for inner products. The goal is to recover the original challenge after obtaining the encrypted result. It operates in a prime order subgroup of $\mathbb{F}_p$ , with the order and generator denoted as $(q,g)$ .

Generate master key:

pk_i = g^{sk_i}

Encrypt:

enc = (g_r, c) = (g^r, [pk_i^r \cdot g^{x_i}]) = (g^r, [g^{r \cdot sk_i + x_i}])

Keygen:

sk = g_r^t = g^{r \sum{sk_i \cdot y_i}}

Decrypt:

\begin{gather} u = sk^{-1} \cdot \prod{c_i^{y_i}} = sk^{-1} \cdot g^{\sum y_i r sk_i + x_i y_i} = g^{\sum x_i y_i} \\ \sum x_i y_i = \log_g u \end{gather}

The server provides a keygen oracle where you can specify $g_r, y$ for keygen, and the attack method for this oracle is to specify a non-quadratic residue $g_r$ , with order $2q=p-1$ , and then use $y=[2^i \, 0 \, 0 \, 0 \, 0]$ to get $sk_0$ using the LSB oracle under $\mod{q}$ . Using the same method, all $sk_i$ can be obtained.

During the challenge, $g^{x_i}$ can be obtained, and since it is only 40 bits, it can be solved directly using sage discrete_log.

from pwn import process, remote
import ast
from sage.all import GF, discrete_log

p = 16288504871510480794324762135579703649765856535591342922567026227471362965149586884658054200933438380903297812918052138867605188042574409051996196359653039
q = (p - 1) // 2
n = 5

# io = process(["python", "server.py"])
io = remote("challs.nusgreyhats.org", 35102)
io.recvuntil(b"g: ")
g = int(io.recvlineS().strip())
io.recvuntil(b"mpk: ")
mpk = ast.literal_eval(io.recvlineS().strip())


def oracle(g_r, y):
    io.sendline(b"2")
    io.sendline(" ".join(map(str, y)).encode())
    io.sendline(str(g_r).encode())
    io.recvuntil(b"s_k: ")
    return int(io.recvlineS().strip())


def recover(oracle, idx):
    g_r = 7
    assert pow(g_r, q, p) != 1
    a = pow(2, -1, q)
    bits = []
    for i in range(q.bit_length()):
        y = [0, 0, 0, 0, 0]
        y[idx] = pow(2, -i, q)
        r = int(pow(oracle(g_r, y), q, p) != 1)  # lsb
        k = sum((pow(a, i + 1, q) * b) % q for i, b in enumerate(bits[::-1])) % q
        bits.append((r - k) % 2)
    return sum(b << i for i, b in enumerate(bits))


def batch_oracle(g_r_ar, y_ar):
    for g_r, y in zip(g_r_ar, y_ar):
        io.sendline(b"2")
        io.sendline(" ".join(map(str, y)).encode())
        io.sendline(str(g_r).encode())
    sk_ar = []
    for _ in range(len(g_r_ar)):
        io.recvuntil(b"s_k: ")
        sk_ar.append(int(io.recvlineS().strip()))
    return sk_ar


def recover_batch(batch_oracle, idx):
    g_r = 7
    assert pow(g_r, q, p) != 1
    a = pow(2, -1, q)
    ys = []
    for i in range(q.bit_length()):
        y = [0, 0, 0, 0, 0]
        y[idx] = pow(2, -i, q)
        ys.append(y)
    sk_ar = batch_oracle([g_r] * len(ys), ys)
    bits = []
    for i in range(q.bit_length()):
        r = int(pow(sk_ar[i], q, p) != 1)  # lsb
        k = sum((pow(a, i + 1, q) * b) % q for i, b in enumerate(bits[::-1])) % q
        bits.append((r - k) % 2)
    return sum(b << i for i, b in enumerate(bits))


msk = []
for i in range(n):
    # sk = recover(oracle, i)
    sk = recover_batch(batch_oracle, i)
    assert pow(g, sk, p) == mpk[i]
    msk.append(sk)
    print(i, sk)

io.sendline(b"3")
io.recvuntil(b"g_r: ")
g_r = int(io.recvlineS().strip())
io.recvuntil(b"c: ")
c = ast.literal_eval(io.recvlineS().strip())

gxs = []
for i in range(n):
    gsr = pow(g_r, msk[i], p)
    gx = pow(c[i] * pow(gsr, -1, p), 1, p)
    gxs.append(gx)
    print(i, gx)

F = GF(p)

challenge = []
for i in range(n):
    x = discrete_log(F(gxs[i]), F(g), bounds=(0, 2**40))
    challenge.append(x)
    print(i, x)

io.sendline(" ".join(map(str, challenge)).encode())
io.interactive()
# grey{catostrophic_failure_7eE37WLLdYgg}

Coding

#!/usr/local/bin/python

from secrets import randbelow
from numpy.linalg import matrix_rank
import numpy as np

FLAG = 'REDACTED'

n = 100
k = int(n * 2)
threshold = 0.05

M = []

def matrix_to_bits(G):
    return "".join([str(x) for x in G.flatten()])

def bits_to_matrix(s):
    assert len(s) == n * k
    return np.array([[int(s[i * k + j]) for j in range(k)] for i in range(n)]) % 2

def setupMatrix(G):
    assert G.shape == (n, k)
    global M

    perm = np.array([i for i in range(k)])
    np.random.shuffle(perm)
    PermMatrix = []
    for i in range(k):
        row = [0 for _ in range(k)]
        row[perm[i]] = 1
        PermMatrix.append(row)
    PermMatrix = np.array(PermMatrix)

    while True:
        S = np.array([[randbelow(2) for _ in range(n)] for i in range(n)])        
        if matrix_rank(S) == n:
            break

    M = (S @ G @ PermMatrix) % 2

def initialize():
    G = np.array([[randbelow(2) for _ in range(k)] for i in range(n)])
    setupMatrix(G)

def encrypt(m):
    original = (m @ M) % 2

    noise = [0 for _ in range(k)]
    for i in range(k):
        if randbelow(1000) < threshold * 1000:
            noise[i] = 1
    noise = np.array(noise)

    ciphertext = (original + noise) % 2
    return ciphertext

initialize()
print("M:", matrix_to_bits(M))

while True:
    '''
    0. Exit
    1. Set Matrix
    2. Encrypt (You can do this yourself honestly)
    3. Challenge
    '''
    option = int(input("Option: "))
    if (option == 0):
        exit(0)
    elif (option == 1):
        G = bits_to_matrix(input("G: ").strip()) % 2
        setupMatrix(G)
        print("M:", matrix_to_bits(M))
    elif (option == 2):
        m = np.array([randbelow(2) for _ in range(n)])
        print("m:", matrix_to_bits(m))
        print("c:", matrix_to_bits(encrypt(m)))
    elif (option == 3):
        count = 0
        for _ in range(200):
            print("Attempt:", _)
            challenge = np.array([randbelow(2) for _ in range(n)])
            check_arr = []
            print("c:", matrix_to_bits(encrypt(challenge)))
            for i in range(20):
                check = input("challenge: ").strip()
                check_arr.append(check)
            if matrix_to_bits(challenge) in check_arr:
                count += 1
                print("Correct!")
            else:
                print("Incorrect!")
        print(f"You got {count} out of 200")
        if (count >= 120):
            print("flag:", FLAG)
        else:
            print("Failed")
        exit(0)
    else:
        print("Invalid option")

This problem is about McEliece, where the generator $G$ can be specified, but it will be combined with the server’s randomly generated $S,P$ to form $M=SGP$ . The goal is to efficiently decode $c=mM+e$ , with the noise amount being around $200 \times 0.05 = 10$ , and using a binomial distribution to capture $\pm 2\sigma$ , it is around $5$ to $15$ .

I treated $M$ as a $n,k=200,100$ linear code and found that sage’s LeeBrickellISDAlgorithm can efficiently decode within this error range, with a timeout at most.

from sage.all import *
from sage.coding.linear_code import LinearCode
from sage.coding.information_set_decoder import LeeBrickellISDAlgorithm
from pwn import process, remote, context
import signal

n = 100
k = int(n * 2)
threshold = 0.05
F = GF(2)


def bits_to_matrix(s):
    assert len(s) == n * k
    return matrix(F, [[int(s[i * k + j]) for j in range(k)] for i in range(n)])


def timed_call(fn, args, timeout=1):
    def handler(signum, frame):
        raise TimeoutError()

    signal.signal(signal.SIGALRM, handler)
    signal.alarm(timeout)
    try:
        return fn(*args)
    finally:
        signal.alarm(0)


# io = process(["python", "server.py"])
io = remote("challs.nusgreyhats.org", 35103)
io.recvuntil(b"M: ")
M_str = io.recvlineS().strip()
M = bits_to_matrix(M_str)
assert M.rank() == n, ":("
C = LinearCode(M)
D = LeeBrickellISDAlgorithm(C, decoding_interval=(5, 15))
io.sendline(b"3")

correct_cnt = 0
for rnd in range(200):
    print(rnd)
    io.recvuntil(b"c: ")
    c_str = io.recvlineS().strip()
    ct = vector(F, [int(x) for x in c_str])
    try:
        if correct_cnt >= 120:
            raise TimeoutError()
        dec = timed_call(D.decode, (ct,), timeout=1)
        print("noise", ct - dec)
        sol = M.solve_left(dec)
        sol_str = "".join([str(x) for x in sol])
        sols = [sol_str] * 20
        print(sol_str)
    except TimeoutError:
        print("timeout")
        dummy = "1" * n
        sols = [dummy] * 20
    io.recvuntil(b"challenge: ")
    io.sendline("\n".join(sols).encode())
    io.recvuntil(b"challenge: " * 19)
    res = io.recvline()
    print(res)
    correct_cnt += int(res == b"Correct!\n")
    print(f"{correct_cnt}/{rnd + 1}")
io.interactive()
# grey{what_linear_code_did_you_use?_zcUQenJEv4wXNRYxB5pPkH}

Curve

from param import p, b, n
from secrets import randbelow
from hashlib import shake_128

def encrypt(msg, key):
    y = shake_128("".join(map(str, key)).encode()).digest(len(msg))
    return bytes([msg[i] ^^ y[i] for i in range(len(msg))])
    
FLAG = b'REDACTED'
m = 150

F1 = GF(p)
F2.<u> = GF(p^2)

hidden = [randbelow(2) for _ in range(m)]
factors = []
output = []

for _ in range(900):
    E1 = EllipticCurve(GF(p), [0, b])
    E2 = EllipticCurve(F2, [0, F2.random_element()])

    g = E1.random_point()
    h = E2.random_point()

    factor = [randbelow(2) for _ in range(m)]
    k = sum([hidden[i] * factor[i] for i in range(m)]) % 2
    factors.append(factor)
    
    if (k):
        x, y, z = [randbelow(n) for _ in range(3)]
    else:
        x, y = [randbelow(n) for _ in range(2)]
        z = x * y

    output.append([g, x * g, y * g, z * g, h, x * h])

output = [[(point[0], point[1]) for point in row] for row in output]

f = open("output.txt", "w")
f.write(f"c='{encrypt(FLAG, hidden).hex()}'\n")
f.write(f"{factors=}\n")
f.write(f"{output=}\n")

This problem is the most interesting and difficult crypto problem in this CTF. First, we have

\begin{gather} E_1(\mathbb{F}_p): y^2 = x^3 + b \\ E_2(\mathbb{F}_{p^2}): y^2 = x^3 + r \end{gather}

and random $g \in E_1, h \in E_2$ .

Where $b=6$ is fixed, and $r \in \mathbb{F}_{p^2}$ is random. The factor and hidden parts are a $\mathbb{F}_2$ linear system that can be ignored for now, focusing on the cases where $k=0$ or $k=1$ , resulting in $z=xy$ or $z\neq xy$ .

It provides $g,xg,yg,zg,h,xh$ , and the goal is to distinguish between $z=xy$ or $z\neq xy$ to get $k$ , and then solve the linear system to get hidden.

To determine this, my idea is to use pairing, because:

e(xg,yg)=e(g,xyg) \overset{?}{=} e(g,zg)

However, pairing for linearly independent $P,Q$ ( $\exists x ,\, P=xQ$ ) results in $e(P,Q)=e(P,P)^x=1$ , so it cannot be done with $g$ on $E_1$ alone. Therefore, I hope that $h$ on $E_2$ is somewhat linearly independent of $g$ , but pairing requires both points to be on the same curve.

First, check the parameters of the problem:

p = 2956673455706017732726395787961404603421884201335599271480572766387023983052387933523497453145098834977111426152922969191412599940148797425165972377716091055492258826885933065623708772008210452334640417645070465335307327936488470721870990368244784905723647386940034701846717718881287895717648756082302396599141
n = 2956673455706017732726395787961404603421884201335599271480572766387023983052387933523497453145098834977111426152922969191412599940148797425165972377716091001116956936174395309176601513634561168168290944226676456373026396891854015965003822945171727063054140667291090754603076704996926282408059289968479821894541
b = 6

It can be seen that $j(E_1)=j(E_2)=0$ , so if they are on the same field $K$ , $E_1$ and $E_2$ are isomorphic. Also, $n=\# E_1$ satisfies $p^{12}-1 \equiv 0 \pmod{n}$ , meaning the embedding degree of $E_1$ is $k=12$ , so using $K=\mathbb{F}_{p^{12}}$ , pairing can be efficiently done on $E_1(K)$ .

If you have experience, you might find it very similar to BLS12-381

Converting points on $E_1(\mathbb{F}_p)$ to $E_1(K)$ is easy because $(x,y) \in E_1(\mathbb{F}_p)$ naturally satisfies $y^2=x^3+b$ on $K$ . The difficulty lies in converting points on $E_2$ to $K$ .

I did this by noting that $\mathbb{F}_{p^2}=\mathbb{F}_p[x]/f(x)$ , where $f(x)$ is an irreducible polynomial, and the field generator $u$ satisfies $f(u)=0$ . For example, according to the problem’s sage code, $f(x)=x^2+x-3$ , so $u^2+u-3=0$ .

Then $K=\mathbb{F}_{p^{12}}=\mathbb{F}_p[x]/g(x)$ , where $g(x)$ is another degree 12 irreducible polynomial. To convert $u$ to $K$ , find the root $u' \in K$ of $f(t)=t^2+t-3$ in $K[t]$ , and replace $u$ with $u'$ in the original $h,xh$ . There will also be an $r'$ obtained by replacing $r$ with $u \rightarrow u'$ , and that curve is $E_2(\mathbb{F}_{p^{12}})$ .

Next, since $y^2=x^3+b_1$ and $y^2=x^3+b_2$ have the same j-invariant, they are isomorphic. This can be done using sage’s isomorphism_to or directly using $(x,y) \rightarrow (u^2 x, u^3 y), b_1 u^6=b_2$ .

Thus, we can convert all $g,xg,yg,zg,h,xh$ to $E_1(K)$ , and use tate pairing to determine $z \overset{?}{=} xy$ to get $k$ .

One thing to note is that the converted $g,h$ may not be linearly independent, so check $e(\phi(g), \pi(h)) \neq 1$ .

from hashlib import shake_128

def encrypt(msg, key):
    y = shake_128("".join(map(str, key)).encode()).digest(len(msg))
    return bytes([msg[i] ^^ y[i] for i in range(len(msg))])

proof.arithmetic(False)

p = 2956673455706017732726395787961404603421884201335599271480572766387023983052387933523497453145098834977111426152922969191412599940148797425165972377716091055492258826885933065623708772008210452334640417645070465335307327936488470721870990368244784905723647386940034701846717718881287895717648756082302396599141
n = 2956673455706017732726395787961404603421884201335599271480572766387023983052387933523497453145098834977111426152922969191412599940148797425165972377716091001116956936174395309176601513634561168168290944226676456373026396891854015965003822945171727063054140667291090754603076704996926282408059289968479821894541
b = 6

F1 = GF(p)
F2.<u> = GF(p^2)
E1 = EllipticCurve(F1, [0, b])

k = 12
K.<a> = GF(p^k)
PR.<t> = PolynomialRing(K)
uk = K(str(F2.modulus().change_ring(ZZ)(t).roots(multiplicities=False)[0]))
EK = EllipticCurve(K, [0, b])

with open('output.txt') as f:
    exec(f.read())
flag_ct = bytes.fromhex(c)

lhs = []
rhs = []
iso_cache = {}
for i, (g, xg, yg, zg, h, xh) in enumerate(output):
    g = E1(g)
    xg = E1(xg)
    yg = E1(yg)
    zg = E1(zg)
    b1 = h[1] ** 2 - h[0] ** 3
    b2 = xh[1] ** 2 - xh[0] ** 3
    assert b1 == b2
    E2 = EllipticCurve(F2, [0, b1])
    h = E2(h)
    xh = E2(xh)


    def E2_to_EK(P):
        x, y = P.xy()
        x = x.polynomial().change_ring(ZZ)(uk)
        y = y.polynomial().change_ring(ZZ)(uk)
        return x, y

    x1, y1 = E2_to_EK(h)
    x2, y2 = E2_to_EK(xh)
    # aa, bb = matrix([[x1, 1], [x2, 1]]).solve_right(
    #     vector([y1**2 - x1**3, y2**2 - x2**3])
    # )
    # EK2 = EllipticCurve(K, [aa, bb])
    # phi = EK2.isomorphism_to(EK) if (aa, bb) not in iso_cache else iso_cache[(aa, bb)]
    # iso_cache[(aa, bb)] = phi
    # hk = phi(EK2(x1, y1))
    # xhk = phi(EK2(x2, y2))
    aa = 0
    bb = y1 ** 2 - x1 ** 3
    uuu = (b / bb).nth_root(6)
    hk = EK(x1 * uuu**2, y1 * uuu**3)
    xhk = EK(x2 * uuu**2, y2 * uuu**3)
    gk = EK(g)
    xgk = EK(xg)
    ygk = EK(yg)
    zgk = EK(zg)
    if gk.tate_pairing(hk, n, 12) == 1:
        print(":(", i)
        continue
    k = int(ygk.tate_pairing(xhk, n, 12) != zgk.tate_pairing(hk, n, 12))
    lhs.append(factors[i])
    rhs.append(k)
    print("collected", i)

sol = list(matrix(GF(2), lhs).solve_right(vector(rhs)))
print(encrypt(flag_ct, sol).decode())
# grey{tate_ate_weil_VfWZTKzMmgYhpEL7xvRwFu}

Filter Ciphertext#

Filter Plaintext#

AES#

PRG#

IPFE#

Coding#

Curve#

Filter Ciphertext

Filter Plaintext

AES

PRG

IPFE

Coding

Curve