tour

TCPサーバの接続情報、テキストファイル Dockerfile、ELFファイル tour が与えられた。

tour をGhidraで逆コンパイルすると、以下のmain関数があった。

Information to connect to a TCP server, a text file Dockerfile, and a ELF file tour were given.

Decompiling tour via Ghidra, I found this function main:

main.c

これは、都市0から始めて次に行く都市を指定していくことで、 合計コストが多くなりすぎないようにしながら全都市を訪れた後、都市0に戻ると flag.txt の内容を出力する、というものであった。
コストは、移動元と移動先の都市の組み合わせで埋め込まれたテーブルを参照することでわかる。

以下の処理をするプログラムにより都市を訪れる順番を求め、求めた順番をサーバに入力することで、flagが得られた。

  1. ファイル tour からコストのテーブルを読み込む
  2. ワーシャル-フロイド法で、各都市間の移動のための最小コストとそれを実現するために次に行くべき都市を求める
  3. メモ化探索により、全都市を訪れて都市0に戻るための最小コストと、その状態から次に行くべき都市を求める
  4. これらの結果を用いて、具体的に都市を訪れる順番を求める

This function starts a tour from city 0, has the user select the next city to visit, and prints the contents of flag.txt when it returns to the city 0 after visiting all cities without consuming too much cost.
The cost is determined by looking up the embed table using the combination of the current city and the next city to move.

I obtained the flag by determing the order of cities of visit using a program that does following process, and entering the order to the server.

  1. Read the table of the cost from the file tour.
  2. Determine the minimum cost to move from one city to another and the next city to move to archive the minimum cost via Floyd–Warshall Algorithm.
  3. Determine the minimum cost to visit all cities and return to city 0 and the next city to move to from each status via memoized recursion.
  4. Determine concluding order of cities to visit using these results.

solve.pl

flag{r3v_a1g0_cl0s3_3n0ugh_3293011594}

PBjar CTF