AlpacaHack Round 4 (Rev)へ参加しました。そのwrite-up記事です。

コンテスト概要
結果
環境
- Windows
  - 他ソフト
- WSL2(Ubuntu 24.04)
解けた問題
- [Rev] Simple Flag Checker (42 solves, 146 points)
感想

コンテスト概要

2024/10/05(土) 12:00 +09:00 - 10/05(土) 18:00 +09:00の6時間開催でした。他ルールはコンテストページから引用します:

AlpacaHack Round 4 (Rev) へようこそ！
AlpacaHack は個人戦の CTF を継続して開催する新しいプラットフォームです。

AlpacaHack Round 4 は AlpacaHack で行われる 4 回目の CTF で、Rev カテゴリから 4 問が出題されます。 幅広い難易度の問題が出題されるため、初心者を含め様々なレベルの方に楽しんでいただけるようになっています。 問題作成者は xornet、keymoon、ptr-yudai です！

参加方法
1. 右上の「Sign Up」ボタンから AlpacaHack のユーザー登録をしてください。
2. 登録完了後、このページの「Register」ボタンを押して CTF の参加登録をしてください。

注意事項
- AlpacaHack は個人戦のCTFプラットフォームであるため、チームでの登録は禁止しています。
- 問題は運営が想定した難易度の順に並んでいます。
- 問題の配点は解いた人数に応じて変動します。
- 全てのアナウンスは AlpacaHack の Discord サーバー で行われます。
  - アナウンスは本サービス上でも行うことがありますが、Discord サーバーが主な連絡手段となります。
  - 問題が発生した場合、#ticket チャンネルから連絡してください。ただし、問題のヒントは提供しません。
- 競技システム自体への攻撃は行わないでください。なお、偶然発見したバグの報告は歓迎します。

Round 2～3同様に問題は運営が想定した難易度の順に並んでいますと明記されており、並び順で想定難易度が示されました。また、コンテスト開始前に別途NOTE: 3問目と4問目の推定難易度は同程度です。というアナウンスもありました。

結果

正の得点を得ている43人中、146点で13位でした:

また、Certificate箇所から順位の証明書も表示できます:

環境

WindowsのWSL2(Ubuntu 24.04)を使って取り組みました。

Windows

c:\>ver

Microsoft Windows [Version 10.0.19045.4957]

c:\>wsl -l -v
  NAME                   STATE           VERSION
* Ubuntu-24.04           Running         2
  docker-desktop-data    Running         2
  kali-linux             Stopped         2
  docker-desktop         Running         2
  Ubuntu-22.04           Running         2

c:\>

他ソフト

IDA Free Version 9.0.240925 Windows x64 (64-bit address size)(Free版IDAでもversion 7頃からx64バイナリを、version 8.2からはx86バイナリもクラウドベースの逆コンパイルができます)

WSL2(Ubuntu 24.04)

$ cat /proc/version
Linux version 5.15.153.1-microsoft-standard-WSL2 (root@941d701f84f1) (gcc (GCC) 11.2.0, GNU ld (GNU Binutils) 2.37) #1 SMP Fri Mar 29 23:14:13 UTC 2024
$ cat /etc/os-release
PRETTY_NAME="Ubuntu 24.04.1 LTS"
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04.1 LTS (Noble Numbat)"
VERSION_CODENAME=noble
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=noble
LOGO=ubuntu-logo
$ python3 --version
Python 3.12.3
$ python3 -m pip show pwntools | grep Version:
Version: 4.13.0
$ python3 -m pip show tqdm | grep Version:
Version: 4.66.4
$ gdb --version
GNU gdb (Ubuntu 15.0.50.20240403-0ubuntu1) 15.0.50.20240403-git
Copyright (C) 2024 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
$ pwninit --version
pwninit 3.3.1
$

解けた問題

[Rev] Simple Flag Checker (42 solves, 146 points)

A simple flag checker :)

配布ファイルとして、checkerがありました:

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

IDAで開いて解析しました。main関数は次の内容でした(変数名の変更や型付けを行った後です):

