前置き

こんにちは！最近、CTFに触れる機会が少なくなってしまい、ひさしぶりに触りたくなり、AlpacaHackさんのデイリーチャレンジに挑戦してみました！

挑戦した問題はこちら。

image.png (126.9 kB)

この問題では、Linuxのバイナリファイルが与えられます。どうやら、シンプルなフラグチェッカーのようですが、少し様子がおかしいコードの予感がします。

今回のゴールは、実行時に展開される検証ロジックを取り出し、フラグ再構築まで到達することです。

babar:$ ./chal
flag: hogehoge
wrong...

実装はどうなってる？

まずは入口として、main が何をしているかを読み解きます。

mainの実装は以下のような内容でした。デコンパイラを使うと、入口の挙動を短時間で把握しやすく、重宝しています。

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  unsigned int i; // [rsp+8h] [rbp-B8h]
  char *v5; // [rsp+10h] [rbp-B0h]
  void *dest; // [rsp+20h] [rbp-A0h]
  char s[136]; // [rsp+30h] [rbp-90h] BYREF
  unsigned __int64 v8; // [rsp+B8h] [rbp-8h]

  v8 = __readfsqword(0x28u);
  printf("flag: ");
  if ( !fgets(s, 128, stdin) )
    return 1;
  v5 = strchr(s, 10);
  if ( v5 )
    *v5 = 0;
  if ( strlen(s) == 36 )
  {
    dest = mmap(0, 0x11Bu, 7, 34, -1, 0);
    if ( dest == (void *)-1LL )
    {
      return 1;
    }
    else
    {
      memcpy(dest, &unk_4020, 0x11Bu);
      for ( i = 0; i <= 0x11A; ++i )
        *((_BYTE *)dest + (int)i) *= 115;
      if ( ((unsigned int (__fastcall *)(char *))dest)(s) )
        puts("correct!");
      else
        puts("wrong...");
      return 0;
    }
  }
  else
  {
    puts("wrong...");
    return 0;
  }
}

以下のソースコードから、フラグの文字数は36文字で、フラグがあっているかどうかを (unsigned int (__fastcall *)(char *))dest)(s) でチェックしているように見えます。

解析の壁 (1): mmapって？

ここでは、最初の方に呼び出されている関数、mmap の呼び出し意味を仕様ベースで確認してみます。

https://mkguytone.github.io/allocator-navigatable/ch73.html

を参照すると、Windows APIでいうところのVirtualAllocに近い役割の関数だということがわかりました。

void *mmap(void * addr , size_t length , int prot , int flags , int fd , off_t offset );

ここで、実際の使用例を見ると

長さが283バイト
メモリ保護属性が7
flagsが34

で、新しく領域を確保していることがわかります。

dest = mmap(0, 283u, 7, 34, -1, 0);

ここで注目したいのが、保護属性が7であるということでした。

https://github.com/torvalds/linux/blob/master/arch/alpha/include/uapi/asm/mman.h#L7

PROT_READ/WRITE/EXEC の定義値を参照すると、

#define PROT_READ    0x1     /* page can be read */
#define PROT_WRITE  0x2     /* page can be written */
#define PROT_EXEC   0x4     /* page can be executed */

になっており、

つまり今回の場合、7はこれらをすべて組み合わせたメモリ保護属性であることがわかります。

>>> 0x1 | 0x2 | 0x4
7

ここからわかるのは、今回のメモリ確保で、実行可能かつ読み書きできる領域を動的に確保している点です。

ここは実装上の本質でもあります。 RWX領域を確保して、その場でバイト列を書き換えたうえで関数として実行しているため、構造としてはJIT・シェルコード実行・unpackingでよく出てくる典型パターンです。

先ほど、 (unsigned int (__fastcall *)(char *))dest)(s) で、フラグのチェックを走らせていることが読み取れました。このdestに動的にコードを展開し、フラグチェックのロジックを実行していることがわかりました。

解析の壁 (2): どうやってコードを展開している？

展開ロジック

この問題を解くには実際に展開しているロジックを発見し、どのようなデータが入っているかを特定する必要がありそうです。

