[日本語] [English]

Key exchange 2

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

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_secretBBの2乗、1のどれかになるはずである。

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

n=12251795882968515335720230660073746659413869760924025221649852208035051237856708925781912778413121581923338535504285363717654276804327121718065343894161577

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

求まった3乗根の1つ

7191913673163613897488283950986433933185763568097469131901982702534156192969929339505441043029606560041994238242674105317600356701526959347916836181617823

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

ciphertext = 981a500a7b227d47cea9a32643c76240e5a6f06e3515e04853e078e2ca1d9ccf9cffbe5e5addb8d05c45210a10bb8940

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

Fork, From Hex, SHA1, Drop bytes - CyberChef

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

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

Register, 7 more - CyberChef

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

buckeye{sup3r_dup3r_t1ny_m1cr0sc0p1c_subgr0up5!}

writeup by MikeCAT

BuckeyeCTF 2021