アルゴリズムで解決するCTF Web問 @ GMO IERAE HackNight #1 「Webセキュリティ編」

アルゴリズムで解決するCTF Web問 Takeshi Kaneko / @arkark_

Takeshi Kaneko @arkark_ 高度診断部 高度診断課 CTF Web担当 experimental と deprecated な機能が好き 推しのパズル: The Witness 最近遊んだパズル: The Regions

アルゴリズム？ アルゴリズムの知識や考え方がCTFで役立つことがある • 高速化 / 必要リクエスト数の最小化 • 現実的な時間内に探索したい • クライアント問でbotのtimeoutに間に合わせたい • 攻撃ペイロードやオラクルの構築 • ライブラリの実装理解 など

二分探索 身近な例: Blind SQL Injectionの二分探索 ' OR IF(flag REGEXP '^FLAG¥{foo[a-e].*', SLEEP(5), 1=1) # 5秒 → 「FLAG{fooa, …, FLAG{fooe」のいずれか 一瞬 → 「FLAG{foof, …, FLAG{fooz」のいずれか 計算量: 𝑂 𝐿 Σ → 𝑂(𝐿 log Σ ) クエリ数減少！ 高速化！ うれしい！ ※ 汎用性が高いのでSQLi以外でも使える

二分探索: fire-leak (ASIS CTF Finals 2024) XS-Leak with Client-Side ReDoSの例 • <input>のpattern属性は正規表現 → ReDoSが可能 （※ 一部のブラウザのみ） • この問題ではbotのtimeoutが短い → 二分探索 + α で要・高速化 参考: https://blog.arkark.dev/2024/12/30/asisctf-finals/#web-fire-leak

• https://blog.arkark.dev/2024/12/30/asisctf-finals/#web-fire-leak

アジェンダ CTFでアルゴリズムが関係する問題を2問紹介します • 0CTF 2023 - newdiary • SECCON CTF 2023 Quals - hidden-note

0CTF 2023 newdiary (14 solves) Trigram CSS Injection

問題概要: 0CTF 2023 - newdiary
• ゴール: XSS
• CSP
<meta http-equiv="Content-Security-Policy"
content="script-src 'nonce-<%= nonce %>'; frame-src
'none'; object-src 'none'; base-uri 'self'; style-src
'unsafe-inline' https://unpkg.com">
• nonce例: nonce-5a1b8ueu308zz8j09ibr5advzszzgaiz

• HTML Injectionのチャンスが2回
• 目標:
• ① CSS Injectionでnonceリーク
• ② リークしたnonceを使ってscriptの挿入 → XSS

問題概要: 0CTF 2023 - newdiary 従来のCSS injection（例: recursive @import) • 1文字ずつ先頭からリーク • 問題点: 時間がかかりすぎる→ botがtimeoutする → 高速化手法を考える必要がある

解法: 0CTF 2023 - newdiary アイデア • ① 「nonceの部分(連続)文字列」の情報をたくさん収集 • ② 得た部分文字列の情報からnonce全体を復元 イメージ • 5a1, 1b8, b8u, 8ue, ... が部分文字列だとわかったとする • 「nonce-5a1b8ue...」がnonce？

解法: 0CTF 2023 - newdiary 長さ3の文字列全ての組合せに対して部分文字列のCSSiで判定 （部分文字列である場合は /leak?q=... にリクエストが送信される）

解法: 0CTF 2023 - newdiary アルゴリズムパート • 入力 • 任意の3文字の文字列sについて • sがnonceの部分文字列であるかどうかのYes/Noが与えられる • 出力 • 条件を満たす文字列nonceを復元 競技プログラミングでいうところの構築問題

関連リンク: 0CTF 2023 - newdiary 参加者writeup: • https://github.com/salvatore-abello/CTF-Writeups/blob/main/0c tf%20-%202023/newdiary/README.md • https://blog.huli.tw/2023/12/11/en/0ctf-2023-writeup/#web-n ewdiary-14-solves 参考: • Code Vulnerabilities Put Proton Mails at Risk • https://www.sonarsource.com/blog/code-vulnerabilities-leakemails-in-proton-mail/ ※ 現在ではCSS injection典型テクニックのひとつです

• https://github.com/salvatore-abello/CTF-Writeups/blob/main/0ctf - 2023/newdiary/README.md
• https://blog.huli.tw/2023/12/11/en/0ctf-2023-writeup/#web-newdiary-14-solves
• https://www.sonarsource.com/blog/code-vulnerabilities-leak-emails-in-proton-mail/

SECCON CTF 2023 Quals hidden-note (1 solve) Algorithm-Based Oracle

