UCSB iCTF 2018 - fantasticiot, hero_text_adventure

attack and deference形式のCTFにオンラインで参加した。dodododoは19位。

f:id:akiym:20180318184839p:plain

sshできるサーバが1台与えられて、そこで8つのサービスを正しく動かしつつ、攻撃と防御を行う。
flagは運営からサービスが正しく動いているかどうかの確認と一緒に送られてくる。例えば秘密のメモアプリみたいなのがあったとして、正規の方法だとメモの閲覧にはパスワードが必要だけど、サービスに残された脆弱性を使うと任意のメモを見られるになればflagを入手して提出することで攻撃できる。
サービスはxinetd経由で起動するようになっていて、サービスの脆弱性を潰すためバイナリを書き換えたり、途中にバリデーション用のスクリプトを挟んだりしてflagを持ち出されないように防御できる。

このCTF専用のサービス一覧/参加チーム取得やフラグ提出用のクライアントがあって、それを使うと手軽に攻撃の自動化ができる。 事前にサンプル が渡されたのだけど、結構ミスっていて困っていた。事前にテストして欲しい……

fantasticiot

% file ./fantasticiot
./fantasticiot: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), statically linked, for GNU/Linux 3.2.0, BuildID[sha1]=baa3e0fa48be4715a10784c2dd5e7d3adb5d9181, not stripped

冷蔵庫サービス。static linkされていて一瞬ぎょっとするけど、中身は単純にJSON経由で冷蔵庫に入れたりすることができるサービス。flagはsetflagで保存されたflag。

  • setflag
    • {"token": "A", "flag": "B", "id": "2", "service": "flag", "op": "setflag"}
    • flag/1 に書き込む
  • getflag
    • {"token": "A", "id": "1", "service": "flag", "op": "getflag"}
    • flag/1 から取得する
    • ただし正しいtokenである必要がある
  • addfridge
    • {"content": "AAAAAAAAAA", "item": "1", "service": "fridge", "op": "addfridge"}
    • fridge/1 に書き込む
  • getfridge
    • {"item": "1", "service": "fridge", "op": "getfridge"}
    • fridge/1 から取得する

脆弱性

  • getfridgeの際にserviceを flag に指定することでディレクトリを変更できる
  • getfridgeの際にitemを ../flag/1 にすることでディレクトリを変更できる

こういう雑なバリデータを挟むことで回避できる。

import sys
import json

src = sys.stdin.readline()

try:
    data = json.loads(src)
    if data['op'] == 'getfridge':
        assert data['service'] == 'fridge'
        assert '/' not in data['item']
    sys.stdout.write(src)
except:
    pass
  • strncmpにbackdoorが仕掛けられている

static linkされているのはこういうことだったのか!上位チームでも意外と気づかなかったチームが結構いた。

f:id:akiym:20180318184751p:plain

つまり、getflagの際にtokenを victor に指定すればtokenチェックが問答無用に突破可能。

def exp(s, flag_id):
    payload = {
        "service": "flag",
        "op": "getflag",
        "id": flag_id,
        "token": "victor",
    }
    s.send(json.dumps(payload) + '\n')
    return json.loads(s.recvuntil('\n'))['flag']

hero_text_adventure

% file ./hero_text_adventure
./hero_text_adventure: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=98aac0bf05483d6328b1640625404c533c785999, not stripped
% ./hero_text_adventure
Hello superhero, are you continuing your previous adventure? (y/N)
n
Welcome to the beta test of the Marvel Super Hero text adventure!
Enter your name:
test
Pick a character
1) Star Lord
2) Dr Strange
3) wanda maximoff
4) Hulk
5) Thor
1
test, what would you like to do?
1) BATTLE!
2) buy weapon
3) equip weapon
4) give weapon a new name
5) load game
6) exit
6
Exiting. Save game? (y/N)
y
enter a password to protect your save file
secretpassword!
id of your adventure: 7906397325484763355

アドベンチャーゲーム。戦ったり、武器を買ったり、データをロード/セーブできる。flagはセーブされているデータのname部分。

