EKOPARTY PRE-CTF 2015: Perfect security
問題
問題文
It is not maybe so perfect.
Hints: Use the golden math!
crypto200.zip
※問題ファイルは下記のものを利用できる。
https://github.com/ctfs/write-ups-2015/tree/master/ekoparty-pre-ctf-2015/crypto/perfect-security
問題概要
暗号処理を行うプログラム perfect とそのプログラムにより暗号化されたファイル output.enc が与えられる。
平文を複合せよ。
解答例
指針
- 与えられたプログラムを解析し、平文を複合する。
解説
crypto200.zip を解凍すると、pefect, output.enc という 2つのファイルが得られる。
$ unzip crypto200.zip Archive: crypto200.zip inflating: output.enc inflating: perfect
file コマンドでファイルの種類を調べると pefect は 64bit の ELFファイルで output.enc は 16進文字列のみのテキストファイルであることが分かる。
$ file perfect perfect: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=403ba926372be30e5a1f0bd4549951178c6cc1cf, stripped $ file output.enc output.enc: ASCII text, with very long lines, with no line terminators $ cat output.enc 76677009015147631fc7cf240369 ... (snip) ... 837313838363238353938333630333734363530353731
IDA の Freeware 版を使って perfect を解析した。(以前は Freeware 版では 64bitの ELF や exe を解析することは出来なかったが割と最近になって出来るようになった。)
https://www.hex-rays.com/products/ida/support/download_freeware.shtml
逆アセンブルコードを読むとこのプログラムは引数として平文とワンタイムパッドの鍵のファイル名を受け取り、1バイトごとに XOR した値を 16進文字列で表示するプログラムであることが分かる。
ワンタイムパッドは鍵が分からない限りは確かに問題名の通り完全な暗号である。
暗号化されたファイルを Hex デコードしてみると末尾に数字のみで構成される文字列が現れた。
#!/usr/bin/env python2 # coding: utf-8 with open('output.enc', 'r') as f: data = f.read() print data.decode('hex')
- 実行結果
(snip) ▒▒▒-z▒▒▒▒h▒▒i▒6g▒▒▒4'▒wuw& d▒y▒▒'h▒g▒▒▒▒U(Mc▒`R0>0 18853307623055638163164019224545032576567392599765175308014271607143087188628598360374650571
ヒントの Use the golden math! からこれは黄金比の一部であると推測できる。
黄金比の値をワンタイムパッドの鍵として XOR をとると平文の GIF ファイルが生成され FLAG が得られた。
#!/usr/bin/env python2 # coding: utf-8 with open('output.enc', 'r') as f: data = f.read() data = data.decode('hex') # from https://www.goldennumber.net/phi-million-places/ phi = """ 1.61803398874989484820458683436563811772030917980576286213544862270526046281890 244970720720418939113748475408807538689175212663386222353693179318006076672635 (snip) 1885330762305563816316401922454503257656739259976517530801427160 7143087188628598360374650571""" phi = phi.replace("\n", "") with open('flag', 'wb') as m: for i in range(len(data)): m.write(chr(ord(data[i]) ^ ord(phi[i])))
- 実行結果
$ python solve.py $ file flag flag: GIF image data, version 89a, 20596 x
平文の末尾が 0 で埋められていたことにより鍵の一部を知ることができ、また鍵が乱数ではなく容易に推測できるものであったため完全であるはずのワンタイムパッドを破ることが出来たのである。
