Key exchange 2

TCPサーバの接続情報が与えられた。
Tera Termで接続してみると、以下のような出力がされた。

Informattion to connect to a TCP server was given.
Connecting to the server using Tera Term, the server printed things like this:

I'm going to send you the flag. However, I noticed that an FBI agent has been eavesdropping on my messages, so I'm going to send it to you in a way that ONLY YOU can decrypt the flag. p = 12251795882968515335720230660073746659413869760924025221649852208035051237856708925781912778413121581923338535504285363717654276804327121718065343894161577 g = 5 Can you still get the shared secret without my public key A? Give me your public key B:

これは、Key exchangeと同様の処理を、Aを出力せずに行っていると予想した。
そうだとすれば、shared_secretの値を求めることができれば暗号化の鍵を求めることができるはずである。

Key exchange においては、shared_secretは入力されたBの値をa乗してpで割った余りをとることで作られる。
ということは、もし1以外に mod p における1の3乗根が存在すれば、 その数をBとして入力すると、shared_secretはB、Bの2乗、1のどれかになるはずである。

先ほどのサーバの出力の例について、以下のようにしてSage Cell Serverを用いて1の3乗根を求めた。
pの値によっては1以外の3乗根が求まらないことがあったが、何回か接続し直すと1以外の3乗根が求まるpの値になった。

I guessed that this is doing a process like one done in Key exchange without printing the value of A.
Assuming that, we can get the encryption key by obtaining the value of shared_secret.

In "Key exchange", shared_secret is B to the a-th power modulo p.
Therefore, if the 3rd root of 1 modulo p other than 1 exists, using the value as B will make shared_secret one of B, the square of B, or 1.

Regarding the example of the output from the server, I used Sage Cell Server to obtaine the 3rd root of 1.
There were no 3rd roots other than 1 for some value of p, but a value of p with which we can calculate 3rd roots other than 1 appeared after several reconnections.

n=12251795882968515335720230660073746659413869760924025221649852208035051237856708925781912778413121581923338535504285363717654276804327121718065343894161577 F = IntegerModRing(n) print(F(1).nth_root(3, all=True))

求まった3乗根の1つ

This is one of the 3rd roots:

7191913673163613897488283950986433933185763568097469131901982702534156192969929339505441043029606560041994238242674105317600356701526959347916836181617823

をサーバに送信すると、以下の出力が得られた。

Sending this value to the server, it printed this:

ciphertext = 981a500a7b227d47cea9a32643c76240e5a6f06e3515e04853e078e2ca1d9ccf9cffbe5e5addb8d05c45210a10bb8940

PythonのインタラクティブモードでB、およびBの2乗をpで割った余りの16進表現を求め、 以下のようにCyberChefで対応する暗号鍵を取得した。

I obtained hexadecimal representations of B and square of B modulo p using the interactive mode of Python, and obtained corresponding encryption keys using CyberChef in this way:

Fork, From Hex, SHA1, Drop bytes - CyberChef

さらに、以下のようにしてそれぞれの暗号鍵で得られた暗号文の復号を行った。

  1. 暗号文と鍵候補を入力として受け取る。
  2. 暗号文をRegisterに保存し、入力から消す。
  3. Forkを行い、それぞれの鍵候補について以下を行う。
    1. 鍵候補をRegisterに保存し、入力を空にする。
    2. パディングのブロックを作成するため、この空を暗号化する。
    3. 得られた暗号文の前に、入力の暗号文を追加する。
    4. その結果を復号する。

Then, I decrypted the ciphertext sent from the server using each encryption keys in these steps:

  1. Receive the ciphertext and the candidates of the key as the input.
  2. Put the ciphertext to Register and remove that from the input.
  3. Using Fork, do this for each candidates of the key:
    1. Put the candidate of the key to Register and make the input empty.
    2. Encrypt the empty input to create a padding block.
    3. Add the ciphertext from the input before the resulting ciphertext.
    4. Decrypt the result.

Register, 7 more - CyberChef

その結果、flagが得られた。

I obtained the flag from the result.

buckeye{sup3r_dup3r_t1ny_m1cr0sc0p1c_subgr0up5!}

BuckeyeCTF 2021