picoCTF 2018: keygen-me-1

問題

問題文

Can you generate a valid product key for the validation program in /problems/keygen-me-1_1_8eb35cc7858ff1d2f55d30e5428f30a7

問題概要

x86のELFファイルが与えられる.

解答例

指針

  • Cutter で解析

解説

wget コマンドで問題ファイルを取ってくる.

$ wget --no-check-certificate https://2018shell.picoctf.com/static/a9ea8df4fd1086f02554dcbdbe627457/activate

file コマンドでファイルの種類を確かめる.

$ file activate
activate: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=f20cb6f0063ed2c236fbf37039f3621ac0037b40, not stripped

x86 の ELF ファイルだった.

実行権限を付与して実行してみる.

$ chmod +x activate
$ ./activate
Usage: ./activate <PRODUCT_KEY>

引数を与えずに実行したところ, 使い方が表示された.

引数に <PRODUCT_KEY> なるものを与える必要があるらしい. 引数を与えて実行してみる.

$ ./activate AAAAAA
Please Provide a VALID 16 byte Product Key.

16 byte の Key を渡せと言われたので, 16文字の文字列を与えて再度実行.

$ ./activate AAAAAAAAAAAAAAAA
INVALID Product Key.

Cutter で解析してみる.

Cutter を起動したら, 右上の Edit タブから, Preferences という項目を選択し,

Disassembly の項目で StyleShow empty line after every basic blockShow x-refs にチェックを入れた. また, Disassembly の項目の MetadataSubstitute variables のチェックを外した.

以下が Cutter により main の先頭部分の逆アセンブルコードを Graph 表示させたときの画像.

f:id:kira000:20200319223944p:plain

今回はバイナリを読む練習をするため, デコンパイラは使わずに解いてみる.

先頭から jg 命令までの逆アセンブルコードを丁寧に読んでいく.

call 命令は戻り先のアドレスをスタックに積んで, jump する命令であるから, main が呼ばれたとき, Call Stack は以下のようになっているはずである.

(lower address)

ebp-0x04 |             | <- esp - 0x04
ebp+0x00 | return addr | <- esp (スタックトップを指す)
ebp+0x04 |   argc      | <- esp + 0x04
ebp+0x08 |  *argv[]    | <- esp + 0x08

(hiher address)

したがって esp + 4 が指す値 [esp + 4] は argc, すなわち引数の個数となる.

0x0804881d      lea ecx, [esp + 4]    ; ecx = [esp + 4] (アドレス値)
0x08048821      and esp, 0xfffffff0   ; esp の値の下位4bitを0埋め
0x08048824      push dword [ecx - 4]  ;  
0x08048827      push ebp              ; ebp の退避
0x08048828      mov ebp, esp
0x0804882a      push ebx              ; ebx の退避
0x0804882b      push ecx
0x0804882c      mov ebx, ecx          ; ebx = [esp + 4] (アドレス値)
0x0804882e      mov eax, dword [stdout] ; obj.__TMC_END
                                   ; 0x804a03c
0x08048833      push 0             ; size_t size
0x08048835      push 2             ; 2 ; int mode
0x08048837      push 0             ; char *buf
0x08048839      push eax           ; FILE*stream
0x0804883a      call setvbuf       ; sym.imp.setvbuf ; int setvbuf(FILE*stream, char *buf, int mode, size_t size)
0x0804883f      add esp, 0x10
0x08048842      cmp dword [ebx], 1 ; cmp argc, 1
0x08048845      jg 0x804885e

jg 命令の直前の cmp 命令では, dword [ebx] と 1 が比較されている.

dword [ebx] は ebxレジスタに格納されているアドレス値が指す値から dword, すなわち 4byte だけ読み込む. ebx の値を追っていくと, 引数の個数である argc の値を指すアドレス値であることが分かる.

したがって, この部分をC言語のコードに直すと以下のようになる. (一部省略している)

int main(int argc, char *argv[]) {
  if ( argc > 1 ) {
    goto(0x804885e);
  }
}