脆弱性

  • weaponのhandlerのアドレス書き換え
    • 1) BATTLE! のときに任意のアドレスに対して飛べるようになる
    • readlineの最初(0x400C8C)に飛ぶことで、bssのプレイヤー名のあるアドレス(0x603240)以降の書き換えができる
    • そこから装備中の武器のアドレスを書き換えると、 4) give weapon a new name から任意のアドレスへの書き込みができるようになる
    • GOTにあるstrcmpをstrchrに書き換えるとデータのロード時のパスワードチェックで、strcmpが strchr("real_password", "input") になり、これはNULLを返すので任意のデータをロードできるようになりflagが入手できる

exploit: hero_text_adventure · GitHub

防御に関しては、give weapon a new nameのときのreadlineが36バイト読み込むのを32バイトだけ読み込むようにバイナリを変更した。

感想

自分の現在の順位よりも上のチームにしか攻撃できない(flagの提出もできず、サーバへのアクセスも遮断されている)ようになっていて珍しいルールだった。よくあるA&D形式のCTFだと防御がボロボロだと上位チームに攻撃されて、点数が減る一方で最後までやる気がなくなってしまうのだけど、これならまだ最後までできる。
一見よいルールに見えるのだけど、順位をわざと下げて攻撃対象を増やして、一度に大量の得点を取得することが可能で(もちろん攻撃が塞がれてなければだけど)割と入れ替わりが激しく、崩壊していた気がする。

今回はRuCTFEのようにVPNの提供はなく、サーバが与えられて手元から他チームに攻撃するときはsocks経由でやってくれ、というかんじだったので運営のことを考えると準備の手間をあまり考える必要なく、これなら手軽にA&D形式のCTFを開催できるのではという気がした。
ただチェックシステムを準備するのが大変という話はありそうだけど、ちょっと調べたらRuCTFEで使われているコードが公開されていた。A&D形式のCTF増えて欲しい。

github.com

YAPC::Okinawaで「Perlコーディングテクニック2018」という話をしました

speakerdeck.com

最近の便利Perl情報や好きなモジュールの話をしました。 トーク応募したときには話したかった細かい話題がいくつかあったのですが、20分では収まらなかったのもありクラスビルダやクラスローダ、バリデータ、Type::Tinyの話になりました。

トークの中で紹介した、拙作のSmart::Args::TypeTinyが結構好きで最近よく使っています。

Smart::Args::TypeTiny - We are smart, smart for you - metacpan.org

詳しい使い方やSmart::Argsと比較したときのメリットをあまり説明できなかったのですが、Smart::Args::TypeTinyについては昨年 id:papix さんが紹介している記事があります。(ありがとうございます!!!)

papix.hatenablog.com

自分のトーク後の id:shoichikaji さんのトークの冒頭では、手元環境ではstricturesのPERL_STRICTURES_EXTRAを設定しているという話がありました。便利ですね。

strictures - turn on strict and make most warnings fatal - metacpan.org

参加者の皆様並び運営スタッフの皆様お疲れ様でした。次回も楽しみにしています。

YAPC::Fukuokaで「新時代のテストフレームワークTest2」という話をしました

speakerdeck.com

トークの内容はTest2の導入から便利情報を紹介したりしました。少しでもTest2使う人が増えるといいですね。

スライド中にも触れていますが、基本的にはTest2に移行するにあたってはTest2::Plugin::UTF8を使うようにすれば大丈夫かなと思います。

一部Test::ClassのハックをTest2に対応するといった特殊な例も紹介しました。スライドでは時間の都合上省いたのですが、Test::Classは意外と扱いが難しく、テストファイルから読み込まれるモジュールでTest::Moreを直接使っていると$TODOが動かなくなるというケースもありました。Test::Moreokを直接呼んでいる場合はTest2::APIcontextで書き換える必要があります。

また、Test::Warningsでテスト中で警告が出ていたらfailする機能(Test::Builder::done_testingを書き換えている lib/Test/Warnings.pm - metacpan.org)が動かなくなっていることに関してはTest2::Plugin::NoWarningsを使うことにより代用することができます。

Test2::Plugin::NoWarnings - Fail if tests warn - metacpan.org

参加者の皆様並び運営スタッフの皆様お疲れ様でした。次のYAPCは沖縄で開催するとのことで楽しみにしています。

株式会社はてなに入社しました

株式会社はてなに入社しました

株式会社はてなに入社しました - hitode909の日記

年賀状CTF 2017 writeup

