手順を逆にたどれば入力が分かる
逆算とは、結果から、元の値を求めることです。プログラムの検査が、足す、XOR、引くだけでできているなら、手順を逆にたどると、通る入力が分かります。
検査の中身を読み、数学のパズルとして解く。これは、リバースエンジニアリングの基本の1つです。
このレッスンのゴール
メモ
足し算、XOR、引き算の検査を、逆にたどって解ける。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| XOR | 2つのビットが違うときだけ 1 にする演算 | ^ |
| ビット | 0 か 1 の、1けたの数 | |
| 逆演算 | 元の値に戻す演算。足すの逆は引く | |
| 逆算 | 結果から、最初の値を求めること | |
| 定数 | 命令に直接書かれた、変わらない数 | 0x55 |
学生が入力するセルは、このプレビューでは空白です。
XOR は2回かけると元に戻る
XOR は、ビットごとに、違えば 1、同じなら 0 にします。同じ数で2回 XOR をかけると、必ず元の値に戻ります。
5 を 3 で XOR すると 6 になり、6 をもう一度 3 で XOR すると 5 に戻ります。
5 と 3 の XOR
| 値 | 2進数 | 説明 |
|---|---|---|
| 5 | 0101 | もとの値 |
| 3 | 0011 | かける数 |
| 6 | 0110 | 5 XOR 3。違うビットだけ 1 |
| 5 | 0101 | 6 XOR 3。元に戻った |
学生が入力するセルは、このプレビューでは空白です。
逆演算の表
| 手順 | 戻すには |
|---|---|
| k を足す | k を引く |
| k を引く | k を足す |
| k で XOR | もう一度 k で XOR |
学生が入力するセルは、このプレビューでは空白です。
3つの手順で通る検査
次の練習用プログラムは、入力の数に3つの手順をかけ、結果が 400 かどうかを調べます。7 を引き、85 で XOR し、100 を足します。
ソースを作ってバイナリにし、ソースを消してから、命令だけを読みます。
ソースを書く
printf '%s\n' '#include <stdio.h>' '#include <stdlib.h>' 'static int check(unsigned n) {' ' unsigned x = n;' ' x = x - 7;' ' x = x ^ 85;' ' x = x + 100;' ' return x == 400;' '}' 'int main(int c, char **v) {' ' if (c == 2) {' ' if (check((unsigned)strtoul(v[1], 0, 10))) { puts("OK"); return 0; }' ' }' ' puts("NG");' ' return 1;' '}' > /tmp/rev5.cここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
プログラムを作る
gcc -O0 -no-pie -o /tmp/rev5 /tmp/rev5.cここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
ソースを消す
rm /tmp/rev5.cここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
検査の4行を読む
objdump -d -M intel --no-show-raw-insn /tmp/rev5 --disassemble=check | grep -E "sub|xor|add|cmp" | cut -f2ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
4行から手順が読める
4行は、上から sub、xor、add、cmp です。ソースを知らなくても、手順が分かります。
定数は16進数です。0x55 は 85、0x64 は 100、0x190 は 400 です。最後の cmp が、結果と比べる目標です。
400 から手順を戻す
| 戻す手順 | 計算 | 値 |
|---|---|---|
| 目標 | cmp の相手 | 400 |
| add 100 を戻す | 400 - 100 | 300 |
| xor 85 を戻す | 300 XOR 85 | 377 |
| sub 7 を戻す | 377 + 7 | 384 |
学生が入力するセルは、このプレビューでは空白です。
手順を逆にたどる
# 400 から、手順を逆にたどって、通る入力を求めます。
x = 400
x = x - 100 # 最後の「100を足す」を戻します。
x = x ^ 85 # XOR は同じ操作で戻ります。
x = x + 7 # 最初の「7を引く」を戻します。
print(x)
# 求めた値を、もとの手順に通して確かめます。
y = x
y = y - 7
y = y ^ 85
y = y + 100
print(y == 400)
# x = 400 を x = 500 に変えて、もう一度実行しましょう。
求めた入力で実行
/tmp/rev5 384ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
1つ違う入力で実行
/tmp/rev5 385ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
手順の順番はそのままで、演算だけ逆にすればよいと思いがちです。実際は、順番も逆にします。最後の手順から戻します。この例なら、最初に戻すのは、最後の「100 を足す」です。
32ビットでは0より下は一周する
符号のない32ビットの数は、0 から 4294967295 までです。0 から 1 を引くと、4294967295 になります。
逆算でも同じです。足した数を戻すとき、結果が 0 より小さくなったら、4294967296 で割った余りにします。