jg でジャンプしない場合, すなわち引数が与えられなかったときは, 使い方を表示して終了する. なので, jg のジャンプ先である 0x804885e の処理を読んでいく.

0x0804885e      mov eax, dword [ebx + 4]
0x08048861      add eax, 4
0x08048864      mov eax, dword [eax]
0x08048866      sub esp, 0xc
0x08048869      push eax
0x0804886a      call check_valid_key ; sym.check_valid_key
0x0804886f      add esp, 0x10
0x08048872      test al, al
0x08048874      jne 0x804888d

以下の命令で eax の値は ebx + 4 が指すアドレスの値から1Byte, すなわち, ebp+0x08 に格納されている値となる. (ebx レジスタに格納されている値を追っていけば分かる)

0x0804885e      mov eax, dword [ebx + 4]

次の add 命令で, eax の値に4を足している.

*argv[] は文字列のポインタの配列であり, これは1つの要素が32bitの配列である.

argv[] の先頭アドレスが eax に格納されているとき, +4 をすると, 先頭から2番目を指してくれる.

0x08048861      add eax, 4

次の mov 命令で, eax に eax に格納されているアドレス値が指す値を代入してる.

0x08048864      mov eax, dword [eax]

このとき eax レジスタコマンドライン引数として与えた文字列を指すアドレス値が格納されいている. 以下の命令で, コマンドライン引数として与えた文字列のアドレスを引数として, check_valid_key を呼んでいる. 面倒なので, check_valid_key の詳細は追わない. 実行させたときの挙動から文字列の長さ16かどうかなどを判定していると推測できる.

0x08048869      push eax
0x0804886a      call check_valid_key ; sym.check_valid_key

check_valid_key の認証が通ったあとは以下のような処理になっている.

0x0804888d      mov eax, dword [ebx + 4]
0x08048890      add eax, 4
0x08048893      mov eax, dword [eax]
0x08048895      sub esp, 0xc
0x08048898      push eax           ; char *s
0x08048899      call validate_key  ; sym.validate_key
0x0804889e      add esp, 0x10
0x080488a1      test al, al
0x080488a3      jne 0x80488bc

今度は, コマンドライン引数として与えた文字列のアドレスを引数として, validate_key を呼んでいる. validate_key は以下のような処理となっている。

f:id:kira000:20200320002515p:plain

validate_key が呼ばれた直後の Call Stack の状態を考える.

以下の命令でコマンドライン引数として与えた文字列のアドレスが Call Stack に積まれる.

0x08048898      push eax           ; char *s
0x08048899      call validate_key  ; sym.validate_key

以下の命令が実行されたとき, Call Stack の状態を考える.

0x08048771      push ebp
0x08048772      mov ebp, esp

Call Stack は以下のようになる.

(lower address)

ebp+0x00 | saved ebp   |  <- esp
ebp+0x04 | return addr | 
ebp+0x08 |  argv[1]    | 

(hiher address)

以下の処理では, strlen により文字列の長さを取得し, [ebp - 0xc] に値を格納している.

0x08048771      push ebp
0x08048772      mov ebp, esp
0x08048774      push ebx
0x08048775      sub esp, 0x14
0x08048778      sub esp, 0xc
0x0804877b      push dword [ebp + 8] ; const char *s
0x0804877e      call strlen        ; sym.imp.strlen ; size_t strlen(const char *s)
0x08048783      add esp, 0x10
0x08048786      mov dword [ebp - 0xc], eax
0x08048789      mov dword [ebp - 0x14], 0
0x08048790      mov dword [ebp - 0x10], 0
0x08048797      jmp 0x80487c9

jmp 先は以下のようなコードだった. どうやら, [ebp - 0xc] に格納されている値をデクリメントして, [ebp - 0xc] が [ebp-0x10] より大きいとき 0x8048799 に jump している. あとの処理を読むと分かるが [ebp-0x10] は ループカウンターとして使われている.

0x080487c9      mov eax, dword [ebp - 0xc]
0x080487cc      sub eax, 1
0x080487cf      cmp eax, dword [ebp - 0x10]
0x080487d2      jg 0x8048799

