はじめに

2022年4月8日に Plaid CTF 2022 が開催されました。開催中はほとんど時間が取れず、どんな問題が出たのかだけ見ておこうと思いざっと眺めていたのですが、その中で Secret Token Formulating Utility という Rev 問（6 solves, 333 points）が目にとまりました。とても読ためのではない複雑な ELF バイナリの解析で、競技中 1時間ほど眺めましたが取っ掛かりすらつかめず、これは人類にはまだ早いのではとすら思ったのですが、最終的に 6 チームも解いていてびっくりしました。

今までチャレンジした大抵の Rev 問は、IDA を頑張って読んだり、gdb でブレークポイントを張りながら解析すれば解けることが多く、どんなに複雑怪奇なバイナリでも、競技である以上取っ掛かりを用意してくれているのですが、今回は今までのようなアプローチではとても手に負えそうもありません。後で誰かが解説してくれないかなという淡い期待もあったのですが、公開された Writeup はソルバーのみでリバエンに関する説明は見当たりませんでした。どうやったら解けるのか気になって仕方がなかったので、後日改めてこの問題にじっくりチャレンジしてみましたが、色々と今後にも応用が利きそうな学びが多かったので記事にしました。

どんな問題？

問題文はこちらです。ELF バイナリと接続先が用意されています。バイナリはこちらで公開されています。

とりあえず ELF を実行してみると、異常終了します。なにやら Rust で作成されたようなバイナリであることが分かります。

# ./secret-token-formulating-utility
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/main.rs:145644:76
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Aborted (core dumped)

引数に数値を入れると、何かしらの演算結果が出力されます。この値は入力に応じて固定です。ただし、1000000000 などの大きな数値を指定すると、計算に時間がかかるようで結果が返ってきません。

# ./secret-token-formulating-utility 1000
5563761278022392369

サーバーに接続すると大きな値がチャレンジとして降ってきますので、この問題は指定された数値に対する演算結果（トークン）を効率良く計算して送信すれば良いことが分かります。

IDA で開いてみる

IDA でバイナリを開いて演算処理を解析しようとしてみますが、中を見て絶望します。途中でサイズが大きすぎてグラフビューが開けないというエラーも出ていますね。gdb で追跡したりもしてみたのですが、どこから手を付けて良いのか全く想像できません。

とりあえず IDA で分かったのは、main 関数のこのあたりに client::WasmModule::func_174::h36e0bfd11f57c262、client::WasmModule::func_53::h9761402b65816a8e という 2 つの関数があることと、

client::WasmModule::func_53::h9761402b65816a8e のこのあたりに client::WasmModule::func_15::he5b8622441173dc6 という関数があって、この辺りが演算に関係しそうなことが分かりました。ただし他にも関数はたくさんあって、この問題の解答には必要ないような気もするのですが、現時点では確証が持てません。あと Rust だと思ってたバイナリですが何故か関数名に Wasm という文字が見えます。

演算処理の一番の肝は client::WasmModule::func_15::he5b8622441173dc6 な気がするのですが、デコンパイル結果が 5000 行あって読めません。このような一見手に負えなさそうなバイナリは過去にも何度か遭遇しましたが、今までのケースでは本質的な処理はコードの一部のブロックだけでその部分を見つけて解析すれば良いことが多かったりして何とかなりました。今回はそのような雰囲気を感じません。気のせいで合って欲しいのですが、でもやっぱり変換処理はこの関数全体で行っているとしか思えません。これを読めと・・・

動的解析をもとに通過したパスを把握する

ここまでで分かった難しいポイントは、

関数が大量にあってどこを読めば良いか（func_15 で良いのか）確証がないこと
関数の CFG が複雑過ぎてまともに読めないこと

の 2点です。

読むべき関数を確定させる

まずは func_15 を読めば良いことを確定させたいと思います。処理はとても長いのですが、入力に依存する命令を探してみます。以前作成した pintr というトレーサーを使用して、実行時のログを記録したあと、IDA にマッピングするスクリプトを書いてみました。

