In this challenge, we are given a file called asemoon.sage. It starts by generating some parameters:

def gen_CP(nbit):
	R.<x> = PolynomialRing(GF(2))
	while True:
		c = ''.join([hex(randint(0, 15))[2:] for _ in range(nbit >> 2)])
		G = R(Integer(int(c, 16)).bits()[::-1]) + x ^ nbit
		if G.is_irreducible():
			return int(c, 16)

nbit = 64
skey = getRandomNBitInteger(nbit)
CP, CT = gen_CP(nbit), []
for _ in range(256):
    cb = _
    for _ in range(8):
        if cb & 1:
            cb = (cb >> 1) ^^ CP
        else:
            cb >>= 1
    CT.append(cb & 0xFFFFFFFFFFFFFFFF)

For now, it is enough to know that CP is a random integer of less than 64 bits and CT is generated from CP deterministically. Then, we have the main loop of the challenge:

def recheck(msg, v):
	for m in msg:
		v = v ^^ m
		v = (v >> 8) ^^ CT[v & 0xFF] 
	return v & 0xFFFFFFFFFFFFFFFF 

def verify(v, t):
	return recheck(long_to_bytes(skey ^^ t), v) == v

while True:
    pr(f"{border} Options: \n{border}\t[L]ogin \n{border}\t[P]ublic information! \n{border}\t[Q]uit")
    ans = sc().decode().strip().lower()
    if ans == 'l':
        pr(border, 'Please send your hex token here:')
        token = sc().decode().strip()
        try:
            token = int(token, 16)
        except:
            die(border, "Your token is invalid! Bye!!")
        if 0 <= token < 2**nbit:
            t = int(time.time())
            t -= t % 10
            if verify(token, t):
                die(border, f"Congrats, you got the flag: {flag}")
        die(border, "Your token is wrong!")
    elif ans == 'p':
        t = int(time.time())
        t -= t % 10
        pub_1 = recheck(b"CCTF", recheck(long_to_bytes(skey ^^ t), 0))
        print(long_to_bytes(skey ^^ t))
        while True:
            pub_2 = getPrime(nbit)
            if pub_2 > CP:
                break
        pub_3 = pow(5, CP, pub_2)
        pr(border, f'The first public information is:  {pub_1}')
        pr(border, f'The second public information is: {pub_2}')
        pr(border, f'The third public information is:  {pub_3}')
    elif ans == 'q': die(border, "Quitting...")
    else: die(border, "Bye...")

The flag is retreived in the “L” option. To make the server give us the flag, we need to pass the verify check, which depends on skey ^^ t, where skey is a secret number generated at the beginning and we don’t know yet.

The other option is the “P” option, that can be used to get public information. First, it computes a number t (which we could also compute, as it depends on the current time). Then, we get three numbers:

  • pub_1 = recheck(b"CCTF", recheck(long_to_bytes(skey ^^ t), 0))
  • pub_2, which is a 64 bit prime number
  • pub_3, which is computed as pow(5, CP, pub_2)

First, we note that the number CP (and, therefore, CT) can be recovered if we can solve the DLP in $\mathbb{Z}_{p_2}$. As $p_2$ is a small prime, this is an easy problem for most of the primes. We can do this using this sagemath piece of code:

def get_pub_info():
    r.sendlineafter(b"[Q]uit\n", b"p")
    print("line", r.recvline())
    r.recvuntil(b"information is: ")
    pub1 = int(r.recvline())
    r.recvuntil(b"information is: ")
    pub2 = int(r.recvline())
    r.recvuntil(b"information is: ")
    pub3 = int(r.recvline())

    return pub1, pub2, pub3

r = process("./asemoon.sage")

pub1, pub2, pub3 = get_pub_info()
print("Computing CP...")
CP = discrete_log(GF(pub2)(pub3), GF(pub2)(5))
print(f"{CP = }")

CT = []
for _ in range(256):
    cb = _
    for _ in range(8):
        if cb & 1:
            cb = (cb >> 1) ^ CP
        else:
            cb >>= 1
    CT.append(cb & 0xFFFFFFFFFFFFFFFF)

