CTF Writeup: XOR-CBC - AlpacaHack
XORなブロック暗号をCBCモードで暗号化した暗号文が与えられる。鍵は与えられない。
ここから平文を求めるには…?
暗号文の構造
暗号文は$ 8バイトずつブロックになっている。平文も同様に$ 8バイトずつのブロックとして扱われる。
暗号文の$ i番目のブロックを$ C_i、平文の$ i番目のブロックを$ P_i、初期化ベクトルを$ \text{IV}、鍵を$ Kとすると、以下のように表せる。
$ C_1 = \text{IV}
$ C_{i + 1} = C_i \oplus \text{Key} \oplus P_i
復号するときは、$ P_i = C_i \oplus C_{i + 1} \oplus \text{Key}とすることで求まる。
平文の推測
平文はRTACTF{ ... }という形式になっており、よく見ると最初のブロックの先頭$ 7文字はすでにわかっている。
よって、$ 8文字目を全探索することで平文の最初のブロックを$ 256通りに絞ることができる。
これにより$ P_1が求まるため、これを使って鍵を以下のとおり求めることができる。
$ \text{Key} = C_1 \oplus C_2 \oplus P_1
求めた鍵を使うことで、$ 256通りの平文が求まる。
最もそれらしいものを選ぶことで正答が得られる。
おわり
ブロック暗号としてXORを使うと、平文の1ブロックが求まっただけで鍵がわかってしまう。
この問題は、XORがブロック暗号に求められる「平文と暗号文のペアから鍵を求めることが困難」という性質を満たしていないため発生する。