DownUnder CTF 2023 Writeup

apbq II

Challenge

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001

hints = []
for _ in range(3):
    a, b = randint(0, 2**312), randint(0, 2**312)
    hints.append(a * p + b * q)

FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')

Analysis: The challenge provides 3 numbers that are linear combinations of p and q along with their product, and asks us to recover p and q in order to break the RSA encryption.

Since there are 3 hints, I’ll label the three equations as:

a1q + b1p == h1 (1)
a2q + b2p == h2 (2)
a3q + b3p == h3 (3)

Eliminating q from equations (1) and (2) gives us $a_2h_1 - a_1h_2 = (b_1a_2-b_2a_1)~p$ , or equivalently $a_2h_1-a_1h_2 = 0 ~ mod ~ p$

Similarly, $b_2h_1-b_1h_2 = 0 ~ mod ~ q$

Multiplying these together yields $a_1b_1 h_2^2 - (a_2b_1 +a_1b_2) h_1h_2 + a_2b_2 h_1^2 = 0 ~ mod ~ N (*)$

Following this approach we can build up 9 equations. However, looking back after the event ended, it turns out just 2 hints are actually enough to solve the challenge.

Building a lattice matrix:

Looking at equation (*), we can treat it as a 3-variable equation $xh_2^2 - yh_1h_2 + zh_1^2 = 0$

This is a linear equation, so we can solve it with LLL using the matrix:

\begin{pmatrix} \frac{1}{2^{614}} & & & h_{2}^2 \\ & \frac{1}{2^{615}} & & -h_{1}h_{2} \\ & & \frac{1}{2^{614}} & h_{1}^2 \\ & & & N \\ \end{pmatrix}

This matrix will contain a short vector holding the solution: $(\frac{a_1a_2}{2^{614}}...., 0)$ (I’ll spare the full derivation).

We also have the identity $a_1b_1 a_2^2 + a_2b_2 a_1^2 = (a_2b_1 + a_1b_2)a_1a_2$

From this degree-2 homogeneous equation I can recover the ratio $a_1/a_2 = t_1/t_2$ , and since $t_1h_2 - t_2h_1$ is divisible by $p$ , we can compute the gcd to recover p.

Solution

from Crypto.Util.number import long_to_bytes

n = 19604411241131769363446674414275822275458180476470552084588074159518829172495704100505151090666577360738167275118902368371310303168115405693118232835691333564186301532462296609038929723894816307213749698854885742811071911120730847279568876996811433319487396434622751326281226335521193361938724747445445693062336009352580319440819629260614301234971135026395941954109172567154559773437059174108362692061503832044135079892892132874437669744266153424229215832487832220575345912010076934611701182205068942016022731469408259665250938484104489962832891496953003599692437819685070043991828977623632396604764153766442526750861
c = 16285668872352205553535195410427806596787838055817589230402081772267074935944610262823936480340920868690431897597533868262062616060037808676539290467732178272289192993251540763800683055555842878669862850848141950704501553807462214356142018528608581546359772903806691435935873069006470208826518183488708349814610769150918356795466688732617809664831695402633481224388822180989614886783145141129157248734213457746877012517003702540070132542733288350979858743766340483503277308585752213220454288897741262154622769402029906981612699288206404870733274360554941455758083078106150045394190625280336371690998959720015636304971
hints = [773921762798470573303163880380136299117907456177270598418425239064611119645412840945432294881005107606154919094297188183879147500755682510817840590276985061404198538395146658442221987303866921786284298394947485319583779671756246394491275898343836522004269864718405399287554020900395899143149709408762450693357109188640512875099087677956684946219071353228860650842182953922400081939934842271539450654323, 1506346165967409413422972644306025635334450240732478358292064973873339506571546529986180145578525288707094235933775031106971678278204568310035260899591267480098015553318079460357474533531922997212816264042117005473870580122983241038123126855791876827449194400045937398578284016176289760858365282167537689282643483235235028505475719615108102516557986483184881658418430287064598580231630440534438966422546, 531028473288853560172466570664059891687387973059926255729701774553291285115938502989142318123512885100092638435578692032744904444237266108167428726130739434630511943317357743527053899234918340191006102436386051432760331852295930159729030763033361158582919982579082557775409422474301977588011705535991555292564664521116375190464371518812625647175447427886432255779925378071998411170643507118426289778768]

