はじめに

久しぶりにCTF再開しました。例によってまたCryptoです。

Writeupと書いてますが、いきなりネタバラシをするつもりはなく、答えに行き着くまでの自分の思考回路を記しつつ、というスタンスです。

なお、ぶっちゃけるとこの問題100%理解できている訳ではありません。
うやむやのまま解き切った、という箇所が存在します(後述)

Count me in!

以下のリード文。

I've been lately using this cool AES-CTR, but it was super slow, so I made a parallel version. Now it's blazing fast, but for some reason I have trouble decrypting the data...

与えられたデータはPythonのコードと、暗号化された文字列が並ぶ.txtファイル。
GitHubに解答用.ipynbファイルと共に置いておきますので、皆さんも一緒に動作させながら読んでくれればと思います。

まずPythonのコードを覗いてみます。
このままではコードは動きません。そもそも

from secret import key, flag

なんてモジュールはググっても見つかりません(意外とここで時間持っていかれました)。
main関数から1つずつ潜っていきましょう。

見やすさのため、一部切り貼りしています。

count.py

def encrypt_parallel(plaintext, workers_number):
    #このchunksの正体は？
    chunks = chunk(pad(plaintext), 16)

    #ここは一旦後回し
    results = distribute_work(worker_function, chunks, workers_number)
    return "".join(results)

def main():
    #改行(\n)の存在を無視してはいけないことに注意
    plaintext = """The Song of …
    …
    … of the Count!
    """ + flag
    encrypted = encrypt_parallel(plaintext, 32)
    print(encrypted.encode("hex"))

main関数で「長い文字列+flag」というplaintextをencrypt_parallel関数に突っ込んでます。どうせflagは最後までわからないので無視してしまいましょう。
コードにも書いてますが、まずは「plaintextにpad関数とchunk関数を施したchunks」が何者かを明らかにします。
まずはpad関数。簡単な例で処理を把握します。

pad.py

# テスト用に作成
def pad(data):
    pad_byte = 16 - len(data) % 16
    return data + (chr(pad_byte) * pad_byte)

pad("a")
# 'a\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'
pad("bb")
# 'bb\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'

dataの長さ % 16 == 0だったら16文字分をAsciiの0x10(10進数の16)で補う
dataの長さ % 16 == 1だったら15文字分をAsciiの0x0f(10進数の15)で補う
といった感じです。

chunk関数も、実際に実行してみたほうが理解が早いと思います。

chunk.py

# テスト用に作成
def pad(data):
    pad_byte = 16 - len(data) % 16
    return data + (chr(pad_byte) * pad_byte)

def chunk(input_data, size):
    return [input_data[i:i + size] for i in range(0, len(input_data), size)]

plaintext = """The Song of …
            …
            … of the Count!
            """
chunk(pad(plaintext), 16)
# ['The Song of the ',
# 'Count\n\nYou know ',
#        …
# 'g of the Count!\n',      ・・・(1)
# '\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10']

16文字ずつ区切ってリストにしているだけです。この結果が得られない場合、おそらく改行を考慮していないと思いますのでご注意を。

ここまででchunks(リスト)の正体はつかめました。
flag, pad関数は共にplaintextの末尾に足していくので、(1)までは変化することはありません。

さて、一旦保留していた

count.py

def encrypt_parallel(plaintext, workers_number):
    #このchunksの正体は？ -> 解決
    chunks = chunk(pad(plaintext), 16)

    #ここは一旦後回し -> 解読にかかる
    results = distribute_work(worker_function, chunks, workers_number)
    return "".join(results)

に戻ります。
実は、distribute_work関数の中のmultiprocessing.Poolなどのワードをググればわかりますが「worker_functionにchunksを突っ込む作業をマルチプロセス化して高速にしている」だけです。深い意味はないので次に進みます。

count.py

counter = 0
aes = AES.new(key, AES.MODE_ECB)
def worker_function(block):
    global counter
    # counterが変わるためkey_streamも変化する
    key_stream = aes.encrypt(pad(str(counter)))
    result = xor_string(block, key_stream)
    counter += 1
    return result

ここが暗号化のコアの部分になります。
AESによって作られた鍵(key_stream)と平文の一部(block = chunksの要素)のXORをとると暗号化完成、といったところでしょうか。
xor_stringsの中身にordやchrが入っていることから、おそらくchunks要素の各文字をAsciiに変換して¹XORを取っているんだろうな、と推測できます。
気になる人はpadやchunkの時のようにサンプルコードで確かめてみてください。ここでは割愛します。

