💬

SECCON CTF 2023 Finals muck-a-mac, v_v_m_m_v_m_m writeup

2023/12/28に公開

introduction

I wrote two challenges for SECCON CTF 2023 Finals.
they are "muck-a-mac" and "v_v_m_m_v_m_m"
I think both challenges are easy to solve if you know cryptosystem well.
The fact that there was little novelty in these challenges is my lack of ability. I hope to become stronger by next year and make challenges that are still difficult even if I know how cryptosystem work.

However, if they did not know those cryptosystems, I believe it would be an educational.
I would be more than happy if you could gain knowledge through this CTF that you did not know.

muck-a-mac

problem

import os
from base64 import b64encode, b64decode
from Crypto.Cipher import ChaCha20_Poly1305
from Crypto.Util.strxor import strxor
from Crypto.Util.number import long_to_bytes, bytes_to_long
import string
import random
import secrets
import signal

signal.alarm(300)

def encrypt(key, aad, plaintext, nonce):
    cipher =  ChaCha20_Poly1305.new(key=key, nonce=nonce)
    cipher.update(aad)
    ciphertext, mac = cipher.encrypt_and_digest(plaintext)
    return ciphertext, mac

class Challenge:
    def __init__(self):
        self.key = secrets.token_bytes(32)
        self.nonce = secrets.token_bytes(12)
        # debug

        self.plaintext = b""
        for i in range(4):
            self.plaintext += b"\x00"*13 + secrets.token_bytes(3)

        self.aad = b""
        for i in range(16):
            self.aad += bytes([random.choice(bytes(string.printable, 'ascii'))])
        

        self.is_get_ciphertext = False
        self.is_default = False
        self.is_change_aad = False
        self.is_xor_plaintext = False
        self.is_change_length = False
    
    def get_availables(self):
        res = ""
        if not self.is_get_ciphertext:
            res += f"[1]: get_ciphertext\n"
        if not self.is_default:
            res += f"[2]: default\n"
        if not self.is_change_aad:
            res += f"[3]: change_aad\n"
        if not self.is_xor_plaintext:
            res += f"[4]: xor_plaintext\n"
        if not self.is_change_length:
            res += f"[5]: change_length\n"
        res += f"[6]: answer\n"
        return res

    def get_ciphertext(self, plaintext):
        if self.is_get_ciphertext:
            return None
        self.is_get_ciphertext = True

        ciphertext, _ = encrypt(self.key, self.aad, plaintext, self.nonce)
        return ciphertext
    
    def default(self):
        if self.is_default:
            return None
        self.is_default = True

        _, mac = encrypt(self.key, self.aad, self.plaintext, self.nonce)
        return mac
    
    def change_aad(self, aad):
        if self.is_change_aad:
            return None
        self.is_change_aad = True
        _, mac = encrypt(self.key, aad, self.plaintext, self.nonce)
        return mac

    def xor_plaintext(self, target):
        if self.is_xor_plaintext:
            return None
        self.is_xor_plaintext = True
        _, mac = encrypt(self.key, self.aad, strxor(self.plaintext, target), self.nonce)
        return mac

    def change_length(self,l,r):
        if self.is_change_length or l < 0 or r < 0:
            return None
        self.is_change_length = True

        _, mac = encrypt(self.key, self.aad, self.plaintext[l:r], self.nonce)
        return mac

    def answer(self, ans):
        return self.plaintext == ans
        
def challenge():
    chal = Challenge()
    for count in range(6):
        print(chal.get_availables())
        menu = int(input("[menu]> "))

        if menu == 1:
            plaintext = b64decode(input("plaintext:"))
            print("(*'-') <", b64encode(chal.get_ciphertext(plaintext)).decode('utf-8'))
            pass

        if menu == 2:
            print("(*'-') < ", b64encode(chal.default()).decode('utf-8'))
            pass

        if menu == 3:
            aad = b64decode(input("aad:"))
            print("(*'-') <", b64encode(chal.change_aad(aad)).decode('utf-8'))
            pass

        if menu == 4:
            target = b64decode(input("target:"))
            print("(*'-') <", b64encode(chal.xor_plaintext(target)).decode('utf-8'))
            pass

        if menu == 5:
            l = int(input("l:"))
            r = int(input("r:"))
            print("(*'-') <", b64encode(chal.change_length(l,r)).decode('utf-8'))
            pass

        if menu == 6:
            answer = b64decode(input("answer:"))
            return chal.answer(answer)

