Substitution Cipher II

プログラム substitution-cipher-ii.sage とその出力 output.txt が与えられた。
プログラムは、以下の処理をするものだった。

  1. 使う可能性がある文字を集めた文字列 CHARSET を用意する
  2. f = P.random_element(6) を用意する
  3. ./flag.txt の内容を読み込み、FLAG とする
  4. FLAGの各文字について、 CHARSET 内の文字の位置を用いて f.substitute で変換を行う
  5. 変換結果の文字列を出力する

まず、Sage Cell Server において、f の内容を出力するなどの実験を行った。
その結果、f は x の6次式になり、計算結果は CHARSET の長さで割った余りになりそうなことがわかった。

これを踏まえ、FLAG は DUCTF{ で始まって } で終わると仮定した上で、 変換結果が条件を満たす f をZ3で求めようとする以下のプログラムを書き、実行した。
しかし、しばらく待っても答えは出なかった。

A program substitution-cipher-ii.sage and its output output.txt were given.
What the program does is:

  1. Prepare a string that contains all characters that may be used CHARSET.
  2. Prepare f = P.random_element(6).
  3. Read the contents of ./flag.txt and store it to FLAG.
  4. Convert each characters in FLAG using the position of the character in CHARSET and f.substitute.
  5. Output the resulting string.

Firstly I did some experiments including printing f on Sage Cell Server.
As a result, I found that f is a sixth degree polynomial of x, and that the result of calculation is the remainder divided by the length of CHARSET.

Based on these findings, and an assumption that FLAG begins with DUCTF{ and ends with }, I created this program to obtain f using Z3 that realizes the conversion, and executed that.
However, the program didn't give me an answer in a reasonable time.

solve.py

ここで、CHARSETの長さは47であり、計算はこの長さで余りをとるので、 6次式 f の各係数は0～46のみを考えればよく、 考えられるパターン数は47**7 = 506,623,120,463通りである。
1秒あたり10**8パターン程度試せると仮定すると、1～2時間程度で全通り試せると見積もることができ、これは十分短いと考えられる。
そこで、以下のプログラムで f を全探索することにした。

Considering that the length of CHARSET is 47, and that the calculation is done with dividing by this length and taking the remainder, we should think only values between 0 and 46 as each elements of the sixth degree polynomial f.
This means that the number of all possible putterns is 47**7 = 506,623,120,463.
Assuming that we can try about 10**8 putterns per second, we can estimate that the brute-force searching will take about 1 or 2 hours, and this is short enough.
Therefore I decided to perform a brute-force search f using this program:

bruteforce.c

その結果、10分程度で探索が終わり、f = 1 + 27*x + 28*x^2 + 9*x^3 + 40*x^4 + 15*x^5 + 41*x^6 の1通りが見つかった。
この係数を指定し、以下のプログラムで逆変換テーブルを作ってもとの FLAG の内容を求めようとした。

As a result, the search completed in about 10 minutes and only one result f = 1 + 27*x + 28*x^2 + 9*x^3 + 40*x^4 + 15*x^5 + 41*x^6 was found.
Then, I tried to obtain the value of FLAG with this coefficients using this program to create an inversion table:

solve2.py

係数は以下のように指定する。

How to specify the coefficients is:

solve2.py 1 27 28 9 40 15 41

その結果、FLAG は DUCTF{go0d_0l'_l4gr4fg3} と求まったが、これはIncorrectだった。
ただし、いくつかの文字については逆変換テーブルの衝突が報告されており、特にこの結果に使われている文字については以下の可能性があった。

f を n に変えてみたところ、Correctとなり、flagが得られた。

The answer was that the FLAG is DUCTF{go0d_0l'_l4gr4fg3}, but this was judged as Incorrect.
Now note that some collisions in the inversion table were found. Here are the other possibilities about the characters used here:

I tried changing f to n. It was judges as Correct and I obtained the flag.

DUCTF{go0d_0l'_l4gr4ng3}

DownUnderCTF 2021