int __fastcall main()
{
  __int64 dwIndex; // rbx
  int bSucceeded; // r12d
  __m128i converted; // [rsp+0h] [rbp-98h] BYREF
  __int64 v4; // [rsp+10h] [rbp-88h]
  __int64 v5; // [rsp+18h] [rbp-80h]
  int v6; // [rsp+20h] [rbp-78h]
  char strInput50[56]; // [rsp+30h] [rbp-68h] BYREF
  unsigned __int64 v8; // [rsp+68h] [rbp-30h]

  v8 = __readfsqword(0x28u);
  __printf_chk(1LL, "flag? ");
  fgets(strInput50, 50, stdin);
  converted = 0uLL;
  v4 = 0LL;
  v5 = 0LL;
  v6 = 0;
  dwIndex = 0LL;
  LOBYTE(bSucceeded) = 1;
  do
  {
    update(&converted, strInput50[dwIndex]);
    bSucceeded = (memcmp(&converted, table[dwIndex++], 0x10uLL) == 0) & (unsigned __int8)bSucceeded;
  }
  while ( dwIndex != 49 );
  if ( bSucceeded )
  {
    __printf_chk(1LL, "Correct! Your flag is: %s\n", strInput50);
    return 0;
  }
  else
  {
    puts("Wrong...");
    return 1;
  }
}

main関数は次のことを行うと分かります:

標準入力から、終端のNUL文字を除いて、最大49文字を受け付けます。
ループ中で、入力された文字を先頭から1文字ずつ処理します。
update関数へ、第1引数を入出力両方として、第2引数の今回処理する文字を入力のみとして渡します。update関数は何らかの変換を行い、第1引数のポインタ変数へ変換結果を格納します。
update関数により更新された第1引数内容と、グローバル変数table内容の各要素16バイトと一致しているか、memcmp関数で比較します。
49回のループ全てでtable内容と一致する場合に正解判定となり、Correct! Your flag is:を表示するルートに入ります。

さて、update関数を見てみると、SIMD命令やビット演算命令が大量に並んでいました。あまりにも複雑なので読解をすぐに諦めました。一方でupdate関数中では、グローバル変数を参照しておらず、別の関数呼び出し等も行っていないため、update関数への入力が同一なら変換結果も同一になりそうなことも確認しました。

(なお、コンテスト中ではupdate関数の第1引数のポインタ変数が出力専用と誤解していました。そのため「update関数の変換結果は文字種のみに依存し、文字の位置へは依存しない」と誤解してしまっていました。実際は前述の通り、update関数の第1引数は入力としても使われます。)

解くための方法として、次の方法を考えました:

GDB経由でcheckerバイナリを実行します。
入力先頭から順番に、1文字ずつ総当たりで探索します。
結果を比較するためのmemcmp呼び出し時にブレークさせて、引数内容を確認します。
update関数の出力結果と、table内容が一致しているかを確認します。一致している場合は正解の文字としてみなし、次の文字の探索へ進みます。

なお、今となってはmemcmp関数の処理完了にブレークさせて、戻り値だけを確認するのがもっと手っ取り早い方法だと思います。前述の誤解などや試行錯誤の結果、memcmp関数の呼び出し時にブレークさせる方針を取っていました……。

上述の発想でソルバーを書きました。GDBの自動操作にはpwntoolsライブラリを使いました。また、時間がかかるのでtqdmライブラリを使って進捗を表示しました:

#!/usr/bin/env python3

import pwn
import tqdm

pwn.context.log_level = "CRITICAL"  # プロセス起動ログを抑制