Solving recheck(msg, x) == r

Now, what can we get from pub_1? It would be cool if we could solve the equation recheck(msg, x) == r knowing msg and r. This way, we could recover the value of recheck(long_to_bytes(skey ^^ t), 0). Well, this is the most straigtforward way I found to do this (probably not the most elegant, though).

The recheck function is defined as follows:

def recheck(msg, v):
	for m in msg:
		v = v ^^ m
		v = (v >> 8) ^^ CT[v & 0xFF] 
	return v & 0xFFFFFFFFFFFFFFFF

Our goal is to recover the v value, which is 64 bits long. First, we note that (v >> 8) is, at most, 56 bits long. Then, when XORed with CT[v & 0xFF], it will be a 64 bits number again. Then, we can compute r ^^ CT[i], for every i. When the result of that is a number whose length is less than or equal to 56 bits, we have a possible value for v & 0xFF and for v >> 8, so can get v doing (((v ^ CT[idx]) << 8) + idx) ^ m. For every round (4 in the case of msg = b"CCTF"), we keep a list of the possible values for v so far and return the last list we compute:

def recover_possible_v(msg, recheck, CT):
    vs = [[recheck]]
    for m in msg[::-1]:
        next_vs = []
        for v in vs[-1]:
            bls = []
            for ct in CT:
                bls.append((ct^v).bit_length())
            idxs = [i for i,x in enumerate(bls) if x <= 56]
            for idx in idxs:
                next_vs.append((((v ^ CT[idx]) << 8) + idx) ^ m)
        vs.append(next_vs)

    return vs[-1]

Solving recheck(x, v) == r

At this point, we have a list of possible values of recheck(long_to_bytes(skey ^^ t), 0). Now, it would be cool to recover long_to_bytes(skey ^^ t), because it is used in the verify function, which we need to pass to get the flag.

Let’s do some maths :D

Let’s think of v as a vector $v \in \mathbb{F}_2^{64}$, corresponding to its bits representation, of course. Let $m_i$ be the i-th character of the message.

The first operation that is performed in the recheck function is v ^^ m. This is a linear operation in $\mathbb{F}_2^{64}$. The next operation we see is v >> 8. This is another linear operation. More specifically, it is the result of the left multiplication by this matrix:

$$S = \begin{pmatrix} 0_{8\times56} & 0_{8} \newline I_{56} & 0_{56\times8} \end{pmatrix} $$

Then, we have this operation v & 0xFF which is the result of the left multiplication by this other matrix:

$$ P = \begin{pmatrix} 0_{56} & 0_{56\times8} \newline 0_{8\times56} & I_{8} \end{pmatrix} $$

The only operation left is CT[idx]. This is a lookup table, so one may think that it is nonlinear. However, let’s look at how CT is constructed:

for _ in range(256):
    cb = _
    for _ in range(8):
        if cb & 1:
            cb = (cb >> 1) ^^ CP
        else:
            cb >>= 1
    CT.append(cb & 0xFFFFFFFFFFFFFFFF)

The operations involved are >>, CP and an if condition, which is the tricky one. However, we can rewrite the whole condition as cb = (cb >> 1) ^^ (CP * (cb & 1)). Now, all the operations involved there are linear!

This means that the recheck function itself is an affine linear function. That is, given a $v_0$ and $CT$, there exist a matrix $A$ and a vector $b$ such that:

$$\text{recheck}(m, v_0) = Am + b$$

Finding $b$ is easy:

$$b = \text{recheck}(0, v_0)$$

So now we have that the function $m \mapsto \text{recheck}(m, v_0) + b$ is a linear one, represented by $m \mapsto Am$. To find $A$, we need to evaluate the function at the standard basis vectors ($e_i$) and write the output as columns to get the $A$ matrix. In code, this can be done like:

