Seed Me

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

  1. 数値の入力を受け付ける。
  2. 入力された数値をシードとして、Random オブジェクトを生成する。
  3. 以下を16回繰り返す。
    1. nextFloat メソッドを用いて、乱数を 03777 回 (2047回) 生成する。
    2. nextFloat メソッドを用いて乱数を生成し、その値が 7.331f*.1337f 以上かをチェックする。
  4. 16回全てでチェックの結果がyesなら、flag.txt の内容を出力する。

nextFloat メソッドは、next(24) / ((float)(1 << 24)) を返す。
next メソッドは、seed を (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1) に更新し、seed の上位ビットを返す。
このことから、nextFloat メソッドの返り値が 7.331f*.1337f 以上となるためには、更新後の seed の値が 16444268 << 24 以上になればいいことがわかる。
そして、16回のチェックを通るためには、最初のチェック時およびその後15回のチェック時においてこの条件を満たすことが必要となる。
そこで、条件を満たす seed の値のうち、その後15回のチェック時においても条件を満たすものを全探索することにした。

ここで、最初の seed の値を a、b = 0x5DEECE66, c = 0xB として、最初の数回の乱数生成の様子を見てみると、以下のようになる。

Information to connect to a TCP server, a program Main.java, and text files Dockerfile and flag.txt were given.
What Main.java does is:

  1. Accept an input of a number.
  2. Create an object of Random using the entered value as the seed.
  3. Repeat this 16 times:
    1. Generate random numbers via nextFloat method 03777 (2047) times.
    2. Generate a random number via nextFloat method and check if the value is 7.331f*.1337f or more.
  4. Output the contents of flag.txt if all of the 16 checks resulted in "yes".

The nextFloat method returns next(24) / ((float)(1 << 24)).
The next method updates the value of seed to (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1) and returns the upper bits of seed.
Therefore, we can say that the value of seed should be 16444268 << 24 or greater to make the return value of nextFloat not less than 7.331f*.1337f.
Moreover, to pass all of the 16 checks, this condition has to be satisfied in the first check and the 15 checks after that.
Based on this, I decided to perform a brute-force search for the value of seed that satisfies the condition and satisfies the condition at the upcoming 15 checks.

By the way, calling the initial value of seed as a and defining b = 0x5DEECE66, c = 0xB, this is how the random number is generated in the first few rounds:

0: a 1: a * b + c 2: (a * b + c) * b + c = a * b^2 + c * b + c 3: ((a * b + c) * b + c) * b + c = a * b^3 + c * b^2 + c * b + c

したがって、n回後の seed の値は a*b^n + c * b^(n-1) + ... + c * b + c となる。
ここで、b^n および c * b^(n-1) + ... + c * b + c の値はn (乱数を何個生成するか) のみに依存し、 a にはよらない。
以下のプログラムを用い、n = 2048 におけるこれらの値を求めた。

This implies that the value of seed after n rounds will be a*b^n + c * b^(n-1) + ... + c * b + c.
Note that the value of b^n and c * b^(n-1) + ... + c * b + c depend only on n (the number of random numbers to generate) and don't depend on a.
I used this program to obtain the value at n = 2048:

calc_the_seq.py

その結果、2048回の乱数生成による seed の変化を、seed * 0xba17a0bd2001 + 0xe5b38f05c800 という1回の計算で求めることができることがわかった。

これを用い、以下のプログラムで条件を満たす seed の全探索を行った。

As a result, I found that the change in seed in the 2048 rounds of random number generation can be calculated by this single calculation: seed * 0xba17a0bd2001 + 0xe5b38f05c800.

Using this formula, I created this program to brute-force search for seed that satisfies the condition.

bruteforce_ocl.c

このプログラムはOpenCLを用いており、ビルド時は以下の初期化プログラムと組み合わせる。

OpenCL is used for this program and this program should be linked with this initialization program to build:

ocl-test/common.c at master · mikecat/ocl-test · GitHub

その結果、10分ほどで条件を満たす最初の seed の値 275901075310942 が得られた。

次に、この値から乱数を逆算し、入力するべき値を求める。
シードを指定したRandomクラスのコンストラクタは setSeed メソッドを呼び出し、 setSeed メソッドは引数に 0x5DEECE66D をxorした値を seed に設定する。
従って、入力するべき値は、これまで求めた値を利用して以下のプログラムで求めることができる。

As a result, it took about 10 minutes before emitting the first satisfying value of seed: 275901075310942.

What to do next is reversing the random number generation from this value to obtaine the value to input.
The constructor of Random with specifying seed calls the setSeed method. Then, the setSeed method sets the value of seed to the argument with exclusive-ored with 0x5DEECE66D.
Therefore, the value to input can be obtained using this program with values obtained before:

get_input.py

結果、272526698751795 を入力すればいいことがわかった。

この値を入力するためにサーバに接続すると、以下が出力された。

The program told me that what to enter is 272526698751795.

Connecting to the server to enter this value, this was printed:

== proof-of-work: enabled == please solve a pow first You can run the solver with: python3 <(curl -sSL https://goo.gle/kctf-pow) solve s.ADQ6.AACP774m5ETUXNMvN9rAV11m =================== Solution?

出力されたURLから curl でダウンロードすると、別のURLが書かれたHTMLデータが得られた。
このURLから curl でダウンロードすると、プログラム pow.py が得られた。
このプログラムを用い、pow.py solve s.ADQ6.AACP774m5ETUXNMvN9rAV11m を実行すると、約2分後出力が得られた。
この出力のうち Solution: の後の部分をサーバに送信すると、Main.java の実行が開始されたようだった。
ここで、先ほど求めた値 272526698751795 を入力すると、flagが得られた。

Downloading data from the URL in the output via curl yielded HTML data that contains another URL.
Downloading data from the new URL via curl yielded a program pow.py.
I executed pow.py solve s.ADQ6.AACP774m5ETUXNMvN9rAV11m using this program. It emitted some output after about 2 minutes.
I sent the part after Solution: of this output to the server. Then, Main.java looked launched.
I entered the value 272526698751795, which I calculated before, and obtained the flag.

pbctf{intended_is_LLL_with_branch_and_bound_9ad09becbc4c7685}

pbctf 2021