Google CTF 2023 WriteUps

發表於 2023-06-26

分類於 CTF

This article is LLM-translated by GPT-4o, so the translation may be inaccurate or complete. If you find any mistake, please let me know.

This year, I participated in the Google CTF with the joint team TTT from TSJ and THC. Initially, I hoped to solve more web challenges this year, but in reality, I only solved 4 crypto challenges and 1 web challenge. However, among the unsolved challenges, there was one crypto challenge that I almost solved, and one web challenge that was just one step away from being solved QQ.

crypto

LEAST COMMON GENOMINATOR?

This challenge involved a multi-prime RSA, where all the primes were generated using an LCG through rejection sampling. The parameters were unknown, but the seed was known along with the first six outputs. So, by reversing the LCG parameters from the outputs, we could generate the same primes and then decrypt the flag.

with open("dump.txt") as f:
    nums = [int(l.strip()) for l in f]
    nums = [
        211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
    ] + nums


def get_n_mul(s0, s1, s2, s3):
    return (s2 - s1) ** 2 - (s3 - s2) * (s1 - s0)


def get_n(nums):
    n_muls = [get_n_mul(*nums[i : i + 4]) for i in range(0, len(nums) - 4)]
    return reduce(gcd, n_muls)


def lcg_recover(nums):
    n = get_n(nums)
    m = (nums[2] - nums[1]) * pow(nums[1] - nums[0], -1, n) % n
    c = (nums[1] - nums[0] * m) % n
    assert all((nums[i + 1] == (nums[i] * m + c) % n for i in range(len(nums) - 1)))
    return m, c, n


m, c, n = lcg_recover(nums)
print(f"{m = }")
print(f"{c = }")
print(f"{n = }")

Then, by feeding the parameters back into the original script to calculate the primes, we could decrypt the flag:

