CTF、pwnable #6 randomのwriteup

2017.09.22
CTF

(writeupみちゃいました)

調査

ファイルの動作

指示されている通りにSSH接続します。
実行ファイルrandomを実行して、好きな数字を入力すると、
Wrong, maybe you should try 2^32 cases.

と言われてしまいます。

#include <stdio.h>

int main(){
        unsigned int random;
        random = rand();        // random value!

        unsigned int key=0;
        scanf("%d", &key);

        if( (key ^ random) == 0xdeadbeef ){
                printf("Good!n");
                system("/bin/cat flag");
                return 0;
        }

        printf("Wrong, maybe you should try 2^32 cases.n");
        return 0;
}

ソースコードを見るとシードを与えるsrand関数無しに、rand関数を使っています。

randの実装

ここでglibcのrandの実装を見ると…(ももいろテクノロジー：Z3Pyでglibc rand(3)の出力を推測してみる)

int
__random_r (buf, result)
     struct random_data *buf;
     int32_t *result;
{
  int32_t *state;

  if (buf == NULL || result == NULL)
    goto fail;

  state = buf->state;

  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }
  else
    {
      int32_t *fptr = buf->fptr;
      int32_t *rptr = buf->rptr;
      int32_t *end_ptr = buf->end_ptr;
      int32_t val;

      val = *fptr += *rptr;
      /* Chucking least random bit.  */
      *result = (val >> 1) & 0x7fffffff;
      ++fptr;
      if (fptr >= end_ptr)
    {
      fptr = state;
      ++rptr;
    }
      else
    {
      ++rptr;
      if (rptr >= end_ptr)
        rptr = state;
    }
      buf->fptr = fptr;
      buf->rptr = rptr;
    }
  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}

詳細は元記事をご覧ください…、上では前後端折ってるのでわかりにくいですがrandが呼ばれるたびに何やらポインタを進めているというのがわかります。

なおbuf->rand_type  はTYPE_3になるそうです。
よってelseのカッコの中が行われるメインの処理です。
(TYPE_0指定の場合はifのカッコの中が実行され、線形合同法で乱数が生成されます)

ポインタたちが指すのはrandtblという、内部状態の表みたいです。そこから2つを足し算して、一番ランダムじゃないLSB側1bitを捨てて31bit乱数とする…みたい。

元記事にあるように、乱数をたくさん生成させれば内部状態が推測でき、そこからどんな乱数が生成されるのかわかってしまうようになります。

解法

内部状態のテーブルが同じなら同じ乱数が同じ順番で生成されるので、今回は内部状態を調べなくても、rand関数で最初に生成される値を見ておけばOK。srand関数使ってないからいつも同じなのです。

(よくわからんけどsrand関数を使わない限りrandtblは同じ内容？みたい、違かったらごめんなさい)

random@ubuntu:~$ gdb random
(gdb) b *0x0000000000400606
Breakpoint 1 at 0x400606
(gdb) r
Starting program: /home/random/random 

Breakpoint 1, 0x0000000000400606 in main ()
(gdb) print/x $eax
$1 = 0x6b8b4567

のようにgdb等で、rand関数を実行した後にブレークポイントを仕掛けEAXレジスタの中身を見ます。(戻り値はEAXレジスタ)
何回やっても同じく0x6b8b4567が生成されていることが確認できます。

XOR演算は2回掛けると元に戻せます。
key xor random = 0xdeadbeef
より
key xor random xor random = 0xdeadbeef xor random
からkeyが求められます。
よって、0xdeadbeefと0x6b8b4567のXORをとったものが、入力されるkeyになります。

key = 0xb526fb88
です。

これを10進数で入力すればOK。

以上です。

コメント