pintr は以下のようにログを取得します。合計 3回ログを取得して、最初の 2回は入力値 1で、最後の 1回は入力値 2でログを取ります。

# pin -t pintr.so -Td -Ti secret-token-formulating-utility -Tr _ZN6client4main17h556cebc31b99593eE -Tr _ZN6client10WasmModule8func_17417h36e0bfd11f57c262E -Tr _ZN6client10WasmModule7func_5317h9761402b65816a8eE -Tr _ZN6client10WasmModule7func_1517he5b8622441173dc6E -- ./secret-token-formulating-utility 1
# pin -t pintr.so -Td -Ti secret-token-formulating-utility -Tr _ZN6client4main17h556cebc31b99593eE -Tr _ZN6client10WasmModule8func_17417h36e0bfd11f57c262E -Tr _ZN6client10WasmModule7func_5317h9761402b65816a8eE -Tr _ZN6client10WasmModule7func_1517he5b8622441173dc6E -- ./secret-token-formulating-utility 1
# pin -t pintr.so -Td -Ti secret-token-formulating-utility -Tr _ZN6client4main17h556cebc31b99593eE -Tr _ZN6client10WasmModule8func_17417h36e0bfd11f57c262E -Tr _ZN6client10WasmModule7func_5317h9761402b65816a8eE -Tr _ZN6client10WasmModule7func_1517he5b8622441173dc6E -- ./secret-token-formulating-utility 2

取得したログファイルを IDA にマッピングしてみます。3回とも実行結果が同じであった命令を黄色、3回目の実行だけ実行結果が変化した命令を赤色、全て結果が異なる命令を灰色で塗っています。ついでに実行時の値もコメントとして載せてみました。とても長い main 関数ですが、入力値に依存した（赤色の）命令はここだけで、func_53 で入力値 1 に対する結果 0x173d73ea5e3d9e45（=1674622086892330565）を得ていることがすぐに分かります。

同様に func_53 でも赤色の部分は少なく、func_15 の前後で同様に入力値 1 に対する結果 0x173d73ea5e3d9e45 を得ています。この結果から、func_15 を解析すれば良さそうなことが確信できます。

複雑な CFG を読み解く

CFG にはおびただしい数の分岐が含まれていますが、多くはエラーに関する処理に見えるので、このあたりは本質的でないような気がします。先ほどの実行結果で実行されなかった命令は白色のままになりますが、コードの何割かは通過しなかったことが分かります。

次に、以下のような実際は分岐しないジャンプを簡略化してみます。先ほどのスクリプトを改変して、以下のような分岐しない jcc 命令に jmp か nop のパッチを当てる機能を追加しました。

するとグラフビューは多少簡略化され、デコンパイル結果の方は関係のない処理をごっそりと落とすことができ、600 行以下まで削減できました。

グラフビューの方ももっと見やすくしたいです。例えば、以下のように条件分岐命令を削除したため到達し得なくなったブロックは Undefine (U) を押すとグラフから削除することができます。

CFG はさらに整理されて、以下のようになりました。縦に長いですが、初期化、ループ、後処理、という極めてきれいな構造であることが分かります。

ここで一度、パッチを適用したバイナリを -patched という名前で保存します。実行結果が変わらないことを確認できると、ここまで間違えていないことが分かって安心です。

# ./secret-token-formulating-utility-patched 1000
5563761278022392369

無関係なコードを取り除く

構造が単純化されたとはいえ、各ブロックには大量の四則演算が並んでいて、まだまだコードは複雑です。

このコードを変更すると結果がどのように変化するか確かめるため、Patching というプラグインを使用して、バイナリを改変しながら実行してみます。実は少し実験すると、このコードの多くは無関係なコードであることが分かります。ここから呼ばれているいくつかの関数も全て無視できます。

