💭
Daily AlpacaHack "Useful Machine" Writeup
Useful Machine
添付ファイルの確認
$ ls -l
total 8
-rw-r--r-- 1 shiragi shiragi 1086 Dec 7 03:57 program
-rw-r--r-- 1 shiragi shiragi 1713 Dec 7 03:57 vm.py
$ file *
program: data
vm.py: Python script, ASCII text executable
vm.pyを眺めてみると，独自言語で実装されたプログラムを実行するプログラムとわかった．
そのプログラムコードはprogramというバイナリファイルに書かれているらしい．
バイナリだからリバースするならもうちょっと読みやすくしたいな...
というわけでGPTにPythonに変換するコードを書いてもらった
import sys
# このスクリプトは、vm.py が実行するバイトコード ("program") を
# 同等な処理を行う Python 関数 run(input_string: str) に変換して標準出力に出します。
# 使い方:
# python bytecode_to_python.py program > decompiled_program.py
def translate(program: bytes) -> str:
lines: list[str] = []
# ヘッダ部分: メモリと入力処理の定義
lines.append("def run(input_string: str):")
lines.append(" mem = [0] * 256")
lines.append(" input_index = 0")
lines.append("")
lines.append(" def read_char():")
lines.append(" nonlocal input_index")
lines.append(" if input_index >= len(input_string):")
lines.append(" return '\\x00'")
lines.append(" ch = input_string[input_index]")
lines.append(" input_index += 1")
lines.append(" return ch")
lines.append("")
# 本体: 各命令をそのままPython文として展開
if len(program) % 3 != 0:
raise ValueError(f"Program length {len(program)} is not a multiple of 3")
ip = 0
while ip < len(program):
opcode = program[ip]
oprand1 = program[ip + 1]
oprand2 = program[ip + 2]
# コメントとして元の ip と生の命令を残す
lines.append(f" # ip={ip}, opcode={opcode}, oprand1={oprand1}, oprand2={oprand2}")
if opcode == 0:
# 入力1文字を読み込み、その ord % 256 をメモリに格納
lines.append(f" mem[{oprand1}] = ord(read_char()) % 256")
elif opcode == 1:
# 即値を書き込み
lines.append(f" mem[{oprand1}] = {oprand2}")
elif opcode == 2:
# 別のセルからコピー
lines.append(f" mem[{oprand1}] = mem[{oprand2}]")
elif opcode == 3:
# 加算 (mod 256)
lines.append(f" mem[{oprand1}] = (mem[{oprand1}] + mem[{oprand2}]) % 256")
elif opcode == 4:
# 乗算 (mod 256)
lines.append(f" mem[{oprand1}] = (mem[{oprand1}] * mem[{oprand2}]) % 256")
elif opcode == 5:
# XOR
lines.append(f" mem[{oprand1}] = mem[{oprand1}] ^ mem[{oprand2}]")
elif opcode == 6:
# 論理NOT (0 なら 1、それ以外なら 0)
lines.append(f" mem[{oprand1}] = 0 if mem[{oprand1}] != 0 else 1")
else:
raise ValueError(f"Unknown opcode {opcode!r} at ip={ip}")
ip += 3
lines.append("")
lines.append(" # vm.run と同様に、mem[0] == 0 を戻り値にする")
lines.append(" return mem[0] == 0, mem")
return "\n".join(lines) + "\n"
def main() -> None:
if len(sys.argv) < 2:
path = "program"
else:
path = sys.argv[1]
with open(path, "rb") as f:
program = f.read()
src = translate(program)
sys.stdout.write(src)
if __name__ == "__main__":
main()
それで出力されたPythonコードが以下になる．
# 前略
# これは最初だけの処理
# ip=0, opcode=1, oprand1=0, oprand2=1
mem[0] = 1
# ここからパターン処理
# ip=3, opcode=0, oprand1=1, oprand2=0
mem[1] = ord(read_char()) % 256
# ip=6, opcode=3, oprand1=1, oprand2=3
mem[1] = (mem[1] + mem[3]) % 256
# ip=9, opcode=1, oprand1=2, oprand2=9
mem[2] = 9
# ip=12, opcode=5, oprand1=1, oprand2=2
mem[1] = mem[1] ^ mem[2]
# ip=15, opcode=2, oprand1=3, oprand2=1
mem[3] = mem[1]
# ip=18, opcode=1, oprand1=2, oprand2=184
mem[2] = 184
# ip=21, opcode=3, oprand1=1, oprand2=2
mem[1] = (mem[1] + mem[2]) % 256
# ip=24, opcode=6, oprand1=1, oprand2=0
mem[1] = 0 if mem[1] != 0 else 1
# ip=27, opcode=4, oprand1=0, oprand2=1
mem[0] = (mem[0] * mem[1]) % 256
# ここまでがパターン1回分の処理
# 後略
コードを眺めてみると，1パターンのコードが繰り返されていることが判明．
多分文字数の分だけ繰り返されている．
最後の部分を見ると
mem[0] = (mem[0] * mem[1]) % 256
# ip=1083, opcode=6, oprand1=0, oprand2=0
mem[0] = 0 if mem[0] != 0 else 1
つまりmem[0]が0でない数字ならmem[0]になってフラグと一致．
その前の行を見ると，mem[0] * mem[1]だから，mem[1]の結果が1文字だけの比較結果．
mem[0]が今までの結果を累積しているメモリだろう．
なんとかmem[0] != 0でない値にするには，プログラム内のmem[0] * mem[1]の演算が行われるときすべてにおいて，mem[1] != 0である必要がある．もし一度でもmem[1] == 0になってしまうと，フラグと一致しないといえるであろう．
てことは，mem[0] != 0(mem[1] != 0でもいい)がtrueになるstepの回数をキーに貪欲法でさがせばOK
よってvm.pyを以下のようにいじった．
solver.py
class VM:
def __init__(self, program: bytes):
self.program = program
self.mem = [0] * 256
self.ip = 0
self.input_string = ""
self.input_index = 0
def _read_input_char(self) -> str:
# ch = sys.stdin.read(1)
# if ch == "":
# return "\x00"
# return ch
if self.input_index >= len(self.input_string):
return "\x00"
ch = self.input_string[self.input_index]
self.input_index += 1
return ch
def step(self) -> bool:
if self.ip < 0 or self.ip >= len(self.program):
return False
code = self.program
opcode = code[self.ip]
oprand1 = code[self.ip + 1]
oprand2 = code[self.ip + 2]
self.ip += 3
if opcode == 0:
ch = self._read_input_char()
self.mem[oprand1] = ord(ch) % 256
elif opcode == 1:
self.mem[oprand1] = oprand2
elif opcode == 2:
self.mem[oprand1] = self.mem[oprand2]
elif opcode == 3:
self.mem[oprand1] = (self.mem[oprand1] + self.mem[oprand2]) % 256
elif opcode == 4:
self.mem[oprand1] = (self.mem[oprand1] * self.mem[oprand2]) % 256
elif opcode == 5:
self.mem[oprand1] = self.mem[oprand1] ^ self.mem[oprand2]
elif opcode == 6:
self.mem[oprand1] = 0 if self.mem[oprand1] != 0 else 1
else:
raise RuntimeError(f"Unknown opcode {opcode!r} at ip={self.ip}")
return True
def run(self, input_string: str, max_steps: int = 10_000_000) -> bool:
self.mem = [0] * 256
self.ip = 0
self.input_string = input_string
self.input_index = 0
self.zero_count = 0
steps = 0
while steps < max_steps and self.step():
steps += 1
if self.mem[0] != 0:
self.zero_count += 1
return self.mem[0] == 0, self.zero_count
def main():
with open("program", "rb") as f:
program = f.read()
vm = VM(program)
flag = "Alpaca{"
while True:
max_step = -1
max_char = ''
for c in range(0x20, 0x7f):
candidate = flag + chr(c) + '}'
ret, steps = vm.run(candidate)
if ret:
print(f'\nFound flag: {candidate}')
return
if steps > max_step:
max_step = steps
max_char = chr(c)
flag += max_char
print(f'\r{flag}', end='')
if __name__ == "__main__":
main()
Discussion