Tsumiki

コース目次 / 第1章

鍵の使い回し — XOR暗号を、既知平文で崩す

短い鍵を繰り返すXOR暗号文を生成し、フラグの先頭が既知(flag{)であることを手がかりに鍵を割り出して復号します。既知平文攻撃という手口を体で理解します。

第1章 / 全4章目安 約12分この章のゴール: 既知平文攻撃で、鍵を使い回したXOR暗号を解読できるようになる

XOR(排他的論理和)は、同じ値で2回XORすると元に戻る、という性質を持ちます。この性質を使った暗号化は手軽ですが、鍵を使い回す(短い鍵を繰り返す)と、危険なほど脆くなります。

暗号文を、作る

gen_challenge.py として保存します。

def xor(data, key):
    return bytes(b ^ key[i % len(key)] for i, b in enumerate(data))

key = b'\x2a\x7f\x1c'  # わずか3バイトの鍵
flag = b'flag{xor_key_reuse_is_weak}'
ct = xor(flag, key)
print(ct.hex())
python3 gen_challenge.py
4c137d4d0464450d43411a65750d795f0c7975166f7508794b1461

これが「暗号化」されたフラグです。鍵を知らないあなたは、これをどう解読しますか?

手がかり — フラグの形式は、決まっている

CTFのフラグは、ほぼ必ず flag{…} という決まった形式で始まります。つまり、平文の先頭5バイトは、暗号文を見る前から分かっています。これを既知平文(known-plaintext)と呼びます。
XORの性質(暗号文 = 平文 XOR 鍵)を使えば、鍵 = 暗号文 XOR 平文——つまり、既知の平文と暗号文から、鍵そのものを計算できます。

鍵を、割り出して復号する

crack.py として保存します。鍵の長さが分からないので、1〜8バイトを総当たりします。

def xor(data, key):
    return bytes(b ^ key[i % len(key)] for i, b in enumerate(data))

ct = bytes.fromhex(input("暗号文(hex): ").strip())
known = b'flag{'  # フラグの先頭は必ずこれ

for keylen in range(1, 9):
    candidate = bytes(c ^ p for c, p in zip(ct[:keylen], known[:keylen]))
    full_key = (candidate * (len(ct) // keylen + 1))[:len(ct)]
    plain = xor(ct, full_key)
    if plain.startswith(b'flag{') and all(32 <= b < 127 for b in plain):
        print(f"鍵の長さ {keylen}: {plain.decode()}")
echo "4c137d4d0464450d43411a65750d795f0c7975166f7508794b1461" | python3 crack.py
暗号文(hex): 鍵の長さ 3: flag{xor_key_reuse_is_weak}

取れました。鍵の長さを1つずつ試し、「既知平文から割り出した鍵で全体を復号したら、印字可能な文字列になり、しかも flag{ で始まるか」を確かめる——これが、既知平文攻撃の基本の形です。鍵の長さが小さいほど(=鍵が使い回されているほど)、この総当たりはあっという間に終わります。

本物の暗号は、これを許さない

AES のようなちゃんとした暗号は、1バイトの平文の違いが、暗号文全体を大きく変えるように設計されています(拡散という性質)。だから、こんな単純な既知平文攻撃は通用しません。今回崩れたのは、暗号アルゴリズムそのものではなく、「短い鍵を繰り返す」という使い方の弱さです。CTFのcryptoカテゴリの多くは、この「アルゴリズムではなく、使い方」を突く問題です。

持ち帰る一言

既知平文があれば、鍵を計算できる。 鍵の使い回しは、フラグの決まった接頭辞のような、ほんの少しの手がかりから崩れます。次は、もう一つの弱さ——「ランダム」という言葉の中身を疑います。

こうなっていればOK

卒業まであと2章です。

この章はまだ完了していません。