F = GF(2)
A = Matrix(F, 64, 64)
for bit in range(64):
    msg = bytearray(8)
    msg[bit // 8] = 1 << (bit % 8)
    out = recheck(msg, v0) ^ base

    for i in range(64):
        A[i, bit] = (out >> i) & 1

Now that we have $A$, we can recover $m$ by solving the equation

$$Am = r + b$$

Maybe $A$ is not invertible, so we can use the solve_right sagemath’s method to solve the equation instead. This is the function that recovers the message:

def recover_msg(r, v0, CT):
    F = GF(2)
    A = Matrix(F, 64, 64)
    rhs = vector(F, 64)

    base = recheck(b"\x00"*8, v0)
    delta = r ^ base

    for i in range(64):
        rhs[i] = (delta >> i) & 1

    for bit in range(64):
        msg = bytearray(8)
        msg[bit // 8] = 1 << (bit % 8)
        out = recheck(msg, v0) ^ base

        for i in range(64):
            A[i, bit] = (out >> i) & 1

    sol = A.solve_right(rhs)

    msg = bytearray(8)
    for i in range(64):
        if sol[i]:
            msg[i // 8] |= 1 << (i % 8)

    return bytes(msg)

Recovering the flag

Now that we can recover the value of long_to_bytes(skey ^^ t), we can look at the piece of code to retrieve the flag:

def verify(v, t):
	return recheck(long_to_bytes(skey ^^ t), v) == v

if ans == 'l':
    pr(border, 'Please send your hex token here:')
    token = sc().decode().strip()
    try:
        token = int(token, 16)
    except:
        die(border, "Your token is invalid! Bye!!")
    if 0 <= token < 2**nbit:
        t = int(time.time())
        t -= t % 10
        if verify(token, t):
            die(border, f"Congrats, you got the flag: {flag}")
    die(border, "Your token is wrong!")

Basically, we need to find a fixed point for the function $v \mapsto \text{recheck}(m_0, v)$. Following the exact same logic as before, this function is an affine linear function, and looks like:

$$\text{rechec}(m_0, v) = Bv + c$$

We can find $c$ and $B$ following a similar process as before, and we need to solve this system:

$$v = Bv + c \iff (I - B)v = c$$

We can do all of this with this code:

def fixed_point(msg, CT):
    F = GF(2)
    B = Matrix(F, 64, 64)
    for bit in range(64):
        v0 = 1 << bit
        out = recheck(b"\x00"*8, v0)
        for i in range(64):
            B[i, bit] = (out >> i) & 1

    I = identity_matrix(F, 64, 64)

    rhs_val = recheck(msg, 0)
    rhs = vector(F, [(rhs_val >> i) & 1 for i in range(64)])

    v_vec = (I - B).solve_right(rhs)

    v = 0
    for i in range(64):
        if v_vec[i]:
            v |= 1 << i

    return v

Finally, the main code of our solver looks like this:

possible_vs = []
while len(possible_vs) <= 0:
    r = process("./asemoon.sage")

    pub1, pub2, pub3 = get_pub_info()
    print("Computing CP...")
    CP = discrete_log(GF(pub2)(pub3), GF(pub2)(5))
    print(f"{CP = }")

    CT = []
    for _ in range(256):
        cb = _
        for _ in range(8):
            if cb & 1:
                cb = (cb >> 1) ^ CP
            else:
                cb >>= 1
        CT.append(cb & 0xFFFFFFFFFFFFFFFF)

    possible_vs = recover_possible_v(b"CCTF", pub1, CT)

possible_msgs = []
for v in possible_vs:
    try:
        msg = recover_msg(v, 0, CT)
        possible_msgs.append(msg)
    except:pass

msg = possible_msgs[0]
fp = fixed_point(msg, CT)
r.sendlineafter(b"[Q]uit\n", b"l")
r.sendlineafter(b"token here:\n", hex(fp)[2:].encode())
r.interactive()

which we can execute and recover the flag!

$ python get_flag.py
[+] Starting local process './asemoon.sage': pid 46244
Computing CP...
CP = 3177915011014156697
[*] Switching to interactive mode
┃ Congrats, you got the flag: CCTF{flag_for_testing}
[*] Got EOF while reading in interactive