たぬき暗号で学ぶDeflate（SECCON 2019 Online CTF Tanuki Writeup）

はじめに

この記事は Recruit Engineers Advent Calendar 2019 の10日目です。2019年10月に開催されたSECCON 2019 Online CTFの"Tanuki"という問題が面白かったので、その出題内容と解法をご紹介します。

Deflateという圧縮アルゴリズムに関する問題なのですが、解くためには圧縮ファイルを展開するプログラムを改造する必要があり、ちゃんとDeflateのアルゴリズムについて勉強しないと解けない内容となっています。

Deflateはzipやpngなど様々な所で使われているアルゴリズムですし、知っておくと役に立つこともあると思います。この記事ではDeflateの展開アルゴリズムについて知らない人が大体のイメージが掴めるようになる程度にアルゴリズムの解説をしつつ解いていきたいと考えています。

はじめに
Tanuki (misc, 439pts, 14solves)
Deflateについて
LZ77の繰り返しを無効化する
おわりに

Tanuki (misc, 439pts, 14solves)

では、早速ですが問題の内容について説明します。

この問題では、問題文とtanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gzという名前のgzipファイルが与えられます。

問題文

原文

Behold! We invented the brand-new, super-difficult, hyper-cryptic, and ultra-undecipherable cryptosystem for this SECCON CTF 2019! And we have the name of it: たぬき (Tanuki) !

Samples

Ciphertext 1: たたせくたこたたたんた
Plaintext 1: せくこん

Ciphertext 2: たSたEたたたたたCCたたたたたOたNたたた
Plaintext 2: SECCON

Oh, it's too difficult for you to decrypt? So then... TRY HARDER!

Google翻訳版

見よ！私たちは、このSECCON CTF 2019向けに、まったく新しい、非常に難しく、ハイパー暗号化された、超解読不可能な暗号化システムを発明しました！そして、その名前があります：たぬき（たぬき）！

サンプル

暗号文1：たたせくたこたたたたたた
平文1：せくこん

暗号文2：たSたEたたたたたCCたたたたたOたNたたた
平文2：SECCON

ああ、解読するのは難しすぎる？それでは... TRY HARDER！

「たぬき」と書いて「た抜き」な暗号ですね。小学生の頃に読んだナゾナゾの本に出てきたような記憶があります。なつかしい。

「た」を抜くだけならば、sed -e 's/た//g'で一発です。しかし、この問題の厄介なところは添付ファイルにあります。

_{（ちなみに、CTFをご存知無い方のために説明すると、CTFでは問題のどこかに隠されているSECCON{......}形式の文字列（FLAG）を見つけ出すと点数が貰えます。様々な技術を駆使し、FLAGを見つけて獲得した点数を競い合う競技がCTFです）}

添付ファイル

tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz

❯ ls -l tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz
-rwxr-xr-x  1 omd  staff  20522 12  2 23:24 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz*

約20KBのgzipファイルです。tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gzというファイル名から、このファイルが「12回gzipで圧縮されたテキストファイル」であることが推測できます。

展開してみましょう。

❯ gzip -dk tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz
❯ gzip -dk tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz
❯ gzip -dk tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz
❯ gzip -dk tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz
❯ gzip -dk tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz
❯ gzip -dk tanuki.txt.gz.gz.gz.gz.gz.gz.gz

6回目の展開で固まってしまいました。ファイルサイズを見てみます。

❯ ls -lSr tanuki.txt*
-rwxr-xr-x  1 omd  staff        20522 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz*
-rwxr-xr-x  1 omd  staff        24260 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz*
-rwxr-xr-x  1 omd  staff      3283140 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz*
-rwxr-xr-x  1 omd  staff     44067495 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz*
-rwxr-xr-x  1 omd  staff   1212607563 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz*
-rwxr-xr-x  1 omd  staff  15393074341 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz*

