1. The Horn — Writeup

The Horn — Writeup

カテゴリ: Crypto
元問題: DiceCTF 2026 “Carry the Flame”

1. チャレンジの読み解き

まず the_horn.py を読んで、「何が秘密で、何が目標か」を整理します。

KEY       = os.urandom(BLOCK_SIZE)   # 32バイトのランダムな秘密鍵（こちらには見えない）
CHALLENGE = os.urandom(32)           # 32バイトのランダムな値（これを当てるのが目標）

print(f"CHALLENGE: {encrypt(CHALLENGE, KEY).hex()}")  # 暗号化済みの値だけ教えてもらえる

サーバーとのやりとりは以下の流れです:

サーバー → 私: CHALLENGE_CT = encrypt(CHALLENGE, KEY)  ← 最初に渡される
私 → サーバー: 好きな平文（hex）
サーバー → 私: その平文を encrypt した結果               ← これを最大210回使える
私 → サーバー: "guess"
私 → サーバー: CHALLENGE の元の値（当てられればフラグ）

つまり、「暗号化オラクル」（任意の値を暗号化してもらえる窓口）を使って、CHALLENGE の元の値を復元せよ という問題です。

2. XOR とは何か（復習）

XOR（排他的論理和）はビット演算の一種で、以下の重要な性質があります:

A XOR A = 0           （同じ値と XOR すると 0 になる）
A XOR 0 = A           （0 と XOR しても変わらない）
A XOR B = B XOR A     （順番を入れ替えても同じ）
(A XOR B) XOR C = A XOR (B XOR C)   （結合法則）

特に重要なのは 「A XOR B XOR B = A」 という性質で、
「XOR した値をもう一度 XOR すると元に戻ります」。

3. pbox とは何か

pbox は バイトの並び順を入れ替えるだけ の操作です。バイトの値自体は変えません。

PBOX = [5, 22, 31, 18, 3, 19, ...]  # 長さ32の配列

def pbox(pt):
    return bytes([pt[PBOX[index]] for index in range(BLOCK_SIZE)])
    # 出力の 0 バイト目 ← 入力の 5 バイト目
    # 出力の 1 バイト目 ← 入力の 22 バイト目
    # 出力の 2 バイト目 ← 入力の 31 バイト目
    # ...

具体的な例（簡略化して4バイトで考える）:

1
2
3

入力:  [A, B, C, D]
PBOX:  [2, 0, 3, 1]   ← 0番目は2番目から取る、1番目は0番目から取る、...
出力:  [C, A, D, B]

pbox の重要な性質：XOR に対して分配法則が成り立つ

1	pbox(X XOR Y) = pbox(X) XOR pbox(Y)

なぜでしょうか？ XOR はバイト同士で独立に計算されます。
(X XOR Y) の i バイト目 = X[i] XOR Y[i]

pbox はその i バイト目を別の場所に移動させるだけなので:

1
2
3

pbox(X XOR Y)[j] = (X XOR Y)[PBOX[j]]
                 = X[PBOX[j]] XOR Y[PBOX[j]]
                 = pbox(X)[j] XOR pbox(Y)[j]

よって pbox(X XOR Y) = pbox(X) XOR pbox(Y) が成り立ちます。

4. encrypt を1ラウンドずつ追う

def encrypt(pt, key):
    for _ in range(32):
        pt = bxor(pt, key)   # ① KEY と XOR
        pt = pbox(pt)        # ② バイトを並び替え
    return pt

1ラウンドを式で書くと:

1	round(x) = pbox(x XOR KEY)

pbox の分配法則を使うと:

1 2	round(x) = pbox(x XOR KEY) = pbox(x) XOR pbox(KEY) ← ここがポイント！

つまり1ラウンドは「pbox を適用してから、pbox(KEY) という固定値と XOR する」操作です。

5. アフィン写像という見方

「固定の変換行列 L(x) に定数 c を足す」形の写像を アフィン写像 といいます:

1
2
3

f(x) = L(x) XOR c
       ^^^^   ^^^
       線形部分  定数部分（c は x によらない固定値）

1ラウンドに当てはめると:

1
2
3

round(x) = pbox(x)  XOR  pbox(KEY)
           ^^^^^^^        ^^^^^^^^^
           L(x)           c（定数。KEY が決まれば固定）

アフィン写像を何度合成してもアフィン写像のままです。では32ラウンド合成したときの 線形部分 はどうなるでしょうか？

1ラウンド目の線形部分: pbox
2ラウンド目の線形部分: pbox ∘ pbox = pbox^2
...
32ラウンド目の線形部分: pbox^32

つまり:

1
2
3

encrypt(x, KEY) = pbox^32(x)  XOR  C(KEY)
                  ^^^^^^^^^^^        ^^^^^^
                  線形部分（x に依存）  定数部分（KEY のみに依存）

ここで C(KEY) は KEY だけで決まる定数（複雑な式ですが x には依存しません）。

6. 全ゼロを使ったトリック

アフィン写像 f(x) = L(x) XOR c に対して、x = 0 を代入すると:

1	f(0) = L(0) XOR c = 0 XOR c = c

（L は線形写像なので L(0) = 0）

