ångstromCTF 2021 - Exclusive Cipher

問題概要

Clam decided to return to classic cryptography and revisit the XOR cipher! Here's some hex encoded ciphertext:

ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c
The key is 5 bytes long and the flag is somewhere in the message.

XOR暗号（正式名称か不明）です。

解説

ヒントとしてありそうなのは「The key is 5 bytes long」です。鍵が5文字なので全探索出来そう？と思いますが、1文字辺り7bitあるので、全探索すると$(2^7)^5=34,359,738,368$。時間かければ出来そうな気もしますが、問題の難易度にしては非現実的ですね。

考えるべきはflagの先頭がactf{で始まっているということで、この文字列が与えられている暗号のどこにあるかを全探索することで鍵を明らかに出来ます。例えば一番最初の5文字がactf{であると仮定すると、鍵は暗号とXORして\x00\x06\x46\x51\x1eになります。

このようにactf{の位置で全探索すると現実的な範囲でflagを探せます。最後にflag候補が大量に出てくるのでそれっぽいのを目grepして終了。

solve.py

c = bytes.fromhex("ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c")
# header: actf{...}
for start in range(5, len(c)):
    keys = []
    keys.append(c[start - 5] ^ ord("a"))
    keys.append(c[start - 4] ^ ord("c"))
    keys.append(c[start - 3] ^ ord("t"))
    keys.append(c[start - 2] ^ ord("f"))
    keys.append(c[start - 1] ^ ord("{"))
    m = b"actf{"
    for i in range(len(c) - start):
        m += (keys[i % 5] ^ c[i + start]).to_bytes(1, "big")
    if b"{" in m:
        print(m)