chunksの各要素は16文字。各文字を16進Asciiで表記する²と計32文字。なのでXORを取る鍵と暗号化されたものも32文字と考えるべきでしょう。

暗号化データoutput.txtを32文字ごとに区切ると、ちょうど61個に。flagを追加していないplaintextでのchunks要素数が58なので、見当はずれではなさそうです。

XORなので
・chunks XOR key_stream $\rightarrow$ output
・chunks XOR output $\rightarrow$ key_stream
・output XOR key_stream $\rightarrow$ chunks
が成立します。以上をもとにして、復号作業に入ります。
chunks各要素とoutput.txtの32文字ずつのXORをとり、鍵を特定していきます。
(ex.
chunks[0] = 'The Song of the '$\rightarrow$54 68 65 20 53 6f 6e 67 20 6f 66 20 74 68 65 20
output.txt冒頭32文字 : 9d 5c 66 e6 5f ae 92 af 9c 8a 55 d9 d3 bf 64 0e
XORを取るとc9 34 03 c6 0c c1 fc c8 bc e5 33 f9 a7 d7 01 2e
見やすさのため半角スペースを挟んでます。)

これをchunks[56]までおこなって鍵を求めた結果が以下となります³。

最後の方こそばらつきがありますが、マルチプロセスによって同じ鍵を使ってchunks[0]〜[9]など10個ほどを並列して暗号化し、counter += 1で次の鍵を生成しているようです。
(ここが疑問。どこから10が出てきた？コード中には10という数字はないが…)

では、flagも加わった場合のchunks[57]〜はどうなるのでしょうか？
暗号文はoutput.txtで与えられており、使用するべき鍵も上記画像の下の方(まだ次の鍵に更新されていない)
・0x21a727f144239e5101349adc6a521168
・0x5fa3a9db2ed370cfec522b31af1b3410・・・(a)
・0xa7412169207d3758c13bdec564d4a0f0・・・(b)
あたりであると予想を立て、XORでchunks[57]〜を求めます。
そして、Ascii$\rightarrow$文字列変換で無事意味の通じるものが得られたら正解となります。

今回は(a)を用いることで
chunks[57] : 70 34 7b 61 74 5f 74 68 65 5f 65 6e 64 5f 6f 66 $\rightarrow$ p4{at_the_end_of
chunks[58] : 5f 74 68 65 5f 64 61 79 5f 79 6f 75 5f 63 61 6e $\rightarrow$ _the_day_you_can
(b)を用いることで
chunks[59] : 5f 6f 6e 6c 79 5f 63 6f 75 6e 74 5f 6f 6e 5f 79 $\rightarrow$ _only_count_on_y
chunks[60] : 6f 75 72 73 65 6c 66 7d 08 08 08 08 08 08 08 08 $\rightarrow$ ourself}⁴

以上から
p4{at_the_end_of_the_day_you_can_only_count_on_yourself}

おわりに

ここには詳しく書ききれなかったこととして、
(1)AES-ECBは鍵と暗号文がわかれば復号できる、というサイトは見かけましたが暗号文(key_stream)と平文(pad(str(counter)))から鍵(冒頭でもあげたfrom secret import key, flagのkeyの部分)を求めることはできないらしい。
(2)(マルチプロセスのことを考慮せず)counter += 1としているから毎回鍵が変わるはずなのに、chunks[0]とchunks[1]を暗号化する鍵が一緒なのはなぜ…？
の2点については大いに悩みました。

もうちょっとササっと解けるようにしたいですね…
ではでは。長文最後まで読んでいただき有難うございました。

Web、Revも気が向いたら記事にします。

そうでないと、どうやって'The Song of the 'などの文字列とXORを取るんだ、って話になります。 ↩
例えば"T $\rightarrow$ 0x54"なら54だけを用います。念の為。 ↩
最後のchunks[57]は元々"\x10"で埋まっている上、flagで置き換わる可能性が高いため除外しました。chunks[56]まではflag, pad関数の影響は受けません。 ↩
chunks[60]最後の08はpad関数による付け足しなので関係ありません ↩

CONFidence 2019 CTF Writeup

はじめに

Count me in!

おわりに