SECCON CTF 2023 Finals muck-a-mac, v_v_m_m_v_m_m writeup
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.
where:
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
then,
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
.
where
then,
In addition, aad(
self.aad = b""
for i in range(16):
self.aad += bytes([random.choice(bytes(string.printable, 'ascii'))])
so, you can recover
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
.
So, you can recover
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
Note here that
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
be the generated matrixm_0, m_1, ..., m_{43} - 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)
andeval(message+v)-eval(message)
are returned. where eval is
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
Here, we use the following properties.
where:
then, if you choose 21 vectors from
The vector described in 2 of the "Overview of this challenge" is as follows.
And since
where
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.
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.
Discussion