この記事は CTF Advent Calendar 2016 - Adventar の22日目の記事です. 21日目の記事は@nolzeさんの どのCTFに出たらいいか分からない人のためのCTF年表 (2016年版) - A602 です.
多表式暗号の解読ではカシスキー・テストを用いた解読法がよく知られているが, 実はFriedman Testと呼ばれる一致指数(Index of coincidence)を用いた方法がこれとは別に存在し, (精度は劣るものの)カシスキー・テストよりも単純な計算で鍵長を推測することができる. この記事では, 一致指数を用いて多表式暗号を解読する手法をVigenere暗号に対して解説した後CTF(Capture the Flag)の暗号カテゴリの過去問題を実際に解いてみる. この記事では通して英語を平文にもつことを仮定するが, 他の言語でも同様に解読が可能である.
今回題材とする問題は 0CTF 2015: oldcrypto である.
一致指数
一致指数(Index of coincidence)とは, 通常の文字列に対して考えると2つの文字列の間の一致の割合を見る計測の手段として用いることの出来る手法である. しかし, 暗号解析の分野では2つの文字列の間ではなく1つの文字列から2つの文字をそれぞれ取ってきた時にどの程度一致するかを見るために使う. 考え方としては, ある文字列$t$とある文字$x$について, $t$の異なる位置から文字$a$, $b$を取ってきた時, $a = b = x$ を満たす割合を求めれば良い. これは$a = x$となる割合が$\frac{tに含まれるxの数}{tの長さ}$, かつ$b = x$となる割合が$\frac{tに含まれるxの数 - 1}{tの長さ - 1}$であることからこれらの積を取ることで求められる. 実際には$x$は文字全体を動く*1ので, 各$x$について総和を取ることでこれを計算する. 定義をちゃんと書き直すなら以下の通りになる.
長さ$N$の文字列$t$とアルファベット$\Omega = \{x_i\}$がある時, $t$に文字$x\in \Omega$が含まれる数を$\phi_t(x)$で表すと, 一致指数$\mathrm{IC} _ \Omega(t)$は次のように定義できる.
$$ \mathrm{IC} _ \Omega (t) := \frac{1}{N(N-1)} \sum_{x \in \Omega} \phi_t(x)(\phi_t(x) - 1) $$
実際にはアルファベットの長さ$|\Omega|$をかけて正規化したりもするが, この記事では正規化はしない.
暗号解読への応用 - シーザー暗号
一致指数の定義は示したが, どう応用されるのかは見当が付かない. なので, まずはシンプルなシーザー暗号について考える.
シーザー暗号は, 鍵文字を1文字決め, その文字を0-indexな数値にした数だけ平文をずらすことで暗号化している. 例えば, 鍵文字をCとし, HELLOWORLDを暗号化する時を考えると, 鍵文字Cは0-indexで2番目の文字なので
H -> J E -> G L -> N O -> Q W -> Y R -> T D -> F
とずらせる. すると, 暗号文はJGNNQYQTNFであることが分かる. ここで重要なのは, 暗号文は常に平文の同じ文字は同じ文字へ動くということで, このことは文字列の頻度解析による解読法の考案に至っている. 頻度解析はここでは扱わないが, 文字通り文字の分布を調べてその分布に従って鍵を推測していく手法だ.
シーザー暗号を解読するために, まずは一般的な平文の一致指数を考える. 自然言語の場合文字分布がある程度偏っている(英語ではeが一番高頻度で出現する等)ことから, その一致指数の値は計算可能であると言える.
英語の頻度表を利用してこの一致指数の値を求めてみる. 文字列の長さは$\infty$とするのが理想だが, 大きな値(ここでは65537)で代用する.
これを動かすと, 0.0661051931653という値が得られる. つまり, 平均的な英語の文字列の一致指数は約0.0661だと言える.
これを利用してシーザー暗号を解いてみる. 考え方としてはある文字$x$を鍵を仮定し, 実際にその鍵で解読した際にその解読文について「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算し, これと標準的な一致指数0.0661との差の絶対値を求める. この差の絶対値が一番小さなものが鍵だと推測できる.
少しわかりづらい説明になってしまったので, プログラムコードを先に示す. サンプルとして, Lady Chatterly's Lover: History of English - van Gelderenのテキストを利用させて頂いた.
このスクリプトは動かすと実際に鍵sを出力し, 平文へと解読ができる.
キモとなるのは,
table += [abs(0.0661 - sum(map(lambda x: (x[0]-1)*x[1][1] / (len(tmp) - 1), zip(count_alphabet(tmp, alphabet), sorted_freq))))]
の行だ. これはまさに『解読文について「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算し, これと標準的な一致指数0.0661との差の絶対値を求める』という記述をそのまま実装したものだと言える.
一致指数のシグマの中は$\frac{\phi_t(x)}{N} \frac{\phi_t(x) - 1}{N-1}$と書くこともできることから, $\frac{\phi_t(x)}{N}$を英語の頻度表(つまり, 理想的な(平文に一番近いような)値)から直接代入した上で$\frac{\phi_t(x)-1}{N-1}$を解読文から計算し, これを全ての$x$について計算して総和を取ることで「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算している. これは解読文の頻度が平文と言える値になると0.0661に近くなることから, 差の絶対値の中で最小値を取った鍵が実際の鍵だという推測ができる.
暗号解読への応用 - Vigenere暗号
多表式暗号では, まずシーザー暗号では使えた頻度解析が原則的に使えない. なぜなら, 平文と暗号文の文字は一対一ではないため, 頻度解析を行っても平文と同じ頻度表には成り得ないためだ. これを一致指数を用いて考えると, 鍵長$k$の多表式暗号によって暗号化された暗号文$t$から2つ文字を持ってきた時にこの文字が文字$t$と一致する割合は, 鍵長$k - 1$の時よりも低くなる. なぜなら, 平文と暗号文の文字が一対一ではなく一対$k$の対応になることからランダムネスが上がるため, 全体としての一致の割合が低くなるからだ. 逆に考えれば, 多表式暗号の場合、一致指数はその「鍵の長さ」によって変わるとも言えることが分かる. つまり, 文字列全体の一致指数を取ることで鍵長をある程度推測できると言えるのではないか?と考えられる. これがFriedman Testと呼ばれる鍵長推測の手法である.
以下のスクリプトを用いて実際に実験してみる. サンプルテキストは, 上で用いたものと同じものを使う.
このスクリプトは, 鍵の長さごとにランダムな鍵でVigenere暗号を用いて暗号化し, その一致指数の平均値を算出して表示する. 実行結果は以下のようになる.
[+] Key length = 1, IC = 0.0653856 [+] Key length = 2, IC = 0.0510465 [+] Key length = 3, IC = 0.0466506 [+] Key length = 4, IC = 0.04432 [+] Key length = 5, IC = 0.0433219 [+] Key length = 6, IC = 0.0418646 [+] Key length = 7, IC = 0.0413971 [+] Key length = 8, IC = 0.040794 [+] Key length = 9, IC = 0.0403788 [+] Key length = 10, IC = 0.0402034 [+] Key length = 11, IC = 0.0398683 [+] Key length = 12, IC = 0.0396422 [+] Key length = 13, IC = 0.0394859 [+] Key length = 14, IC = 0.0393217 [+] Key length = 15, IC = 0.0392352 [+] Key length = 16, IC = 0.0390873 [+] Key length = 17, IC = 0.039084 [+] Key length = 18, IC = 0.0389093 [+] Key length = 19, IC = 0.038822 [+] Key length = 20, IC = 0.0387942 [+] Key length = 21, IC = 0.0387419 [+] Key length = 22, IC = 0.0386404 [+] Key length = 23, IC = 0.0386087 [+] Key length = 24, IC = 0.0385671 [+] Key length = 25, IC = 0.0384884
鍵長1の時は最初に計算した0.0661に近く, 鍵長毎に差があるのは確かに見て取れる. *2 これを利用して鍵長を推測してみる. 平文は先と同じものを使い, 鍵長3, 5, 7のそれぞれで一致指数を計算し, 一番近い鍵長の一致指数を求めることで鍵長を推測する.
何度か動かすと分かるが, 誤差が$\pm 1$〜$2$ほど存在する. うまく行けば,
[+] K = oau (3) [+] Guessed key length = 3 [+] K = imryu (5) [+] Guessed key length = 5 [+] K = qzomygn (7) [+] Guessed key length = 7
のように綺麗に判定してくれるが,
[+] K = jeg (3) [+] Guessed key length = 5 [+] K = abfsn (5) [+] Guessed key length = 6 [+] K = vsbgyqd (7) [+] Guessed key length = 9
のようにずれることもある. こればかりは鍵長が長くなれば長くなるほど誤差も大きくなるため比較手法について考えるか誤差を大きく判定するしか無いだろう. しかし, こうやって鍵長の候補が求まれば, シーザー暗号と同じように一致指数から平文に一番近い解読文を導出できる. 最終的な解読文の中でも一番一致指数が鍵長1の時の一致指数に近いものが平文に近いと言えるので, 判定も容易そうに思える. 実際, カシスキー・テストでは鍵長の倍数が求まることがあり, この倍数から鍵長を導出するには因数分解しなければならないので, こちらのほうが自動化をしやすいと言える*3.
それも含めて, 上のコードに解読部分のコードを付け加えたものが以下になる. このコードは実質的に任意のVigenere暗号文を解読することのできるコードになっている.
暗号解読への応用 - CTF過去問題
ここでは冒頭に言ったようにCTFの過去問題を一致指数を用いて解く. 問題は0CTF 2015 - oldcryptoを使う. この問題はタイトルからして古典暗号, 配布されている問題ファイルの中身はというと暗号化用スクリプトと暗号文のみというシンプルなもの. 暗号化・復号関数を以下に抜粋する.
def encrypt(plaintext, key): ciphertext = "" for i in xrange(len(plaintext)): p = ord(plaintext[i]) - ord('a') k = ord(key[i % len(key)]) - ord('a') c = (tr[k][p] + i**7) % 26 ciphertext += chr(c + ord('a')) return ciphertext def decrypt(ciphertext, key): plaintext = "" for i in xrange(len(ciphertext)): c = ord(ciphertext[i]) - ord('a') k = ord(key[i % len(key)]) - ord('a') p = tr[k][(c - i**7) % 26] plaintext += chr(p + ord('a')) return plaintext
tr はファイル中に定義されている変換テーブル. 簡単に暗号化処理をわかりやすく書き直すと,
import string def encrypt(plaintext, key): ciphertext = "" keylen = len(key) alphabet = string.lowercase plaintext = map(lambda x: alphabet.index(x), plaintext) key = map(lambda x: alphabet.index(x), key) for i in xrange(len(plaintext)): k = key[i % keylen] p = plaintext[i] c = (tr[k][p] + i**7) % 26 ciphertext += alphabet[c] return ciphertext
i**7 は暗号文から簡単に取り除ける上本質的ではないのでこれを取り除く. すると,
import string def encrypt_without_i7(plaintext, key): ciphertext = "" keylen = len(key) alphabet = string.lowercase plaintext = map(lambda x: alphabet.index(x), plaintext) key = map(lambda x: alphabet.index(x), key) for i in xrange(len(plaintext)): k = key[i % keylen] p = plaintext[i] c = tr[k][p] ciphertext += alphabet[c] return ciphertext
これは典型的な多表式暗号である. よって, 先の一致指数を用いたVigenere暗号と同じ議論で鍵長を求め, 鍵を導出することができる. これらを踏まえてコードに起こすと, 次のようになる.
しかし, この暗号文は鍵長が長いためか誤差が大きく, $\pm 2$の誤差では解読ができなかった. そのため, 鍵長を導出できた10から今回計算している25まで全て候補に探索してやることで鍵が導出できた. 具体的には132行目の
for L in xrange(guessed_len - 2, guessed_len + 3):
を
for L in xrange(guessed_len - 2, guessed_len + 26):
と書き換える.
> python oldcrypto.py [+] Guessed key length = 10 +- 2 skumsnui snucgshin iphssisfun qniqnllggsz sdussncgscum gninihcwnsnni nnwdqiqnunlgxg ipasniyaunicanl slkmswumscunsnks ucnsginhnhinscvzn snicqnaqknnucgqgis kishnsniignnqgdwlsg classicalcipherisfun hincgiznlgsichunqygzk qnsdqmsikntinfhindgnin zazuumqukdlznrzwcgvgiiu slumsncwncumcniihicgszuv igankiphnuiuausiyaunilaun kvxnulcwtslnigaiuiioanurhd nnucflhiignlgwjgisiniigmcsl ncgmhnqnnnussknnhdwmsruilguz lkipitcisirsswglskngdrvngqqqq cphsrisfucilaisisfuniyhvsicgun kiwjawqlbjlsznmqcnfnuahhnvionuq slkmquqinnunsukinokishumscusznis cogginsnicfqnhlnlsgzlzgnscuglwnso qwgssilllhspangnnmghniinhdlgnmkvwu ikaunisauniuzznighsiiraizipannilaes [+] Guessed Key = classicalcipherisfun [+] plaintext = incryptanalysiskasiskiexaminationisamethodofattackingpolyalphabeticsubstitutioncipherssuchasthevigenerecipherinpolyalphabeticsubstitutioncipherswherethesubstitutionalphabetsarechosenbytheuseofakeywordthekasiskiexaminationallowsacryptanalysttodeducethelengthofthekeywordusedinthepolyalphabeticsubstitutioncipheroncethelengthofthekeywordisdiscoveredthecryptanalystlinesuptheciphertextinncolumnswherenisthelengthofthekeywordtheneachcolumncanbetreatedastheciphertextofamonoalphabeticsubstitutioncipherassucheachcolumncanbeattackedwithfrequencyanalysisthekasiskiexaminationinvolveslookingforstringsofcharactersthatarerepeatedintheciphertextthestringsshouldbethreecharacterslongormorefortheexaminationtobesuccessfulthenthedistancesbetweenconsecutiveoccurrencesofthestringsarelikelytobemultiplesofthelengthofthekeywordthusfindingmorerepeatedstringsnarrowsdownthepossiblelengthsofthekeywordsincewecantakethegreatestcommondivisorofallthedistancesthereasonthistestworksisthatifarepeatedstringoccursintheplaintextandthedistancebetweencorrespondingcharactersisamultipleofthekeywordlengththekeywordletterswilllineupinthesamewaywithbothoccurrencesofthestringthedifficultyofusingthekasiskiexaminationliesinfindingrepeatedstringsthisisaveryhardtasktoperformmanuallybutcomputerscanmakeitmucheasierhowevercareisstillrequiredsincesomerepeatedstringsmayjustbecoincidencesothatsomeoftherepeatdistancesaremisleadingthecryptanalysthastoruleoutthecoincidencestofindthecorrectlengththenofcoursethemonoalphabeticciphertextsthatresultmustbecryptanalyzedoooooooooooooooooooopsflagisthekeywithoopsprefixandbraces
flagisthekeywithoopsprefixandbraces とあるように, 鍵の前後に 0ctf{ } を付けたものがフラグになる.
よって, 最終的なフラグは 0ctf{classicalcipherisfun} である.
まとめ
一度計算すれば大方の予測がついてしまうため, 一致指数を用いるFriedman Testはカシスキー・テストよりも扱いやすい. しかし, その分誤差も大きく, その意味ではカシスキー・テストのように鍵長の倍数がすぐに出てくるものよりは劣る. 実際に解読するツールにするには, これらを組み合わせて誤差を吸収するような仕組みを作るほうが良いだろう. 一致指数自体は一般に2つの文字列の差とも言えることから, ある程度の平文がわかっている換字式の自動解読コードを書く時には利用できるかも知れない. テクニックとして覚えておくことに損はないので, 是非とも覚えて使ってもらいたい.
参考文献
- Modern Cryptanalysis: Techniques for Advanced Code Breaking
- Index of coincidence - https://en.wikipedia.org/wiki/Index_of_coincidence
- Cryptanalysis of the Vigenère Cipher: The Friedman Test - http://www.nku.edu/~christensen/1402%20Friedman%20test%202.pdf
- Lady Chatterly's Lover: History of English - van Gelderen - http://www.public.asu.edu/~gelderen/hel/lchatterly.html
明日は@hama7230氏によるcamp ctfのwriteupです.
