[日本語] [English]

gipfel

TCPサーバの接続情報と、サーバのプログラム vuln.py およびテキストファイル pow-solver.cpp が与えられた。
vuln.py は、以下の処理をするものだった。

  1. 素数の定数 q を用意する。
  2. 0以上10**6未満の乱数 password を生成する。
  3. 以下を3回繰り返す。
    1. password のSHA-256値を整数として g に格納する。
    2. 40の倍数である乱数 privA を生成する。
    3. gprivA 乗して q で割った余り pubA を求め、出力する。
    4. 1より大きく q 未満の整数 pubB を読み込む。
    5. pubBprivA 乗して q で割った余り shared を求める。
    6. gshared**3 乗して q で割った余り verA を求め、出力する。
    7. 整数 verB を読み込む。
    8. 読み込んだ整数 verBgshared**5 乗して q で割った余りと一致した場合、以下の処理を行う。
      1. password の十進数表現、"\0"shared の十進数表現をこの順番で連結した文字列のSHA-256値 key を求める。
      2. ファイル flag.txt の内容を読み込み、flag に格納する。
      3. flag の内容を、鍵 key とnonce b'' を用いて AES.MODE_CTR で暗号化し、出力する。

この処理は、BuckeyeCTF 2021 の Key exchange 2 に似ているようだった。

今回の定数 q を小さい値で割って余りをチェックした結果、4で割ると余りが1になった。
そこで、以下のコードをSage Cell Serverに入力し、mod q における1の4乗根を求めた。

n=0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5

F = IntegerModRing(n)
print(F(1).nth_root(4, all=True))

その結果、以下の4乗根が求まった。

1
21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331785823395914742996088304304555885698180826189819001027801777676309939507353142989960235700998476739551309053606306431
21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331790513011401920585195969087140918256569620608732530453375717414098148438918130733211117668960801178110820764957628836
4689615487177589107664782585032558388794418913529425573939737788208931564987743250881967962324438559511711351322406

求めた4乗根のうち1でないもの(どれか1個)を pubB として入力すると、privA は40の倍数、すなわち4の倍数なので、shared は必ず1になる。
すると、1を3乗しても1なので、g の1乗、すなわち g の値が verA として出力される。
同様に gshared**5 乗も g になるので、verB には出力された verA の値をそのまま入力するとよい。

Tera Termで指定のサーバに接続すると、以下の出力がされた。

please give S such that sha256(unhex("ee82fd8332a66055" + S)) ends with 32 zero bits (see pow-solver.cpp).

そこで、この問題を解くため、以下のプログラムを作成した。

get_S_mp.py

このプログラムを12並列に設定して実行した結果、5分程度でSが求まった。
(なお、今回短時間で求まったのは解が探索範囲の最初の方にあったからであり、求まるまで30分程度かかることもありそうである)
求まった b88c3eee をサーバに送信すると、vuln.py が実行されたようで、以下のデータ (送信したデータを含む) が得られた。

pubA = 0x37ee2185ff6b6beb6e8a42dc609889f47e232d7884669644fdd87f2fabe836b81b7efa8e9f82a8beb98e833f2c43be8bfd10d7c7aa15fe32332c715e299cda900a2588c35b27b9598814479ffb8df9b8506fea70904c96cb6bb9967f13b8b68
21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331785823395914742996088304304555885698180826189819001027801777676309939507353142989960235700998476739551309053606306431
verA = 0x91defc8d7a3f9fc49d54795b661d82cd45baa118fc14295c90896353c34deee5
0x91defc8d7a3f9fc49d54795b661d82cd45baa118fc14295c90896353c34deee5
flag: 634387009c90e6fc151e73b8296c439176bfb5a00ab1307775ac46637bfdddc03e14283dd65b66b5

verA の値(0xは除く)が password のSHA-256値になっているので、これをファイル hashcat_target.txt に保存し、 以下のようにhashcatを用いて password の値を求めた。

hashcat -m 1400 -a 3 -w 4 D:\...\hashcat_target.txt --increment ?d?d?d?d?d?d?d

得られた password の値 919081 と、shared の値 1 を用い、以下のようにCyberChefを用いて key を求めた。

Find / Replace, SHA2 - CyberChef

この key を用いて flag を復号しようとすると、16バイトのIVを要求された。
IVとして全部ゼロのデータを入力すると、flagが得られた。

AES Decrypt - CyberChef

hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}

writeup by MikeCAT

hxp CTF 2021