これを C言語に直すと以下のようになる.

int len = strlen(s);
int idx = 0;
if (len-1 > idx) {
  goto 0x8048799;
}

0x8048799 は以下のようなコードだった.

0x08048799      mov edx, dword [ebp - 0x10]   ; edx = [ebp-0x10]
0x0804879c      mov eax, dword [ebp + 8]      ; eax = argv (文字列の先頭アドレス)
0x0804879f      add eax, edx                  ; eax += edx
0x080487a1      movzx eax, byte [eax]
0x080487a4      movsx eax, al
0x080487a7      sub esp, 0xc
0x080487aa      push eax                      ; eax = argv[edx]
0x080487ab      call ord           ; sym.ord
0x080487b0      add esp, 0x10
0x080487b3      movsx eax, al                 ; eax = ord(argv[edx])
0x080487b6      lea edx, [eax + 1]            ; edx = eax + 1
0x080487b9      mov eax, dword [ebp - 0x10]   ; eax = [ebp-0x10]
0x080487bc      add eax, 1                    ; eax++
0x080487bf      imul eax, edx                 ; eax = eax * edx
0x080487c2      add dword [ebp - 0x14], eax   ; [ebp - 0x14] += eax * edx
0x080487c5      add dword [ebp - 0x10], 1     ; [ebp-0x10]++

文字列を一文字ずつ見て, ord という関数に渡している. ord の処理は面倒なので追わないが, 文字をそれに対応する数字に変換する処理をしていた.

"1" => 1
"2" => 2
"A" => 10
"B" => 11

今までの処理をC言語に直すと以下のようになる.

int validate_key(char *s) {
  int len = strlen(s);
  int key_sum = 0;
  for (int idx = 0; idx < len-1; idx++) {
    char c = s[idx];
    key_sum += (idx+1) * (ord(c) + 1);
  }
  // 
}

これらの処理が終わった後は以下のような処理をしていた.

0x080487d4      mov ecx, dword [ebp - 0x14]  ; ecx = key_sum
0x080487d7      mov edx, 0x38e38e39          ; edx = 0x38e38e39
0x080487dc      mov eax, ecx                 ; eax = key_sum
0x080487de      mul edx                      ; edx = (key_sum * 0x38e38e39) >> 32; eax = (key_sum * 0x38e38e39) & 0xffffff
0x080487e0      mov ebx, edx                 ; ebx = (key_sum * 0x38e38e39) >> 32
0x080487e2      shr ebx, 3                   ; ebx = ((key_sum * 0x38e38e39) >> 32) >> 3
0x080487e5      mov eax, ebx                 ; eax = ((key_sum * 0x38e38e39) >> 32) >> 3
0x080487e7      shl eax, 3                   ; eax = (((key_sum * 0x38e38e39) >> 32) >> 3) << 3
0x080487ea      add eax, ebx                 ; eax = eax + ebx
0x080487ec      shl eax, 2                   ; eax = eax << 2
0x080487ef      sub ecx, eax                 ; ecx = key_sum - eax
0x080487f1      mov ebx, ecx                 ; ebx = ecx
0x080487f3      mov eax, dword [ebp - 0xc]   ; eax = str_len
0x080487f6      lea edx, [eax - 1]           ; edx = str_len - 1
0x080487f9      mov eax, dword [ebp + 8]     ; eax = argv[1]
0x080487fc      add eax, edx                 ; eax = argv[1][str_len-1]
0x080487fe      movzx eax, byte [eax]
0x08048801      movsx eax, al
0x08048804      sub esp, 0xc
0x08048807      push eax
0x08048808      call ord           ; sym.ord ; eax = ord(argv[1][str_len-1])
0x0804880d      add esp, 0x10
0x08048810      movsx eax, al
0x08048813      cmp ebx, eax                 ; cmp(ebx, eax)
0x08048815      sete al                      ; if (ebx == eax) { al = 1 }
0x08048818      mov ebx, dword [ebp - 4]
0x0804881b      leave
0x0804881c      ret