今年もid:nanuyokakinuさんによる年賀状CTFが開催されていたので参加した.
reversing問題が全部で3問.すべて解くと最後のフラグにAmazonのギフト券が書いてあり,お年玉が貰える.今年はなんと0x1337円.ありがとうございました :)

nanuyokakinu.hatenablog.jp

以下,解いた問題のwriteup.

stage1

% file stage1.exe
stage1.exe: PE32+ executable for MS Windows (console) Mono/.Net assembly

64bitのPE.IDA Pro Freeが使えないのでHopperを使って読んだ.ただし,静的解析の妨害として,文字列がエンコードされているので,x64dbgというデバッガで動かしながら確認していった.

notepad.exeのプロセスのメモリをWriteProcessMemoryで書き換えている.ダンプするとまたPEが出てくるのでそれらしい処理をしているところを見ると,HappyNewYear2017を鍵として暗号化したものがERV5vdff++FakEbRj0z8UyhZPPBYLLPm5xYAeVPPKsGlvRzPH4Bq+o1tZQB2wgznになればよいらしい.
stage1.exeに同様の___ENCRYPTKEY___が鍵の復号処理があるので,それを流用した.

# -*- coding: utf-8 -*-
import base64
import struct

p = lambda x: struct.pack('<I', x)
u = lambda x: struct.unpack('<I', x)[0]
u4 = lambda x: [u(x[i:i+4]) for i in range(0, len(x), 4)]

password = u4(base64.b64decode('ERV5vdff++FakEbRj0z8UyhZPPBYLLPm5xYAeVPPKsGlvRzPH4Bq+o1tZQB2wgzn'))
enckey = u4('HappyNewYear2017')

length = len(password)
blocknum = 52 / length + 6

block = password[0]

i_1 = blocknum * 0x9e3779b9
i_1 &= 0xffffffff

for _ in range(blocknum):
    i_2 = (i_1 >> 2) & 3
    for j in range(length-1, -1, -1):
        c = password[j-1]

        edx = (c >> 5) ^ ((block << 2) & 0xffffffff)
        r8d = (block >> 3) ^ ((c << 4) & 0xffffffff)
        ecx = edx + r8d
        ecx &= 0xffffffff

        edx = block ^ i_1
        r8d = enckey[(j & 3) ^ i_2] ^ c

        edx += r8d
        edx &= 0xffffffff
        ecx ^= edx
        eax = password[j]
        eax -= ecx
        eax &= 0xffffffff
        d = eax

        password[j] = d
        block = d

    i_1 -= 0x9e3779b9
    i_1 &= 0xffffffff

print ''.join([p(x) for x in password])
NYC{L0gg1ng_Cl1pb04rd_w17h_Dll_1nj3c710n})

notepad.exeに対して,dll injectionを行い,その中でクリップボードのデータからフラグチェックを行うものだったらしい.

stage2

WebAssembly!! wasmファイルが同梱されていて,フラグチェックがWebAssembly上で行われる.ブラウザ上で動かす場合,Chromeならchrome://flags/#enable-webassemblyから有効にできる.

まずはwasmをwastに変換して読み始める. https://github.com/WebAssembly/wabt にあるwasm2wastを使うと変換できる.命令セットについては, https://github.com/WebAssembly/design/blob/master/BinaryEncoding.md を参照.

main関数まわりを読んでみると,スタックに引数を積んでいきながら命令を実行していくスタックマシンのようなかんじ.ローカル変数は関数に渡された引数,関数内で使っている変数という順番に番号が振られる.