どの行が必要でどの行が不要なのかは一見して分からないので、実験して進めるしかありません。何百回と命令を nop に置き換えて、パッチを適用して、実行して試す、というルーティーンを繰り返しながら、可能な限りバイナリを簡略化していきます。そこで、nop-filter と easy-patching という 2つのプラグインを作成して、nop 命令を非表示にしながらショートカットで小気味よく作業を進められるよう工夫しました。作業自体は地道ですが、途中結果を確かめながら手戻りなく安心して進められるのは大きく、精神的にはきつくありませんでした。

IDA で最終的に得られたコードは以下のようになります。

void __fastcall func_15(__int64 *a1, int a2, signed int a3, __int64 a4)
{
    int v8; // r9d
    __int64 v9; // rsi
    unsigned __int64 v10; // r8
    __int64 v11; // r10
    unsigned __int64 v12; // rbp
    int v13; // edi
    int v14; // edi
    int v15; // ecx
    int v16; // eax
    int v17; // ecx
    int v18; // edi
    int v19; // ecx
    int v20; // edi
    int v21; // ecx
    __int64 v22; // r9
    unsigned __int64 v23; // rdi
    __int64 v24; // rdi
    int v25; // ecx
    unsigned __int64 v26; // rax
    __int64 v27; // rdi
    int v28; // ecx
    __int64 v29; // rax
    int v30; // ecx
    __int64 v31; // rax
    int v32; // ecx
    int v33; // esi
    int v34; // r10d
    int v35; // edx
    int v36; // r9d
    __int64 x20; // r8
    unsigned __int64 v38; // rcx
    __int64 v39; // [rsp+30h] [rbp-338h]
    unsigned __int64 v40; // [rsp+38h] [rbp-330h]
    int x10; // [rsp+38h] [rbp-330h]
    int x10a; // [rsp+38h] [rbp-330h]
    int v43; // [rsp+68h] [rbp-300h]
    unsigned __int64 x11; // [rsp+78h] [rbp-2F0h]
    unsigned __int64 v45; // [rsp+80h] [rbp-2E8h]
    __int64 x17; // [rsp+80h] [rbp-2E8h]
    unsigned __int64 x12; // [rsp+88h] [rbp-2E0h]
    unsigned __int64 v48; // [rsp+90h] [rbp-2D8h]
    unsigned int x01; // [rsp+90h] [rbp-2D8h]
    unsigned __int64 x16; // [rsp+A8h] [rbp-2C0h]
    __int64 x16_8; // [rsp+A8h] [rbp-2C0h]
    unsigned __int64 x14; // [rsp+B0h] [rbp-2B8h]
    unsigned __int64 x13; // [rsp+B8h] [rbp-2B0h]
    __int64 x18; // [rsp+E0h] [rbp-288h]
    unsigned __int64 x15; // [rsp+E8h] [rbp-280h]
    __int64 v56; // [rsp+F8h] [rbp-270h]
    __int64 x09; // [rsp+100h] [rbp-268h]
    __int64 x08; // [rsp+108h] [rbp-260h]
    __int64 x07; // [rsp+110h] [rbp-258h]
    unsigned __int64 x06; // [rsp+118h] [rbp-250h]
    unsigned __int64 x05; // [rsp+120h] [rbp-248h]
    __int64 x04; // [rsp+128h] [rbp-240h]
    __int64 x03; // [rsp+130h] [rbp-238h]
    unsigned __int64 x02_8; // [rsp+198h] [rbp-1D0h]
    __int64 v65; // [rsp+2D0h] [rbp-98h]
    __int64 v66; // [rsp+2D8h] [rbp-90h]
    __int64 x19; // [rsp+2E0h] [rbp-88h]
    __int64 v68; // [rsp+2E8h] [rbp-80h]
    __int64 v69; // [rsp+2F0h] [rbp-78h]
    __int64 v70; // [rsp+2F8h] [rbp-70h]
    __int64 v71; // [rsp+300h] [rbp-68h]

    client::WasmModule::func_16::h7dc42ea2a69f8ef2(a1, 0xFFF88, a3, 0x100000u, 1u);
    *(_QWORD *)(*a1 + a3 + 4LL) = 0LL;
    *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) = 0xFFF8C;
    *(_QWORD *)(*a1 + (int)(16 * *(_DWORD *)(*a1 + 0xFFF88) + 32 + a1[2])) = 0x10000000000000LL;
    v48 = 0xF08D70B3923D1570LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048568) = 0xF08D70B3923D1570LL;
    x02_8 = 0xA1CE9B3BE90D1802LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048552) = 0xA1CE9B3BE90D1802LL;
    x03 = 0x7953163B864ECA95LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048536) = 0x7953163B864ECA95LL;
    x04 = 0x2FC1C5CAD1DBB675LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048520) = 0x2FC1C5CAD1DBB675LL;
    x05 = 0x94AEDB33A79ACDE6LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048504) = 0x94AEDB33A79ACDE6LL;
    x06 = 0xF4BE5D2A92C9C93CLL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048488) = 0xF4BE5D2A92C9C93CLL;
    x07 = 0x29C91EB9CAB7C67LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048472) = 0x29C91EB9CAB7C67LL;
    x08 = 0x1D33F3FCE0737437LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048456) = 0x1D33F3FCE0737437LL;
    v8 = *(_DWORD *)(*a1 + a3);
    x09 = 0x7C59A1115F898C02LL;
    *(_QWORD *)(*a1 + v8 + *(_DWORD *)(*a1 + v8 + 0xFFFD8) + 0xFFF78) = 0x7C59A1115F898C02LL;
    *(_QWORD *)(*a1 + v8 + *(_DWORD *)(*a1 + v8 + 0xFFFD8) + 0xFFFF0) = 0x2DEF3A950A3DF2EELL;
    v40 = 0x88C7AF20A872B40FLL;
    *(_QWORD *)(*a1 + v8 + *(_DWORD *)(*a1 + v8 + 0xFFFD8) + 0xFFFE0) = 0x88C7AF20A872B40FLL;
    x11 = 0x1E948B96DC61489LL;
    *(_QWORD *)(*a1 + v8 + *(_DWORD *)(*a1 + v8 + 0xFFFD8) + 0xFFFD0) = 0x1E948B96DC61489LL;
    x12 = 0x4707916C3F4F882CLL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048512) = 0x4707916C3F4F882CLL;
    x13 = 0x4A901FC9B5E1F7EFLL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 0xFFFB0) = 0x4A901FC9B5E1F7EFLL;
    x14 = 0x12DA654BC29E00CLL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 0xFFFA0) = 0x12DA654BC29E00CLL;
    x15 = 0x405943E2C746EF8ALL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 0xFFF90) = 0x405943E2C746EF8ALL;
    x16 = 0x2CE572B38B540058LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 0xFFF80) = 0x2CE572B38B540058LL;
    v45 = 0xBDEF1E03F8A42971LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048432) = 0xBDEF1E03F8A42971LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048424) = 0xDA17EDC974CBF88BLL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048416) = 0x5BA2B30F33009E3LL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 1048400) = 0xAB1C846768A45CEDLL;
    *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 0xFFF58) = 0x666659374175332CLL;
    v9 = *a1;
    v43 = *(_DWORD *)(*a1 + a3);
    v10 = 0x818A2AA968E6F32LL;
    v56 = 3186564611LL;
    v11 = 0x709A25560524A886LL;
    v12 = 0x2DEF3A950A3DF2EELL;
    while ( 1 )
    {
        v13 = *(_DWORD *)(v9 + (unsigned int)(v43 + 0xFFFD8));
        *(_QWORD *)(v9 + (unsigned int)(v43 + v13 + 0xFFF40)) = v11;
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v13 + 0xFFF48) = 0x646B9980 * v56
                                                                 - 0xC7F3C1B69F8FE67LL * v45
                                                                 + 0x646B9980E07FBDE6LL * x09
                                                                 + HIDWORD(v10);
        v14 = *(_DWORD *)(*a1 + a3);
        v15 = *(_DWORD *)(*a1 + (unsigned int)(v14 + 0xFFFD8));
        *(_QWORD *)(*a1 + v14 + v15 + 0xFFF30) = 565223972LL * (unsigned int)x16
                                               + ((0xD005C986LL * (unsigned int)x16 + 0x21B0A224 * HIDWORD(x16)) << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v15 + 1048376) = 0x6154BEC0CD734930LL * x16
                                                                 - 0x2FFA3679DE4F5DDCLL * x08
                                                                 + 0xD005C986 * HIDWORD(x16)
                                                                 + ((unsigned __int64)(0xD005C986LL * (unsigned int)x16
                                                                                     + 0x21B0A224 * HIDWORD(x16)) >> 32);
        v16 = *(_DWORD *)(*a1 + a3);
        v17 = *(_DWORD *)(*a1 + v16 + 0xFFFD8);
        *(_QWORD *)(*a1 + v16 + v17 + 0xFFF20) = 0x1AA38888LL * (unsigned int)x15
                                               + ((0xDED12B1LL * (unsigned int)x15 + 0x1AA38888 * HIDWORD(x15)) << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v17 + 0xFFF28) = 0x468F22365BD9E2EDLL * x15
                                                                 + 0xDED12B11AA38888LL * x07
                                                                 + 0xDED12B1 * HIDWORD(x15)
                                                                 + ((unsigned __int64)(0xDED12B1LL * (unsigned int)x15
                                                                                     + 0x1AA38888 * HIDWORD(x15)) >> 32);
        v18 = *(_DWORD *)(*a1 + a3);
        v19 = *(_DWORD *)(*a1 + (unsigned int)(v18 + 0xFFFD8));
        *(_QWORD *)(*a1 + v18 + v19 + 0xFFF10) = 1619620158LL * (unsigned int)x14
                                               + ((0x895DD3AALL * (unsigned int)x14 + 0x6089713E * HIDWORD(x14)) << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v19 + 1048344) = 0x603FFACC774E09F2LL * x14
                                                                 - 0x76A22C559F768EC2LL * x06
                                                                 + 0x895DD3AA * HIDWORD(x14)
                                                                 + ((unsigned __int64)(0x895DD3AALL * (unsigned int)x14
                                                                                     + 0x6089713E * HIDWORD(x14)) >> 32);
        v20 = *(_DWORD *)(*a1 + a3);
        v21 = *(_DWORD *)(*a1 + (unsigned int)(v20 + 0xFFFD8));
        v22 = v20 + v21 + 0xFFF00;
        v23 = 677938030LL * (unsigned int)x13 + 0xDEE04734 * HIDWORD(x13);
        *(_QWORD *)(*a1 + v22) = 0xDEE04734LL * (unsigned int)x13 + (v23 << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v21 + 0xFFF08) = 0x7BB0FFD1D80FB321LL * x13
                                                                 + 0x2868836EDEE04734LL * x05
                                                                 + 0x2868836E * HIDWORD(x13)
                                                                 + HIDWORD(v23);
        v24 = *(_QWORD *)(*a1 + a3);
        v25 = *(_DWORD *)(*a1 + (unsigned int)(v24 + 0xFFFD8));
        v26 = 0xD313806DLL * (unsigned int)x12 + 2908783370u * HIDWORD(x12);
        *(_QWORD *)(*a1 + (int)v24 + v25 + 0xFFEF0) = 2908783370LL * (unsigned int)x12 + (v26 << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v25 + 0xFFEF8) = 0x92C103F01E7DDCA6LL * x12
                                                                 - 0x2CEC7F92529F7CF6LL * x04
                                                                 + 0xD313806D * HIDWORD(x12)
                                                                 + HIDWORD(v26);
        v27 = *(_QWORD *)(*a1 + a3);
        v28 = *(_DWORD *)(*a1 + (unsigned int)(v27 + 0xFFFD8));
        *(_QWORD *)(*a1 + (int)v27 + v28 + 0xFFEE0) = 0x2D6FD165LL * (unsigned int)x11
                                                    + ((0xF63D4B11LL * (unsigned int)x11 + 0x2D6FD165 * HIDWORD(x11)) << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v28 + 0xFFEE8) = 0xBA665904D9CE575BLL * x11
                                                                 - 0x9C2B4EED2902E9BLL * x03
                                                                 + 0xF63D4B11 * HIDWORD(x11)
                                                                 + ((unsigned __int64)(0xF63D4B11LL * (unsigned int)x11
                                                                                     + 0x2D6FD165 * HIDWORD(x11)) >> 32);
        v29 = *(_QWORD *)(*a1 + a3);
        v30 = *(_DWORD *)(*a1 + (int)v29 + 0xFFFD8);
        *(_QWORD *)(*a1 + (int)v29 + v30 + 0xFFED0) = 0x6CF43679LL * (unsigned int)v40
                                                    + ((0x4BDA5E34LL * (unsigned int)v40 + 0x6CF43679 * HIDWORD(v40)) << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v30 + 0xFFED8) = 0x3B8EFD66D9AB488ALL * v40
                                                                 + 0x4BDA5E346CF43679LL * x02_8
                                                                 + 0x4BDA5E34 * HIDWORD(v40)
                                                                 + ((unsigned __int64)(0x4BDA5E34LL * (unsigned int)v40
                                                                                     + 0x6CF43679 * HIDWORD(v40)) >> 32);
        v31 = *(_QWORD *)(*a1 + a3);
        v32 = *(_DWORD *)(*a1 + (int)v31 + 0xFFFD8);
        *(_QWORD *)(*a1 + (int)v31 + v32 + 0xFFEC0) = 0x6BF7691FLL * (unsigned int)v12
                                                    + ((0x1C4EF525LL * (unsigned int)v12 + 0x6BF7691F * HIDWORD(v12)) << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v32 + 0xFFEC8) = 0xAADC352D97357094LL * v12
                                                                 + 0x1C4EF5256BF7691FLL * v48
                                                                 + 0x1C4EF525 * HIDWORD(v12)
                                                                 + ((unsigned __int64)(0x1C4EF525LL * (unsigned int)v12
                                                                                     + 0x6BF7691F * HIDWORD(v12)) >> 32);
        v33 = 0;
        for ( x01 = 144; x01 > 3; x01 -= 4 )
        {
            v34 = *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8);
            *(_DWORD *)(*a1 + v34 + v33 + 0xFFF60) = *(_DWORD *)(*a1 + v34 + v33 + 0xFFF70);
            v33 += 4;
        }

        v39 = *a1;
        x10 = *(_DWORD *)(*a1 + a3);
        v35 = *(_DWORD *)(*a1 + x10 + 0xFFFD8);
        v12 = *(_QWORD *)(v39 + x10 + v35 + 0xFFEC0)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFED0)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFEE0)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFEF0)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFF00)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFF10)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFF20)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFF30)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFF50)
            + *(_QWORD *)(v39 + x10 + v35 + 0xFFF40);
        v48 = 0LL;
        *(_QWORD *)(v39 + x10 + v35 + 1048568) = 0LL;
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + *(_DWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + 0xFFFD8) + 0xFFFF0) = v12;
        if ( !--a4 )
            break;
        x10a = *(_DWORD *)(*a1 + a3);
        v36 = *(_DWORD *)(*a1 + (unsigned int)(x10a + 0xFFFD8));
        v71 = (unsigned int)(x10a + v36 + 0xFFFD0);
        v70 = (unsigned int)(x10a + v36 + 1048512);
        v69 = x10a + v36 + 0xFFFB0;
        v68 = x10a + v36 + 0xFFFA0;
        x17 = x10a + v36 + 0xFFF90;
        x16_8 = x10a + v36 + 0xFFF80;
        v66 = x10a + v36 + 0xFFF70;
        v65 = x10a + v36 + 0xFFF50;
        x20 = HIDWORD(*(_QWORD *)(*a1 + x10a + v36 + 0xFFF60));
        x19 = *(_QWORD *)(*a1 + x10a + v36 + 0xFFF60);
        x02_8 = *(_QWORD *)(*a1 + x10a + v36 + 1048552);
        x03 = *(_QWORD *)(*a1 + x10a + v36 + 1048536);
        x04 = *(_QWORD *)(*a1 + x10a + v36 + 1048520);
        x05 = *(_QWORD *)(*a1 + x10a + v36 + 1048504);
        x06 = *(_QWORD *)(*a1 + x10a + v36 + 1048488);
        x07 = *(_QWORD *)(*a1 + x10a + v36 + 1048472);
        x08 = *(_QWORD *)(*a1 + x10a + v36 + 1048456);
        x09 = *(_QWORD *)(*a1 + x10a + v36 + 1048440);
        x18 = *(_QWORD *)(*a1 + x10a + v36 + 1048424);
        v40 = *(_QWORD *)(*a1 + (unsigned int)(x10a + v36 + 0xFFFE0));
        x11 = *(_QWORD *)(*a1 + v71);
        x12 = *(_QWORD *)(*a1 + v70);
        x13 = *(_QWORD *)(*a1 + v69);
        x14 = *(_QWORD *)(*a1 + v68);
        x15 = *(_QWORD *)(*a1 + x17);
        x16 = *(_QWORD *)(*a1 + x16_8);
        v45 = *(_QWORD *)(*a1 + v66);
        v38 = 0xEC32EF2CLL * (unsigned int)x19 + 0xA379F6EFLL * x20;
        *(_QWORD *)(*a1 + v65) = 0xA379F6EFLL * (unsigned int)x19 + (v38 << 32);
        *(_QWORD *)(*a1 + *(_DWORD *)(*a1 + a3) + v36 + 0xFFF58) = 0x654006A05AD681D0LL * x19
                                                                 - 0x13CD10D35C860911LL * x18
                                                                 + 0xEC32EF2CLL * x20
                                                                 + HIDWORD(v38);
        v9 = *a1;
        v43 = *(_DWORD *)(*a1 + a3);
        v56 = HIDWORD(v45);
        v10 = 0x646B9980LL * (unsigned int)v45 + 0xE07FBDE6 * HIDWORD(v45);
        v11 = 0xE07FBDE6LL * (unsigned int)v45 + (v10 << 32);
    }
    *(_QWORD *)(*a1 + (unsigned int)(a2 + 8)) = v12;
}