mmapの結果をdestに代入した後、以下のような処理を動かしています。ただ単に、プログラムに含まれるデータをコピーするだけではなく、115を乗算する単純な変換が施されていると推測できます。

   memcpy(dest, &unk_4020, 0x11Bu);
      for ( i = 0; i <= 0x11A; ++i )
        *((_BYTE *)dest + (int)i) *= 115;

115倍の意味をもう一段掘る

この* 115は、mod 256上での1バイト変換です。 1バイト演算はオーバーフローしても下位8ビットだけが残るため、実質的には次の式になります。

decoded = (encoded * 115) mod 256

ここで重要なのは、115がmod 256で可逆かどうかです。

gcd(115, 256) = 1
したがって、115にはmod 256で逆元があります

実際、逆元は187です。

115 * 187 mod 256 = 1

つまり、変換は次のように往復できます。

復号（このバイナリが実行時にやっている処理）: x -> (x * 115) & 0xFF
逆変換: x -> (x * 187) & 0xFF

「なぜ115なのか」に対する答えは、1バイト空間で可逆な係数を選んでいるためです。これにより、定数倍だけで軽量に難読化と復元を両立できます。

バイトコードをダンプ&復号化しよう

実際に確認したいのはこの部分なので、まずは対象バイト列をダンプする必要があります。筆者はIDAの無料版を利用していたため、IDA Pythonによる自動抽出は今回は見送ることにしました。

代わりに、バイナリファイルからバイト列をスキャンする簡単なPythonスクリプトをAIで書き、実際のバイトコードが存在する物理アドレスを特定します。

C:\blog>python pattern_scanner.py chal "\xCB\x40\x80\x05\x7B\xF5\x27\xF5\xBB\x00"
Pattern bytes: cb 40 80 05 7b f5 27 f5 bb 00
Matches: 1
- offset(dec)=12320, offset(hex)=0x3020

先頭から0x3020バイト目がバイトコードの開始位置と判断できたため、抽出用コードを用意しました。

改めて、今までの前提を整理すると、

バイトコードの物理アドレス = 0x3020
バイトコードの長さ = 283バイト
乗算する数 = 115

これで、フラグをチェックするロジックのバイトコードを抽出できます。

C:\blog>python bytecode_decryptor.py
Input: chal
Offset: 0x3020
Size: 0x11B (283 bytes)
Output: extracted.bin
Done

解析の壁 (3): どうやってフラグを再構築する？

この章では、逆アセンブル結果から文字列比較の実体を復元してみます。

抽出したバイトコードをIDAで解析すると、フラグチェックのロジックが確認できました。

image.png (77.6 kB)

全体は以下のとおりです。