success_cnt = 0
for i in range(100):
    if challenge():
        print(f"(*'-') <challenge{i} success")
        success_cnt += 1
    else:
        print("(*'-') <fail")
        break

if success_cnt == 100:
    print("(*'-') <perfect! here you are")
    flag = os.getenv("FLAG", "SECCON{dummyflagdummyflagdummyf}")
    print("(*'-') <flag is", flag)

how to solve

The goal of this problem is to recover the plaintext from multiple macs and a single ciphertext.

ChaChaPoly is structured as shown in the following figure (ref: https://en.wikipedia.org/wiki/ChaCha20-Poly1305).
In this problem, we need to find r,s,aad,ciphertext from mac.

this explanation will the following flow of the solution.

solve the internal parameter r of ChaChaPoly
solve aad
solve the internal parameter s of ChaChaPoly
solve the ciphertext c
solve the plaintext from the ciphertext

prepairing to solve

Poly1305(mac) is calculated by following equation.

\mathrm{mac} = ((a r^6 + c_1 r^5 + c_2 r^4 + c_3 r^3 + c_4 r^2 + L r) \mod 2^{130} - 5) + s \\

where:

\begin{aligned} c_i &: \mathrm{ciphertext}[i:i+16] \\ a &: \mathrm{aad(16 bytes)} \\ r,s &: \mathrm{one\ time\ key(but\ fixed\ in\ this\ challenge)} \\ L &: \mathrm{len}(\mathrm{aad}) + \mathrm{len}(\mathrm{ciphertext}) \end{aligned}

However, please PAY CLOSE ATTENSION TO THE FOLLOWING TWO POINTS.

poly1305 uses little endian
Mac is converted into a byte string using little endian, and then truncated to 16 bytes.

Therefore, all mac contain several bits error

1. solve the internal parameter 'r' of ChaChaPoly

To recover r, we can use menu 2 and menu 4

\begin{aligned} \mathrm{mac2} &= ((a r^6 + c_1 r^5 + c_2 r^4 + c_3 r^3 + c_4 r^2 + L r) \mod 2^{130} - 5) + s + \mathrm{error}\\ \mathrm{mac4} &= ((a r^6 + c_1 r^5 + c_2 r^4 + c_3 r^3 + (c_4 \pm 1) r^2 + L r) \mod 2^{130} - 5) + s + \mathrm{error} \end{aligned}

then,

\mathrm{mac2} - \mathrm{mac4} = r^2 + \mathrm{error}

You can find candidates for r using the source code below.

def solve_r(tag2, tag4):
    rs = []
    p = (1<<130) - 5
    K = GF(p)

    for diff in range(-(2**5),2**5):
        d = (diff << (8*16))
        rs.extend(K(tag4-tag2+d).nth_root(2, all=True) + K(tag2-tag4+d).nth_root(2, all=True) )

    rs = list(set(rs))
    return rs
    
bit_flip_mac = le_bytes_to_num(xor_plaintext(io, b'\x00'*(16*3) + b'\x01' + b'\x00'*15))
default_mac = le_bytes_to_num(default(io))
rs = solve_r(default_mac, bit_flip_mac)

2. solve 'aad'

To recover aad, we can use menu 3, menu 2.

\begin{aligned} \mathrm{mac2} &= ((a r^6 + c_1 r^5 + c_2 r^4 + c_3 r^3 + c_4 r^2 + L r) \mod 2^{130} - 5) + s + \mathrm{error}\\ \mathrm{mac3} &= ((a_2 r^6 + c_1 r^5 + c_2 r^4 + c_3 r^3 + c_4 r^2 + L r) \mod 2^{130} - 5) + s + \mathrm{error} \end{aligned}

where

a_2: \mathrm{`aad`\ givened\ by\ you}

then,

\mathrm{mac3} - \mathrm{mac2} = (a - a_2) r^6 + \mathrm{error}

In addition, aad( $=a$ ) is printable in this challenge.

self.aad = b""
for i in range(16):
    self.aad += bytes([random.choice(bytes(string.printable, 'ascii'))])

so, you can recover $a$ by using the source code below.

def solve_a(rval, aad_mac, default_mac, myaad):
    res = []
    for diff in range(-(2**5),2**5):
        d = (diff << (8*16))
        p = (1<<130) - 5
        aad = (le_bytes_to_num(myaad + pad16(myaad) + b'\x01')*rval^6 - aad_mac + default_mac + d)*pow(rval,-6,p)
        if all(char in printable_chars for char in num_to_16_le_bytes(int(aad))):
            res.append(int(aad))
    return res
    
myaad = b"0000000000000000"
default_mac = le_bytes_to_num(default(io))
aad_mac = le_bytes_to_num(change_aad(io, myaad))
    
for r in rs:
    for a in solve_a(r, aad_mac, default_mac, myaad):
        ras.append((r,a))

3. solve the internal parameter 's' of ChaChaPoly

In this challenge, we can get zero length ciphertext by menu 5.

\begin{aligned} \mathrm{mac5} &= ((a r^2 + L r) \mod 2^{130} - 5) + s + \mathrm{error} \end{aligned}

So, you can recover $s$ by using this source code.

def solve_s(rval,aad,zero_length_mac):
    mac_data = aad + pad16(aad)
    mac_data += num_to_8_le_bytes(len(aad))
    mac_data += num_to_8_le_bytes(0)
    p = (1<<130) - 5
    r = rval

    a = 0
    for i in range(1, math.ceil(len(mac_data)/16) + 1):
        n = le_bytes_to_num(mac_data[(i-1)*16 : i*16] + b'\x01')
        a += n
        a = r * a
    # a += sval
    poly3 = a-zero_length_mac
    s = -poly3
    return int(s%p)
    
zero_length_mac = le_bytes_to_num(change_length(io, 0, 0))
rases = []
zero_length_mac_cand = []
    for i in range(2**5):
        zero_length_mac_cand.append((i << (8*16)) + zero_length_mac)
for ra in ras:
    for mac in zero_length_mac_cand:
        r,a = ra
        s = solve_s(r,num_to_16_le_bytes(a),mac)
        rases.append((r,a,s))

4. solve the ciphertext 'c'

plaintext is generated by following code in this challenge.
From this, we can see that the upper 13 bytes are known.

self.plaintext = b""
for i in range(4):
    self.plaintext += b"\x00"*13 + secrets.token_bytes(3)

Moreover, if the key and nonce are fixed, ChaCha20 generates ciphertext by always taking xor the same value for the plaintext.

the image is described below:

ciphertext is image. same char means same value.

plaintext1 : 0000000000000???0000000000000???0000000000000???0000000000000???
ciphertext1: abcdefghijklm???qrstuvwxyzABC???GHIJKLMNOPQRS???WXYZ!@#$%^&*(???
(ciphertext1 = plaintext1 ^ key)

plaintext2 : 0000000000000000000000000000000000000000000000000000000000000000
ciphertext2: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+
(ciphertext2 = plaintext2 ^ key)

in other wards, we can say that the ciphertext is known except where indicated by "?".

Recalling that mac is generated by the following equation, it can be solved by LLL, since $c$ and "error" is unknown.

\mathrm{mac} = ((a r^6 + c_1 r^5 + c_2 r^4 + c_3 r^3 + c_4 r^2 + L r) \mod 2^{130} - 5) + s + \mathrm{error} \\

Note here that $r$ , $a$ , and $s$ have multiple candidates.
In my solution, the ERROR was small enough that I brute-forced it.

def solve_c(tag, ciphertext_zero, aad, r, s):
    p = (1<<130) - 5
    K = GF(p)
    tag -= K(r^5*le_bytes_to_num(ciphertext_zero[0:13]+b'\x00'*3) + r^4*le_bytes_to_num(ciphertext_zero[16:29]+b'\x00'*3) + r^3*le_bytes_to_num(ciphertext_zero[32:45]+b'\x00'*3) + r^2*le_bytes_to_num(ciphertext_zero[48:61]+b'\x00'*3))
    constant = s-tag
    memo = le_bytes_to_num(num_to_8_le_bytes(16) + num_to_8_le_bytes(16*4) + b'\x01')
    constant += memo * r
    memo = le_bytes_to_num(aad + pad16(aad) + b'\x01')
    constant += memo * r^6
    constant = K(constant)

    mat = [
        [r^5*(2^104),r^4*(2^104),r^3*(2^104),r^2*(2^104),-constant,p],
        [1/2^100,0,0,0,0,0],
        [0,1/2^100,0,0,0,0],
        [0,0,1/2^100,0,0,0],
        [0,0,0,1/2^100,0,0],
        [0,0,0,0,2**24/2^100,0],
    ]

    mat = matrix(QQ, mat).transpose()

    res = []
    for lll in mat.LLL():
        if abs(lll[-1]) == 2^24/2^100:
            flag = True
            for v in lll[1:5]*2^100:
                if abs(v) >= 2^25:
                    flag = False
            if flag:
                res.append(lll[1:5]*2^100)

    return res
    
for ras in rases:
    for i in range(2**5):
        r,a,s = ras
        tag = (i << (8*16)) + default_mac
        c = solve_c(tag, ciphertext_zero, num_to_16_le_bytes(a), int(r), int(s))

        if len(c) > 0:
            for t in c:
                plaintexts = []
                for j in range(4):
                    plaintexts.append(strxor(ciphertext_zero[j*16+13:(j+1)*16], struct.pack('<Q', abs(t[j]))[:3]))

                print("ans:", plaintexts)
                answer = b""
                for plaintext in plaintexts:
                    answer += b"\x00"*13+plaintext

                print(send_answer(io, answer))
                return

5. solve the plaintext from the ciphertext

then, you can get ciphertext.
But you want to get plaintext right?
Please remember this equation.

ciphertext1 = plaintext1 ^ key
ciphertext2 = plaintext2 ^ key

you got pair of ciphertext and plaintext by menu 1.
So, you can get key and you can get plaintext immediatly.

full source code

from pwn import remote
from base64 import b64decode, b64encode
import struct   
import string
from tqdm import tqdm
from Crypto.Util.strxor import strxor
import os

printable_chars = bytes(string.printable, 'ascii')

def pad16(x: bytes) -> bytes:
    if len(x) % 16 == 0: return b''
    return b'\x00' * (16 - (len(x) % 16))

def le_bytes_to_num(byte) -> int:
    res = 0
    for i in range(len(byte) - 1, -1, -1):
        res <<= 8
        res += byte[i]
    return res

def num_to_16_le_bytes(num: int) -> bytes:
    res = []
    for i in range(16):
        res.append(num & 0xff)
        num >>= 8
    return bytearray(res)

def num_to_8_le_bytes(num: int) -> bytes:
    return struct.pack('<Q', num)

def get_ciphertext(io, plaintext):
    io.recvuntil('[menu]> ')
    io.sendline('1')
    io.sendline(b64encode(plaintext))
    io.recvuntil("(*'-') <")
    resp = io.recvline().strip()

    return b64decode(resp)

def default(io):
    io.recvuntil('[menu]> ')
    io.sendline('2')
    io.recvuntil("(*'-') <")
    resp = io.recvline().strip()
    return b64decode(resp)

def change_aad(io, aad):
    io.recvuntil('[menu]> ')
    io.sendline('3')
    io.sendline(b64encode(aad))
    io.recvuntil("(*'-') <")
    resp = io.recvline().strip()
    return b64decode(resp)

def xor_plaintext(io, target):
    io.recvuntil('[menu]> ')
    io.sendline('4')
    io.sendline(b64encode(target))
    io.recvuntil("(*'-') <")
    resp = io.recvline().strip()

    return b64decode(resp)

def change_length(io,l,r):
    io.recvuntil('[menu]> ')
    io.sendline('5')
    io.sendline(str(l))
    io.sendline(str(r))
    io.recvuntil("(*'-') <")
    resp = io.recvline().strip()
    return b64decode(resp)

def send_answer(io, ans):
    io.recvuntil('[menu]> ')
    io.sendline('6')
    io.sendline(b64encode(ans))
    io.recvuntil("(*'-') <")
    resp = io.recvline().strip()
    return resp

def solve_r(tag2, tag4):
    rs = []
    p = (1<<130) - 5
    K = GF(p)

    for diff in range(-(2**5),2**5):
        d = (diff << (8*16))
        rs.extend(K(tag4-tag2+d).nth_root(2, all=True) + K(tag2-tag4+d).nth_root(2, all=True) )

    rs = list(set(rs))
    return rs

def solve_a(rval, aad_mac, default_mac, myaad):
    res = []
    for diff in range(-(2**5),2**5):
        d = (diff << (8*16))
        p = (1<<130) - 5
        aad = (le_bytes_to_num(myaad + pad16(myaad) + b'\x01')*rval^6 - aad_mac + default_mac + d)*pow(rval,-6,p)
        if all(char in printable_chars for char in num_to_16_le_bytes(int(aad))):
            res.append(int(aad))
    return res

def solve_s(rval,aad,zero_length_mac):
    mac_data = aad + pad16(aad)
    mac_data += num_to_8_le_bytes(len(aad))
    mac_data += num_to_8_le_bytes(0)
    p = (1<<130) - 5
    r = rval

    a = 0
    for i in range(1, math.ceil(len(mac_data)/16) + 1):
        n = le_bytes_to_num(mac_data[(i-1)*16 : i*16] + b'\x01')
        a += n
        a = r * a
    # a += sval
    poly3 = a-zero_length_mac
    s = -poly3
    return int(s%p)

def solve_c(tag, ciphertext_zero, aad, r, s):
    p = (1<<130) - 5
    K = GF(p)
    tag -= K(r^5*le_bytes_to_num(ciphertext_zero[0:13]+b'\x00'*3) + r^4*le_bytes_to_num(ciphertext_zero[16:29]+b'\x00'*3) + r^3*le_bytes_to_num(ciphertext_zero[32:45]+b'\x00'*3) + r^2*le_bytes_to_num(ciphertext_zero[48:61]+b'\x00'*3))
    constant = s-tag
    memo = le_bytes_to_num(num_to_8_le_bytes(16) + num_to_8_le_bytes(16*4) + b'\x01')
    constant += memo * r
    memo = le_bytes_to_num(aad + pad16(aad) + b'\x01')
    constant += memo * r^6
    constant = K(constant)

    mat = [
        [r^5*(2^104),r^4*(2^104),r^3*(2^104),r^2*(2^104),-constant,p],
        [1/2^100,0,0,0,0,0],
        [0,1/2^100,0,0,0,0],
        [0,0,1/2^100,0,0,0],
        [0,0,0,1/2^100,0,0],
        [0,0,0,0,2**24/2^100,0],
    ]

    mat = matrix(QQ, mat).transpose()

    res = []
    for lll in mat.LLL():
        if abs(lll[-1]) == 2^24/2^100:
            flag = True
            for v in lll[1:5]*2^100:
                if abs(v) >= 2^25:
                    flag = False
            if flag:
                res.append(lll[1:5]*2^100)

    return res

def solve(io):
    myaad = b"0000000000000000"
    ciphertext_zero = get_ciphertext(io, b'\x00'*(16*4))
    bit_flip_mac = le_bytes_to_num(xor_plaintext(io, b'\x00'*(16*3) + b'\x01' + b'\x00'*15))
    zero_length_mac = le_bytes_to_num(change_length(io, 0, 0))
    default_mac = le_bytes_to_num(default(io))
    aad_mac = le_bytes_to_num(change_aad(io, myaad))
    rs = solve_r(default_mac, bit_flip_mac)

    ras = []
    for r in tqdm(rs):
        for a in solve_a(int(r), aad_mac, default_mac, myaad):
            ras.append((r,a))

    zero_length_mac_cand = []
    for i in range(2**5):
        zero_length_mac_cand.append((i << (8*16)) + zero_length_mac)

    rases = []
    for ra in ras:
        for mac in zero_length_mac_cand:
            r,a = ra
            s = solve_s(r,num_to_16_le_bytes(a),mac)
            rases.append((r,a,s))


    rases = list(set(rases))

    for ras in rases:
        for i in range(2**5):
            r,a,s = ras
            tag = (i << (8*16)) + default_mac
            c = solve_c(tag, ciphertext_zero, num_to_16_le_bytes(a), int(r), int(s))

            if len(c) > 0:
                for t in c:
                    plaintexts = []
                    for j in range(4):
                        plaintexts.append(strxor(ciphertext_zero[j*16+13:(j+1)*16], struct.pack('<Q', abs(t[j]))[:3]))

                    print("ans:", plaintexts)
                    answer = b""
                    for plaintext in plaintexts:
                        answer += b"\x00"*13+plaintext

                    print(send_answer(io, answer))
                    return

io = remote(os.getenv("SECCON_HOST"), int(os.getenv("SECCON_PORT")))
for i in range(100):
    solve(io)

print(io.recvuntil("flag is"))
print(io.recvline())

How this challenge was created

Every year Kurenaif had one challenge on symmetric key cryptography at SECCON, but we ran out of ideas last year and could not made challenge in the qualifiers this year lol.
I gave up using AES and was looking at other symmetric key ciphers when I found ChaCha20-Poly1305.
When I came up with the idea for this problem, I had no idea that it would be such a painful problem lol.

v_v_m_m_v_m_m

problem

import os
from Crypto.Cipher import AES
import signal
signal.alarm(3600)

q = 16
vsize = 22
o1 = 22
o2 = 22
m = o1 + o2
n = vsize + o1 + o2
K = GF(q)

poly2int = {}
for i in range(q):
    poly2int[K(Integer(i).digits(2))] = i

# r: random_element()
# e.g. size1 = 4, size2 = 6
#
#   size2
#   vvvvvv
#  [rrrrrr000] < size1
#  [0rrrrr000] < size1
#  [00rrrr000] < size1
#  [000rrr000] < size1
#  [000000000]
#  [000000000]
#  [000000000]
#  [000000000]
#  [000000000]
def make_UD_matrix(size1, size2):
    res = Matrix(K, n, n)
    small_size = min(size1, size2)
    big_size = max(size1, size2)

    for i in range(small_size):
        for j in range(big_size):
            if i <= j:
                res[i,j] = K.random_element()
    return res

# res = mat * vec
def product(mat, vec):
    res = []
    for i in range(mat.nrows()):
        element = Matrix(K, n, n)
        for j in range(mat.ncols()):
            element += mat[i,j] * vec[j]
        res.append(element)

    return res

def gen_key():
    S = random_matrix(K, n, n)
    T = random_matrix(K, m, m)
    while not S.is_invertible(): S = random_matrix(K, n, n)
    while not T.is_invertible(): T = random_matrix(K, m, m)

    Fs = []
    for _ in range(o1): Fs.append(make_UD_matrix(vsize,vsize+o1))
    for _ in range(o2): Fs.append(make_UD_matrix(n,vsize+o1))

    SFSs = []
    for F in Fs: SFSs.append(S * F * S.transpose())
    pubkey = SFSs
    pubkey = product(T, SFSs)

    return (pubkey, (S, T, Fs))

def eval_v(pubkey, v):
    return vector([v * matp * v for matp in pubkey])

def vec2string(vec):
    res=""
    for e in vec:
        res += str(poly2int[e]) + ","
    return res[:-1]

def mat2strings(mat):
    res = []
    for row in mat:
        res.append(vec2string(row))
    return res

def strings2vec(str):
    res = []
    vals = str.split(',')
    for val in vals:
        res.append(K(Integer(int(val)).digits(2)))
    return vector(K, res)

def strings2mat(strs,nrows,ncols):
    mat = []
    for row in strs:
        mat.append(strings2vec(row))
        assert ncols == len(mat[-1])
    assert nrows == len(mat)
    return matrix(K, mat)

message = random_vector(K, n)
for challenge_id in range(2):
    pubkey, privkey = gen_key()
    ciphertext = eval_v(pubkey, message)

    pubkey_str = []
    for i in range(len(pubkey)):
        pubkey_str.append(mat2strings(pubkey[i]))
        print(f"pubkey[{i}]: {pubkey_str[i]}")

    vecs = []
    for i in range(22):
        vecs.append(strings2vec(input(f"vec{i}:")))
    V = VectorSpace(K,n)
    S = V.subspace(vecs)
    assert S.dimension() == 22
    vec = S.random_element()

    print("eval(vec) result:", vec2string(eval_v(pubkey, vec)))
    print("eval(message+vec)-eval(message) result:", vec2string(eval_v(pubkey, vec+message)-eval_v(pubkey, message)))

answer = strings2vec(input("ans:"))
if answer == message:
    flag = os.getenv("FLAG", "SECCON{dummyflagdummyflagdummyf}")
    print("flag:", flag)
else:
    print("flag:", "fail")

how to solve

Overview of this challenge

44 matrices are generated and sent to you. Let $m_0, m_1, ..., m_{43}$ be the generated matrix
Then, 22 vectors are given from you, and one random vector is generated from that subspace on the server side. Let's call this generated vector $v$
eval(v) and eval(message+v)-eval(message) are returned. where eval is

\mathrm{eval}(v) := (v m_0 v, v m_1 v, ..., v m_{43} v)

The objective is to repeat 1~3 above twice and recover the message.

step1: what is this cryptosystem?

You must identify this cipher as the MQ cipher rainbow.
This can be identified from the way the matrix is constructed.
And rainbow has vulnerabilities, as shown in this paper: Breaking Rainbow Takes a Weekend on a Laptop.

And you can find this repository: https://github.com/WardBeullens/BreakingRainbow

step2: recover vec

By using BreakinRainbow, you can find 22 vectors (this vector space is called $O_2$ ) that satisfy the following in a realistic amount of time.

\mathrm{eval}(o_2) = 0\ \mathrm{where}\ o_2 \in O_2

Here, we use the following properties.

\mathrm{eval}(v_1 + v_2) = \mathrm{eval}(v_1) + \mathrm{Differencial}(v_1, v_2) + \mathrm{eval}(v_2) \tag{*}

where:

\mathrm{Differencial}(v_1, v_2) := (v_1 m_0 v_2 + v_2 m_0 v_1, v_1 m_1 v_2 + v_2 m_1 v_1, ..., v_1 m_{43} v_2 + v_2 m_{43} v_1)

then, if you choose 21 vectors from $O_2$ and choose 1 vector like $r\ \notin O_2$

The vector described in 2 of the "Overview of this challenge" is as follows.

\begin{aligned} v &= o_2 + k r\ (0 \leq k < 16, \mathrm{k\ is\ unknown}) \\ \mathrm{eval}(v) &= \mathrm{eval}(o_2 + k r) = \mathrm{eval}(o_2) + \mathrm{Differencial}(o_2, k r) + \mathrm{eval}(k r) \\ &= 0 + \mathrm{Differencial}(o_2, k r) + \mathrm{eval}(k r) \end{aligned}

And since $o_2$ is a linear combination of the 21 vectors passed here, we'll call these vectors are $s_1,...,s_{21}$ , it is expressed by the following equation.

o_2 = \begin{bmatrix} \overrightarrow{s_1} & \overrightarrow{s_2} & \cdots & \overrightarrow{s_{21}} \end{bmatrix} \begin{bmatrix} k_1 \\ k_2 \\ \vdots \\ k_{21} \end{bmatrix}

where $0 \leq k_i < 16$ is unknown.

Substituting this value into upper equation(*) completes the 21-variable linear equation.

By solving this equation, the vector computed by the server can be recovered.

step3: recover message

Similarly, given the following formula, we can obtain a linear polynomial of 44 variables with respect to message.

\mathrm{eval}(\mathrm{message}+v) - \mathrm{eval}(\mathrm{message}) = \mathrm{eval}(v) + \mathrm{Differencial}(\mathrm{message}, v)

message is an 88 variable, but fortunately it is repeated twice in this challenge, so it can be uniquely obtained.

source code

from pwn import remote
import pickle
import random
import subprocess
import re
import time
import os

q = 16
v = 22
o1 = 22
o2 = 22
m = o1 + o2
n = v + o1 + o2
K = GF(q)

poly2int = {}
for i in range(q):
    poly2int[K(Integer(i).digits(2))] = i

def Eval(F,x):
    return vector([ x*M*x for M in F])

def Differential(F,x,y):
    return vector([ (x*M*y) + (y*M*x)  for M in F ])

# makes a matrix upper diagonal
def Make_UD(M):
    n = M.ncols()
    for i in range(n):
        for j in range(i+1,n):
            M[i,j] += M[j,i]
            M[j,i] = K(0) 
    return M

def vec2string(vec):
    res=""
    for e in vec:
        res += str(poly2int[e]) + ","
    return res[:-1]

def mat2strings(mat):
    res = []
    for row in mat:
        res.append(vec2string(row))
    return res
    
def strings2vec(str):
    res = []
    vals = str.split(',')
    for val in vals:
        res.append(K(Integer(int(val)).digits(2)))
    return vector(K, res)

def strings2mat(strs,nrows,ncols):
    mat = []
    for row in strs:
        mat.append(strings2vec(row))
        assert ncols == len(mat[-1])
    assert nrows == len(mat)
    return matrix(K, mat)

def get_pubkey(io):
    pubkey = []
    for i in range(m):
        io.recvuntil("pubkey")
        memo = io.readline().split(b':')[1]
        mat = strings2mat(eval(memo), n, n)
        Make_UD(mat)
        pubkey.append(mat)
    return pubkey

def get_resultvec(io):
    io.recvuntil("result")
    res = strings2vec(io.recvline().split(b":")[1].decode('utf-8'))
    return res

def full_attack(PK):
Please copy from https://github.com/WardBeullens/BreakingRainbow/blob/main/Attack_demo/Full_Attack.sage
    return O2
    
# --------------------------------------------------

def send_vecs(io, vecs):
    for i in range(len(vecs)):
        print(io.recvuntil(":"))
        io.sendline(vec2string(vecs[i]))
    
def solve_o(io, pubkey, r, mat):
    temp = get_resultvec(io) # Eval(pubkey, r+o)
    for i in range(1,16):
        rr = K(Integer(i).digits(2)) * r
        rhs = temp - Eval(pubkey, rr)
        PRo = PolynomialRing(K, mat.ncols(), 'o')
        o_vars = vector(PRo.gens())
        o = mat * o_vars
        lhs = Differential(pubkey, rr, o)
        eqs = []
        for i in range(len(rhs)):
            eqs.append(lhs[i]-rhs[i])
        ideal = PRo.ideal(eqs).variety(K)
        if len(ideal) != 1:
            continue

        o = []
        print("o_vars:", ideal[0])
        for i in range(mat.ncols()):
            o.append(ideal[0][o_vars[i]])
        o = vector(K, o)
        print("o:", o)
        return vector(rr + mat*o)

def get_x_eqs(io, x_vars, pubkey, vec):
    a = get_resultvec(io)
    print("eval(sig+vec)-eval(sig):", vec2string(a))
    print("eval(vec):", vec2string(Eval(pubkey, vec)))
    rhs = a - Eval(pubkey, vec)
    print("rhs", rhs)
    print("vec", vec2string(vec))
    lhs = Differential(pubkey, x_vars, vec)
    eqs = []
    for i in range(len(rhs)):
        eqs.append(lhs[i]-rhs[i])
    return eqs

def solve(io, x_vars):
    pubkey = get_pubkey(io)
    print("--------------------------------------------------pubkey--------------------------------------------------")
    print(pubkey[0])
    print("--------------------------------------------------pubkey--------------------------------------------------")

    O2, O1, W = full_attack(pubkey)
    r = random_vector(K, n)

    vecs = []
    SubO2 = []
    for i in range(21):
        vecs.append(O2.column(i))
        SubO2.append(O2.column(i))
    SubO2 = matrix(SubO2).transpose()

    vecs.append(r)

    send_vecs(io, vecs)
    vec = solve_o(io, pubkey,r,SubO2)
    if vec == None:
        return None
    
    return get_x_eqs(io, x_vars, pubkey, vec)

def solve2(io):
    PRx = PolynomialRing(K, n, 'x')
    x_vars = vector(PRx.gens())
    eq1 = solve(io, x_vars) # Todo: loop
    if eq1 == None:
        return None 
    eq2 = solve(io, x_vars)
    if eq2 == None:
        return None
    print(eq1)
    print("--------------------------------------------------eq1--------------------------------------------------")
    print(eq2)
    print("--------------------------------------------------eq2--------------------------------------------------")
    ideal = PRx.ideal(eq1+eq2).variety(K)

    print("--------------------------------------------------ideal--------------------------------------------------")
    print(ideal)
    if len(ideal) != 1:
        return None 

    ans = []
    for i in range(n):
        ans.append(ideal[0][x_vars[i]])
    ans = vector(K, ans)

    print(io.recvuntil("ans:"))
    io.sendline(vec2string(ans))
    io.recvuntil("flag:")
    res = io.recvline()
    return res

cnt = 0
while True:
    cnt += 1
    print("challenge:", cnt)
    io = remote(os.getenv("SECCON_HOST"), int(os.getenv("SECCON_PORT")))
    res = solve2(io)
    io.close()
    if res != None:
        print(res)
        break
    break

print("cnt: ", cnt)

How this challenge was created

When I was studying uov, I was impressed that inputting o2 resulted in a linear equation, so I decided to use that as a problem.
If someone knew how to do this, it might be a obvious problem, but fortunately not everyone could solve it.

I found this characteristic very easy to produce in CTF. PQC is still rare in CTF, but I have recently felt limited in creating problems with elliptic curve cryptography and RSA cryptography and wanted to learn more about PQC.

I hope this helps you understand the attack methods against uov.

introduction

muck-a-mac

problem

how to solve

prepairing to solve

1. solve the internal parameter 'r' of ChaChaPoly

2. solve 'aad'

3. solve the internal parameter 's' of ChaChaPoly

4. solve the ciphertext 'c'

5. solve the plaintext from the ciphertext

full source code

How this challenge was created

v_v_m_m_v_m_m

problem

how to solve

Overview of this challenge

step1: what is this cryptosystem?

step2: recover vec

step3: recover message

source code

How this challenge was created

Discussion