ソースコードを整形する

抽象度が格段に上がって問題も小さくなったので、ここまでくれば最後まで行けそうな気がしてきます。先ほどのコードとにらめっこしながらポインタを配列化したり、規則性をヒントに順番を並べ替えたりしながら、コンパイル可能なコードに落とし込みます。コンパイルが成功したら、さらに実行結果を確かめながら簡略化します。最終的に以下のようなコードができあがります。

#include <iostream>

using namespace std;

unsigned long long func_15(unsigned long long count)
{
    unsigned long long buf[0x140];

    buf[0xA0]  = 0x05BA2B30F33009E3;
    buf[0xB0]  = 0xBDEF1E03F8A42971;
    buf[0xC0]  = 0x2CE572B38B540058;
    buf[0xD0]  = 0x405943E2C746EF8A;
    buf[0xE0]  = 0x012DA654BC29E00C;
    buf[0xF0]  = 0x4A901FC9B5E1F7EF;
    buf[0x100] = 0x4707916C3F4F882C;
    buf[0x110] = 0x01E948B96DC61489;
    buf[0x120] = 0x88C7AF20A872B40F;
    buf[0x130] = 0x2DEF3A950A3DF2EE;

    while (count--) {
        unsigned long long sum = 0;
        sum += 0xEC32EF2CA379F6EF * buf[0xA0];
        sum += 0x646B9980E07FBDE6 * buf[0xB0];
        sum += 0xD005C98621B0A224 * buf[0xC0];
        sum += 0x0DED12B11AA38888 * buf[0xD0];
        sum += 0x895DD3AA6089713E * buf[0xE0];
        sum += 0x2868836EDEE04734 * buf[0xF0];
        sum += 0xD313806DAD60830A * buf[0x100];
        sum += 0xF63D4B112D6FD165 * buf[0x110];
        sum += 0x4BDA5E346CF43679 * buf[0x120];
        sum += 0x1C4EF5256BF7691F * buf[0x130];

        for (int i = 0; i < 0x90; i += 4) {
            buf[i + 0xA0] = buf[i + 0xB0];
        }

        buf[0x130] = sum;
    }

    return buf[0x130];
}

