Aliyun CTF 2026

(Updated: )
, , , ,

Nice challenges from @hash_hash and @AquaCat, all of which are short enough but hard enough.

Official Writeup

Griffin

Curve Stuff

First things first we need to reconstruct the curve and do some basic analysis.

1
2
3
4
5
6
7
8
9
10
11
12
a, b = ZZ["a", "b"].gens()
Fs = [x**3 + a*x + b - y**2 for x, y in Griffin[0][:10]]
B = Ideal(Fs).groebner_basis()
p = B[-1]
a = ZZ(-B[0].univariate_polynomial().monic()(0) % p)
b = ZZ(-B[1].univariate_polynomial().monic()(0) % p)

E = EllipticCurve(GF(p), [a, b])
G = E.lift_x(GF(p)(3137))
G_order = G.order()
facs = [66179, 67247, 70271, 76679, 78803, 86693, 107791, 116273, 119677, 121309]
assert prod(facs) == G_order

Turns out the curve is smooth enough to solve DLP, so from now on we consider operations on $\mathbb{Z}_n$.

Actually we just need to recover some specific DLPs as needed, saving a lot of time.

Reed-Solomon Code Distinction

Let’s consider the problem on $\mathbb{F}_q$ where $ q | n $. What we’re supposed to do here is to distinguish all $2 \cdot d$ of the Reed-Solomon codes Hawk, combined with $k$ junk data Lion. It’s worth noting the degree of the polynomials is $d-1$.

Since I am not familiar with RS Code, I’ll give a linear-algebra-based solution. Consider $x_i$ and the code vector $ \vec{v_i} = [f_{0}(x_i), …, f_{m-1}(x_i)] = [1, x_i, …, x_i^{d-1}] \cdot F_{d \times m} $. For the linear space $\mathcal{C} = Span( \{ \vec{v_0}, …, \vec{v_{2 \cdot d - 1}} \} )\subset \mathbb{F}_q^m $, we have $\dim(\mathcal{C}) = d$. We can construct a distinguisher leveraging the property:

For a vector subset $\mathcal{V} \subseteq \{ \vec{v_0}, …, \vec{v_{2 \cdot d - 1}} \} $ uniformly sampled from Griffin, which contains $h$ Hawk vectors and $t-h$ Lion vectors (s.t. $| \mathcal{V} | = t$), we have $\dim(Span(\mathcal{V})) = \min(m, t-\max(h-d, 0))$.