問題概要: hidden-note • 一般的なノートアプリ • ノートの作成・削除（自明なCSRF） • 検索機能 • 共有機能（※後述） • サーバサイド言語: • Go • ゴール: • admin botのノート（フラグ）を奪取 • 形式: SECCON{[a-z0-9_]+}

問題概要: hidden-note 共有機能 • 検索結果を共有できる • URLは誰でもアクセス可能 • 検索結果をリークできる • SECCON{.*} にマッチ → 表示されない • フラグをリークできない

考察: hidden-note /?query=du検索時の共有の流れを確認する ① ユーザのノートを取得 変な実装はなさそう

考察: hidden-note /?query=du検索時の共有の流れを確認する ② duを含むノートでフィルタ（検索） ③ 文字列でソート 変な実装はなさそう

考察: hidden-note /?query=du検索時の共有の流れを確認する ④ SECCON{.*}にマッチするノートを除去 変な実装はなさそう

考察: hidden-note /?query=du検索時の共有の流れを確認する ① ユーザのノートを取得: getNotes ② duを含むノートでフィルタ: search ③ 文字列でソート: sort ④ SECCON{.*}にマッチするノートを除去: filter getNotes → search → sort → filter 何も不自然な箇所はなさそう... 本当に？

考察: hidden-note /?query=du検索時の共有の流れを確認する ① ユーザのノートを取得: getNotes ② duを含むノートでフィルタ: search ③ 文字列でソート: sort ④ SECCON{.*}にマッチするノートを除去: filter アイデア: • 検索にフラグがヒットするかどうかでソートの挙動が変化するケースは ないだろうか？ → オラクルにしたい • ただし、観測可能なソート結果にはフラグが消えている...

考察: hidden-note ところでGoのソート実装ってどうなってたっけ？ https://pkg.go.dev/sort#Slice The sort is not guaranteed to be stable: equal elements may be reversed from their original order. • not guaranteed to be stable • 安定であることが保証されていない • → 不安定ソートじゃん！！！

• https://pkg.go.dev/sort#Slice

考察: hidden-note 安定ソートとは？ • ソート順序が同じ要素同士の相対順序がソート前後で変化しない (id, content) の組に対して content を基準にソート（全順序ではない）: (1, "ccc") (2, "aaa") (3, "ccc") (4, "aaa") (5, "aaa") (2, "aaa") (4, "aaa") (5, "aaa") (1, "ccc") (3, "ccc") 2 < 4 < 5 の順序は保存されている

考察: hidden-note ソートの実装をよく読む① • ソートアルゴリズム: • pdqsort • ソート対象の状態に応じて、 処理内容が分岐している • 要素数が12以下のとき: • insertion sort • → 安定ソート https://github.com/golang/go/blob/go1.21.0/src/sort/zsortfunc.go#L61

• https://github.com/golang/go/blob/go1.21.0/src/sort/zsortfunc.go#L61

考察: hidden-note ソートの実装をよく読む② • 要素数が12より大きいときは？ • 最初にシャッフルしている！ • → 不安定だあ https://github.com/golang/go/blob/go1.21.0/src/sort/zsortfunc.go#L246-L252

• https://github.com/golang/go/blob/go1.21.0/src/sort/zsortfunc.go#L246-L252

考察: hidden-note Goのソートの性質 • 要素数 ≦ 12: 安定ソート • 要素数 ＞ 12: 不安定ソート 12を境に挙動が切り替わる！！！ → XS-Leakのオラクル構築に使えそう

解法: hidden-note オラクルの構築レシピ 1. CSRFで「 SECCON{d 」のノートを 12個 追加する 2. 「 /?query=SECCON{d 」の検索結果を取得する • フラグがヒットした場合: • ソート対象の要素数: 13 → 不安定ソート • 順序がめちゃくちゃになる • フラグがヒットしなかった場合: • ソート対象の要素数: 12 → 安定ソート • 順序が保存される オラクルを実装して、XS-Leak！

補遺: hidden-note 言語実装のソートアルゴリズムの挙動に着目したXS-Leak問 • 解くうえで知っていたら得してた事前知識 • 安定ソート / 不安定ソート の性質 • ソート対象の性質に応じて処理が切り替わるソートアルゴリズム • 例: IntroSort, TimSort ソートアルゴリズムオタクにおすすめです！

関連リンク: hidden-note 公式writeup • https://blog.arkark.dev/2023/09/21/secconquals#web-hidden-note

• https://blog.arkark.dev/2023/09/21/seccon-quals#web-hidden-note

まとめ アルゴリズムが関連するCTFの問題を紹介しました • 二分探索 • 構築問題 • ソートアルゴリズム アルゴリズムに限らずコンピュータサイエンスの他の分野と 交わる問題は特に面白い