int main()
{
    cout << func_15(1) << endl;
    cout << func_15(2) << endl;
    cout << func_15(3) << endl;
    cout << func_15(4) << endl;
    cout << func_15(1000) << endl;
    cout << func_15(1001) << endl;
}

ソルバーを作る

元のコードは入力値の回数だけ行列の積を求めるプログラムであることが分かります。ループの実行に時間がかかりますが、この部分をバイナリ法による乗算に変更して高速化することで、瞬時に結果を得ることができるようになります。

def matmul(A, B, m = 2**64):
    return [[sum([A[i][k]*B[k][j] for k in range(len(A[0]))]) % m for j in range(len(B[0]))] for i in range(len(A))]

def matpow(A, n):
    res = [[0] * i + [1] + [0] * (len(A)-1-i) for i in range(len(A))]
    for i in bin(n)[2:]:
        res = matmul(res, res)
        res = matmul(res, A) if i == "1" else res
    return res

def solve(chal_n):
    init = [[0x05BA2B30F33009E3], [0xBDEF1E03F8A42971], [0x2CE572B38B540058], [0x405943E2C746EF8A], [0x012DA654BC29E00C], [0x4A901FC9B5E1F7EF], [0x4707916C3F4F882C], [0x01E948B96DC61489], [0x88C7AF20A872B40F], [0x2DEF3A950A3DF2EE]]
    coef  = [[0] * i + [1] + [0] * (len(init)-1-i) for i in range(1, len(init))]
    coef += [[0xEC32EF2CA379F6EF, 0x646B9980E07FBDE6, 0xD005C98621B0A224, 0x0DED12B11AA38888, 0x895DD3AA6089713E, 0x2868836EDEE04734, 0xD313806DAD60830A, 0xF63D4B112D6FD165, 0x4BDA5E346CF43679, 0x1C4EF5256BF7691F]]

    mat = matmul(matpow(coef, chal_n) , init)

    return mat[-1][0]

