# trilemma [InterKosenCTF 2020]
###### tags: `InterKosenCTF2020` `reversing`

## 概要

`main.c`と3つの共有ライブラリ`libcitizen.so`, `libemperor.so`, `libslave.so`が与えられる。

/**
   $ gcc main.c -L./ -lemperor -lcitizen -lslave
   $ LD_LIBRARY_PATH=./ ./a.out
 */
#include <stdio.h>

char *emperor_flag(void);
char *citizen_flag(void);
char *slave_flag(void);

int main(void) {
  printf("The flag is %s%s%s\n", emperor_flag(), citizen_flag(), slave_flag());
  return 0;
}

`main.c`はおそらく3つの共有ライブラリの関数を呼び出して、フラグを生成している。のであれば、コメントの指示に従ってコンパイルをするだけで良さそうに見える。

が、そううまくはいかず、実行してみると次のようなメッセージとともに処理が終了してしまった。

[libslave.so] Citizen despises slave.

## 解析

仕方がないのでIDAなどで共有ライブラリの処理を見る。3つの共有ライブラリはほとんど同じ構造をしていて、`slave`, `slave_flag`, `slave_secret`という3つの関数が存在している（libemperorやlibcitizenではそれぞれ対応した名前がついている）。さらに`lookup`という関数も見える（こちらは3つの共有ライブラリで共通の名前）。

ここで、`slave`関数の処理を見ると、先頭でなにやら`dl_iterate_phdr`を用いて、`lookup`で何かしらを探している（`dl_iterate_phdr`を呼び出すと、読み込まれている共有ライブラリが得られる）。そして結果によっては先程の `[libslave.so] Citizen despises slave.` というメッセージを表示したり、また`[libslave.so] Slave thirsts for rebellion.`というメッセージも用意されていて、こちらを表示したりする。

そこで`lookup`が何を探しているのかを見ると、案の定`libcitizen.so`や`libemperor.so`が読み込まれているかどうかを見ている。`libcitizen.so`の`lookup`関数では`libemperor.so`と`libslave.so`が読み込まれているかを見ているし、`libemperor.so`では`libcitizen.so`と`libslave.so`が読み込まれているかを見ている。それぞれが読み込まれているとうまく動作しないところが、"trilemma"なのだろう。

ではライブラリを1つだけ読み込めばこのチェックはくぐり抜けられるのでは、と思うが、そううまくはいかず`slave_flag`というフラグの一部を生成する関数では内部で`emperor_secret`を呼び出しており、`libemperor.so`なしではフラグを読み込むことが出来なさそうに見える。

また、`slave_flag`関数の先頭では`mmap`を呼び出してメモリのある領域を確保しているが、このアドレスが`citizen_secret`で確保しているアドレスと重複しており、療法を呼び出すと`Resource conflicts.`と言われて処理が異常終了してしまう。

## 解法

そこで次のような方針でフラグを得ることにした。
1. 各共有ライブラリのコンストラクタ関数(`slave`関数など)でのライブラリの呼び出しチェックを、バイナリにパッチをあてて回避する
2. `*_flag`関数を1つだけ呼び出して`mmap`によるアドレスのコンフリクトを回避する
3. これをそれぞれの共有ライブラリについてやって、フラグの全体を取得する

1ではジャンプの条件部分を反転させるようなパッチをあてた。バイナリの変更はIDAでもdiffを生成することでできるし、radare2のようなツールを使ってもできる。

2では次のようにフラグを出力する関数をひとつだけ呼び出した。

/**
   $ gcc emperor.c -o emperor -L. -lemperor -lcitizen -lslave
   $ LD_LIBRARY_PATH=./ ./emperor
 */
#include <stdio.h>

char *emperor_flag(void);
char *citizen_secret(void);

int main(void) {
  printf("%s", emperor_flag());
  return 0;
}

/**
   $ gcc citizen.c -o citizen -L. -lcitizen -lslave -lemperor
   $ LD_LIBRARY_PATH=./ ./citizen
 */
#include <stdio.h>

char *slave_secret(void);
char *citizen_flag(void);

int main(void) {
  printf("%s", citizen_flag());
  return 0;
}

/**
   $ gcc slave.c -o slave -L. -lslave -lemperor -lcitizen
   $ LD_LIBRARY_PATH=./ ./slave
 */
#include <stdio.h>

char *slave_flag(void);
char *emperor_secret(void);

int main(void) {
  printf("%s\n", slave_flag());
  return 0;
}

$ gcc emperor.c -o emperor -L. -lemperor -lcitizen -lslave
$ gcc citizen.c -o citizen -L. -lcitizen -lslave -lemperor
$ gcc slave.c -o slave -L. -lslave -lemperor -lcitizen
$ export LD_LIBRARY_PATH=.
$ ./emperor; ./citizen; ./slave 
KosenCTF{emperor_wins_with_a_probability_of_four-fifths}

他にもmmapで確保する領域を変えたり、エラーを握りつぶしたりする方法はあったと思うが、個人的にはこれが一番楽だった。（とくに前者は`*_secret`が割り当てたアドレスを使った計算を行っていることもあり難しい）

## 感想

方針がはっきりしていて解きやすく、かつ問題として面白くて嬉しい。easyかmediumくらいだと思う