# .data:0000000000004020     table
table = bytes.fromhex(
    "42 3C F1 21 A3 0F 05 AC 57 FD 40 B0 A2 14 01 98 7D 2E AD 5D D6 23 77 C1 06 7A 50 CB F8 CD 1D BC A8 25 D2 DD 9B 73 59 16 0D AD 28 22 F9 10 81 8A 50 52 38 AF 80 4F 15 F2 9A BD 06 65 75 98 A2 7C 49 79 7E D2 DC DB FE C1 36 A3 AA 97 1B 00 D2 32 BF 81 62 0A BD 10 98 1C 8C D6 33 82 2E 93 89 46 0F 2E C0 27 82 56 0A 1F D4 C6 32 49 93 DE 02 5D 90 67 9B 06 4C CB 78 0A 6F F3 9C 0E 5E 8E 3A D6 93 6F 9C A1 54 8F C5 0E 48 1B 81 31 A6 47 D9 E3 C9 CD A1 7E AF 46 9A BC AD 1C C8 C0 8C 9D D9 16 9B D2 22 82 35 C3 B0 8F 5A 05 55 58 45 C5 EB 67 0B 17 D6 A2 20 8B 6B B3 1B B8 88 6F DD 0C 1C 8F E9 5E 28 B3 05 4B 52 9B 83 FA BA 1A BD 5D 7E D5 DD 95 7F 8D 26 A0 FB 1A E5 30 AD AA 01 B7 9E 1E 10 FA AC 9C 72 57 2A 7B E3 C6 1B 8B ED FD 98 BF E1 4F 56 87 7E 8F D9 BA D6 5C 79 4A 43 57 0C 80 B0 19 D8 42 6B 2F 25 DF 59 AA DD 54 12 35 A9 18 8A AC 3F 6A 22 6E 44 7D 13 7D 4B 18 5D D3 C1 86 86 D5 B6 F4 47 9B 26 C2 E3 A4 E0 12 9E CF 12 F5 ED FC 70 4D FF B9 2C 0A BF AA 86 4D 07 FF 22 9E 9A D2 87 E3 66 15 B4 19 27 D1 EB B1 76 E8 48 12 59 AF F1 82 9B 31 92 E6 DD 80 23 3A 3F 9C D6 82 99 F3 98 60 8F D0 39 D5 9C 97 0F EF E6 8C F8 42 7A 9D A9 51 89 13 EE 7B 47 30 FA 14 86 2F 1A D8 DD 09 78 B5 9C 41 C9 62 7D 0F C8 73 42 91 63 07 ED F9 23 B8 73 7F C1 C6 F6 F6 9F 01 D5 A7 29 44 43 43 02 52 2C B5 2F AF 55 63 48 7B 55 9D 45 D9 94 52 64 6B D3 1B B6 FC 10 AF EA 55 9A EC 00 FA 5A 0E 1C EF 10 9A 7F D2 AB 20 CD 8D 8D CF 88 33 10 E4 11 AD E1 7F 7C 59 7F 29 F6 BB 32 0E A8 D9 7B FA 37 A0 41 B3 12 A4 D6 30 E6 D9 7B 1A DB 53 2A CC 13 23 EA 09 DA 46 5D F0 25 46 96 D3 64 D7 98 8E 85 8C F4 FD 85 12 C3 00 6D 0B D1 FF E3 B6 10 35 8B 36 48 5B 7C 69 77 FB 15 65 F1 A5 15 C4 07 2C D5 81 B2 1F 25 20 6F 48 E0 4C 24 54 E9 C2 00 62 08 9D 7A 10 32 B2 7C BB 5A 51 DB BF FB E1 AF 20 81 11 CE A1 9F 79 36 2C 8A B3 0C F0 DF 38 9C C9 1D 25 EF DF 4F 6C C5 3B 74 6F 9D AD 36 05 67 C5 9A AE 2D 6D AA DB 0E E0 A6 67 45 C5 8E F8 C2 1E 64 B8 64 A1 46 18 2D 4A BA 67 8A 30 B5 75 05 20 96 0D CE CC EC 1F 8C FD B0 4F CD 4C 35 46 35 7D D1 F5 83 C7 A3 2E 2E 33 30 1C 92 C9 54 AA D2 0F 66 51 50 85 72 6D BF 8C 57 73 A0 D9 BD 72 75 5A E1 3B 98 06 7D 99 4F BE A3 B3 63 B2 D0 18 17 E9 C1 EA 3B 90 04 57 B4 52 DC 28 33 E1 71 84 97 A7 E2 AD BB BC AB BB F2 17 5D C8 EE E5 32 F8 9C 32 27 10 5B 20 7B 12 46 3D C2 89 15 6F B9 1B 32 EE 5D 7A 8E 13 33 8B E5 36 60 AA 38 53 50 74 B2 86 92 5F A0 FB C6 EE 0C CE DA A2 FE 5D 35 EA"
)


