Decrypt it (Hard) (Crypto 300pts)
コンテスト中に解けなかった問題。バイナリをブラックボックスとして挙動を観察すればすぐに解けたのに,何を思ったのかバイナリを読み始めてコンテスト最後の5時間を潰してしまった。
逆アセンブルして少し観察すると次のことがわかる。
- srand(time())して一回rand()を呼ぶ。
- 6bytes分freadして,7bytes分fwriteする。
- 最後が6bytesに満たない場合はそのまま出力する。
よって6bytesのファイルを作り,さらにrandの出力を固定して挙動を観察する。
次のコードをpreload.cとして作成し,
共有ライブラリを作成,
% gcc -m32 -shared -o preload.so preload.c
これをLD_PRELOADで読み込むことによってrandの戻り値を環境変数から指定できるようにする。
% RAND=1 LD_PRELOAD=./preload.so ./E 1 3 p p.bin
さて,平文は6bytesで1blockだとわかっているので,適当に0や1などの値を平文に設定したファイルを作って暗号化してみる。 まず平文を0に固定してrandの戻り値を変更してみると次のような結果が得られる。
rand = 0 args: 1 1 plaintext: 0 ciphertext: 1 0 rand = 1 args: 1 1 plaintext: 0 ciphertext: 0x1e60 0 rand = 2 args: 1 1 plaintext: 0 ciphertext: 0x39aa400 0 0x39aa400 = 0x1e60**2
ここから,\(g = \mathrm{0x1e60}\)として一番目には\(g^r\)が記録されていることが推測される。
さらに,6乗と11乗の時の値から
>>> hex(Crypto.Util.number.GCD(0x1e60**6 - 0x9e2a68e6bc26, 0x1e60**11 - 0x3aa17cc27eb7)) '0x1000000000015L'
0x1000000000015は素数であるから\(n=\mathrm{0x1000000000015}\)であるとわかる。
eflags.binの\(g^r\)の値は0xb5731391e0d6であるから,
g = 7776; gr = 199505854193878; n = 281474976710677; znlog(gr, Mod(g, n))
をPari/GPで実行して$r=1152852670$を得る。
つづいて,平文を1,2と設定して挙動を観察する。
rand = 1 args: 1 1 plaintext: 1 ciphertext: 0x1e60 1 rand = 1 args: 1 2 plaintext: 1 ciphertext: 0x1e60 2 rand = 1 args: 1 3 plaintext: 1 ciphertext: 0x1e60 3 rand = 1 args: 1 1 plaintext: 2 ciphertext: 0x1e60 2 rand = 1 args: 1 2 plaintext: 2 ciphertext: 0x1e60 4 rand = 2 args: 1 3 plaintext: 2 ciphertext: 0x39aa400 18 rand = 2 args: 1 3 plaintext: 3 ciphertext: 0x39aa400 27
ここから,二番目以降の値は\(m \cdot \mathrm{arg2}^r\)で計算されていると推測できる。
以上の考察より解読プログラムを作成した。
1 from Crypto.Util.number import *
2
3 n = 281474976710677
4 d = inverse(pow(69219086192344, 1152852670, n), n)
5
6 with open("eflag.bin", "rb") as f:
7 f.read(7)
8 while True:
9 s = f.read(7)
10 if len(s) < 7:
11 sys.stdout.write(s)
12 break
13 else:
14 c = bytes_to_long(s)
15 m = (c * d % n)
16 sys.stdout.write(long_to_bytes(m, 6))
% python decrypt.py > flag.png
こうしてflagが得られた。