TCPサーバの接続情報と、サーバのプログラム vuln.py
およびテキストファイル pow-solver.cpp
が与えられた。
vuln.py
は、以下の処理をするものだった。
q
を用意する。10**6
未満の乱数 password
を生成する。password
のSHA-256値を整数として g
に格納する。privA
を生成する。g
を privA
乗して q
で割った余り pubA
を求め、出力する。q
未満の整数 pubB
を読み込む。pubB
を privA
乗して q
で割った余り shared
を求める。g
を shared**3
乗して q
で割った余り verA
を求め、出力する。verB
を読み込む。verB
が g
を shared**5
乗して q
で割った余りと一致した場合、以下の処理を行う。
password
の十進数表現、"\0"
、shared
の十進数表現をこの順番で連結した文字列のSHA-256値 key
を求める。flag.txt
の内容を読み込み、flag
に格納する。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
として出力される。
同様に g
の shared**5
乗も g
になるので、verB
には出力された verA
の値をそのまま入力するとよい。
Tera Termで指定のサーバに接続すると、以下の出力がされた。
please give S such that sha256(unhex("ee82fd8332a66055" + S)) ends with 32 zero bits (see pow-solver.cpp).
そこで、この問題を解くため、以下のプログラムを作成した。
このプログラムを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が得られた。
writeup by MikeCAT