問題 (ソース)

The Horn - AlpacaHack

import os

ROUNDS = 32
BLOCK_SIZE = 32

KEY = os.urandom(BLOCK_SIZE)
FLAG = os.getenv("FLAG", "flag{example_flag}")

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 bxor(bs1, bs2):
    return bytes([b1 ^ b2 for b1, b2 in zip(bs1, bs2)])

def pbox(pt):
    assert len(PBOX) == BLOCK_SIZE
    return bytes([pt[PBOX[index]] for index in range(BLOCK_SIZE)])

def encrypt(pt, key):
    for _ in range(ROUNDS):
        pt = bxor(pt, key)
        pt = pbox(pt)
    return pt

CHALLENGE = os.urandom(32)
print(f"CHALLENGE: {encrypt(CHALLENGE, KEY).hex()}")

for i in range(210):
    inp = input("pt: ")
    if inp != "guess":
        pt = bytes.fromhex(inp)
        assert len(pt) == BLOCK_SIZE
        print(encrypt(pt, KEY).hex())

    else:
        challenge_guess = input("challenge: ")
        if bytes.fromhex(challenge_guess) == CHALLENGE:
            print(f"=== Your score is {i} ===")
            print("flag:", FLAG)
        exit()

考え

encrypt(pt, key) の実装を見ると

pt = bxor(pt, key)
pt = pbox(pt)

を ROUNDS 回繰り返していることがわかる。

今回のソースコードでは ROUNDS = 32 だから

$$ \text{encrypt}(pt, key) = \text{pbox}(\text{pbox}(pt \oplus key) \oplus key) \dots \quad (32\text{回}) $$

と表せる。

pbox(pt) の実装を見ると

pt = bytes([pt[PBOX[index]] for index in range(BLOCK_SIZE)])

とあるが、これは各文字(byte)に対して pt[index] = pt[PBOX[index]] だから、たとえば pt[0] = pt[PBOX[0]] = pt[5] と表せるので、つまり文字を入れ替えていることになる。

また、bxor(pt, key) の実装を見ると

pt = bytes([b1 ^ b2 for b1, b2 in zip(pt, key)])

なので、たんに各文字に対して XOR を適用することになる。

ところで、もし ROUNDS = 2 としたとき encrypt(pt, key) は

$$ \text{pbox}(\text{pbox}(pt \oplus key) \oplus key) $$