h1, h2, h3 = hints
m = Matrix.identity(QQ, 4)
m[0,0] = 1 / 2^614
m[1,1] = 1 / 2^615
m[2,2] = 1 / 2^614
m[0,3] = h2^2
m[1,3] = -h1*h2
m[2,3] = h1^2
m[3,3] = n

m = m.LLL()

a1b1 = m[0][0] * 2**614

a2b1_a1b2 = m[0][1] * 2**615

a2b2 = m[0][2] * 2**614

R.<t> = PolynomialRing(QQ)

f = a1b1*t^2 - a2b1_a1b2 * t + a2b2

t1, t2 = f.roots()[0][0].as_integer_ratio()

p = gcd(h1*t1-h2*t2,n)

q = n // p

d = pow(65537, -1, int(p-1) * int(q-1))

m = pow(c,int(d), n)

print(long_to_bytes(int(m)))

Mini DNS Server

Challenge

import time
from dnslib.server import DNSServer, BaseResolver
from dnslib import RR, TXT, QTYPE, RCODE


class Resolver(BaseResolver):
    def resolve(self, request, handler):
        reply = request.reply()
        reply.header.rcode = RCODE.reverse['REFUSED']

        if len(handler.request[0]) > 72:
            return reply

        if request.get_q().qtype != QTYPE.TXT:
            return reply

        qname = request.get_q().get_qname()
        if qname == 'free.flag.for.flag.loving.flag.capturers.downunderctf.com':
            FLAG = open('flag.txt', 'r').read().strip()
            txt_resp = FLAG
        else:
            txt_resp = 'NOPE'

        reply.header.rcode = RCODE.reverse['NOERROR']
        reply.add_answer(RR(qname, QTYPE.TXT, rdata=TXT(txt_resp)))
        return reply


server = DNSServer(Resolver(), port=8053)
server.start_thread()
while server.isAlive():
    time.sleep(1)

The challenge asks us to send a DNS query to the server for the domain free.flag.for.flag.loving.flag.capturers.downunderctf.com, with a request no longer than 72 bytes and a question type of TXT.

I had been reading up on DNS before this challenge, so I was quite interested when I saw it. Unfortunately, I didn’t have enough time to finish during the competition :((

Structure of a DNS Query

import dns.query
import dns.message
import dns.rdatatype

domain = 'free.flag.for.flag.loving.flag.capturers.downunderctf.com'
qname = dns.name.from_text(domain)
dns.message.make_query(qname, dns.rdatatype.TXT).to_wire()
# b'\x13\xec\x01\x00\x00\x01\x00\x00\x00\x00\x00\x00\x04free\x04flag\x03for\x04flag\x06loving\x04flag\tcapturers\x0cdownunderctf\x03com\x00\x00\x10\x00\x01'

As we can see, the first 2 bytes are the ID, the next 2 bytes are flags, then 2 bytes for the question count (which is 1), followed by 6 bytes for answer, authority, and additional counts that we don’t use — that’s 12 bytes of header in total.

Each subdomain label takes the form \x??abcde where \x?? is the length of that subdomain.

For example: blog.anhtv.live is encoded as \x04blog\x05anhtv\x04live

\x00 marks the end of a domain name.

The 2 bytes near the end indicate the QUERYTYPE (\x00\x10 is TXT).

The last 2 bytes indicate the QUERYCLASS (\x00\x01 is IN — Internet).

So as it stands, the query is already 75 bytes long. How do we get it down to 72?

DNS Pointer and Solution

To handle long messages, DNS uses pointers to refer back to previously seen data.

\xc0 + offset moves the DNS pointer to that position in the packet.

Noticing that the server doesn’t check the flag bytes and the first 2 bytes are arbitrary, we can make use of those 4 bytes by placing .com at the very beginning of the packet:

b = b"\x03com"
# Reuse the \x00 domain terminator byte
b += \x00\x01\x00\x00\x00\x00\x00\x00

# Domain
b += \x04free\x04flag\x03for\x04flag\x06loving\x04flag\tcapturers\x0cdownunderctf
# Pointer back to the start (where .com lives)
b += \xc0\x00
b += \x00\x10\x00\x01

Now we have the complete payload — let’s send it to the server.

import socket

host = "0.0.0.0" # Replace by DNS Server
port = 8053

sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)

sock.sendto(b, (host, port))
t = sock.recv(4096)
print(t)
sock.close()

apbq II

Challenge

Solution

Mini DNS Server

Challenge

Structure of a DNS Query

DNS Pointer and Solution

Comments