key = RSA.import_key(open("public.pem").read())
primes = [
    6964450570065198027118448061962599095969292963451720606983076074110302247620361094481177336650245972387693336005120667581467488333027638118705008539730161,
    7109513965197777738721520789907575526136034746458175895732109137546481171865697500840378508918180196617036069476257074027995108145765959244529836549641993,
    7758154508395114989879950785752176334836698656046420925847088416774817812432659191047047708438059303423539646671584835156522194907603278157965955707005259,
    7955799783393765300984709531409964215101221994176999027251797780817998458393197830706475509797724088969852653876011767020597895098981645731673988999811477,
    8049144504671772187556553424691159710790891318598720019107386049196471499825470743225448919013622833022782797600720245991463382370047241689718971308017941,
    7987778116986381838775258565312725165121950830999324816847582213568425816373564731712259704074323632466001514291790772213690155362407596378791328567707167,
    7742807139391426401434854463005769878789338221498371127433759280276903959426344243059697341236161854231155869200509304579276312983038493231864184737415279,
    7008809633477108007104709300243139302645615208732682375658473606356527935080408259873753634627922136035847144744200184716721386652578226493417857596011803,
]
assert reduce(mul, primes) == key.n
phi = reduce(lambda x, y: x * y, [p - 1 for p in primes])
d = pow(key.e, -1, phi)
assert pow(2, phi, key.n) == 1
with open("flag.txt", "rb") as f:
    c = int.from_bytes(f.read(), "little")
    m = pow(c, d, key.n)
    print(m.to_bytes((m.bit_length() + 7) // 8, "big"))
# CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}

MYTLS

This challenge involved a protocol similar to MTLS implemented in Python, and several keys were provided:

ca-crt.pem: CA’s public key
guest-ecdhkey.pem: guest’s private key
guest-ecdhcert.pem: guest’s certificate
server-ecdhcert.pem: server’s certificate
admin-ecdhcert.pem: admin’s certificate

A certificate is essentially a public key signed by the CA.

The process was roughly as follows:

Loading graph...

After establishing an encrypted connection with the server, it would check if the client certificate’s subject contained CN=admin.mytls. If so, it would send the flag to the client. However, to connect using admin-ecdhcert.pem, you would typically need the corresponding private key, and creating a new public key yourself wouldn’t work because the server would check if the certificate sent by the client was signed by the CA using the CA’s public key.

On the server side, after the connection, it would perform the following actions:

  message = 'Hello guest!'
  if 'CN=admin.mytls' in client_cert.subject.rfc4514_string():
      message = 'Hello admin! ' + _FLAG

  print_encrypted(message, server_ephemeral_random, derived_key)
  while True:
    print_encrypted(
        'Welcome to our write-only file storage!\n\n'
        'Select the storage slot [0-9]:',
        server_ephemeral_random, derived_key)
    storage_slot = input_encrypted(server_ephemeral_random, derived_key)
    path = os.path.join('/tmp/storage/', storage_slot.decode('utf-8'))
    print_encrypted('Gimme your secrets:', server_ephemeral_random,
                    derived_key)
    secret = input_encrypted(server_ephemeral_random, derived_key)
    with open(path, 'rb+') as f:
      h = hashlib.new('sha256')
      h.update(f.read())
      prev_hash = h.hexdigest()
      f.seek(0)
      f.write(secret)
      print_encrypted('Saved! Previous secret reference: ' + prev_hash,
                      server_ephemeral_random, derived_key)

There was an oracle that could open a file according to the specified path (with path traversal) and output its hash, then override the file with the input content. However, the rb+ mode wouldn’t truncate the file when writing.

For example, if the original file content was aaaaa and you wrote only a b, the file would become baaaa. By comparing the hash, you could read the entire file content byte by byte.

Looking at the Dockerfile, the only files on the server container besides flag.txt were server-ecdhkey.pem. However, the former was read into memory and deleted at the start of the server, so the only readable file was the latter, which was the private key corresponding to the server certificate.

Here are the steps to connect and use the oracle to leak the server’s private key:

import binascii
from cryptography import x509
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives import hmac
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
import hashlib
import os
from secrets import token_hex
import string
from pwn import remote, context

with open("ca-crt.pem", "rb") as ca_file:
    ca = x509.load_pem_x509_certificate(ca_file.read())
with open("server-ecdhcert.pem", "rb") as server_cert_file:
    server_cert_content = server_cert_file.read()
    server_cert = x509.load_pem_x509_certificate(server_cert_content)
with open("guest-ecdhcert.pem", "rb") as f:
    client_cert_content = f.read()
    client_cert = x509.load_pem_x509_certificate(client_cert_content)
with open("guest-ecdhkey.pem", "rb") as f:
    client_key = serialization.load_pem_private_key(f.read(), None, default_backend())


io = remote("mytls.2023.ctfcompetition.com", 1337)
io.recvuntil(b"Please provide the client certificate in PEM format:\n")
io.sendline(client_cert_content)

# Generate client random
client_ephemeral_random = token_hex(16).encode()  # not really
io.recvuntil(b"Please provide the ephemeral client random:")
io.sendline(client_ephemeral_random)

# Generate client ephemeral key
client_ephemeral_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
client_ephemeral_public_key = client_ephemeral_key.public_key()

io.recvuntil(b"Please provide the ephemeral client key:")
io.sendline(
    client_ephemeral_public_key.public_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PublicFormat.SubjectPublicKeyInfo,
    )
)

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral random:\n")
server_ephemeral_random = io.recvline().strip()

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral key:\n")
server_ephemeral_public_key_content = b""
while (line := io.recvline()) != b"\n":
    server_ephemeral_public_key_content += line
server_ephemeral_public_key = serialization.load_pem_public_key(
    server_ephemeral_public_key_content
)

# Exchange
client_ephemeral_secret = client_ephemeral_key.exchange(
    ec.ECDH(), server_ephemeral_public_key
)
client_secret = client_key.exchange(ec.ECDH(), server_cert.public_key())
derived_key = HKDF(
    algorithm=hashes.SHA256(), length=32, salt=b"SaltyMcSaltFace", info=b"mytls"
).derive(
    client_ephemeral_secret
    + client_secret
    + client_ephemeral_random
    + server_ephemeral_random
)

# Calculate Client HMAC
client_hmac = hmac.HMAC(derived_key, hashes.SHA256())
client_hmac.update(b"client myTLS successful!")
client_hmac_content = client_hmac.finalize()
io.recvuntil(b"Please provide the client HMAC:")
io.sendline(client_hmac_content.hex().encode())

# Verify Server HMAC
io.recvuntil(b"Server HMAC:\n")
server_hmac_content = bytes.fromhex(io.recvlineS().strip())
server_hmac = hmac.HMAC(derived_key, hashes.SHA256())
server_hmac.update(b"server myTLS successful!")
server_hmac.verify(server_hmac_content)

# mTLS established!


def recv_encrypted(io):
    ct = bytes.fromhex(io.recvlineS().strip())
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    decryptor = cipher.decryptor()
    pt = decryptor.update(ct) + decryptor.finalize()
    return pt.rstrip(b"\x00")


def send_encrypted(io, msg):
    msg = msg + b"\x00" * (16 - len(msg) % 16)
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    encryptor = cipher.encryptor()
    ct = encryptor.update(msg) + encryptor.finalize()
    io.sendline(ct.hex().encode())


# hello message
print(recv_encrypted(io).decode())


def poc():
    secret = b"x"  # guess the file prefix

    print(recv_encrypted(io).decode())
    send_encrypted(io, b"/app/server-ecdhkey.pem")
    print(recv_encrypted(io).decode())
    send_encrypted(io, secret)
    print(recv_encrypted(io).decode())  # hash 1

    print(recv_encrypted(io).decode())
    send_encrypted(io, b"/app/server-ecdhkey.pem")
    print(recv_encrypted(io).decode())
    send_encrypted(io, secret)
    print(recv_encrypted(io).decode())  # hash 2

    # if our guess is right, then two hash should be the same


target_file = b"/app/server-ecdhkey.pem"


def oracle(secret):
    # we do this twice as the server returns previous hash
    send_encrypted(io, target_file)
    send_encrypted(io, secret)
    recv_encrypted(io)
    recv_encrypted(io)
    recv_encrypted(io)

    send_encrypted(io, target_file)
    send_encrypted(io, secret)
    recv_encrypted(io)
    recv_encrypted(io)
    return recv_encrypted(io).decode().split("reference: ")[-1]


def oracle_batch(secrets):
    # batch query to reduce network latency
    for secret in secrets:
        send_encrypted(io, target_file)
        send_encrypted(io, secret)
        send_encrypted(io, target_file)
        send_encrypted(io, secret)
    for _ in secrets:
        recv_encrypted(io)
        recv_encrypted(io)
        recv_encrypted(io)
        recv_encrypted(io)
        recv_encrypted(io)
        yield recv_encrypted(io).decode().split("reference: ")[-1]


target_hash = oracle(b"")
charset = (
    "- " + string.ascii_uppercase + string.ascii_lowercase + string.digits + "+/=\n"
)
known_content = b""

while True:
    ss = [known_content + c.encode() for c in charset]
    hs = list(oracle_batch(ss))
    for secret, h in zip(ss, hs):
        if h == target_hash:
            known_content = secret
            break
    else:
        print("Either EOF or charset is wrong")
        break
    print(known_content)
print(known_content.decode())

I know I didn’t check the server certificate because I read the server certificate directly from the filesystem instead of the socket, so it didn’t matter.

Once we know the server’s private key, we need to think about how to get the flag. Checking the certificates, we find that the only subject that can pass the check is admin-ecdhcert.pem. The private key we obtained is the server’s, not the admin’s, so it seems useless, right…?

Actually, looking at the process diagram again, if we use admin-ecdhcert.pem when sending the client cert initially, the difficulty lies in calculating the secret using ECDH with the certificate. However, according to the key exchange property, we know exchange(client_priv, server_pub) == exchange(server_priv, client_pub). Here, the only unknown is client_priv (admin private key), so using the leaked server private key and the admin cert for the exchange would also yield the correct secret.

According to the official solution, this attack is called Key Compromise Impersonation (KCI) attack.

So, finally, modifying the script a bit, we get the flag:

import binascii
from cryptography import x509
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives import hmac
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
import hashlib
import os
from secrets import token_hex
import string
from pwn import remote, context

with open("ca-crt.pem", "rb") as ca_file:
    ca = x509.load_pem_x509_certificate(ca_file.read())
with open("server-ecdhcert.pem", "rb") as server_cert_file:
    server_cert_content = server_cert_file.read()
    server_cert = x509.load_pem_x509_certificate(server_cert_content)
with open("guest-ecdhcert.pem", "rb") as f:
    client_cert_content = f.read()
    client_cert = x509.load_pem_x509_certificate(client_cert_content)
with open("guest-ecdhkey.pem", "rb") as f:
    client_key = serialization.load_pem_private_key(f.read(), None, default_backend())
with open("server-ecdhkey.pem", "rb") as f:
    server_key = serialization.load_pem_private_key(f.read(), None, default_backend())
with open("admin-ecdhcert.pem", "rb") as f:
    admin_cert_content = f.read()
    admin_cert = x509.load_pem_x509_certificate(admin_cert_content)

context.log_level = "debug"

io = remote("mytls.2023.ctfcompetition.com", 1337)
io.recvuntil(b"Please provide the client certificate in PEM format:\n")
io.sendline(admin_cert_content)

# Generate client random
client_ephemeral_random = token_hex(16).encode()  # not really
io.recvuntil(b"Please provide the ephemeral client random:")
io.sendline(client_ephemeral_random)

# Generate client ephemeral key
client_ephemeral_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
client_ephemeral_public_key = client_ephemeral_key.public_key()

io.recvuntil(b"Please provide the ephemeral client key:")
io.sendline(
    client_ephemeral_public_key.public_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PublicFormat.SubjectPublicKeyInfo,
    )
)

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral random:\n")
server_ephemeral_random = io.recvline().strip()

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral key:\n")
server_ephemeral_public_key_content = b""
while (line := io.recvline()) != b"\n":
    server_ephemeral_public_key_content += line
