qasm

ELFファイル qasm と、それの入力ファイル prog.qasm が与えられた。

qasm をGhidraで逆コンパイルすると、 以下のmain関数と、f00からf71までの「f」と16進数2桁を組み合わせた名前の関数があった。

An ELF file qasm and an file to use as input of that prog.qasm were given.

Decompiling qasm via Ghidra, I found this fundtion main and functions from f00 to f71, which are named with "f" and two-didit hexadecimal numbers.

main.c

これは、以下の特徴を持つ仮想マシンのプログラムのようである。

これを踏まえ、以下の逆アセンブラを作成した。 なお、このプログラムは命令の引数の数を取得するためにファイルqasmを参照する。

This looks like a program for virtual machine with these characteristics:

Based on these information, I created this disassembler. This program refers to the file qasm to determine the number of arguments for each instructions.

convert.pl

以下が prog.qasm を逆アセンブルした結果である。

This is disassembled prog.qasm:

convert_res.txt

さらに可読性を高めるため、以下のように整理した。 なお、convert_res.txtの後半部分は実行されなそうだったので、この結果には含まれていない。

For better readability, I organized what are done like this. I didn't include latter part of convert_res.txt which didn't seem to be executed.

kaiseki.txt

解析の結果、これは、以下のような処理をしているようだった。

  1. 文字列を読み込む。
  2. 読み込んだ文字列の長さをチェックし、57バイトでなかったら no >:( を出力して終了する。
  3. 読み込んだ文字列に対し、足し算を用いた何らかの変換を行う。
  4. 変換結果とあらかじめ埋め込まれた数列を比較する。
  5. 比較の結果、全ての要素が一致していたら yes :) を、そうでなければ no >:( を出力する。

入力がどのような数列に変換されるかを調べるため、CS50 IDEのGDBを用い、 比較のために数列の値を取得するのに使われる関数f53内のret命令にブレークポイントを置き、変換結果の値を調べた。
ここでは変換結果と比較対象の値が交互に取得されるので、GDBのc 2コマンドを用いて1回ブレークポイントを無視させることで、変換結果の値を連続で見ることができる。
また、ignore (ブレークポイント番号) 100 コマンドでブレークポイントを100回無視する設定にしてから実行を開始することで、57個中最後7個の値を見ることができる。

Analyzing this, I found this doing this process:

  1. Read a string.
  2. Check the length of the string read. If the length is not 57 bytes, output no >:( and exit.
  3. Apply some conversion using addition to the string read.
  4. Compare the result of conversion and an embed sequence of numbers.
  5. Output yes :) if all elements of the sequences are the same. Output no >:( otherwise.

To investigate how the input is converted, I used GDB in CS50 IDE.
I set a breakpoint on the ret instruction in the function f53, which is used to fetch elements of the sequences for comparision, to obtain the values in the result of conversion.
This function is used to fetch the value in the conversion result and one in the target of comparision in turn.
We can use a command c 2 in GDB to have it ignore the breakpoint once and continuously watch the values in the conversion result.
Also, we can watch the last 7 elements out of 57 by using the ignore (the no. of breakpoint) 100 command to have it ignore the breakpoint 100 times before starting execution.

When I entered this:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

を入力すると、変換結果の最初の6要素は

The first 6 elements in the conversion result were:

0x42, 0x5a, 0x14, 0x6e, 0x6a, 0x8

となり、隣り合う要素の差 (mod 127) が33 (!の文字コード) ずつ変わっていることに気がついた。
また、変換結果の最後の7要素を見ると、

I found that the difference of the next elements (modulo 127) was changing by 33 (the character code for !).
Also, the last 7 elements in the conversion result were:

0x23, 0x3a, 0x72, 0x4c, 0x47, 0x63, 0x21

となり、最後から順に0x21の1倍、3倍、6倍、10倍、15倍、21倍、28倍 (mod 127) となっていることに気がついた。
さらに、

I found that these are 1, 3, 6, 10, 15, 21, 28 times 0x21 modulo 127, respectively, from the last element.
Moreover, when I entered this:

-------------------------------------------nmlkjihgfedcba

を入力すると、最後の7要素は

The last 7 elements became:

0x22, 0x4b, 0x62, 0x65, 0x52, 0x27, 0x61

となり、最後からn番目 (1-origin) の値は「最後からk番目の値をk倍したもの」の最後から1番目からn番目までの和 mod 127 になっていそうなことに気がついた。
これに基づき、以下のプログラムでflagが得られた。

And I guessed that the n-th element from the last is the sum of n elements of "k times the k-th element from the last" from the last modulo 127.
Based on this, I obtained the flag via this program:

solve.py

このプログラムで用いたリストの値は、以下のRecipeにより prog.qasm の逆アセンブル結果から抽出した。

The values in the list used in this program is extracted from the disassembled prog.qasm using this Recipe:

Find / Replace, From Decimal, To Decimal - CyberChef

flag{i_w0nd3r_1f_th1s_is_ev3n_4_qu3u3_4nym0r3_2396538203}

PBjar CTF