Nostalgic - SECCON CTF 14 (2025)
Challenge:
from Crypto.Cipher import ChaCha20_Poly1305
from Crypto.Random import get_random_bytes
import os
def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))
FLAG = os.getenv("FLAG", "flag{dummy}")
key = get_random_bytes(32)
nonce = get_random_bytes(12)
SPECIAL_MIND = get_random_bytes(16)
print(f"my SPECIAL_MIND is {SPECIAL_MIND.hex()}")
def enc(plaintext=None):
if plaintext == None:
plaintext = get_random_bytes(15)
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(plaintext)
return ct, tag
special_rain = get_random_bytes(16)
special_ct, special_tag = enc(plaintext=special_rain)
print(f"special_rain_enc = {special_ct.hex()}")
print(f"special_rain_tag = {special_tag.hex()}")
while True:
if (inp := input("what is your mind: ")) != "need":
if enc(plaintext=xor(special_rain, bytes.fromhex(inp)))[1] == SPECIAL_MIND:
print(f"I feel the same!!.. The flag is {FLAG}")
else:
print("No... not the same...")
break
else:
print(f"my MIND was {enc(plaintext=None)[1].hex()}")
Solve:
Well don’t let the ChaCha trick you into thinking this is about stream cipher shenanigans, it’s more mathematical.
This was the first chall I’ve tried that deals with Poly1305, so I had lots of research to do, here’s a dump:
https://l3ak.team/2024/04/21/plaid24/
https://zenn.dev/kurenaif/articles/2a005936de308a
https://github.com/tl2cents/AEAD-Nonce-Reuse-Attacks
https://github.com/kalmarunionenctf/kalmarctf/tree/main/2024/crypto/PolyCG1305
https://datatracker.ietf.org/doc/html/rfc7539
https://github.com/ph4r05/py-chacha20poly1305/blob/master/chacha20poly1305/poly1305.py
https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/ChaCha20.py#L244
https://github.com/Legrandin/pycryptodome/blob/master/src/poly1305.c
Well first I learned what the 1305 means:
sage: p = 2**130 - 5
sage: is_prime(p)
True
Now to look at the chall, if we just keep sending ‘need’, we can collect infinite sample of print(f"my MIND was {enc(plaintext=None)[1].hex()}")
That is, we have access to as many 16-byte MAC tags as we like.
Now I needed to learn how these MAC tags are created.
https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/ChaCha20.py#L244
Here we see r and s are derived from the key and nonce. The key and nonce are static in the chall, so r and s are both static too!
r and s come from 16 bytes, so they are both <2**128. Also note everything seems to use little endian.
In Crypto/Cipher/ChaCha20_Poly1305.py we see how the ciphertext is modified:
def _compute_mac(self):
"""Finalize the cipher (if not done already) and return the MAC."""
if self._mac_tag:
assert(self._status == _CipherStatus.PROCESSING_DONE)
return self._mac_tag
assert(self._status != _CipherStatus.PROCESSING_DONE)
if self._status == _CipherStatus.PROCESSING_AUTH_DATA:
self._pad_aad()
if self._len_ct & 0x0F:
self._authenticator.update(b'\x00' * (16 - (self._len_ct & 0x0F)))
self._status = _CipherStatus.PROCESSING_DONE
self._authenticator.update(long_to_bytes(self._len_aad, 8)[::-1])
self._authenticator.update(long_to_bytes(self._len_ct, 8)[::-1])
self._mac_tag = self._authenticator.digest()
return self._mac_tag
We have no aad (additional associated data) in this chall so that is ignored.
From this writeup we see the input is usually AD || pad(AD) || C || pad(C) || len(AD) || len(C) but C || pad(C) || len(AD) || len(C) with no aad.
As a one-liner,
msg = ct + b'\x00' * ((16 - len(ct) % 16) % 16) + (0).to_bytes(8,'little') + len(ct).to_bytes(8,'little')
Next we delve into the c code
Note the poly1305_load_r function, it clamps r.
Finally, this python implementation was very helpful, I just had to edit r and s.
Note the mod 2**128 at the end because the tag is truncated to 16 bytes.
So now we can make a test script for how the MAC tag is created:
from os import urandom
from Crypto.Cipher import ChaCha20_Poly1305
plaintext = urandom(15)
key = urandom(32)
nonce = urandom(12)
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(plaintext)
print(tag.hex()) # can we reproduce this?
And successfully reproduce it:
from os import urandom
from Crypto.Cipher import ChaCha20_Poly1305, ChaCha20
plaintext = urandom(15)
key = urandom(32)
nonce = urandom(12)
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(plaintext)
print(tag.hex()) # can we reproduce this?
# reproduce r, s
rs = ChaCha20.new(key=key, nonce=nonce).encrypt(b'\x00'*32)
r, s = rs[:16], rs[16:]
r, s = int.from_bytes(r, 'little'), int.from_bytes(s, 'little')
def poly1305_mac(r, s, msg):
p = 2**130 - 5
r &= 0x0ffffffc0ffffffc0ffffffc0fffffff # clamped
acc = 0
for i in range(0, len(msg), 16):
block = msg[i:i+16] + b'\x01'
block = int.from_bytes(block, 'little')
acc = (acc + block) * r % p
acc += s
acc = int(acc % 2**128)
return acc.to_bytes(16, 'little')
msg = ct + b'\x00' * ((16 - len(ct) % 16) % 16) + (0).to_bytes(8,'little') + len(ct).to_bytes(8,'little')
reproduced_tag = poly1305_mac(r, s, msg)
print(reproduced_tag.hex())
assert tag == reproduced_tag
In this challenge, the ciphertexts are always the same size and the for loop that does the accumulation only loops twice, so let’s simplify it:
from os import urandom
from Crypto.Cipher import ChaCha20_Poly1305, ChaCha20
plaintext = urandom(15)
key = urandom(32)
nonce = urandom(12)
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(plaintext)
t = int.from_bytes(tag, 'little')
# reproduce r, s
rs = ChaCha20.new(key=key, nonce=nonce).encrypt(b'\x00'*32)
r, s = rs[:16], rs[16:]
r, s = int.from_bytes(r, 'little'), int.from_bytes(s, 'little')
p = 2**130 - 5
m = 2**128
r &= 0x0ffffffc0ffffffc0ffffffc0fffffff # clamped
x = int.from_bytes(ct, 'little') # unknown
b = int.from_bytes((0).to_bytes(8,'little') + len(ct).to_bytes(8,'little') + b'\x01', 'little') # known, msg[16:32]
assert t == ((((256**16+x)*r**2 + b*r) % p) + s) % m
# unknowns:
assert r<2**124 # a bit less than 128 bc of clamping
assert s<2**128
assert x<2**120
Alright now we’ve escaped the crypto stuff and it’s just math equations to solve.
\[t_i = ((((256^{16} + x_i) \cdot r^2 + b \cdot r) \pmod p) + s) \pmod m\]Can get rid of the mods, introduce some new vars k_i and j_i:
\[t_i = 256^{16} \cdot r^2 + x_i \cdot r^2 + b \cdot r + k_i \cdot p + s + j_i \cdot m\]256^16 * r^2 + br + s is constant, if we subtract pairs of equations we can eliminate it:
Now just some notation cleanup:
\[tt_i = t_{i+1} - t_i\] \[xx_i = x_{i+1} - x_i\] \[kk_i = k_{i+1} - k_i\] \[jj_i = j_{i+1} - j_i\] \[R = r^2\] \[tt_i = xx_i \cdot R + jj_i \cdot m + kk_i \cdot p\]And as a reminder,
knowns: tt_i. m, p
unknowns: xx_i, jj_i, kk_i, R
Let’s start another test script:
p = 2**130 - 5
m = 2**128
while True:
r = randint(0, 2**124)
s = randint(0, 2**128)
R = r**2
xx_2 = randint(0, 2**120)
xx_1 = randint(0, 2**120)
xx_i = xx_2 - xx_1
tt_2 = ((xx_2*R) % p) % m
tt_1 = ((xx_1*R) % p) % m
jj_2 = (tt_2 - ((xx_2*R) % p)) // m
jj_1 = (tt_1 - ((xx_1*R) % p)) // m
jj_i = jj_2 - jj_1
tt_i = tt_2 - tt_1
assert -3 <= jj_i <= 3
#print(jj_i)
assert tt_i % p == (xx_i*R + jj_i*m) % p
So we see jj_i is in a very small range. Now we switch the equation back to mod p and begin dealing with orthogonal lattice techniques.
\[tt_i = xx_i \cdot R + jj_i \cdot m \pmod p\]The first thing we want to solve is jj_i:
def find_ortho_mod(mod, *vecs):
assert len(set(len(v) for v in vecs)) == 1, "vectors have different lengths"
base = [[matrix(vecs).T, matrix.identity(len(vecs[0]))]]
if mod is not None:
base += [[ZZ(mod), 0]]
L = block_matrix(ZZ, base)
nv = len(vecs)
L[:, :nv] *= mod
L = L.LLL()
ret = []
for row in L:
if row[:nv] == 0:
ret.append(row[nv:])
return matrix(ret)
p = 2**130 - 5
m = 2**128
r = randint(0, 2**124)
s = randint(0, 2**128)
R = r**2
print(f'{R = }')
N = 100
xx = []
tt = []
jj = []
for _ in range(N):
xx_2 = randint(0, 2**120)
xx_1 = randint(0, 2**120)
xx_i = xx_2 - xx_1
xx.append(xx_i)
tt_2 = ((xx_2*R) % p) % m
tt_1 = ((xx_1*R) % p) % m
tt_i = tt_2 - tt_1
tt.append(tt_i)
jj_2 = (tt_2 - ((xx_2*R) % p)) // m
jj_1 = (tt_1 - ((xx_1*R) % p)) // m
jj_i = jj_2 - jj_1
jj.append(jj_i)
print(f'{jj = }')
orth1 = find_ortho_mod(p, tt).BKZ()[:-2]
for o in orth1:
assert o * vector(GF(p), tt) == 0
# tt_i = xx_i * R + jj_i*m (mod p)
# when we find vectors orthogonal to tt_i, they also happen to be orthogonal to xx_i and jj_i (hopefully)
assert o * vector(GF(p), xx) == 0
assert o * vector(GF(p), jj) == 0
orth2 = find_ortho_mod(p, *orth1)
for o in orth2:
assert o * vector(GF(p), orth1[0]) == 0
assert o * vector(GF(p), orth1[1]) == 0
assert o * vector(GF(p), orth1[2]) == 0
...
print('solved jj (maybe negative):', orth2[0])
Nice it worked, we found some orth1 orthogonal to jj_i and xx_i, then jj_i (the shortest) appeared in orth2.
Now we can use another lattice to solve for xx_i.
\[tt_i = xx_i \cdot R + jj_i \cdot m \pmod p\] \[tt_i - jj_i \cdot m \equiv xx_i \cdot R \pmod p\]Here tt_i - jj_i * m is just a constant now, but there is still 2 unknowns multiplied on the right hand side which is a little annoying.
But we can easily just divide out the R:
\[R^{-1} \cdot (tt_i - jj_i \cdot m) \equiv xx_i \pmod p\]And SVP:
\[R^{-1} \cdot \begin{bmatrix} tt_0 - jj_0 \cdot m \\ tt_1 - jj_1 \cdot m \\ ... \\ tt_i - jj_i \cdot N \end{bmatrix} + kk_0 \cdot \begin{bmatrix} p \\ 0 \\ ... \\ 0 \end{bmatrix} + kk_1 \cdot \begin{bmatrix} 0 \\ p \\ ... \\ 0 \end{bmatrix} + \ ... \ + kk_N \cdot \begin{bmatrix} 0 \\ 0 \\ ... \\ p \end{bmatrix} = \begin{bmatrix} xx_0 \\ xx_1 \\ ... \\ xx_N \end{bmatrix}\]p = 2**130 - 5
m = 2**128
r = randint(0, 2**124)
s = randint(0, 2**128)
R = r**2
print(f'{R = }')
N = 100
xx = []
tt = []
jj = []
for _ in range(N):
xx_2 = randint(0, 2**120)
xx_1 = randint(0, 2**120)
xx_i = xx_2 - xx_1
xx.append(xx_i)
tt_2 = ((xx_2*R) % p) % m
tt_1 = ((xx_1*R) % p) % m
tt_i = tt_2 - tt_1
tt.append(tt_i)
jj_2 = (tt_2 - ((xx_2*R) % p)) // m
jj_1 = (tt_1 - ((xx_1*R) % p)) // m
jj_i = jj_2 - jj_1
jj.append(jj_i)
print(f'{xx = }')
jj_vec = vector(GF(p), jj)
tt_vec = vector(GF(p), tt)
# pow(R, -1, p) * (tt_i - jj_i*M) = xx_i (mod p)
assert pow(R, -1, p) * (tt_vec - jj_vec*m) == vector(GF(p), xx)
M = Matrix(ZZ, tt_vec - jj_vec*m).T.augment(diagonal_matrix([p]*N)).T
print('solved xx (maybe negative)', M.LLL()[1])
Now R is the only unknown left so that’s trivial to rearrange for.
\[R \equiv {xx_i}^{-1} \cdot (tt_i - jj_i \cdot m) \pmod p\]From here you could also solve r as one of the modular sqrts of R, and solve s too, but there’s no need, R is sufficient.
Now let’s think about the final payload forgery. I simplified the source a little:
SPECIAL_MIND = urandom(16) # given
special_rain = urandom(16) # secret
special_ct, special_tag = enc(plaintext=special_rain) # given
payload = ...
if enc(plaintext=xor(special_rain, payload))[1] == SPECIAL_MIND:
print(f"I feel the same!!.. The flag is ...")
else:
print("No... not the same...")
Note that internally, we have ciphertext = plaintext XOR keystream:
ct, tag = enc(plaintext)
keystream, _ = enc(b"\x00" * len(plaintext))
assert ct == xor(plaintext, keystream)
Key and nonce are fixed, so the keystream is also fixed.
We know that special_ct = special_rain XOR keystream
And we will also have forged_ct = (special_rain XOR payload) XOR keystream
So although special_rain and keystream are not known, they both disappear with XOR operations.
Rearranging for payload:
payload = forged_ct XOR special_rain XOR keystream
And sub in special_ct:
payload = forged_ct XOR special_ct
Great, all that remains is to use R and calculate forged_ct that will result in the tag being SPECIAL_MIND.
\[tt_i \equiv xx_i \cdot R + jj_i \cdot m \pmod p\]Let:
t1 = special_tag, x1 = special_ct
t2 = SPECIAL_MIND, x2 = forged_ct (what we are solving for)
j = j2 - j1
\[(t_2 - t_1) \equiv (x_2 - x_1) \cdot R + j \cdot m \pmod p\] \[x_2 \equiv (t_2 - t_1 - j \cdot m) \cdot R^{-1} + x_1 \pmod p\]If you are unlucky then x2 is bigger than 2**128 and we can’t send it because it’s more than 16 bytes.
But other than that, we are done!
Another quick test script:
from os import urandom
from Crypto.Cipher import ChaCha20_Poly1305, ChaCha20
def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))
def enc(plaintext):
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(plaintext)
return ct, tag
plaintext = urandom(15)
key = urandom(32)
nonce = urandom(12)
ct, tag = enc(plaintext)
# reproduce r, s
rs = ChaCha20.new(key=key, nonce=nonce).encrypt(b'\x00'*32)
r, s = rs[:16], rs[16:]
r, s = int.from_bytes(r, 'little'), int.from_bytes(s, 'little')
p = 2**130 - 5
m = 2**128
r &= 0x0ffffffc0ffffffc0ffffffc0fffffff # clamped
R = r**2
SPECIAL_MIND = urandom(16) # given
special_rain = urandom(16) # secret
special_ct, special_tag = enc(plaintext=special_rain) # given
t1 = int.from_bytes(special_tag, 'little')
x1 = int.from_bytes(special_ct, 'little')
t2 = int.from_bytes(SPECIAL_MIND, 'little')
for j in range(-3, 4):
print(j)
x2 = ((t2 - t1 - j*m) * pow(R, -1, p) + x1) % p
if x2 > 2**128:
continue
forged_ct = x2.to_bytes(16, 'little')
payload = xor(forged_ct, special_ct)
if enc(plaintext=xor(special_rain, payload))[1] == SPECIAL_MIND:
print(f"I feel the same!!.. The flag is ...")
else:
print("No... not the same...")
Final script:
from pwn import process, remote, xor
def find_ortho_mod(mod, *vecs):
assert len(set(len(v) for v in vecs)) == 1, "vectors have different lengths"
base = [[matrix(vecs).T, matrix.identity(len(vecs[0]))]]
if mod is not None:
base += [[ZZ(mod), 0]]
L = block_matrix(ZZ, base)
nv = len(vecs)
L[:, :nv] *= mod
L = L.LLL()
ret = []
for row in L:
if row[:nv] == 0:
ret.append(row[nv:])
return matrix(ret)
p = 2**130 - 5
m = 2**128
N = 100
def attempt():
#io = process(["/home/connor/.p/bin/python", "chall.py"])
io = remote("nostalgic.seccon.games", "5000")
SPECIAL_MIND = bytes.fromhex(io.recvline().decode().split()[-1])
special_ct = bytes.fromhex(io.recvline().decode().split()[-1])
special_tag = bytes.fromhex(io.recvline().decode().split()[-1])
io.recv()
io.send(b'need\n'*(N+1)) # batched request
recv = io.recvlines(N+1)
ts = [int.from_bytes(bytes.fromhex(line.decode().split()[-1]), 'little') for line in recv]
tt = [ts[i+1] - ts[i] for i in range(N)]
orth1 = find_ortho_mod(p, tt).BKZ()[:-2]
orth2 = find_ortho_mod(p, *orth1)
jj = orth2[0]
if not all(-4 <= i <= 4 for i in jj) or list(jj).count(0) > N//2 :
print('failed solving jj')
io.close()
return False
print(f'{jj = }')
for jj in [jj, -jj]:
jj_vec = vector(GF(p), jj)
tt_vec = vector(GF(p), tt)
M = Matrix(ZZ, tt_vec - jj_vec*m).T.augment(diagonal_matrix([p]*N)).T
xx = M.LLL()[1]
for xx in [-xx, xx]:
try:
R = (pow(xx[0], -1, p) * (tt[0] - jj[0]*m)) % p
except:
print('inverse error')
return False
if not GF(p)(R).is_square():
continue
t1 = int.from_bytes(special_tag, 'little')
x1 = int.from_bytes(special_ct, 'little')
t2 = int.from_bytes(SPECIAL_MIND, 'little')
for j in range(5):
try:
x2 = ((t2 - t1 - j*m) * pow(R, -1, p) + x1) % p
except:
print('inverse error')
return False
if x2 > 2**128:
print('forged ct too big')
continue
forged_ct = x2.to_bytes(16, 'little')
payload = xor(forged_ct, special_ct)
print(io.recv(), j)
io.sendline(payload.hex().encode())
flag = io.recv()
io.close()
print(flag)
if b'SECCON' in flag:
return True
return False
io.close()
return False
while True:
if attempt():
break
# SECCON{Listening_to_the_murmuring_waves_and_the_capricious_passing_rain_it_feels_like_a_gentle_dream}