KalmarCTF 2026 0racle Writeup — Heaven's Gate と自己書き換えコードを剥がして FNV-1a を総当りする

概要

KalmarCTF 2026 の Rev 問題「0racle」（123pts）。Free Pascal / Lazarus 製の Windows PE32 GUI アプリケーションで、テーマは「Oracle of Delphi」。正しい入力を与えると “The gods are pleased” と表示される。フラグは入力そのもの（40文字） で、正解を逆算するのがゴールだ。

一見ただの「入力チェック」問題だが、検証ロジックにたどり着くまでに XOR エンコード → 自己書き換えコード → Heaven’s Gate（32bit→64bit 切替） という3枚の殻が被さっている。1枚ずつ剥がしていく。

解析

Step 1: XOR エンコードされた文字列を剥がす

バイナリ内の文字列は XOR 0x57 でエンコードされている。デコードすると UI メッセージが出てくる。

• "Speak your truth and i shall convene with the gods on your behalf!" — 入力プロンプト
• "I feel a bit woozy, what were you saying?" — 不正解
• "The gods are pleased and commend your insight." — 正解メッセージ

正解メッセージの参照元をたどると、検証の入口が見える。

Step 2: 入力をキーにした自己書き換えコード

offset 0x154AC2 に、暗号化されたコードブロック（1109バイト）が埋まっている。これは 入力の最初の7文字をキーにして復号される。

# 復号: flag_data[i] ^= input[i % 7] ^ 0x57
# 最初の7バイトが全て 0x90 (NOP) になれば検証パス
# input[i] = flag_data[i] ^ 0xC7 → "kalmar{"