stage2.htmlを見ると,main関数にコマンドライン引数として比較される文字列を渡している. main(func 28)を見ると,2つの引数argc, argvを持っていることが分かる.コード中に*(argv+4)のような処理があるので合っているはず.

  (func (;28;) (type 1) (param i32 i32) (result i32)
    (local i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32)
    block i32  ;; label = @1
      get_global 9
      set_local 47
      get_global 9
      i32.const 32
      i32.add
      set_global 9
      get_global 9
      get_global 10
      i32.ge_s
      if  ;; label = @2
        i32.const 32
        call 3
      end
      i32.const 0
      set_local 12
      get_local 0
      set_local 23
      get_local 1
      set_local 34
      get_local 34
      set_local 44
      get_local 44
      i32.const 4
      i32.add
      set_local 45
      get_local 45
      i32.load
      set_local 2
      get_local 2
      call 41
      set_local 3
      get_local 3
      set_local 42
      get_local 42
      set_local 4
      get_local 4
      i32.const 46
      i32.ne
      set_local 5
      get_local 5
      i32.eqz
      if  ;; label = @2
        get_local 42
        set_local 6
        get_local 6
        i32.const 1
        i32.add
        set_local 7
        get_local 7
        i32.const 1
        call 52
        set_local 8
        get_local 8
        set_local 41
        get_local 41
        set_local 9
        get_local 34
        set_local 10
        get_local 10
        i32.const 4
        i32.add
        set_local 11
        get_local 11
        i32.load
        set_local 13
        get_local 9
        get_local 13
        call 42
        drop
        i32.const 0
        set_local 43
        loop  ;; label = @3
          block  ;; label = @4
            get_local 43
            set_local 14
            get_local 42
            set_local 15
            get_local 14
            get_local 15
            i32.lt_u
            set_local 16
            get_local 16
            i32.eqz
            if  ;; label = @5
              br 1 (;@4;)
            end
            get_local 43
            set_local 17
            get_local 41
            set_local 18
            get_local 18
            get_local 17
            i32.add
            set_local 19
            get_local 19
            i32.load8_s
            set_local 20
            get_local 20
            i32.const 255
            i32.and
            set_local 21
            get_local 21
            i32.const 255
            i32.xor
            set_local 22
            get_local 22
            i32.const 255
            i32.and
            set_local 24
            get_local 19
            get_local 24
            i32.store8
            get_local 43
            set_local 25
            get_local 41
            set_local 26
            get_local 26
            get_local 25
            i32.add
            set_local 27
            get_local 27
            i32.load8_s
            set_local 28
            get_local 28
            call 27
            set_local 29
            get_local 29
            call 3
            get_local 43
            set_local 30
            get_local 41
            set_local 31
            get_local 31
            get_local 30
            i32.add
            set_local 32
            get_local 32
            get_local 29
            i32.store8
            get_local 43
            set_local 33
            get_local 33
            i32.const 1
            i32.add
            set_local 35
            get_local 35
            set_local 43
            br 1 (;@3;)
          end
        end
        get_local 41
        set_local 36
        get_local 42
        set_local 37
        get_local 36
        i32.const 1144
        get_local 37
        call 37
        set_local 38
        get_local 38
        i32.const 0
        i32.ne
        set_local 39
        get_local 39
        i32.eqz
        if  ;; label = @3
          i32.const 1195
          call 49
          drop
          i32.const 1
          set_local 12
          get_local 12
          set_local 40
          get_local 47
          set_global 9
          get_local 40
          return
        end
      end
      i32.const 1191
      call 49
      drop
      i32.const 0
      set_local 12
      get_local 12
      set_local 40
      get_local 47
      set_global 9
      get_local 40
      return
    end)

これだと読みにくいので,擬似コードに直すスクリプトを書いて変換して読んだ.

@1: {
  l[47] = g[9]
  g[9] = g[9] + 32
  if g[9] >= g[10] {
    call 3(32)
  }
  l[12] = 0
  l[23] = l[0]
  l[34] = l[1]
  l[44] = l[34]
  l[45] = l[44] + 4
  l[2] = *l[45]
  call 41(l[2]) # strlen
  l[3] = RETVAL
  l[42] = l[3]
  l[4] = l[42]
  l[5] = l[4] != 46 # 入力は46文字
  if l[5] == 0 {
    l[6] = l[42]
    l[7] = l[6] + 1
    call 52(l[7], 1) # バッファの確保?
    l[8] = RETVAL
    l[41] = l[8]
    l[9] = l[41]
    l[10] = l[34]
    l[11] = l[10] + 4
    l[13] = *l[11]
    call 42(l[9], l[13]) # 確保したバッファに文字列をコピー?
    drop
    l[43] = 0
    loop@3: {
      @4: {
        l[14] = l[43]
        l[15] = l[42]
        l[16] = l[14] < l[15]
        if l[16] == 0 {
          br (;@4;)
        }
        l[17] = l[43]
        l[18] = l[41] # 渡された文字列
        l[19] = l[18] + l[17]
        l[20] = *l[19]
        l[21] = l[20] & 255
        l[22] = l[21] ^ 255
        l[24] = l[22] & 255
        *l[19] = l[24]
        l[25] = l[43]
        l[26] = l[41]
        l[27] = l[26] + l[25]
        l[28] = *l[27]
        call 27(l[28]) # 変換
        l[29] = RETVAL
        l[30] = l[43]
        l[31] = l[41]
        l[32] = l[31] + l[30]
        *l[32] = l[29]
        l[33] = l[43]
        l[35] = l[33] + 1
        l[43] = l[35]
        br (;@3;)
      }
    }
    l[36] = l[41]
    l[37] = l[42]
    # 
    call 37(l[36], 1144, l[37]) # strncmp
    l[38] = RETVAL
    l[39] = l[38] != 0
    if l[39] {
      call 49(1195) # good
      drop
      l[12] = 1
      l[40] = l[12]
      g[9] = l[47]
      return l[40]
    }
  }
  call 49(1191) # bad
  drop
  l[12] = 0
  l[40] = l[12]
  g[9] = l[47]
  return l[40]
}

