maotiplication

TCPサーバの接続情報と、サーバのプログラムが与えられた。

サーバは与えられた条件を満たす文字列の置換規則を入力させるものだった。
redpwnCTF 2021 の the-substitution-game に続いてまたMarkov Algorithm Online的なやつである。
今回は停止規則にも対応しており、さらにMAOに近づいている。

the-substitution-game用のシミュレータが、 置換規則の区切り文字をテキストエディタで置換して入力することで今回も役立った。
3ステージをクリアすることでflagが得られた。

Information to connect to a TCP server and the server program were given.

The server asked us to enter a set of replacement rules for strings that satisfies the condition.
Something like Markov Algorithm Online again! (the previous one is "the-substitution-game" in redpwnCTF 2021)
This challenge supports the terminating rule and is closer to MAO.

My simulator was also helpful for this challenge with replacing the delimiter in the rules via a text editor.
I obtained the flag by solving 3 rounds.

Round 1

strellicが何回か繰り返された入力を、1個のjsgodに置換することが求められた。

the-substitution-game の Level 4に似ているが、 入力と出力が被らないのでこっちのほうが簡単である。
strellicが2個連続していたら1個にすることで減らしていき、最後に1個残ったstrellicをjsgodに置換すればよい。

The task was replacing strellic repeated some times to one jsgod.

This looked like the Level 4 in "the-substitution-game", but this challenge is easier because the output and input don't overlap.
This can be archived by reducing strellic by replacing two consecutive occurrences of that to one, and replacing the last one occurrence of strellic to jsgod.

Round_1.txt

Round 2

11010000^10111001を1101001にするというように、 与えられた2進数値をそのXORに置換することを求められた。

これは、以下のようにすることで実現できた。

  1. ^の左側の0や1を、別の記号(zとo)に変換し、右に送る
  2. 右の数値の右端に到達したら、このビットのXORをとり、さらに別の記号(-と+)に変換する
  3. XORを求め終わったら、-と+を0と1に戻す
  4. 先頭の余計な0を消去する
  5. 最後に^を消去し、完成させる

The task was replacing two binary numbers to their XOR like replacing 11010000^10111001 to 1101001.

I archived this in the following way:

  1. Replace the 0 or 1 at the left of ^ to another mark (z or o) and send it to the right.
  2. When it reaches at the right end of the right number, calculate XOR of the bit and express the result using another mark (- or +).
  3. After finishing calculating XOR, replace back - and + to 0 and 1.
  4. Remove the extra 0 at the top.
  5. Finally, remove the ^ to complete the replacement.

Round_2.txt

Round 3

1110111x10101011を100111101111101にするというように、 与えられた2進数値をその積に置換することを求められた。

これは、以下のようにすることで実現できた。

  1. 右の数値の右側に、答えと区切るための記号=と答え0を入れる。この処理の前の状態と区別するため、xを*に置換する。
  2. *の左の0や1を、別の記号(zやo)に変換して右に送る。
  3. zが右の数値の右端に着いたら、次の桁のために右の数値の右端に0を足して2倍にし、2に戻る。
  4. oが右の数値の右側に着いたら、次の桁のために右の数値の右端に0(次の手順に合わせて-で表現する)を足して2倍にし、文字Cを生成して数値のコピーを開始する。
  5. 文字Cをコピー位置の基準にし、右の数値の0と1をvと^で表現して答えに足すためにコピーする。 コピーした0や1は-や+に変換する。
  6. コピーが完了したら、-や+を0や1に戻し、Cを消去する。
  7. vや^で表現された右の数値のコピーを答えに加算する。
    1. コピーの右端のビットを、nやpで表現して右に送る。
    2. nやpが答えの右端に着いたら、加算を行い、結果をNかPで表現する。
    3. 繰り上がりがある場合は、文字cを生成し、答えのまだ加算処理をしていない部分に1を加算する。
    4. 加算処理が完了したら、NやPを0や1に戻す。
  8. 左の数値にまだビットが残っているなら、2に戻る。
  9. 左の数値の全ビットを処理したら、仕上げを行って答えを完成させる。
    1. 右の数値と*を消去する。
    2. 答えの先頭の余計な0を消去する。
    3. =を消去する。

The task was replacing two binary numbers to their product like replacing 1110111x10101011 to 100111101111101.

I archived this in the following way:

  1. Add a separator = and the (tentative) answer 0 to the right of the right number. To distiguish it from the status before this process, replace x with *.
  2. Send the 0 or 1 at the left of * to the right with replacing to another mark (z or o).
  3. When z arrives at the right end of the right number, append 0 at the right end of the right number to double the right number for process of next digit and go back to the step 2.
  4. When o arrives at the right end of the right number, append 0 (expressed as - for the next step) at the right end of the right number to double the right number for process of next digit. Then, put the mark C to start copying the number.
  5. Copy the right number for adding to the (tentative) answer. Express 0 and 1 as v and ^ for work. Use the mark C to decide where to copy from. After copying, replace 0 or 1 with - or +.
  6. When the copying completes, replace back - and + to 0 and 1 and remove C.
  7. Add the copied right number (expressed in v and ^) to the (tentative) answer.
    1. Send the rightmost bit of the copy to the right with expressing it as n or p.
    2. When n or p arrives at the right end, perform addition and express the result as N or P.
    3. When there is a carry, add a mark c and add one to the unprocessed part of the (tentative) answer.
    4. After finishing addition, replace back N and P to 0 and 1.
  8. Go back to the step 2 if there still be some bits in the left number.
  9. After processing all bits in the left number, finalize the replacement.
    1. Remove the right number and *.
    2. Remove extra 0 at the top.
    3. Remove =.

Round_3.txt

flag

corctf{qu1nt3c_w0u1d_b3_pr0ud}

corCTF 2021