ログイン
編集不可のページディスカッション情報添付ファイル
CTF/Writeup/SECCON 2014 Quals Online Winter/Decrypt it (Hard)

MMA

Decrypt it (Hard) (Crypto 300pts)

コンテスト中に解けなかった問題。バイナリをブラックボックスとして挙動を観察すればすぐに解けたのに,何を思ったのかバイナリを読み始めてコンテスト最後の5時間を潰してしまった。

逆アセンブルして少し観察すると次のことがわかる。

よって6bytesのファイルを作り,さらにrandの出力を固定して挙動を観察する。

次のコードをpreload.cとして作成し,

   1 int rand(void) {
   2   return atoi(getenv("RAND"));
   3 }

共有ライブラリを作成,

% 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}\),randの戻り値を\(r\)として一番目には\(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\)として\(m \cdot \mathrm{arg2}^r\)で計算されていると推測できる。だいたいElGamal暗号である。

以上の考察より解読プログラムを作成した。

   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が得られた。

flag.png

CTF/Writeup/SECCON 2014 Quals Online Winter/Decrypt it (Hard) (最終更新日時 2014-12-11 22:44:49 更新者 ytoku)