func 27:

@1: {
  l[8] = g[9]
  g[9] = g[9] + 16
  if g[9] >= g[10] {
    call 3(16)
  }
  l[1] = l[0]
  l[2] = l[1]
  call 26(l[2], 12, 2)
  l[3] = RETVAL
  l[1] = l[3]
  l[4] = l[1]
  call 26(l[4], 34, 1)
  l[5] = RETVAL
  l[1] = l[5]
  l[6] = l[1]
  g[9] = l[8]
  return l[6]
}

func 26:

@1: {
  l[31] = g[9]
  g[9] = g[9] + 16
  if g[9] >= g[10] {
    call 3(16)
  }
  l[23] = l[0]
  l[24] = l[1]
  l[25] = l[2]
  l[27] = l[23]
  l[28] = l[27] & 255
  l[29] = l[25]
  l[3] = l[28] >> l[29]
  l[4] = l[23]
  l[5] = l[4] & 255
  l[6] = l[3] ^ l[5]
  l[7] = l[24]
  l[8] = l[7] & 255
  l[9] = l[6] & l[8]
  l[10] = l[9] & 255
  l[26] = l[10]
  l[11] = l[23]
  l[12] = l[11] & 255
  l[13] = l[26]
  l[14] = l[13] & 255
  l[15] = l[12] ^ l[14]
  l[16] = l[26]
  l[17] = l[16] & 255
  l[18] = l[25]
  l[19] = l[17] << l[18]
  l[20] = l[15] ^ l[19]
  l[21] = l[20] & 255
  l[23] = l[21]
  l[22] = l[23]
  g[9] = l[31]
  return l[22]
}

後半に表われる1144や1195, 1191はデータを参照している.

  (data (i32.const 1024) "\04\04\00\00\05\00\00\00\00\00\00\00\00\00\00\00\01\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\02\00\00\00\03\00\00\00\d8\06\00\00\00\04\00\00\00\00\00\00\00\00\00\00\01\00\00\00\00\00\00\00\00\00\00\00\00\00\00\0a\ff\ff\ff\ff\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\04\04\00\00\8b\9c\da\90\c8\f0\d3\e5\d0\d0\f0\86\d3\87\94\88\e5\83\c7\88\87\87\c1\86\88\e5\d1\f0\88\c9\f0\d1\94\88\f4\83\e0\f0\d1\f0\e4\e0\f4\83\c2\84\00bad\00good"))

手軽にデバッグするがないか探していたら,importされているabortStackOverflowを使うとabortのメッセージで値をリークできた.

f:id:akiym:20170103100438p:plain

例えば,ローカル変数28が文字列への参照だったときに,その先頭1バイトを確認する場合は以下のコードを追加して,wast2wasmでwasmに変換して実行する.

get_local 28
i32.load8_u
call 3

入力を変換した後の結果が\x8b\x9c\xda\x90\xc8\xf0\xd3\xe5\xd0\xd0\xf0\x86\xd3\x87\x94\x88\xe5\x83\xc7\x88\x87\x87\xc1\x86\x88\xe5\xd1\xf0\x88\xc9\xf0\xd1\x94\x88\xf4\x83\xe0\xf0\xd1\xf0\xe4\xe0\xf4\x83\xc2\x84になれば正解.
1文字ずつ総当たりして求めた.

