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. g を privA 乗して q で割った余り pubA を求め、出力する。
    4. 1より大きく q 未満の整数 pubB を読み込む。
    5. pubB を privA 乗して q で割った余り shared を求める。
    6. g を shared**3 乗して q で割った余り verA を求め、出力する。
    7. 整数 verB を読み込む。
    8. 読み込んだ整数 verB が g を shared**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乗根を求めた。

Information for connecting to a TCP server, a program for the server vuln.py, and a text file pow-solver.cpp were given.
What vuln.py does is:

  1. Prepare a constant prime number q.
  2. Generate a non-negative random number password which is smaller than 10**6.
  3. Repeat this 3 times:
    1. Store the SHA-256 value of password to g as an integer.
    2. Generate a random number privA which is a multiple of 40.
    3. Calculate pubA which is g to the privA-th power modulo q and print that.
    4. Read an integer pubB which is greater than 1 and smaller than q.
    5. Calculate shared which is pubB to the privA-th power modulo q.
    6. Calculate verA which is g to the shared**3-th power modulo q and print that.
    7. Read an integer verB.
    8. If verB equals to g to the shared**5-th power modulo q, perform this:
      1. Calculate key which is a SHA-256 value of a string created by concatenating a decimal representation of password, "\0", and a decimal representation of shared in this order.
      2. Read the contents of a file flag.txt and store that to flag.
      3. Encrypt flag via AES.MODE_CTR using a key key and nonce b'' and print that.

This process looks similar to what was used in Key exchange 2 (BuckeyeCTF 2021).

I divided the constant value q with smaller values and checked the remainders. As a result, I found that the remainder becomes 1 when q is divided by 4.
Seeing this, I calculated the 4th root of 1 modulo q by putting this code to Sage Cell Server.

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

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

Here are the 4th roots:

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で指定のサーバに接続すると、以下の出力がされた。

Putting one of the 4th roots except for 1 as pubB will have shared become 1 because privA is a multiple of 40, which is a multiple of 4.
Then, since 1 to the 3rd power is 1, g to the 1st power, which is g, is printed as verA.
Since g to the shared**5-th power is also g, entering the printed value of verA as verB will work.

Connecting to the specified server via Tera Term, the server printed this:

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

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

Seeing this, I created this program to solve this question.

get_S_mp.py

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

I ran this program, setting it to use 12 processes, and it found the S after about 5 minutes.
(It looks like the answer was found early in this case because it was in the early part of the search space. It may take about 30 minutes to obtain S.)
After sending the answer b88c3eee to the server, it looked like vuln.py was executed and I obtained this data (including data I sent):

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

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

The value of verA (excluding 0x) is the SHA-256 value of password.
I saved the SHA-256 value to a file hashcat_target.txt and obtained the value of password via hashcat in this way:

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 を求めた。

Then, I obtained the value of key via CyberChef using the obtained value of password (919081) and the value of shared (1) in this way:

Find / Replace, SHA2 - CyberChef

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

CyberChef asked a 16-byte IV when I tried to decode flag using this key.
I obtained the flag by entering 16 byts of zero as IV.

AES Decrypt - CyberChef

hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}

hxp CTF 2021