5回展開した時点で約15.4GBもの大きさのファイルになっています。展開するたびに指数関数的にファイルサイズが増加しているので、このまま展開すると途方も無い大きさのファイルが出来上がってしまいます。愚直に展開するのはまず無理そうですね。

元データについて考える

このままでは展開できないので、現在分かっていることから、このファイルを繰り返し展開していったら最終的にどんなデータが出てくるか考えてみます。tanuki.txtの内容が"たぬき暗号"の暗号文だと仮定すると、FLAGのフォーマットから最終的なデータは以下のようになると考えられます。

(た*n_1)S(た*n_2)E(た*n_3)C(た*n_4)C(た*n_5)O(た*n_6)N(た*n_7){(た*n_8)...
※ (た*n)は"た"がn個並んだ文字列

tanuki.txtのファイルサイズは途方も無い大きさになるので、tanuki.txtはその圧倒的大部分が"た"で埋め尽くされたものになっているはずです。

このような文字列が圧縮されると一体どのようなデータになるでしょうか？ここで、gzipに採用されているDeflateという圧縮アルゴリズムについて見てみましょう。

Deflateについて

Deflateは、ハフマン符号とLZ77という2つの可逆圧縮手法を組み合わせたアルゴリズムです。Deflateでは、最初にLZ77で圧縮を行い、その後にハフマン符号化で圧縮するという2段階の圧縮が行われます。

今回は圧縮ファイルの展開が問題なので、「どうやって符号化するか？」についてはあまり説明せず、「どうやって符号からデータを復元するか？」について理解してもらうことを目指して説明します。

ハフマン符号化

ハフマン符号は、出現頻度の高い文字を短いビット列で表し、代わりに滅多に出現しない文字を長いビット列で表すような工夫がされた符号です。ハフマン符号を使用することで文字列全体のデータ量を削減することができます。

具体例で説明します。英語ではE, T, Aの出現率が高く、逆にJ ,Q ,Zの出現率が低いことが知られています。ここで、E T Aを111 001 1100と短いビット列で表し、J Q Zを0100001100 01000011011 01000011011と長いビット列で表す符号を作ってみましょう。この符号のビット長は文字の出現頻度に反比例するように作られており、出現頻度の高い文字を少ないビット数で表現できます。

以下の例では、tanukiという文字列をハフマン符号化しています。ascii文字として表現すると48bitになりますが、ハフマン符号として表すことで28bitにまでデータ量を削減することができました。

t        a        n        u        k        i
01110100 01100001 01101110 01110101 01101011 01101001

　　↓↓↓

t   a    n    u     k        i
001 1100 0101 01001 01000010 1011

上記の逆の操作を行い、符号を元のビット列に戻すことでハフマン符号からデータを復元することができます。

ハフマン符号は「データの出現頻度」に注目した圧縮手法であるといえます。

LZ77

LZ77は、文字列中において、過去に出現したことのある文字列が再出現した際に、その文字列を「前回出現した箇所までの距離」と「長さ」の情報で構成される符号に置き換え、全体のデータ量を削減するアルゴリズムです。ここでは、符号を[距離,長さ]として表現します。例として、次のような文字列を考えてみます。

Tanuki tanuki tanuki tanuki tanuki tanuki!?

この内の一部を取り出して符号に置き換えてみましょう。

Tanuki tanuki

　　↓↓↓

Tanuki t[7,5]

ここでの[7,5]は符号の位置より7文字前から5文字を意味しています。符号の位置から7文字戻って5文字を抜き出すとanukiになります。[7,5]をanukiで置き換えると元通りになることが分かりますね。

この符号を使って残りの文字列も符号化するとどうなるでしょうか。結果は次のようになります。

Tanuki tanuki tanuki tanuki tanuki tanuki!?

　　↓↓↓

Tanuki t[7,33]!?

この符号は一見するとおかしく見えます。なぜなら、[7,33]が示している符号の位置より7文字前から33文字は、現在の符号の位置を超えてしまっているからです。この部分に何が入るのか分からないので、取り敢えず?としてみましょう。

anuki t??????????????????????????

この?の部分に何が入るかというと、現在明らかになっている部分、つまりanuki tの繰り返しが長さいっぱいまで入ります。つまり、次のようになります。

anuki tanuki tanuki tanuki tanuki

この文字列で[7,33]を置き換えると元通りに文字列を復元できることが分かります。このような表現をすることで、LZ77では文字列の繰り返しを効率的に圧縮することができるというわけです。

LZ77は、「データの繰り返し」に注目した圧縮手法であるといえます。

圧縮データについて考える

Deflateは「最初にLZ77で圧縮を行い、その後にハフマン符号化で圧縮する」のでした。たぬき暗号のデータをDeflateで圧縮すると、どのようなデータになるか考えてみましょう。なお、ここではイメージを掴んでもらうことを優先しているため、厳密な説明ではありません。ご容赦ください。

まずは、LZ77で符号化すると以下のような符号に置き換えられると予想できます。

(た*n_1)S(た*n_2)E(た*n_3)C(た*n_4)C(た*n_5)O(た*n_6)N(た*n_7){(た*n_8)...

　　↓↓↓

た[1,n_1-1]Sた[1,n_2-1]Eた[1,n_3-1]Cた[1,n_4-1]Cた[1,n_5-1]Oた[1,n_6-1]Nた[1,n_7-1]{た[1,n_8-1]...

しかし、実際のDeflateのアルゴリズムでは符号が表す文字列の長さの最大値は258文字までとなっており、長さが258文字を超えると1つの符号では表現できなくなります。そのため、次のように[1,258]の符号を並べて表現することになります。このように表現すると、[1,258]一つが258文字の"た"に置き換わります。

1回目の圧縮データ

た[1,258][1,258][1,258][1,258][1,258][1,258][1,258][1,258][1,258][1,258][1,258]...

この文字列をもう一度LZ77で圧縮するとどうなるでしょうか？ここでは[1,258]を(C)に置き換えて表現し、(C)の文字列長を2文字とします。

2回目の圧縮データ

た(C)[2,258][2,258][2,258][2,258][2,258][2,258][2,258][2,258][2,258][2,258][2,258]...

(C)が"た"*258文字だったので、ここでの[2,258]は(C)*129個、つまり"た"*33282文字を表していることになります。ここで重要なのは、「同じデータがひたすら繰り返されるデータ」を圧縮したデータは、元と同じく「同じデータがひたすら繰り返されるデータ」になる、ということです。

実際にはこの2回のLZ77圧縮の間にはハフマン符号化が挟まりますが、ハフマン符号化は個々の文字を符号に置き換えてしまうだけなので、符号化後も「同じデータがひたすら繰り返されるデータ」であることと、「繰り返し部分は展開すると"た"になる」ことには変わりありません。この後10回Deflate圧縮を繰り返すわけですが、このような圧縮後のデータの繰り返しは最後まで残り続けます。

このLZ77のデータの繰り返しさえどうにかして無効化することができれば、データの整合性を保ちつつ、不必要な"た"の展開を防ぐことができそうだ、ということが分かります。

LZ77の繰り返しを無効化する

では、どうすればLZ77の繰り返し表現を無効化することが出来るでしょうか？

LZ77の符号において、繰り返しは「現在の符号の位置を超える長さの符号」として表現するのでした。つまり、[1, 258]のように、距離 <= 長さとなっている符号は繰り返しを表現する符号である、とみなすことができるはずです。

この事から、「gzipファイルを展開中に、距離 <= 長さとなっているLZ77の符号が出現したら無視する」という実装にしてあげれば、繰り返し表現を無効化しつつ圧縮ファイルを展開することができると考えられます。

pyflateの修正

今回は、pyflateという純Python製のgzip展開プログラムを改造して実装することにしました。

LZ77の符号の展開処理はpyflate.pyの605行目に書かれている以下のコードで行われています。

while length > distance:
    out += out[-distance:]
    length -= distance
if length == distance:
    out += out[-distance:]
else:
    out += out[-distance:length-distance]

変数名が示すとおり、distanceは距離を表し、lengthは長さを表しています。先程までの表記で符号を表すと[distance,length]ですね。outは符号から展開されたデータで、while文の中のコードがまさにデータの繰り返しを展開する処理を行っています。

符号が距離 <= 長さとなっていた場合に無視するようにしてあげれば良いので、以下のように修正を加えました。条件を満たした際に符号の展開をスキップするif文を2〜3行目に足しています。

# 距離 <= 長さの場合無視する
if distance <= length:
    continue
while length > distance:
    out += out[-distance:]
    length -= distance
if length == distance:
    out += out[-distance:]
else:
    out += out[-distance:length-distance]

さて、このプログラムで問題のファイルを展開するとどうなるでしょうか。

展開する

元々のpyflateはカレントディレクトリに./outという名前で展開ファイルを出力してしまうので、便利のために元々のファイル名から'.gz'を削って出力するコードを追加しました。

if __name__ == "__main__":
    filename = sys.argv[1]

    if filename.endswith('.gz'):
        with open(filename) as input:
            field = RBitfield(input)
            magic = field.readbits(16)
            out = gzip_main(field)
            with open(filename[:-len(".gz")], "w") as f:
                f.write(out)

これで修正は全てです。早速展開してみます。

❯ python2 pyflate.py tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz
...
❯ python2 pyflate.py tanuki.txt.gz.gz.gz.gz.gz.gz.gz

前回は固まってしまった6回目の展開も一瞬で終わりました。

❯ ls -lr tanuki.txt*                                       
-rwxr-xr-x  1 omd  staff  20522 12  3 00:44 tanuki.txt.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz.gz*
...
-rw-r--r--  1 omd  staff   6824 12  8 03:41 tanuki.txt.gz.gz.gz.gz.gz.gz

ファイルサイズも増えるどころか減っていっていることが分かります。

❯ ls -l tanuki.txt
-rw-r--r--  1 omd  staff    255 12  8 03:44 tanuki.txt

その後も順調に展開に成功し、無事に最後のgzipを解凍することができました！最終的なファイルサイズは僅か255バイトになっています。

FLAG

❯ cat tanuki.txt
たSたEたCたCたOたたたNた{たDた3たFたLたaたTたたた3た_た1たsた_たたたたたsたたたたたたたたたたたたたたたたたたた0た_たたたCたOたMたPたLたEたXたたた,た_たBた4たbたyたたたたた!た}たたた

展開されたファイルの内容は以上のようなものです。少し"た"が残っていますが…

❯ cat tanuki.txt | sed -e 's/た//g'
SECCON{D3FLaT3_1s_s0_COMPLEX,_B4by!}

任意の方法で"た"を取り除けばFLAGを得ることができます。

SECCON{D3FLaT3_1s_s0_COMPLEX,_B4by!}

おわりに

この記事ではSECCON 2019 Online CTFの"Tanuki"という問題をご紹介しました。やったことと言えば既存Deflate実装のソースコードに2行足しただけなのですが、ここに2行を足すためにはLZ77の繰り返しの仕組みを正しく理解している必要があり、個人的にはとても勉強になって良い問題だと思いました。

今年のSECCONは他にも沢山楽しい問題があり、参加者として満足の行くものでした。R19というチームでSECCON 2019 国内決勝にも参加させていただく予定です。

もしこの記事を読んでCTFに興味を持った方がいらっしゃったら、初心者向けCTFのpicoCTFをおすすめします。CTFはコンピュータセキュリティの総合格闘技と言われたりしますし、ゲーム感覚で学べて非常に楽しいのでどんどん広めていきたいですね。

ommadawn46's blog

きまぐれセキュリティブログ