server_ephemeral_public_key = serialization.load_pem_public_key(
    server_ephemeral_public_key_content
)

# Exchange
client_ephemeral_secret = client_ephemeral_key.exchange(
    ec.ECDH(), server_ephemeral_public_key
)
server_secret = server_key.exchange(ec.ECDH(), admin_cert.public_key())
derived_key = HKDF(
    algorithm=hashes.SHA256(), length=32, salt=b"SaltyMcSaltFace", info=b"mytls"
).derive(
    client_ephemeral_secret
    + server_secret
    + client_ephemeral_random
    + server_ephemeral_random
)


# Calculate Client HMAC
client_hmac = hmac.HMAC(derived_key, hashes.SHA256())
client_hmac.update(b"client myTLS successful!")
client_hmac_content = client_hmac.finalize()
io.recvuntil(b"Please provide the client HMAC:")
io.sendline(client_hmac_content.hex().encode())

# Verify Server HMAC
io.recvuntil(b"Server HMAC:\n")
server_hmac_content = bytes.fromhex(io.recvlineS().strip())
server_hmac = hmac.HMAC(derived_key, hashes.SHA256())
server_hmac.update(b"server myTLS successful!")
server_hmac.verify(server_hmac_content)

# mTLS established!


def recv_encrypted(io):
    ct = bytes.fromhex(io.recvlineS().strip())
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    decryptor = cipher.decryptor()
    pt = decryptor.update(ct) + decryptor.finalize()
    return pt.rstrip(b"\x00")


