前置き
こんにちは！
最近、CTFに触れる機会が少なくなってしまい、ひさしぶりに触りたくなり、AlpacaHackさんのデイリーチャレンジに挑戦してみました！
挑戦した問題はこちら。
この問題では、Linuxのバイナリファイルが与えられます。
どうやら、シンプルなフラグチェッカーのようですが、少し様子がおかしいコードの予感がします。
今回のゴールは、実行時に展開される検証ロジックを取り出し、フラグ再構築まで到達することです。
babar:$ ./chal
flag: hogehoge
wrong...
実装はどうなってる？
まずは入口として、main が何をしているかを読み解きます。
mainの実装は以下のような内容でした。
デコンパイラを使うと、入口の挙動を短時間で把握しやすく、重宝しています。
__int64 __fastcall main(int a1, char **a2, char **a3)
{
unsigned int i;
char *v5;
void *dest;
char s[136];
unsigned __int64 v8;
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で解析すると、フラグチェックのロジックが確認できました。
全体は以下のとおりです。
seg000:0000000000000000 xor eax, eax
seg000:0000000000000002 cmp byte ptr [rdi], 41h
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
seg000:0000000000000019 jnz locret_11A
seg000:000000000000001F cmp byte ptr [rdi+10h], 6Eh
seg000:0000000000000023 jnz locret_11A
seg000:0000000000000029 cmp byte ptr [rdi+4], 63h
seg000:000000000000002D jnz locret_11A
seg000:0000000000000033 cmp byte ptr [rdi+14h], 39h
seg000:0000000000000037 jnz locret_11A
seg000:000000000000003D cmp byte ptr [rdi+5], 61h
seg000:0000000000000041 jnz locret_11A
seg000:0000000000000047 cmp byte ptr [rdi+8], 61h
seg000:000000000000004B jnz locret_11A
seg000:0000000000000051 cmp byte ptr [rdi+17h], 61h
seg000:0000000000000055 jnz locret_11A
seg000:000000000000005B cmp byte ptr [rdi+12h], 34h
seg000:000000000000005F jnz locret_11A
seg000:0000000000000065 cmp byte ptr [rdi+1Ah], 6Eh
seg000:0000000000000069 jnz locret_11A
seg000:000000000000006F cmp byte ptr [rdi+9], 77h
seg000:0000000000000073 jnz locret_11A
seg000:0000000000000079 cmp byte ptr [rdi+0Ch], 69h
seg000:000000000000007D jnz locret_11A
seg000:0000000000000083 cmp byte ptr [rdi+0Ah], 34h
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
seg000:000000000000009B jnz short locret_11A
seg000:000000000000009D cmp byte ptr [rdi+1Eh], 70h
seg000:00000000000000A1 jnz short locret_11A
seg000:00000000000000A3 cmp byte ptr [rdi+0Eh], 6Dh
seg000:00000000000000A7 jnz short locret_11A
seg000:00000000000000A9 cmp byte ptr [rdi+20h], 63h
seg000:00000000000000AD jnz short locret_11A
seg000:00000000000000AF cmp byte ptr [rdi+21h], 61h
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
seg000:00000000000000BF jnz short locret_11A
seg000:00000000000000C1 cmp byte ptr [rdi+2], 70h
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
seg000:00000000000000D1 jnz short locret_11A
seg000:00000000000000D3 cmp byte ptr [rdi+1Dh], 6Ch
seg000:00000000000000D7 jnz short locret_11A
seg000:00000000000000D9 cmp byte ptr [rdi+1Ch], 34h
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
seg000:00000000000000E9 jnz short locret_11A
seg000:00000000000000EB cmp byte ptr [rdi+19h], 31h
seg000:00000000000000EF jnz short locret_11A
seg000:00000000000000F1 cmp byte ptr [rdi+1Fh], 34h
seg000:00000000000000F5 jnz short locret_11A
seg000:00000000000000F7 cmp byte ptr [rdi+0Bh], 69h
seg000:00000000000000FB jnz short locret_11A
seg000:00000000000000FD cmp byte ptr [rdi+3], 61h
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
seg000:000000000000010D jnz short locret_11A
seg000:000000000000010F cmp byte ptr [rdi+16h], 63h
seg000:0000000000000113 jnz short locret_11A
seg000:0000000000000115 mov eax, 1
https://th0x4c.github.io/blog/2013/04/10/gdb-calling-convention/
から、Linux x64の関数呼び出し規則を見てみると、
であることがわかります。
つまりこのコードは、第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], yy80 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
つまり今回のflagは、Alpaca{kaw4ii_min1419aca_1n_4lp4ca!} です！
以上で解答に到達できました。
別解の視点
今回は静的解析で完走しましたが、同じ問題は別ルートでも到達できます。
AIに聞くだけでも、
gdbでmmap後の領域をメモリダンプし、展開後コードを直接逆アセンブルする- エミュレータ（例: Unicorn）で展開コードだけを実行し、比較先データを観測する
LD_PRELOADでmmap/memcpy/間接call周辺をフックし、実行時のバイト列を取得する
のような解法があるようです。
振り返り
今回の問題は、一見すると動的に展開される複雑なロジックに見えましたが、実際には単純な文字列比較を難読化したものでした。
特に印象的だったのは、mmapを用いた実行時コード展開です。
これにより、静的解析ではコードの本体が見えない状態になっており、「まず中身を取り出す」というステップが必要になり、単純な解析では進めないようになっていました。
これからも定期的にAlpacaHackに取り組み、他のCTFでも活躍できるように頑張ります！！
こんにちは、Nemoolaです！
前回の記事に引き続き、AlpacaHackのデイリーチャレンジに挑戦しようと思います！