この関数が返す値は eax レジスタに格納される. 最終的な eax レジスタの値は, 以下の命令により, ebx と eax が等しいとき, 1 を等しくなければ 0 となる. (sete 命令は等しいときバイトをセットする)

0x08048813      cmp ebx, eax                 ; cmp(ebx, eax)
0x08048815      sete al                      ; if (ebx == eax) { al = 1 }

cmp 命令が実行れるときの, ebx, eax レジスタに格納されている値をそれぞれ追っていくと, eax レジスタには, 文字列の末尾を ord により数字に変換した値, ebx レジスタには, 以下の計算結果となる. mul 命令は, 演算結果の上位32bitを edxレジスタに, 下位32bitを eaxレジスタに格納する.

ecx = key_sum
edx = 0x38e38e39
eax = ecx
edx = ((edx * eax) >> 32) & 0xffffffff; eax = (edx * eax) & 0xffffffff
ebx = edx
ebx = (ebx >> 3)
eax = ebx
eax = (eax << 3) & 0xffffffff
eax = eax + ebx
eax = (eax << 2)
ecx = ecx - eax
ebx = ecx
print(ebx)

ここまでの処理をC言語で書くと概ね以下のようになる.

int main(int argc, char *argv[]) {
  if ( argc < 2 ) {
    puts("Usage: ./activate <PRODUCT_KEY>");
    return 0;
  }
  int ret = check_valid_key(argv[1]);
  if (ret == 0) { return 0; }
  
  int ret = validate_key(argv[1]);
  if (ret == 0) { return 0; }
  
  return 0;
}
int validate_key(char *s) {
  int len = strlen(s);
  int key_sum = 0;
  for (int idx = 0; idx < len-1; idx++) {
    char c = s[idx];
    key_sum += (idx+1) * (ord(c) + 1);
  }
  int eax, ebx, ecx, edx;
  ecx = key_sum;
  edx = 0x38e38e39;
  eax = ecx;
  // mul edx
  edx = ((edx * eax) >> 32) & 0xffffffff;
  eax = (edx * eax) & 0xffffffff
  
  ebx = edx;
  ebx = (ebx >> 3);
  eax = ebx;
  eax = (eax << 3) & 0xffffffff;
  eax = eax + ebx;
  eax = (eax << 2);
  ecx = ecx - eax;
  ebx = ecx;
  
  return s[strlen-1] == ord(ebx);
}

したがって, key の最初の15文字を適当に固定し, 最後の文字だけ認証を通るように計算すればいい.

$ cat solve.py
#!/usr/bin/env python3

PRODUCT_KEY = "0" * 15
key_sum = 0

for idx in range(15):
    key_sum += (idx + 1) * (int(PRODUCT_KEY[idx], 16) + 1)

ecx = key_sum
edx = 0x38e38e39
eax = ecx
edx = ((edx * eax) >> 32) & 0xffffffff; eax = (edx * eax) & 0xffffffff
ebx = edx
ebx = (ebx >> 3)
eax = ebx
eax = (eax << 3) & 0xffffffff
eax = eax + ebx
eax = (eax << 2)
ecx = ecx - eax
ebx = ecx
PRODUCT_KEY += format(ebx, "x").upper()

print(PRODUCT_KEY)

$ python solve.py
000000000000000C
  • 実行結果
kira924age@pico-2018-shell:/problems/keygen-me-1_1_8eb35cc7858ff1d2f55d30e5428f30a7$ ./activate 000000000000000C           
Product Activated Successfully: picoCTF{k3yg3n5_4r3_s0_s1mp13_3718231394}

Ghidra のデコンパイラを使うと, 実は最後のビット演算の処理は 0x24 と剰余を取る処理と等価らしいことが分かる. したがって, validate_key は以下のようにも書ける.

int validate_key(char *s) {
  int len = strlen(s);
  int keysum = 0;
  for (int idx = 0; idx < len-1; idx++) {
    keysum += (idx + 1) * (ord(s[idx]) + 1);
  }
  return (keysum % 0x24) == ord(s[len-1]);
}

flag: picoCTF{k3yg3n5_4r3_s0_s1mp13_3718231394}

参考文献