def send_encrypted(io, msg):
    msg = msg + b"\x00" * (16 - len(msg) % 16)
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    encryptor = cipher.encryptor()
    ct = encryptor.update(msg) + encryptor.finalize()
    io.sendline(ct.hex().encode())


# hello message
print(recv_encrypted(io).decode())
# CTF{KeyC0mpromiseAll0w51mpersonation}

PRIMES

This challenge’s source code is very short. In summary, it has a fixed prime $q$ and a bunch of small known primes $p$ . Then, by encoding the flag into bits $b_i$ , it calculates

x = \prod p_i^{b_i} \mod{q}

The goal is to recover the flag from $x$ .

My first thought was multiplicative knapsack, which, after taking the log, becomes:

\log{x} \equiv \sum b_i \log{p_i} \pmod{q}

Then, it could be solved using LLL or similar methods. However, the $q-1$ in this challenge is not very dlog friendly, so I abandoned this approach.

However, after the competition, I heard that partial dlog could also be used to obtain some information, and the parts with insufficient density could be solved by brute-forcing some bits and guessing the flag format.

I thought of a different approach:

x+yq = \prod p_i^{b_i}

This means $x+yq$ is a very smooth integer. So, by taking $M=\prod{p_i}$ and using Coppersmith’s method to find small roots of $f(y)=x+yq$ , we should theoretically find the solution.

Here, finding the unknown modulus, which is $x+yq$ itself, is the key. It obviously satisfies $(x+yq)|M$ , but I didn’t know how large $y$ was. So, I generated a few strings of the same length as the original to estimate its bit length, which could be around 900-1500 bits. The suitable $\beta$ parameter was also determined by trial and error. I set $\beta=0.3$ and brute-forced the possible $y$ sizes to find the solution.

q = 0xD2F8711CB5502C512ACEA59BE181A8FCF12F183B540D9A6998BF66370F9538F7E39FC507545DAD9AA2E71D3313F0B4408695A0A2C03A790662A9BD01650533C584C90779B73604FB8157F0AB7C9A82E724700E5937D9FF5FCF1EE3BE1EDD7E07B4C0F035A58CC2B9DB8B79F176F595C1B0E90B7957309B96106A50A01B78171599B41C8744BCB1C0E6A24F60AE8946D37F4D4BD8CF286A336E1022996B3BA3918E4D808627D0315BFE291AEB884CBE98BB620DAA735B0467F3287D158231D
x = 0x947062E712C031ADD0B60416D3B87D54B50C1EFBC8DBB87346F960B242AF3DF6DD47406FEC98053A967D28FE91B130FF0FE93689122931F0BA6E73A3E9E6C873B8E2344A459244D1295E99A241E59E1EEA796E9738E6B1EDEED3D91AE6747E8ECA634C030B90B02BAF8AE0088058F6994C7CAC232835AC72D8B23A96F10EF03D74F82C49D4513423DAC298698094B5C631B9C7C62850C498330E9D112BB9CAA574AEE6B0E5E66D5B234B23C755AC1719B4B68133E680A7BCF48B4CFD0924D

