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
の項目で Style
の Show empty line after every basic block
と Show x-refs
にチェックを入れた.
また, Disassembly
の項目の Metadata
の Substitute variables
のチェックを外した.
以下が Cutter
により main の先頭部分の逆アセンブルコードを Graph 表示させたときの画像.
今回はバイナリを読む練習をするため, デコンパイラは使わずに解いてみる.
先頭から 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
は以下のような処理となっている。
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}