seg000:0000000000000000                 xor     eax, eax
seg000:0000000000000002                 cmp     byte ptr [rdi], 41h ; 'A'
seg000:0000000000000005                 jnz     locret_11A
seg000:000000000000000B                 cmp     byte ptr [rdi+23h], 7Dh ; '}'
seg000:000000000000000F                 jnz     locret_11A
seg000:0000000000000015                 cmp     byte ptr [rdi+1], 6Ch ; 'l'
seg000:0000000000000019                 jnz     locret_11A
seg000:000000000000001F                 cmp     byte ptr [rdi+10h], 6Eh ; 'n'
seg000:0000000000000023                 jnz     locret_11A
seg000:0000000000000029                 cmp     byte ptr [rdi+4], 63h ; 'c'
seg000:000000000000002D                 jnz     locret_11A
seg000:0000000000000033                 cmp     byte ptr [rdi+14h], 39h ; '9'
seg000:0000000000000037                 jnz     locret_11A
seg000:000000000000003D                 cmp     byte ptr [rdi+5], 61h ; 'a'
seg000:0000000000000041                 jnz     locret_11A
seg000:0000000000000047                 cmp     byte ptr [rdi+8], 61h ; 'a'
seg000:000000000000004B                 jnz     locret_11A
seg000:0000000000000051                 cmp     byte ptr [rdi+17h], 61h ; 'a'
seg000:0000000000000055                 jnz     locret_11A
seg000:000000000000005B                 cmp     byte ptr [rdi+12h], 34h ; '4'
seg000:000000000000005F                 jnz     locret_11A
seg000:0000000000000065                 cmp     byte ptr [rdi+1Ah], 6Eh ; 'n'
seg000:0000000000000069                 jnz     locret_11A
seg000:000000000000006F                 cmp     byte ptr [rdi+9], 77h ; 'w'
seg000:0000000000000073                 jnz     locret_11A
seg000:0000000000000079                 cmp     byte ptr [rdi+0Ch], 69h ; 'i'
seg000:000000000000007D                 jnz     locret_11A
seg000:0000000000000083                 cmp     byte ptr [rdi+0Ah], 34h ; '4'
seg000:0000000000000087                 jnz     locret_11A
seg000:000000000000008D                 cmp     byte ptr [rdi+0Dh], 5Fh ; '_'
seg000:0000000000000091                 jnz     locret_11A
seg000:0000000000000097                 cmp     byte ptr [rdi+0Fh], 69h ; 'i'
seg000:000000000000009B                 jnz     short locret_11A
seg000:000000000000009D                 cmp     byte ptr [rdi+1Eh], 70h ; 'p'
seg000:00000000000000A1                 jnz     short locret_11A
seg000:00000000000000A3                 cmp     byte ptr [rdi+0Eh], 6Dh ; 'm'
seg000:00000000000000A7                 jnz     short locret_11A
seg000:00000000000000A9                 cmp     byte ptr [rdi+20h], 63h ; 'c'
seg000:00000000000000AD                 jnz     short locret_11A
seg000:00000000000000AF                 cmp     byte ptr [rdi+21h], 61h ; 'a'
seg000:00000000000000B3                 jnz     short locret_11A
seg000:00000000000000B5                 cmp     byte ptr [rdi+6], 7Bh ; '{'
seg000:00000000000000B9                 jnz     short locret_11A
seg000:00000000000000BB                 cmp     byte ptr [rdi+15h], 61h ; 'a'
seg000:00000000000000BF                 jnz     short locret_11A
seg000:00000000000000C1                 cmp     byte ptr [rdi+2], 70h ; 'p'
seg000:00000000000000C5                 jnz     short locret_11A
seg000:00000000000000C7                 cmp     byte ptr [rdi+22h], 21h ; '!'
seg000:00000000000000CB                 jnz     short locret_11A
seg000:00000000000000CD                 cmp     byte ptr [rdi+13h], 31h ; '1'
seg000:00000000000000D1                 jnz     short locret_11A
seg000:00000000000000D3                 cmp     byte ptr [rdi+1Dh], 6Ch ; 'l'
seg000:00000000000000D7                 jnz     short locret_11A
seg000:00000000000000D9                 cmp     byte ptr [rdi+1Ch], 34h ; '4'
seg000:00000000000000DD                 jnz     short locret_11A
seg000:00000000000000DF                 cmp     byte ptr [rdi+18h], 5Fh ; '_'
seg000:00000000000000E3                 jnz     short locret_11A
seg000:00000000000000E5                 cmp     byte ptr [rdi+11h], 31h ; '1'
seg000:00000000000000E9                 jnz     short locret_11A
seg000:00000000000000EB                 cmp     byte ptr [rdi+19h], 31h ; '1'
seg000:00000000000000EF                 jnz     short locret_11A
seg000:00000000000000F1                 cmp     byte ptr [rdi+1Fh], 34h ; '4'
seg000:00000000000000F5                 jnz     short locret_11A
seg000:00000000000000F7                 cmp     byte ptr [rdi+0Bh], 69h ; 'i'
seg000:00000000000000FB                 jnz     short locret_11A
seg000:00000000000000FD                 cmp     byte ptr [rdi+3], 61h ; 'a'
seg000:0000000000000101                 jnz     short locret_11A
seg000:0000000000000103                 cmp     byte ptr [rdi+1Bh], 5Fh ; '_'
seg000:0000000000000107                 jnz     short locret_11A
seg000:0000000000000109                 cmp     byte ptr [rdi+7], 6Bh ; 'k'
seg000:000000000000010D                 jnz     short locret_11A
seg000:000000000000010F                 cmp     byte ptr [rdi+16h], 63h ; 'c'
seg000:0000000000000113                 jnz     short locret_11A
seg000:0000000000000115                 mov     eax, 1