def get_updated_value(flag_input: str, index: int) -> bytes:
    PROMPT = b"(gdb)"
    io: pwn.tube
    with pwn.process(["gdb", "-q", "--nx", "./checker"]) as io:
        # memcmpがmain前でも使われるようなので後で仕掛ける
        io.sendlineafter(PROMPT, b"set style enabled off")  # 色付け禁止
        io.sendlineafter(PROMPT, b"b fgets")
        io.sendlineafter(PROMPT, b"run")
        # 次のmemcmp呼び出し時にブレーク
        io.sendlineafter(PROMPT, b"b memcmp")
        io.sendlineafter(PROMPT, b"continue")
        # 入力 b"flag?"を待つと止まってしまったのでやめ。sendlineにする。
        io.sendline(flag_input.encode())

        for _ in range(index):
            io.sendlineafter(PROMPT, b"continue")  # N文字目比較まで飛ばす

        # memcmpでブレークしているので内容確認
        io.sendlineafter(PROMPT, b"x/16bx $rdi")
        # (gdb) x/16bx $rdi
        # 0x7fffffffe0d0: 0x7a    0xaf    0xa6    0xdb    0x59    0x10    0xbb    0x20
        # 0x7fffffffe0d8: 0xe2    0x59    0xa3    0xdb    0x4b    0x6d    0x7f    0x3f
        # (gdb)
        output = io.recvuntil(PROMPT)
        values = bytearray()
        for line in output.decode().splitlines():
            if line.startswith(PROMPT.decode()):
                continue
            # print(f"{line = }")
            for v in line.split(":\t")[1].split():
                values.append(int(v, 16))
        # print(values)
        assert len(values) == 16
        return bytes(values)


candidates = range(0x21, 0x7F)

flag = ""
for i in range(len(flag), 49):
    for c in tqdm.tqdm(candidates, leave=True):
        tmp_input = flag + chr(c)
        updated = get_updated_value(tmp_input, i)
        if updated == table[i * 16 : (i + 1) * 16]:
            flag += chr(c)
            print(flag)
            break
    else:
        raise Exception("Not found...")

実行しました:

$ time ./solve.py
 34%|████████▏               | 32/94 [00:05<00:10,  5.77it/s]
A
 34%|████████▏               | 32/94 [00:05<00:11,  5.53it/s]
 80%|███████████████████▏    | 75/94 [00:12<00:03,  5.71it/s]
Al
(中略)
Alpaca{h4sh_4lgor1thm_1s_b4s3d_0n_MD5_4nd_keccak
 79%|██████████████████▉     | 74/94 [00:15<00:04,  4.92it/s]
 98%|███████████████████████▍| 92/94 [00:17<00:00,  4.97it/s]
Alpaca{h4sh_4lgor1thm_1s_b4s3d_0n_MD5_4nd_keccak}
 98%|███████████████████████▍| 92/94 [00:17<00:00,  5.14it/s]
./solve.py  565.53s user 156.54s system 133% cpu 9:01.32 total
$

10分弱の実行で、フラグを入手できました: Alpaca{h4sh_4lgor1thm_1s_b4s3d_0n_MD5_4nd_keccak}

フラグによるとupdate関数の実装は、MD5やKeccak(本記事記述中に調べるとSHA-3の別名らしい？)を元にした処理のようです。

感想

Revジャンルなので頑張りましたが難しかったです！今回は1問目から難しめに感じました。
2問目に5時間ほど取り組んでいましたが、残念ながら解けませんでした。
- シェルコード内容を都度改変していく内容で、シェルコード内容を都度ダンプすることはできました。それでも全体として何をしているか解明できず、頭を唸らせているうちに終了時刻を迎えました……。

プログラム系統備忘録ブログ

記事中のコードは自己責任の下でご自由にどうぞ。

AlpacaHack Round 4 (Rev) write-up