def gen_primes(r, n):
    primes = Primes()[:n]
    bound = prod(primes[n - r:])
    return primes, next_prime(bound)

lm = 74
p, _ = gen_primes(131, lm * 7)

M = prod(p)
y = Zmod(M)["y"].gen()
f = (x + y * q).monic()
for b in range(900, 1500, 50):
    rs = f.small_roots(X=2**b, beta=0.40, epsilon=0.03)
    if rs:
        # I found answer at b = 1450
        print(b, rs)
        break
fs = [p for p, _ in gcd(ZZ(f(rs[0])), M).factor()]
bits = []
for pp in p:
    if pp in fs:
        bits.append(1)
    else:
        bits.append(0)
bits.reverse()
flag = bytes(
    [int("".join(map(str, bits[i : i + 7])), 2) for i in range(0, len(bits), 7)]
)[::-1]
print(flag)
# CTF{w0W_c0Nt1nUed_fr4Ct10ns_suR3_Ar3_fUn_Huh}

CURSVED

This challenge is based on a group on $\mathbb{F}_p$ defined by $x^2-Dy^2=1$ , implementing a signature scheme similar to eddsa. The goal is to forge a signature.

I’ve seen this type of challenge many times before. Its order is $p-1$ , indicating it likely has a homomorphism that maps the original curve point to $\mathbb{F}_p$ , making DLP easier.

First:

x^2-Dy^2=(x-\sqrt{D}y)(x+\sqrt{D}y)=uv=1

There is a mapping $\varphi: (x,y) \rightarrow x-\sqrt{D}y$ to the multiplicative group of $\mathbb{F}_p$ . Substituting it into the addition formula:

\begin{aligned} (x_1,y_1)+(x_2,y_2)&=(x_1 x_2 + D y_1 y_2, x_1 y_2 + x_2 y_1) \\ \varphi(x_1,y_1)\varphi(x_2,y_2)&=(x_1-\sqrt{D}y_1)(x_2-\sqrt{D}y_2) \\ &= x_1 x_2 - \sqrt{D} (x_1 y_2 + y_1 x_2) + D y_1 y_2 \\ &= \varphi(x_1 x_2 + D y_1 y_2, x_1 y_2 + x_2 y_1) \end{aligned}

We see it is indeed a group homomorphism. So, the original $P=xG$ becomes $\varphi(P)=\varphi(G)^x$ , which is a DLP problem in $\mathbb{F}_p$ .

Decomposing $p-1$ , we find it is a safe prime of the form $p-1=2q$ , so attacks like Pohlig-Hellman are ineffective. However, $q$ is about 253 bits, and finite field DLP can be quickly solved using Number Field Sieve attacks, especially since the prime size is relatively small. So, I directly called cado-nfs to solve it.

A tip for using cado-nfs is that the first time it runs, it spends a lot of time finding many relations and solving linear algebra. However, after solving, it leaves a snapshot file. By letting cado-nfs use the snapshot file (the path can be found in its output message), it can quickly solve for different dlog targets.

from sage.all import *
from pwn import remote
from chal import Curve, Priv
from subprocess import check_output
import ast

# generate cado-nfs snapshot with:
# cado-nfs.py -dlp -ell 11768463700042336292273890180302660989254097664036009733585033009225459108313 target=6995199833182080318718269901795376783328546073433342063509926122404606405798 23536927400084672584547780360605321978508195328072019467170066018450918216627
# and find the message starting with `If you want to compute one or several new target(s)` to get the snapshot file
# target probably doesn't matter
snapshot = "/tmp/cado.8enuuo06/p75.parameters_snapshot.0"

p = 0x34096DC6CE88B7D7CB09DE1FEC1EDF9B448D4BE9E341A9F6DC696EF4E4E213B3
ell = 11768463700042336292273890180302660989254097664036009733585033009225459108313
assert 2 * ell == p - 1
d = 3
F = GF(p)
sD = F(3).sqrt()
phi = lambda x, y: x - sD * y
g = phi(0x2, 0x1)

io = remote("cursved.2023.ctfcompetition.com", 1337)
io.recvuntil(b"pub = ")
pub = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"nonce = ")
nonce = bytes.fromhex(io.recvlineS().strip())


y = phi(*pub)

gell = g**ell
yell = y**ell
x_mod_2 = int(yell.log(gell))

logbase = 9124582963071133528786001226298469992950948841420505614055341832865405446557
g2 = g**2
logg2 = 3825907694889401444121713872797773271827220109941494987822025998908276753583
assert F(logbase) ** logg2 == g2
y2 = y**2
logy2 = int(check_output(["cado-nfs.py", snapshot, f"target={y2}"]).strip().decode())
print(logy2)
assert F(logbase) ** logy2 == y2
x_mod_ell = logy2 * pow(logg2, -1, ell) % ell
assert g2**x_mod_ell == y2