We need to pick up $t \in [m, m+d) \cap \mathbb{Z}$ to construct the distinguisher, which also leads to different success rate (I used $t=m$ during the competition and it’s acceptable). My strategy goes as follows:

  1. Uniformly sample $\mathcal{V}$, where $| \mathcal{V} | = m$.
  2. Check $1[\dim(Span( \mathcal{V}) < m]$, which indicates whether the number of Hawk vectors is strictly larger than $d$.
  3. For a vector $\vec{v}$ from Griffin, $\vec{v}$ is a Hawk vector if and only if:
    • $\vec{v} \notin \mathcal{V} \Rightarrow \dim(Span( \mathcal{V} \cup \{ \vec{v} \} )) = \dim(Span( \mathcal{V} ))$, or the dimension will increase by 1.
    • $\vec{v} \in \mathcal{V} \Rightarrow \dim(Span( \mathcal{V} \setminus \{ \vec{v} \} )) = \dim(Span( \mathcal{V} ))$, or the dimension will decrease by 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
q = 66179 # facs[0]
F = GF(q)

G0 = G*(G_order // q)
griffin = [[E(Griffin[i][j])*(G_order // q).log(G0) for j in range(m)] for i in range(k+2*d)]

hawk_inds = list()
while True:
    pos = sample(range(k+2*d), m)
    if matrix(F, [griffin[i] for i in pos]).T.rank() == m-1:
        for ind in range(k+2*d):
            now = pos[:]
            if ind in pos:
                now.remove(ind)
            else:
                now.append(ind)
            if matrix(F, [griffin[i] for i in now]).T.rank() == m-1:
                hawk_inds.append(ind)
        assert len(hawk_inds) == 2*d
        break

Polynomial Recovery

We need to solve xs for the recovery of the secret polynomials. I used Orthongonal Lattice since xs is sampled from range(1, 257). An all-1s vector is contained in the lattice so we need to enumerate an offset, thus leading to many candidate xs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
hawk = [[E(Griffin[ind][j]).log(G) for j in range(m)] for ind in hawk_inds]
ys = [i[0] for i in hawk]

K = 2**256
L = block_matrix(ZZ, [
    [1, K*matrix(ZZ, hawk)],
    [0, K*G_order]
]).LLL()[:2*d-d, :2*d]
L = block_matrix(ZZ, [
    [1, K*L.T]
]).LLL()[:d, :2*d]

cand_xs = list()
for a in range(-257, 257):
    for b in range(-2, 2):
        xs = (a*L[0] + b*L[1]).list()
        if all([(1 <= x and x <= 257) for x in xs]) and len(set(xs)) == 2*d:
            cand_xs.append(xs)

cand_ct = list()
for xs in cand_xs:
    pts = [(x, y) for x, y in zip(xs, ys)]
    res = list()
    for fac in facs:
        R = GF(fac)["x"]
        f = R.lagrange_polynomial(pts)
        ans = (f - flagct).roots()
        res.append([ZZ(i[0]) for i in ans])
    for tab in itertools.product(*res):
        cand_ct.append(crt(list(tab), facs))

The intended solution from @hash_hash is to decompose the RS Code public key. But it seems that both solutions get the same xs candidates.

The End?

You’ll find out the flag is much bigger than our 165-bits p, so we’re not able to get the flag directly. Luckily there exists specific properties of the flag:

  1. The template of the flag is known.
  2. The content of the flag is a uuid4 string, which is a fixed-format hexadecimal string.

Here we can use a special trick for hexadecimal strings. The only unknown part in the flag is the hex characters, each of which can we consider as two variables: high 4-bits and low 4-bits. Taking a deep look, we will find out that the high 4-bits has only 2 possible values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for ch in '0123456789abcdef':
    print(ch, bin(ord(ch))[2:].zfill(8))
'''
0 00110000
1 00110001
2 00110010
3 00110011
4 00110100
5 00110101
6 00110110
7 00110111
8 00111000
9 00111001
a 01100001
b 01100010
c 01100011
d 01100100
e 01100101
f 01100110
'''

So we can transform the possible values of high/low 4-bits into $[0, 1]\cap \mathbb{Z}$ and $[-5, 4]\cap \mathbb{Z}$, thus building a linear system optimized for LLL-based attack.

The parsing stuff is painful so I managed to implement an abstract code to build the linear system, which seems to be helpful in many similar conditions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def s2v(s: str):
    v = list()
    for si in s:
        x = (ord(si) >> 4) & 0xf # 3, 6
        x = (x - 3) // 3
        v.append(x) # 0, 1

        y = ord(si) & 0xf # 0, ..., 9
        y = y - 5
        v.append(y) # -5, ... 4
    return v

def v2s(v: list):
    s = ""
    for i in range(0, len(v), 2):
        x = v[i]
        x = (x * 3 + 3) % G_order

        y = v[i+1]
        y = (y + 5) % G_order

        s += chr((x << 4) | y)
    return s

X, Y = list(), list()
for _ in range(256):
    FLAG = "alictf{"+str(uuid4())+"}"
    X.append(s2v(FLAG[7:-1].replace("-", "")))
    Y.append(int(FLAG.encode().hex(), 16) % G_order)
X, Y = matrix(Zmod(G_order), X), vector(Zmod(G_order), Y)
H = (X[:-1] - X[1:]).solve_right(Y[:-1] - Y[1:])
Y0 = Y[0] - X[0]*H

# check
for _ in range(10):
    FLAG = "alictf{"+str(uuid4())+"}"
    v = s2v(FLAG[7:-1].replace("-", "")
    ct = int(FLAG.encode().hex(), 16) % G_order
    assert vector(Zmod(G_order), v)*H + Y0 == ct

It’s such a relief that BKZ-22 is enough for this challenge, gg.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
A = matrix(ZZ, H.list()[:24] + H.list()[26:]).T # remove 0 element, since uuid4 has a fixed '4' in the middle
bounds = sum([[1, 4]]*31, []) + [1]
Q = diagonal_matrix(ZZ, [G_order // bound for bound in bounds])

inv_a = inverse_mod(A[-1, 0], G_order)
A = -A[:-1]*inv_a
for ct in cand_ct:
    b = matrix(ZZ, [ct - Y0]).T*inv_a
    L = block_matrix(ZZ, [
        [1, A, 0],
        [0, G_order, 0],
        [0, b, 1]
    ])
    L = (L*Q).BKZ(block_size=22)
    L = (L/Q).change_ring(ZZ)
    for v in L:
        if abs(v[-1]) == 1:
            s = v[-1]*v[:-1]
            try:
                s = v2s(s.list())
                assert all(ch in "0123456789abcdef" for ch in s)
                s = "alictf{" + s[0:8] + '-' + s[8:12] + '-' + '4' + s[12:15] + '-' + s[15:19] + '-' + s[19:] + "}"
                print(f"{s = }\n{ct = }\n{float(s.norm()) = }\n{s = }")
            except:
                pass

(*)Schrödinger’s AEAD

This may be a little too much for a 36h CTF, considering we have 2 other challenges. I was so close for this.

But that does not change the fact that this is a nice chall.

Nonce Reuse Vuln

It turns out that os.urandom will be called only once in the following code, creating a nonce reuse vulnerability with highly practical significance.

Based on which, we will exploit AES-GCM and Chacha20-Poly1305 step by step.

1
2
def aead(mode, nonce=os.urandom(24)):
    ...

AES-GCM

A brief discussion here, since I didn’t implemented this part of the chall.

One may notice that AES-GCM works with xor-friendly operations: For an xor difference $\epsilon$, if we send a plaintext pair $(p, p \oplus \epsilon)$, we can extract a certain tag difference $\Delta_{\oplus} t = f(\epsilon)$ (same with a truncated leakage).

So we can construct several pairs for a fixed $\epsilon$, and locate the AES-GCM pairs by checking the recurring $\Delta_{\oplus} t$. With a single pair, we can efficiently extract a linear leakage $a \otimes H$. We can fully recover $H$ by repeating this process for multiple well-chosen $\epsilon$.

Next we need to recover the keystream. Consider a plaintext $p$ and the 1-byte extended plaintext $p’ = p || ch$. If the last byte $ch$ is encrypted as a null byte, the tag difference will be determinted by the length of the plaintext. In fact we have $\Delta_{\oplus} t = f(len(p)) = (len(p||ch) \oplus len(p)) \otimes H$, which is known to us. So based on this we can construct an oracle and brute-force the keystream byte by byte. It’s worth mentioning that the first byte of each block is not recoverable since we are not allowed to encrypt an empty block.

Then we can recover the $aad$. For two plaintexts with different lengths, we can extract a linear leakage as $aad \otimes (H^i \oplus H^j) \oplus b$, where $b$ is determined by the difference of 1) content and 2) length. Since we know $H$ and the ciphertexts, we can compute $b$ and recover $aad$ in the same way as $H$.

It’s impossible to fully recover $J_0$ here, but we are now able to distinguish whether a single leakage is from AES-GCM or Chacha20-Poly1305. For this challenge, we need to recover both two $aad$ and combine them for the secret key, then we can recover $J_0$.

Chacha20-Poly1305

My sincere thanks go to @tl2cents for his AEAD code, which has been supporting my study of Chacha20-Poly1305. The following code serves as a brief introduction of the Poly1305, which shares a similar structure with AES-GCM actually.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# https://github.com/tl2cents/AEAD-Nonce-Reuse-Attacks/blob/main/chacha-poly1305/chacha_poly1305_forgery.py

# the implementation of the Poly1305 in the standard lib is as follows:
def poly1305(msg:bytes, key:bytes, byteorder='little'):
    """ A pure python implementation of the Poly1305 MAC function
    Reference: https://datatracker.ietf.org/doc/html/rfc7539#section-2.5.1
    Args:
        msg (bytes): The message to authenticate
        key (bytes): The 32 byte key to use
    Returns:
        bytes: The 16 byte MAC
    """
    p = 2**130 - 5 # the prime number used in Poly1305
    r = int.from_bytes(key[:16], byteorder)
    r = r & 0x0ffffffc0ffffffc0ffffffc0fffffff
    s = int.from_bytes(key[16:], byteorder)
    acc = 0
    for i in range(0, len(msg), 16):
        block = msg[i:i+16] + b'\x01'
        block = int.from_bytes(block, byteorder)
        acc = (acc + block) * r % p
    acc = (acc + s) # no more % p here !!!
    acc = int(acc % 2**128)
    return acc.to_bytes(16, byteorder)

$\mathbb{F}_p$ is not xor-friendly, and we can not eliminate the effect of encryption, so this time we need to recover the keystream first. Our null-byte-oracle still works, but here we have $\Delta t = (len(p||ch) - len(p)) \cdot r = r$, which is a constant result.

Instead of byte by byte recovery, we first perform brute-force attacks on multiple positions parallelly. Next we identify the indicator of oracle success $\Delta t = r$ by verifying the most recurring results (it pops up exactly 1 time on each positions), and then deduce the correct attack answers for all positions.

Again, we are not able to recover the first byte of each keystream block. This gives no effect when we are dealing with tag difference, but we need to brute-force it if we want to fully recompute the tag.

With the keystream, we can construct the polynomial of $r$ as in normal nonce-reuse attack, while in this challenge we’re dealing with truncated 16 bits leakage (high 2 bits and low 112 bits get smashed). We can collect several 1-block-ciphertext data and use LLL-based attack to recover $r$.

And in the same way as above can we recover the $aad$.

There also exists a LLL-free attack, using the fact that $p \approx k \cdot 2^{128}$.

With everything except $s$ recovered, we can construct any $t = X + s$ as needed (LLL-based attack appears necessary). Unlike AES-GCM here we can recover $s$ through binary search (by checking the carry bit of the leakage).

Double Forgery

With the full recovery of AES-GCM and Chacha20-Poly1305 secrets, our final step is to forge a valid payload for both two AEADs. We have the following tricks:

  1. For AES-GCM, $x \otimes H^{t+j}$ on the i-th block / $x \otimes H^{t+i}$ on the j-th block, leads to the same effect on the tag.
  2. For Chacha20-Poly1305, $x \cdot r^{t+j}$ on the i-th block / $x \cdot r^{t+i}$ on the j-th block, leads to the same effect on the tag.

This provides us with the opportunity to modify the ciphertext such that the tag of one AEAD remains unchanged, while introducing an uncontrollable change into the tag of the other.

With trick 2, we can find a valid answer by solving a linear system on $\mathbb{F}_2^{128}$. But we need a long enough ciphertext for an appropriate linear space, and 1337 in this challenge is too strict. So instead we may have to use trick 1 to formalize a k-sum problem on $\mathbb{F}_p$, and use wagner algorithm to solve it.

(*)DiceG@me+

I will give a brief summary of the solution, since I didn’t have enough time on this challenge.

All about Hash Functions

The vulnerability lies in the hash function.

1
2
3
4
5
Hash = lambda x: int(sha256(b'.'.join(x)).hexdigest(),16)

def verify(proof, h1, h2, N):
    ri, si = proof
    c = bin(Hash(map(long_to_bytes,[h1, h2]+ri)))[2:][::-1]

We can make some collisions by injecting . into ri. For example the result of Hash([ b2l(b'1'), b2l(b'2') ]) and Hash([ b2l(b'1.2') ]) are exactly the same.

Our target here is to construct a valid proof for (h1, 1). We can fix some k and let r = b2l(b'.'.join([b'\x01']*k)), then we set h1 = r**-1 % N and construct ri by sampling ri[i] from 1 and r. You may notice that c will not change if we rearrange the order of ri, and if the number of 1 in ri is equal to the number of 0 in c, we can always find a valid proof.

MT19937: Seed Construction

With h2 = 1, we can extract entropy from the commitment by solving DLP solving and LLL attack, predicting the whole roll list on the server. Then we need to construct a valid seed for MT19937 with certain prefix and suffix.

Here I may just omit the technical details and wish you a happy new year :D