つまり 全ゼロを入力すると定数部分 c だけが取り出せます。

これを利用すると:

1	f(x) XOR f(0) = (L(x) XOR c) XOR (c) = L(x)

f(x) XOR f(0) を計算すれば、定数 c が消えて線形部分 L(x) だけ残ります！

今回の問題に当てはめると:

1	encrypt(x, KEY) XOR encrypt(\x00*32, KEY) = pbox^32(x)

CHALLENGE について言えば:

1
2
3

encrypt(CHALLENGE, KEY) XOR encrypt(\x00*32, KEY) = pbox^32(CHALLENGE)
     ↑                              ↑
  サーバーから渡された値      ← 全ゼロを送れば教えてもらえる！

KEY の情報が完全に消えて、誰でも計算できる公開済みの置換 pbox^32 だけが残ります。

7. 逆置換で CHALLENGE を復元する

ここまでで:

1	pbox^32(CHALLENGE) = CHALLENGE_CT XOR encrypt(\x00*32, KEY)

の右辺は手元で計算できます。
あとは左辺から CHALLENGE を取り出すために pbox^32 の逆置換 を適用すれば良いです。

pbox^32 を求める

pbox を [0, 1, 2, …, 31] に繰り返し適用すれば、
「どのインデックスがどこに移動するか」を追跡できます:

base = list(range(32))  # [0, 1, 2, ..., 31] = 恒等置換
for _ in range(32):
    base = pbox(base)
# base[i] = 元の i 番目のバイトが最終的に何番目の位置に来るか

例えば base = [7, 3, 19, ...] なら:

元の 0 番目 → 7 番目の位置へ
元の 1 番目 → 3 番目の位置へ
…

逆置換を適用する

pbox^32(x)[i] = x[base[i]] という関係から:

逆に「結果の i 番目は元の何番目から来たか」を求めるには base.index(i):

1 2	# 逆置換: 結果 ct の i 番目は、CHALLENGE の base.index(i) 番目に対応 CHALLENGE = bytes([ct[base.index(i)] for i in range(32)])

直感的に言うと:

「最終的に 0 番目に来るのは、元の何番目？」→ base.index(0) 番目
「最終的に 1 番目に来るのは、元の何番目？」→ base.index(1) 番目
…

8. ソルバの全体像

from ptrlib import *

ROUNDS = 32
BLOCK_SIZE = 32
PBOX = [5, 22, 31, 18, 3, 19, 11, 13, 10, 25, 24, 0, 2, 17, 20, 12, 6, 26, 1, 7, 16, 4, 27, 21, 15, 8, 30, 28, 14, 23, 29, 9]

def pbox(pt):
    # PBOX に従ってバイトを並び替える
    return bytes([pt[PBOX[index]] for index in range(BLOCK_SIZE)])

def bxor(bs1, bs2):
    # 2つのバイト列をバイトごとに XOR する
    return bytes([b1 ^ b2 for b1, b2 in zip(bs1, bs2)])

io = Socket("nc 34.170.146.252 30351")

# ① サーバーから encrypt(CHALLENGE, KEY) を受け取る
CHALLENGE_CT = bytes.fromhex(io.recvlineafter(b": ").decode())

# ② pbox^32 を求める（pbox を恒等置換に32回適用）
base = list(range(BLOCK_SIZE))
[base := pbox(base) for i in range(ROUNDS)]

# ③ 全ゼロを送って encrypt(\x00*32, KEY) を取得する（クエリ1回）
io.sendlineafter(b": ", (b"\x00"*BLOCK_SIZE).hex())
ct_of_zero = bytes.fromhex(io.recvline().decode())

# ④ pbox^32(CHALLENGE) = CHALLENGE_CT XOR encrypt(\x00*32, KEY)
ct = bxor(CHALLENGE_CT, ct_of_zero)

# ⑤ pbox^32 の逆置換を適用して CHALLENGE を復元
CHALLENGE = bytes([ct[base.index(i)] for i in range(BLOCK_SIZE)])

# ⑥ 答えを送ってフラグをもらう
io.sendline("guess")
io.sendlineafter(b"challenge: ", CHALLENGE.hex())
io.sh()

9. まとめ

この問題の核心は以下の1行に集約されます:

1	encrypt(x, KEY) XOR encrypt(0, KEY) = pbox^32(x)

ステップ	やること	理由
全ゼロを暗号化	`encrypt(\x00*32, KEY)` を取得	定数部分 C(KEY) を取り出すため
XOR で差分を取る	`CHALLENGE_CT XOR ct_of_zero`	KEY の影響を打ち消すため
逆置換を適用	`pbox^32` の逆を計算	`pbox^32(CHALLENGE)` から CHALLENGE を復元するため

脆弱性の根本: encrypt が XOR と置換だけで構成されているため、全体としてアフィン写像になってしまっています。アフィン写像は「全ゼロの暗号文を利用して鍵依存の定数を消す」という手法に対して脆弱です。真に安全な暗号（AES など）では、各ラウンドに 非線形変換（S-Box） を入れることでこのような解析を防いでいます。

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

kanon the blog

daily AlpacaHack The Horn Writeup