# -*- coding: utf-8 -*-

def func26(c, x, y):
    A = ((c >> y) ^ c) & x
    return (c ^ A) ^ (A << y) & 0xff

def func27(c):
    return func26(func26(c, 12, 2), 34, 1)

answer = '\x8b\x9c\xda\x90\xc8\xf0\xd3\xe5\xd0\xd0\xf0\x86\xd3\x87\x94\x88\xe5\x83\xc7\x88\x87\x87\xc1\x86\x88\xe5\xd1\xf0\x88\xc9\xf0\xd1\x94\x88\xf4\x83\xe0\xf0\xd1\xf0\xe4\xe0\xf4\x83\xc2\x84'

flag = ''
for i in range(46):
    for c in range(0x20, 0x7f):
        if (ord(answer[i])) == func27(c ^ 0xff):
            flag += chr(c)
            break
print flag
NYC{W3b4ss3mbly_4nd_llvm_4r3_V3ry_1n73r3571ng}

stage3

dlangバイナリ.Hopperにはdlangのdemangle機能がないので,objdump --demangle=dlang --sym stage3の結果を見ながら解析する.
stage1と同様に,この問題でも文字列がエンコードされているので,デバッガで動かしながら確認していくとhttps://userstream.twitter.com/1.1/user.jsonという文字列やstage3.send_dmという関数があるので,Twitterに関連した問題だと分かる.

DMを経由してコマンドを実行するC2サーバのような動作をしている.
.dataセクションにOAuthのconsumer keyとaccess tokenだけではなく,consumer secretとaccess token secretが残っているのでこれを利用すると,@mytyl_nyctfのDMの内容を見ることができる.@tyltyl_nyctfとDMでやりとりされており,その内容がコマンドの実行結果となっている.

コマンド,実行結果は以下の手順で暗号化されている.

  • zlibで圧縮
  • RC4で暗号化 (key=Thank you for playing! Almost there!)
  • カスタムテーブルを持ったBase64エンコード (table=TXyU9lM5VfHkRS0YgvK4hcnb~CEIFBQ7r3zdAqO6DNe2p8sxmtL_JuGa1joZWiP-w)

逆の手順を行うことで復号することができる.カスタムBase64RC4というとDaserfっぽい.

import base64
import string
import zlib
from Crypto.Cipher import ARC4

transtable = string.maketrans(
    'TXyU9lM5VfHkRS0YgvK4hcnb~CEIFBQ7r3zdAqO6DNe2p8sxmtL_JuGa1joZWiP-w',
    'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/='
)
rc4_key = 'Thank you for playing! Almost there!'

enc = [
    'D7puoyfhNkq6zCko6gRw',
    'D78ZUUn0eWXadhnHJp3tF7E_3Yg~oAvG~jY6f2nWK8nyixt-Ax8~ifbWeEgP7V1W1Q0lbvYmZaIIX1_x7UhB9tdzgVIHtUeQbNjODzO15A45sNVlKMN5jPZ9Ra30l6D5LOyUv_6I5y1lcglgk4PH1U3TFpZE',

    'D7suzudHbRRLnhE1cZTeZxcnPWf8Xu1Ynmww',
    open('encflag', 'r').read(),
]

for x in enc:
    x = x.translate(transtable)
    x = base64.b64decode(x)
    x = ARC4.new(rc4_key).decrypt(x)
    x = zlib.decompress(x)
    print x
ls -la
total 5152
drwxr-xr-x 1 vagrant vagrant     136 Dec 31 16:37 .
drwxr-xr-x 1 vagrant vagrant     306 Dec 31 16:28 ..
-rw-r--r-- 1 vagrant vagrant    6980 Dec 31 16:33 flag.jpg
-rwxr-xr-x 1 vagrant vagrant 5264181 Dec 31 16:09 stage3

base64 ./flag.jpg
/9j/4AAQSkZJRgABAQEASABIAAD/4QCMRXhpZgAATU0AKgAAAAgABgEGAAMAAAABAAIAAAESAAMA
...

デコードするとギフト券番号が書いてある画像が出てくる.

まずはCTFの過去問を解く

この記事は,CTF Advent Calendar 2016の1日目です.

www.adventar.org

