Key exchange

TCPサーバの接続情報と、サーバのプログラム server.py が与えられた。
server.py は以下のような処理をするものだった。

  1. 素数pと定数g = 5を用意し、出力する。
  2. 乱数aを用意する。
  3. gのa乗をpで割った余りAを計算し、出力する。
  4. 1より大きくp - 1未満の整数Bを入力させる。
  5. Bのa乗をpで割った余りshared_secretを計算する。
  6. shared_secretをlong_to_bytesで変換したデータのSHA-1ハッシュの先頭16バイトを鍵として、FLAGをAES.MODE_ECBで暗号化し、出力する。

shared_secretの計算には、B ^ a === (g ^ b) ^ a === g ^ (ab) (mod p) というコメントがついていた。
この計算を進めると、g ^ (ab) === (g ^ a) ^ b === A ^ b (mod p) となる。
すなわち、適当な数bを用意し、gをb乗してpで割った余りをBとして送信すると、
Aをb乗してpで割ることでshared_secretの値を求めることができる。

サーバに接続すると、例えば以下が出力された。

Information to connect to a TCP server, and a program for the server server.py were given.
What server.py does is:

  1. Prepare a prime number p and a constant value g = 5, and print them.
  2. Prepare an random integer a.
  3. Calculate g to the a-th power modulo p as A, and print that.
  4. Read an integer B, which is greater than 1 and less than p - 1.
  5. Calculate B to the a-th power modulo p as shared_secret.
  6. Encrypt FLAG with AES.MODE_ECB using the first 16 bytes of the SHA-1 hash value of shared_secret converted via long_to_bytes as the key, and print the result.

There was a comment B ^ a === (g ^ b) ^ a === g ^ (ab) (mod p) for the calculation of shared_secret.
Proceeding this calculation yields g ^ (ab) === (g ^ a) ^ b === A ^ b (mod p).
This means that we can obtain the value of shared_secret by calculating A to the b-th power modulo p
after preparing some random value b and sending g to the b-th power modulo p as B.

For an example, this was printed after connecting to the server:

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 = 13100953797897539436008478171867615770854825342065671749974255587240935194028242863668388402707550617039437399297551882716990247250202130495220466889106119 g = 5 A = 4172727189770658610889137742629770066474852445855501339216972286122628606291523457829146016595944156179125767594146778765988657548101768506883419118758577 Give me your public key B:

これに対し、Pythonのインタラクティブを用いて以下のようにBとして送信する値を計算できる。
なお、接続が切れる前にBを送信できるよう、gやbの値はサーバに接続する前に用意しておくとよい。

Seeing this, we can calculate the value to send as B using the interactive mode of Python like this.
You should prepare the values of g and b before connecting to the server to make it easier to send B before the connection gets closed.

Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 23:03:10) [MSC v.1916 64 bit (AMD64)] on win32 Type "help", "copyright", "credits" or "license" for more information. >>> g = 5 >>> b = 3142857142857 >>> p = 13100953797897539436008478171867615770854825342065671749974255587240935194028242863668388402707550617039437399297551882716990247250202130495220466889106119 >>> B = pow(g, b, p) >>> B 7158990485917916975114189539310763209191741436636609628891953547793497596963956031178839236844427200655067928073491099870766188675029873537034390693810448

ここで求めたBの値を送信すると、サーバから以下の出力がされた。

Sending the value of B obtained here, the server sent this:

ciphertext = e1a24055154c2b29a0f48f977315704dd02d1b735b43907e77c11a96900e9fba81b2b39f883f3238779e581de55658f9fd6cc6f4ad0e05b014426fa48266ce23

Pythonのインタラクティブを用い、Bを求めた続きでshared_secretの値を求める。

Then, calculate the value of shared_secret using the interactive mode of Python after obtaining the value of B.

>>> A = 4172727189770658610889137742629770066474852445855501339216972286122628606291523457829146016595944156179125767594146778765988657548101768506883419118758577 >>> shared_secret = pow(A, b, p) >>> hex(shared_secret) '0x17f4ed4e5f25fa2161e2c70a0b1bf7d863c8a7e8a93055b5df8ec0a483cf6b2f15b99bd99549cfd440cd126a3147aebed1d6ea4d66bef961bd177099b06d9de8'

得られたshared_secretの値をCyberChefに入力し、 SHA-1値の最初16バイトを求める。

After that, put the calculated value of shared_secret to CyberChef to obtain the first 16 bytes of the SHA-1 value.

From Hex, SHA1, Take bytes - CyberChef

これで暗号化の鍵が求まったが、このままサーバから出力されたciphertextをCyberChefの AES Decrypt で複号しようとすると、「Unable to decrypt input with these parameters.」と出てしまう。
これは、(現在の)CyberChefの AES Decrypt のECBモードではパディングの使用が強制されるためである。
そこで、まず空文字列をこの鍵で暗号化し、パディングのブロックを得る。
ECBモードは各ブロックを独立して暗号化する方式なので、ciphertextのデータは不要である。

Now I got the encryption key, but simply trying to decrypt the ciphertext sent from the server using "AES Decrypt" on CyberChef results in "Unable to decrypt input with these parameters.".
This is because using padding is forced in the ECB mode of "AES Decrypt" of (current) CyberChef.
To overcome this, firstly we should encrypt an empty string with this key to obtaine a padding block.
The ciphertext is not needed here because each blocks are encrypted independently in the ECB mode.

AES Encrypt - CyberChef

ciphertextの後ろに得られたパディングのブロックを追加し、AES Decrypt を行うと、flagが得られた。

I obtained the flag by adding the obtained padding block after the ciphertext and applying "AES Decrypt".

AES Decrypt - CyberChef

buckeye{DH_1s_s0_h3ck1ng_c00l_l1k3_wh0_w0uldv3_th0ught_0f_th1s?}

BuckeyeCTF 2021