高水準言語（たとえば C）で書かれたアルゴリズムは、ソースコードを見るととても分かりやすく見えます。しかし、コンパイラはそれらをアセンブリレベルでかなり不可思議なパターンに変換できます。リバースエンジニアリングの技術を高めるには、そうしたパターンを学び、素早く識別できるようにする必要があります。このブログ記事では、今日 CTF 問題を解いているときに遭遇した例をいくつか紹介します。
整数間の符号付き除算
まずはこのコードを見てみましょう。
#include <stdio.h>
int div(int a)
{
return a / 42;
}
int main()
{
int a;
scanf("%d", &a);
a = div(a);
printf("%d", a);
return 0;
}
これをコンパイルして、あなたの素敵な iaito や radare2 を起動し、アセンブリを見てみましょう。main() は気にしなくてよいので、直接 sym.div に進むと、次のようなものが見えます。
36: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x30c30c31
0x0000115d shr rdx, 0x20
0x00001161 sar edx, 3
0x00001164 sar eax, 0x1f
0x00001167 sub edx, eax
0x00001169 mov eax, edx
0x0000116b pop rbp
0x0000116c ret
ここには idiv 命令がありません。代わりに、0x00001156 に imul 命令があり、その後に shr 命令と sar 命令が続いています。その結果は edx レジスタに入ります。
では、別の数を使ったらどうなるでしょうか。試してみましょう。次をコンパイルしてください。
#include <stdio.h>
int div(int a)
{
return a / 6;
}
int main()
{
int a;
scanf("%d", &a);
a = div(a);
printf("%d", a);
return 0;
}
すると、似たような逆アセンブルが得られます。
33: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x2aaaaaab
0x0000115d shr rdx, 0x20
0x00001161 sar eax, 0x1f
0x00001164 sub edx, eax
0x00001166 mov eax, edx
0x00001168 pop rbp
0x00001169 ret
負の数を使うとどうなるでしょうか。6 を -7 に置き換えると、次のようになります。
36: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0xffffffff92492493
0x0000115d shr rdx, 0x20
0x00001161 add edx, eax
0x00001163 sar edx, 2
0x00001166 sar eax, 0x1f
0x00001169 sub eax, edx
0x0000116b pop rbp
0x0000116c ret
では、定数を使わなかったらどうなるでしょうか。次をコンパイルしてください。
#include <stdio.h>
int div(int a, int b)
{
return a / b;
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
a = div(a, b);
printf("%d", a);
return 0;
}
すると、ついに少し違うものが得られます。
19: div (int64_t arg1, signed int64_t arg2);
`- args(rdi, rsi) vars(2:sp[0xc..0x10])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov dword [var_8h], esi ; arg2
0x00001153 mov eax, dword [var_4h]
0x00001156 cdq
0x00001157 idiv dword [var_8h]
0x0000115a pop rbp
0x0000115b ret
x86_64 CPU は 確かに 除算をサポートしていますが、コストは高いです。したがって、除数がすでに定数として与えられている場合、コンパイラはコンパイル時にその最適化を行ってくれます。除数から magic multiplier（魔法の乗数）を計算し、除算を乗算とビットシフトの組み合わせに変換します。このアルゴリズムについては、さらに詳しく説明している論文があります。
ただし、その定数が実行時にしか分からない場合、この最適化は役に立たないため、直接除算命令が使われます。
剰余演算
では、これをコンパイルしてみましょう。
#include <stdio.h>
int mymod(int a)
{
return a % 42;
}
int main()
{
int a;
scanf("%d", &a);
a = mymod(a);
printf("%d", a);
return 0;
}
mymod() の逆アセンブルは次のようになります。
45: mymod (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x30c30c31
0x0000115d shr rdx, 0x20
0x00001161 sar edx, 3
0x00001164 mov ecx, eax
0x00001166 sar ecx, 0x1f
0x00001169 sub edx, ecx
0x0000116b imul ecx, edx, 0x2a
0x0000116e sub eax, ecx
0x00001170 mov edx, eax
0x00001172 mov eax, edx
0x00001174 pop rbp
0x00001175 ret
0x00001150 から 0x00001161 までの命令は、上で説明した magic multiplier を使った除算です。その後、被除数のコピーが ecx に入り、それを 31 ビット算術右シフトします。被除数が非負なら ecx は 0、そうでなければ -1 になります。
これは、被除数から bias を計算するためです。除算は常にゼロ方向へ切り捨てられるからです。商を使って剰余を計算します。正の数では、剰余 = 被除数 - 除数 * 商 です。負の数では、剰余 = 被除数 - 除数 * （商 + 1） です。
バブルソート
最後に、これをコンパイルしてみましょう。
#include <stdio.h>
void bubble(int *arr, int n)
{
for (int i1 = 0; i1 < n - 1; i1++)
{
for (int i2 = 0; i1 + i2 < n - 1; i2++)
{
if (arr[i1] > arr[i2])
{
int tmp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = tmp;
}
}
}
}
int main()
{
int a[42];
for (int i1 = 0; i1 < 42; i1++)
a[i1] = 42 - i1;
bubble(a, 42);
for (int i1 = 0; i1 < 42; i1++)
printf("%d", a[i1]);
return 0;
}
今回は、iaito が生成した sym.bubble のグラフを見てみましょう。
0x00001144 でカウンタが設定されているのが分かります。0x00001209 のブロックには比較があります。カウンタがしきい値にまだ達していなければ、処理は続きます。0x00001150 では別のカウンタが設定されます。0x0000115c のブロックでは、隣り合う 2 つの数の比較が行われます。前者の方が大きければ、0x0000118c のブロック内で交換が行われます。
結論
これは、リバースエンジニアリング中に見かける可能性のあるパターンのほんのいくつかの例にすぎません。リバースエンジニアリングの作業を重ねるほど経験が増え、逆アセンブルの中からより多くのパターンを素早く識別できるようになります。