https://th0x4c.github.io/blog/2013/04/10/gdb-calling-convention/

から、Linux x64の関数呼び出し規則を見てみると、

第一引数はrdi
戻り値はrax

であることがわかります。

つまりこのコードは、第1引数に入った文字列を1文字ずつcmpで比較し、完全一致を判定する単純なロジックのようです。

ただし、比較順と文字位置は一致していないため、上から読むだけでは復元できません。そこでPythonで機械的に復元してみます。

ここは難読化として地味に効いているポイントです。通常のstrncmp系の比較であれば文字位置と比較順が揃いやすいですが、今回は[rdi+offset]のoffsetがランダム順で登場します。そのため、人間が逆アセンブリを目で追うと、断片的な比較が並んでいる状態になり、正しい並びを頭の中で再構成しづらくなります。

また、cmpの直後にjnzが連続するため、制御フローとしては単純でも見た目は散らされます。今回の復元はこの散らし方に対して、命令列を「文字列比較データ」として抽出し、最後にインデックスでソートし直す方針です。

具体的には、復号後バイト列を1バイトずつ走査し、cmp byte ptr [rdi+offset], imm8 の命令パターンを拾っていきます。

x86-64で今回対象とした命令形式は主に2つあります。

80 7F xx yy: cmp byte ptr [rdi+xx], yy
80 3F yy: cmp byte ptr [rdi], yy（offsetが0の特殊形）

前者は3バイト目がインデックス、4バイト目が比較文字なので、そのまま offset -> 文字 の対応表に格納します。この対応表を最終的にインデックス順へ並べることで、比較順がバラバラでも元の文字列を復元できます。

from pathlib import Path

FLAG_LENGTH = 36
CMP_LENGTH = 4

INPUT_FILE = Path("./extracted.bin")
raw = INPUT_FILE.read_bytes()

collected = "????????????????????????????????????"
collected = list(collected)

current_pos = 0
while current_pos + CMP_LENGTH < len(raw):
    if raw[current_pos:current_pos + 2] == b'\x80\x7F':
        flag_pos = raw[current_pos + 2]
        flag_chr = chr(raw[current_pos + 3])
        collected[flag_pos] = flag_chr
    current_pos += 1
    
print("Collected flag:", "".join(collected))

この方法で、ほぼ完成した状態のフラグを抽出できます。

PS C:\blog> python .\flag_reconstructor.py
Collected flag: ?lpaca{kaw4ii_min1419aca_1n_4lp4ca!}

先頭1文字は、命令のバイトコード形式が異なるため当初の抽出条件に含まれていませんでした。該当命令を確認するとASCIIでAを示しているため、これを補完します。

80 3F 41                                                        cmp     byte ptr [rdi], 41h ; 'A'

つまり今回のflagは、Alpaca{kaw4ii_min1419aca_1n_4lp4ca!} です！

以上で解答に到達できました。

別解の視点

今回は静的解析で完走しましたが、同じ問題は別ルートでも到達できます。 AIに聞くだけでも、

gdbでmmap後の領域をメモリダンプし、展開後コードを直接逆アセンブルする
エミュレータ（例: Unicorn）で展開コードだけを実行し、比較先データを観測する
LD_PRELOADでmmap/memcpy/間接call周辺をフックし、実行時のバイト列を取得する

のような解法があるようです。

振り返り

今回の問題は、一見すると動的に展開される複雑なロジックに見えましたが、実際には単純な文字列比較を難読化したものでした。

特に印象的だったのは、mmapを用いた実行時コード展開です。これにより、静的解析ではコードの本体が見えない状態になっており、「まず中身を取り出す」というステップが必要になり、単純な解析では進めないようになっていました。

これからも定期的にAlpacaHackに取り組み、他のCTFでも活躍できるように頑張ります！！

スプーキーズのちょっとTech。

SPOOKIES社内のより技工的な、専門的なブログページです。

AlpacaHackのDaily CTFを解いてみた！

前置き