問題リンク

観察

配布されたchallのファイル形式を調べてみると普通のELFなので、とりあえず実行してみましょう。

$ file ./chall
./chall: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=cad54f8480fb7120a6bf06f1647f1801e946a02c, for GNU/Linux 3.2.0, not stripped

すると、flagの入力を促されます。適当にAlpaca{aaaa}と入力してみます。

$ ./chall
Enter the flag: Alpaca{aaaa}
0x41, 0x6D, 0x72, 0x62, 0x67, 0x64, 0x81, 0x66, 0x69, 0x68, 0x6B, 0x76,

文字列を与えると、16進数の数値の列が出力されました。これは、配布されたout.txtに記載されているものに似ています。

今回与えられたバイナリはフラグチェッカーではなく、入力に何らかの変換を施すプログラムのようです。

Alpaca{aaaa}を入力したときの出力とout.txtの内容を比較すると、0番目から6番目までの数値が一致しています。これはAlpaca{の部分に相当すると考えられます。ここから、今回与えられたプログラムは入力された文字に1文字ずつ何らかの加工をして出力するプログラムと推測できます。また、out.txtに記載されているテキストはflagをこのプログラムに入力したものと考えてよいでしょう。

このことから、このプログラムが文字列にどのような操作をしているか、またその逆操作が分かればflagが取得できそうです。

解法

与えられたバイナリをBinary Ninjaで解析します。疑似Cコードで表示すると、以下のようになっているようです（本当はもっとごちゃごちゃしていますが、一部綺麗にしています）。

uint64_t a(int32_t x, int32_t y) {
  return (uint64_t)(x + y);
}

uint64_t b(int32_t x, int32_t y) {
  return (uint64_t)x ^ (uint64_t)y;
}

int32_t main() {
  printf("Enter the flag: ");
  char var_48[0x28];
  __isoc99_scanf("%33s", &var_48);
  uint64_t (* var_58)(int32_t arg1, int32_t arg2) = a;
  uint64_t (* var_50)(int32_t arg1, int32_t arg2) = b;
  int32_t var_5c = 0; // ループ用のカウンタ変数

  while ((int64_t)var_5c < strlen(&var_48)) {
    int32_t temp0_1;
    int32_t temp1_1;
    temp0_1 = HIGHD((int64_t)var_5c);
    temp1_1 = LOWD((int64_t)var_5c);
    uint32_t rdx_1 = temp0_1 >> 0x1f;
    printf("0x%X, ", (uint64_t)(&var_58)[(int64_t)(((temp1_1 + rdx_1) & 1) - rdx_1)]((uint64_t)var_48[(int64_t)var_5c], (uint64_t)var_5c));
    var_5c += 1;
  }

  putchar(0xa); // LF を出力
}

関数ポインタが使われていたりしてかなり実際の処理が分かりにくいです。ループの中のprintf文が今回の問題の肝なのでここを分解していきましょう。

まずループ中で定義されているtemp0_1とtemp1_1ですが、ここにはそれぞれvar_5cの上位32bitと下位32bitが入ります*1。つまり今回のケースでは常にtemp0_1=0です。ここからrdx_1=0も分かります。

ゆえに、(&var_58)[(int64_t)(((temp1_1 + rdx_1) & 1) - rdx_1)]という部分は(&var_58)[temp1_1 & 1]と簡略化できます。var_5cが偶数か奇数かによって呼び出す関数を切り替えているということが分かりました。

var_5cが偶数のときは(&var_58)[0]（つまり関数a）、奇数のときは(&var_58)[1]（メモリ上でvar_58とvar_50は隣接しているので関数b）が呼び出されます。

引数の方は簡単で、ユーザーからの入力var_48のvar_5c文字目と、var_5cが関数に渡されます。

これらをまとめると、与えられたプログラムchallは以下のようなプログラムと等価です。

#include <iostream>
using namespace std;

uint64_t a(int32_t x, int32_t y) {
  return (uint64_t)(x + y);
}

uint64_t b(int32_t x, int32_t y) {
  return (uint64_t)x ^ (uint64_t)y;
}

int main() {
  string s;
  cin >> s;

  uint64_t (*func_table[2])(int32_t, int32_t);
  func_table[0] = a; // var_58
  func_table[1] = b; // var_50

  int32_t i = 0;
  while (i < s.size())
  {
    uint64_t result = func_table[i % 2](s[i], i);

    printf("0x%X, ", result);
    i++;
  }

  cout << endl;
  return 0;
}

さて、「文字列に対してどのような操作がされているのか」が分かったので、このプログラムの逆の操作をするプログラムも作成できます。

#include <iostream>
using namespace std;

uint64_t rev_a(int32_t x, int32_t y) {
  return (uint64_t)(x - y);
}

uint64_t b(int32_t x, int32_t y) {
  return (uint64_t)x ^ (uint64_t)y;
}

int main() {
  int s[] = {0x41, 0x6D, 0x72, 0x62, 0x67, 0x64, 0x81, 0x46, 0x74, 0x79, 0x6B, 0x68, 0x6D, 0x45, 0x6F, 0x6C, 0x7B, 0x4E, 0x7B, 0x7D, 0x73, 0x42, 0x85, 0x79, 0x7C, 0x7C, 0x8C, 0x77, 0x7D, 0x73, 0x82, 0x62};

  uint64_t (*func_table[2])(int32_t, int32_t);
  func_table[0] = rev_a;
  func_table[1] = b;

  string flag = "";

  int32_t i = 0;
  while (i < 32)
  {
    uint64_t r = func_table[i % 2](s[i], i);

    flag += (char)r;
    i++;
  }

  cout << flag << endl;
  return 0;
}