つまり、復号後の先頭が NOP スレッド（0x90 ×7）になる入力＝kalmar{ が、そのままキーとして要求される。復号された7つの NOP の後ろのバイト列は、x86 コードとして実行される。静的解析だけ見ていると「ただのデータ」に見えるブロックが、実は次段のコードだった。

Step 3: Heaven’s Gate（32bit → 64bit の切り替え）

復号されたコードには Heaven’s Gate が使われている。64bit Windows（WOW64）上で動く 32bit プロセスの中から、CS セレクタを差し替えて 64bit モードへ遷移するアンチリバース手法だ。

PUSH 0x33               ; 64bit モード用の CS セレクタ
CALL +0                 ; リターンアドレスをスタックに積む
ADD dword [ESP], 9      ; リターンアドレスを補正
RETF                    ; far return → 64bit モードへ切り替わる

補正の ADD dword [ESP], 9 は RETF の手前、まだ 32bit で実行されるので、対象はスタック上の 32bit リターンアドレス（esp）だ。切り替え後の 64bit として同じバイト列を逆アセンブルすると [rsp] に見えるが、実行時の意味は 32bit の [esp] 操作である。32bit PE の中に 64bit コードが同居しているため、標準的なデコンパイラは正しく解釈できない。ここが本問題の一番の壁だった。

Step 4: 64bit コードを抽出して Ghidra へ

Heaven’s Gate の先にある 64bit コードを手で切り出し、64bit バイナリとして Ghidra headless に投入して逆コンパイルする。3つの関数が見えてくる。

1. toupper 関数（0x26F）: 入力を大文字化し、長さを返す
2. FNV-1a ハッシュ関数（0x09）: 標準の FNV-1a（init=0x811c9dc5, prime=0x01000193）
3. 多項式評価関数（0x11E）: 各文字を多項式テーブルから計算

Step 5: 検証ロジックの特定

メインの検証関数は、FNV-1a ハッシュで入力を 7つのチャンクに分けて独立に照合していた。

// 入力は 40 文字ちょうどをチェック
// 7 チャンクに分割し、それぞれ FNV-1a ハッシュで期待値と比較
if (fnv1a(input+7,  4) == 0x1FDB82EB &&  // [7:11]
    fnv1a(input+12, 3) == 0xC498C8A6 &&  // [12:15]
    fnv1a(input+16, 5) == 0xD451383B &&  // [16:21]
    fnv1a(input+22, 3) == 0xF1D1BDC9 &&  // [22:25]
    fnv1a(input+26, 5) == 0x5768CCA7 &&  // [26:31]
    fnv1a(input+32, 3) == 0xE25D1966 &&  // [32:35]
    fnv1a(input+36, 4) == 0x45B2772B)    // [36:40]
    return SUCCESS;

ここで重要な観察がある。最終的な一致判定を行う FNV-1a は、toupper を通す前の元の入力（大文字小文字混在）に対して計算される。toupper と多項式チェックは分岐に関わるが、フラグの一致判定そのものは生入力の FNV で行われる。この取り違えが最後まで効いてくる（後述）。

なお、この FNV 条件が照合するのは 7チャンクの領域だけで、区切り位置（offset 11, 15, 21, 25, 31, 35）に入る _ 自体は検証していない。区切り文字は、40文字フラグの骨格（kalmar{ に続けて各チャンクを _ で繋ぐ形式）から確定する。

Step 6: チャンクごとの総当り

各チャンクは 3〜5 文字と短いので、FNV-1a を総当りすれば候補を列挙できる。ただし FNV-1a 32bit は衝突しないハッシュではない。printable ASCII 全体（95文字）で回すと 5文字チャンクには別の前像（衝突）が混じる（例: 0xD451383B は S1gN5 のほか !#Mi" でも一致し、0x5768CCA7 は 3NteR 以外にも複数の前像を持つ）。これらの衝突はいずれも記号を含む文字列だ。フラグが取る文字は英数字だろうというフラグ形式の想定で候補集合を英数字（大文字小文字＋数字、62文字）に絞ると、実際この2つのハッシュはそれぞれ S1gN5 / 3NteR の1通りに定まる（他の5チャンクも同様に一意。printable 全体を列挙してから形式制約で弾いても同じ結論だ）。こうして 40文字全体が正しいフラグ形式になり、チャレンジの検証を通るものを最終フラグとして確定する。

def fnv1a(data):
    h = 0x811c9dc5
    for b in data:
        h ^= b
        h = (h * 0x01000193) & 0xFFFFFFFF
    return h

charset = (string.ascii_letters + string.digits).encode()  # 英数字62文字（記号込みの衝突を避ける）
for c1 in charset:
    h1 = (0x811c9dc5 ^ c1) * 0x01000193 & 0xFFFFFFFF
    for c2 in charset:
        ...  # チャンク単位でブルートフォース

チャンクごとの結果は次の通り。

総当りの規模は、3文字チャンクなら英数字62文字で 62^3 ≈ 24万 通りで一瞬。5文字チャンクは 62^5 ≈ 9.2億 通りある。素朴な CPython ループでは分単位で厳しいが、FNV-1a の prime は 2^32 上で可逆なので、**目標ハッシュから逆算する／前半を前進・後半を目標から後退させて中間で突き合わせる（meet-in-the-middle）**と探索が大幅に減る。prefix の中間状態を再利用する・C 実装・並列化でも十分実用的な時間に収まる（printable 全体の 95^5 ≈ 77億 は前述の衝突が混じるので避ける）。

フラグ

kalmar{M15S_Th3_S1gN5_4Nd_3NteR_tH3_M4Z3

（40文字ちょうど。閉じブレースは含まれない仕様）

ハマったポイント

1. 多項式テーブルの罠: 最初に多項式評価から候補 KALMAR{M15S_TH3_S1GN5_4ND_3NTER_TH3_M4Z3（全部大文字）を得たが、これは使えなかった。FNV-1a は 元の入力（大文字小文字混在） に対して計算されるため、大文字版はハッシュが合わない。多項式・toupper は構造や骨格の制約には関わるが、最終的な大小文字混在フラグの一致判定そのものには効かず、本命は生入力に対する FNV だった。
2. Heaven’s Gate: 32bit PE 内の 64bit コードは標準デコンパイラでは正しく解析されない。コードを手動抽出し、64bit バイナリとして Ghidra に投入して初めて読めた。
3. func_0x0000000f の誤認: Ghidra が FNV-1a 関数の途中（オフセット 0x0f）を別の関数エントリと誤認識した。実際は同じ関数の内部で、スタックフレームのプロローグを飛ばして途中に入るだけ。
4. charset の選び方: 最初は「大文字＋数字」だけで回したが空振り。フラグが大文字小文字混在だったため、小文字を含む英数字（62文字）まで広げて確定した。逆に記号まで含む printable ASCII 全体に広げると FNV の衝突が混じるので、英数字に絞るのがちょうど良い。

キーインサイト

1. 層を1枚ずつ剥がす: XOR 文字列 → 入力キーによる自己書き換え → Heaven’s Gate → 64bit デコンパイル。各段は次段の「鍵」になっている。最初の7文字が kalmar{ を強制されるのは、それが自己書き換えの復号キーだから。
2. Heaven’s Gate は「切って別バイナリにする」: 32/64bit が混在するコードは、64bit 部分を切り出して単独の 64bit バイナリとして解析器に食わせるのが早い。
3. 検証に使われる正規化を取り違えない: toupper を通した値と、生の入力のどちらでハッシュを取っているか。ここを間違えると、正しく総当りしても永久に合わない。
4. チャンク独立検証は総当りに弱い: 40文字を一括ハッシュせずチャンク分割している時点で、各チャンクを独立に潰せる。設計上の弱点を突く。