CTFプレイヤーたるもの,日々の鍛錬は欠かせません. 過去問を解いてこそ,競技中に真の実力を発揮することができるのです.

ということで,bata_24さんが公開しているpwn challenges list - Pastebin.comを管理できるページを作成しました.

http://ctf.katsudon.org/ctf4u/

f:id:akiym:20161201215701p:plain

CTF Advent Calendar 2016 - Adventar にはまだ空きがあるようなので,過去問のwriteupを書いてくれる方をお待ちしています.

全完目指して頑張りましょう.お楽しみください.

高速にリストからハッシュにする

いまいちピンとくる言い方が分からないけれど,つまりはこういうこと.

[
    {
        id => 1,
        value => 'foo',
    },
    {
        id => 2,
        value => 'bar',
    },
]

このようなデータ構造があったときに,以下のようにidをkeyとしてハッシュにしたい.

{
    1 => {
       id => 1,
       value => 'foo',
    },
    2 => {
       id => 2,
       value => 'bar',
    }
}

割とよくあることなので,普段はmapを使ってこのように書いている.

my $x = +{map { ($_->{id} => $_) } @users};

これは,List::Utilreduceを使っても同じように書ける.引数の先頭がハッシュリファレンスになっていて,それを引き回すことで実現している.

use List::Util qw/reduce/;
my $x = reduce { $a->{$b->{id}} = $b; $a } ({}, @users);

実は,reduceで書いたコードはmapよりも40%程度ではあるが若干早く動作する.一見mapのほうがシンプルで値を返しているだけなので早く動作するように見えるがそうではない.

気になったのでList::Utilのコードを見てみたところ,lightweight callbackを使って実装されていた.

https://metacpan.org/source/PEVANS/Scalar-List-Utils-1.46/ListUtil.xs#L370-430

lightweight callbackについてはperldoc perlcallに少しだけではあるがドキュメントが存在する.ループ中に同じ関数を何度も呼び出すようなケースに使う.

reduceで書いたコードが早いのはlightweight callbackのおかげらしい.ということで,List::Utilのコードを参考に,lightweight callbackを使って高速にリストからハッシュにする処理を書いてみた.

github.com

名前が思い付かなかったのでそのままto_hashに……

  • List::Utilのコードはコアモジュールだからかポータブルな実装.ifdefたくさん.
  • $_GvSV(PL_defgv)
  • 返り値は関数呼び出し後に*PL_stack_spを参照
  • Perlのハッシュは,キーにundefを指定することができない(空文字列になる)

ベンチマークは以下の通り.

use strict;
use warnings;
use Benchmark qw/:all/;
use List::ToHash;
use List::Util;

my @ARRAY;
for my $i (1..100) {
    push @ARRAY, {
        id    => $i,
        value => '.' x 100,
    };
}

cmpthese(timethese(0, {
    map => sub {
        my $x = +{map { ($_->{id} => $_) } @ARRAY};
    },
    reduce => sub {
        my $x = List::Util::reduce { $a->{$b->{id}} = $b; $a } ({}, @ARRAY);
    },
    for => sub {
        my $x = {};
        $x->{$_->{id}} = $_ for @ARRAY;
        $x;
    },
    to_hash => sub {
        my $x = List::ToHash::to_hash { $_->{id} } @ARRAY;
    },
}));
Benchmark: running for, map, reduce, to_hash for at least 3 CPU seconds...
       for:  3 wallclock secs ( 3.18 usr +  0.01 sys =  3.19 CPU) @ 19303.13/s (n=61577)
       map:  3 wallclock secs ( 3.13 usr +  0.02 sys =  3.15 CPU) @ 13437.46/s (n=42328)
    reduce:  3 wallclock secs ( 3.20 usr +  0.02 sys =  3.22 CPU) @ 18504.66/s (n=59585)
   to_hash:  4 wallclock secs ( 3.12 usr +  0.01 sys =  3.13 CPU) @ 26635.78/s (n=83370)
           Rate     map  reduce     for to_hash
map     13437/s      --    -27%    -30%    -50%
reduce  18505/s     38%      --     -4%    -31%
for     19303/s     44%      4%      --    -28%
to_hash 26636/s     98%     44%     38%      --

結果としては,mapよりも2倍早く処理することができた.ただこの程度であれば微々たる差のように見える.結局はmap使っておけば良さそう.