# https://gist.github.com/6f70/a361d2bc587152969f53b67eff278050
assert(solve(6535016376403176904) == 8673357082917415256)
assert(solve(2467768788370249308) == 6321414967796127680)
assert(solve(15027414725812929110) == 11980021394058769251)
assert(solve(10702703014918823634) == 10162230340064657963)
assert(solve(9183860382523110997) == 9455870811549556796)
assert(solve(8012324378975699066) == 10956485569638790932)
assert(solve(5586890336573343448) == 4547398440643275083)
assert(solve(13004947060634539310) == 17761150032074348261)
assert(solve(13679116250745902676) == 18220244222682735531)
assert(solve(15455050481726328053) == 15334363509564988023)
print("OK")

おわりに

非常に難しい Rev 問だったのですが、練習ということもあって時間を気にせず、再現性の高い解法を模索しながら取り組んでみました。いくつかの副産物もできたので、使い勝手や応用の幅を広げていけるように洗練させていきたいです。

ちなみに、Writeup によるとフラグは PCTF{rust2wasm2rust2wasm2rust_15a0fc7fa673ae85} だったそうで、Rust → Wasm → Rust → Wasm → Rust と変換したバイナリであることが分かります。作りこんだ難読化ではなく既存の仕組みを難読化として適用した問題は独特の難しさがあるように思います。