x = int(crt([x_mod_2, x_mod_ell], [2, ell]))
assert g**x == y

C = Curve(p, d, p - 1)
G = C @ (0x2, 0x1)
priv = Priv(x, G)
R, S = priv.sign(nonce)
io.sendlineafter(b"sig = ", f"{R.x} {R.y} {S}")
io.interactive()
# CTF{pe11_conics_are_not_quite_e11iptic_curves}

*MHK2

Solution

During the competition, I solved most of this challenge, but couldn’t finish the remaining part in time.

This challenge implemented the public key cryptosystem described in the paper A knapsack public-key cryptosystem using two random sequences, and the goal was to break this system.

Since the paper is paywalled, you can refer to the author’s writeup for a description of this cryptosystem.

This is called MHK2 because the same author previously had a similar cryptosystem: A systematic encryption algorithm for knapsack scheme using random sequence, abbreviated as MHK. Checking related papers, we find Equivalent key attack against a public-key cryptosystem based on subset sum problem, which describes an attack on the original MHK. After reading it, I thought it could also work on MHK2.

The attack is roughly as follows:

\vec{a} = e \vec{s} \pmod{p}

Here, we only know $\vec{a}$ , while $e, p, \vec{s}$ are all unknown. Rewriting it as:

\vec{a} = e \vec{s} + p \vec{k}

Using LLL to find the orthogonal lattice of $\vec{a}$ , denoted as $L(\vec{a})$ , we have:

L(\vec{a}) = e L(\vec{a})\vec{s} + p L(\vec{a})\vec{k} = \vec{0}

Here, $p,e$ are non-zero and coprime, so if a vector $\vec{t}$ in $L(\vec{a})$ is short enough to satisfy $| \vec{t} \cdot \vec{s} | < p$ , then $\vec{t} \cdot \vec{s} = 0$ , which also means $\vec{t} \cdot \vec{k} = 0$ . This implies that $L(\vec{a})$ contains many vectors that are orthogonal to both $\vec{s}$ and $\vec{k}$ .

The attack paper also proves that there is at least one vector $\vec{t_0}$ in $L(\vec{a})$ that does not satisfy $\vec{t_0} \cdot \vec{s} = 0$ . In my tests, I found that there is usually only one such vector, and it appears as the last (largest) vector in the LLL reduced basis.

By the way, I found that $\vec{t_0} \cdot \vec{s}$ is usually $\pm p$ , and $\vec{t_0} \cdot \vec{k}=\mp e$ , because this satisfies $e(p)+p(-e)=0$ , and there are no smaller integer solutions (otherwise, it would violate the coprimality of $p,e$ ).

Next, finding the orthogonal lattice of $L(\vec{a})$ minus the last vector yields two vectors $\vec{u_1}, \vec{u_2}$ , indicating that $\vec{a}, \vec{s}, \vec{k}$ are all in the lattice spanned by $\vec{u_1}, \vec{u_2}$ .

There are only two vectors because, according to the rank-nullity theorem, $L(\vec{a})$ has $n-1$ vectors. Removing one leaves $n-2$ , and finding the orthogonal lattice (kernel) again gives a rank of $n-(n-2)=2$ .

The attack paper then brute-forces the linear combinations of $\vec{u_1}, \vec{u_2}$ to find $\vec{s}, \vec{k}$ , with a search range of about $(2\sqrt{N})^4$ . However, for this challenge, $N=2^{128}$ is relatively large.

According to post-competition discussions, some teams did follow this method, with some optimizations, and successfully found the equivalent key. I also used z3 to find the equivalent key during the competition, but due to some implementation issues, the decrypted bits were completely incorrect.

Here, I took a different approach. First, writing the relationships between the vectors:

\begin{aligned} \vec{a} &= v_1\vec{u_1}+v_2\vec{u_2} \\ \vec{s} &= x_1\vec{u_1}+x_2\vec{u_2} \\ \vec{k} &= y_1\vec{u_1}+y_2\vec{u_2} \end{aligned}

Here, $\vec{a}$ is about $2^{136}$ , $\vec{s}, \vec{k}$ are about $2^{128}$ , and $\vec{u_1}, \vec{u_2}$ are about $2^{64}$ , so $v$ is about $2^{72}$ , and $x, y$ are about $2^{64}$ .

Substituting the relationships into the original equation:

\begin{aligned} \vec{a} &= e \vec{s} + p \vec{k} \\ &= e (x_1\vec{u_1}+x_2\vec{u_2}) + p (y_1\vec{u_1}+y_2\vec{u_2}) \\ &= (ex_1+py_1)\vec{u_1} + (ex_2+py_2)\vec{u_2} \\ &= v_1\vec{u_1}+v_2\vec{u_2} \end{aligned}

Writing the relationships of $v, x, y$ in matrix form:

M \begin{bmatrix} e \\ p \end{bmatrix} = \begin{bmatrix} x_1 & y_1 \\ x_2 & y_2 \\ \end{bmatrix} \begin{bmatrix} e \\ p \end{bmatrix} = \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}

So, we have 6 unknowns and 2 equations, which is obviously unsolvable. However, according to the challenge’s generation method, we know $\sum s_i + 2 = p$ ( $s_i$ represents the $i$ -th component of $\vec{s}$ ), adding another equation, but still not enough.

Through some observations, I found that $\det(M) = x_1 y_2 - x_2 y_1 = \pm 1$ always holds. I’ll explain this later. For now, we have 6 unknowns and 4 equations, which means we still can’t fully determine the solution. However, since $x_1, x_2, y_1, y_2$ are relatively small ( $\approx 2^{64}$ ), we can try using lattice methods.

Using Groebner basis and resultant, I found a linear equation involving only $x_1, x_2$ , with coefficients over $2^{128}$ . So, we can use LLL to solve for $x_1, x_2$ . This allows us to calculate $\vec{s}$ and $p,e$ , and thus the original private key, decrypting the flag.

import ast

with open("output.txt") as f:
    pk = ast.literal_eval(f.readline())
    ct = ast.literal_eval(f.readline())


def find_ortho_zz(*vecs):
    assert len(set(len(v) for v in vecs)) == 1
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]])
    print("LLL", L.dimensions())
    nv = len(vecs)
    L[:, :nv] *= 2**256
    L = L.LLL()
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


def find_key(a):
    # a=e*s+p*k
    t1 = find_ortho_zz(a)
    assert t1 * vector(a) == 0
    # we assume that only t1[-1]*s!=0 and t1[-1]*k!=0
    # so the t1[:-1] is orthogonal to s and k
    # therefore s, k are spanned by u1, u2
    u1, u2 = find_ortho_zz(*t1[:-1])
    # suppose s=x1*u1+x2*u2, k=y1*u1+y2*u2
    # a=e*s+p*k=e*(x1*u1+x2*u2)+p*(y1*u1+y2*u2)
    #          =(e*x1+p*y1)*u1+(e*x2+p*y2)*u2
    #          =         v1*u1+         v2*u2
    v1, v2 = matrix([u1, u2]).solve_left(vector(a))
    print(f"{v1 = } {v2 = }")
    # now we expect to find integers x1, x2, y1, y2, e, p such that
    # matrix([
    #     [x1,y1],
    #     [x2,y2]
    # ])*vector([e,p])==vector([v1,v2])
    # sum(x1*u1+x2*u2)+2==p
    # so there are three equations and six unknowns

    # after some testing, I found that det([[x1,y1],[x2,y2]]) is either 1 or -1
    # so we have four equations and six unknowns, which means it is possible to reduce it to an single equation and two unknowns

    for det in [1, -1]:
        R = QQ["x1s, x2s, y1s, y2s, es, ps"]
        x1s, x2s, y1s, y2s, es, ps = R.gens()
        f1, f2 = matrix([[x1s, y1s], [x2s, y2s]]) * vector([es, ps]) - vector([v1, v2])
        f3 = x1s * y2s - x2s * y1s - det
        f4 = sum(x1s * u1 + x2s * u2) + 2 - ps
        gb = R.ideal([f1, f2, f3, f4]).groebner_basis()
        mul = reduce(lcm, [c.denom() for c, _ in gb[1]])
        eq = gb[1].resultant(f4, ps) * mul
        # this equations appear to be a linear equation in x1, x2
        # so we can solve it using LLL as x1, x2 are small
        print(eq)
        L = matrix(
            QQ,
            [
                [eq.constant_coefficient(), 1, 0, 0],
                [eq.coefficient({x1s: 1}), 0, 1, 0],
                [eq.coefficient({x2s: 1}), 0, 0, 1],
            ],
        )
        bounds = [1, 1, 2**66, 2**66]
        scale = [2**128 // x for x in bounds]
        Q = diagonal_matrix(scale)
        L *= Q
        L = L.LLL()
        L /= Q
        for row in L:
            if row[1] < 0:
                row = -row
            if row[0] == 0 and row[1] == 1:
                x1, x2 = row[2:]
                # while we should be able to plug the x1, x2 into the ideal the get full solution
                # but I found that the dimension of the ideal is 1, so we can't do that here
                # we just solve it manually
                s = (x1 * u1 + x2 * u2).change_ring(ZZ)
                p = sum(s) + 2
                e_cand1 = a[0] * pow(s[0], -1, p) % p
                e_cand2 = a[1] * pow(s[1], -1, p) % p
                if e_cand1 == e_cand2:
                    return s, e_cand1, p


s1, e1, p1 = find_key(pk["a1"])
print("key1 done")
s2, e2, p2 = find_key(pk["a2"])
print("key2 done")


def decrypt_bit(C1, C2):
    M1 = pow(e1, -1, p1) * C1 % p1
    M2 = pow(e2, -1, p2) * C2 % p2
    return (M1 + M2) % 2


def decrypt(ciphertext):
    plaintext_bin = ""
    for C1, C2 in ciphertext:
        plaintext_bin += str(decrypt_bit(C1, C2))

    split_bin = [plaintext_bin[i : i + 7] for i in range(0, len(plaintext_bin), 8)]

    plaintext = ""
    for seq in split_bin:
        plaintext += chr(int(seq, 2))
    return plaintext


print(decrypt(ct))
# CTF{faNNYPAcKs_ARe_4maZiNg_AnD_und3Rr@t3d}

About det(M) = ±1

Here’s a brief explanation of why $\det(M) = x_1 y_2 - x_2 y_1 = \pm 1$ holds. Returning to the original definitions of $\vec{s}, \vec{k}, \vec{u_1}, \vec{u_2}$ :

\begin{aligned} \vec{s} &= x_1\vec{u_1}+x_2\vec{u_2} \\ \vec{k} &= y_1\vec{u_1}+y_2\vec{u_2} \end{aligned}

Rewriting it in matrix form:

M \begin{bmatrix} \vec{u_1} \\ \vec{u_2} \end{bmatrix} = \begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix} \begin{bmatrix} \vec{u_1} \\ \vec{u_2} \end{bmatrix} = \begin{bmatrix} \vec{s} \\ \vec{k} \end{bmatrix}

An important point is that $(\vec{u_1}, \vec{u_2})$ and $(\vec{s}, \vec{k})$ are two different bases of the same lattice. A key property of lattices is that their volume is constant, regardless of the basis.

In fact, since $(\vec{u_1}, \vec{u_2})$ are shorter, we can also say $(\vec{u_1}, \vec{u_2}) = \operatorname{LLL}(\vec{s}, \vec{k})$ .

For square matrices, $\operatorname{vol}(B)=\det(B)$ , and for non-square matrices, $\operatorname{vol}(B)=\sqrt{\det(BB^T)}$ . (Here, row vectors are considered as bases.)

Thus, we have $\operatorname{vol}([\vec{u_1} \, \vec{u_2}]^T) = \operatorname{vol}([\vec{s} \, \vec{k}]^T) = V$ . Multiplying the transpose of the $s,k$ matrix by itself:

\begin{bmatrix} \vec{s} \\ \vec{k} \end{bmatrix} \begin{bmatrix} \vec{s} & \vec{k} \end{bmatrix} = M \begin{bmatrix} \vec{u_1} \\ \vec{u_2} \end{bmatrix} \begin{bmatrix} \vec{u_1} & \vec{u_2} \end{bmatrix} M^T

Taking the determinant:

V^2=\det(M) V^2 \det(M^T)

This means $\det(M)\det(M^T)=1$ , but since $\det(M)=\det(M^T)$ , we have $\det(M)=\pm 1$ .

The $M$ here is the same as the previous matrix, except for a transpose, so the determinants are the same:

\begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix}^T = \begin{bmatrix} x_1 & y_1 \\ x_2 & y_2 \\ \end{bmatrix}

web

UNDER-CONSTRUCTION

This challenge was quite boring. There were two websites, one in Flask and one in PHP, and a registration form where you could set the tier. If the tier was gold, you would get the flag. However, the Flask side would check the tier during registration and not allow you to set it to gold. After registration, it would use requests to call an API on the PHP side, which only Flask could access, to register again.

The key was that Flask and PHP parsed form data differently. One took the first occurrence of a key, and the other took the last. Using this parser differential, you could register an account with a gold tier and get the flag:

curl -v 'https://under-construction-web.2023.ctfcompetition.com/signup' -F 'username=1234xx' -F 'password=1234yy' -F 'tier=green' -F 'tier=gold'
# CTF{ff79e2741f21abd77dc48f17bab64c3d}

crypto#

LEAST COMMON GENOMINATOR?#

MYTLS#

PRIMES#

CURSVED#

*MHK2#

Solution#

About det(M) = ±1#

web#

UNDER-CONSTRUCTION#