[日本語] [English]

Key exchange

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

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

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

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

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を送信できるよう、gbの値はサーバに接続する前に用意しておくとよい。

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の値を送信すると、サーバから以下の出力がされた。

ciphertext = e1a24055154c2b29a0f48f977315704dd02d1b735b43907e77c11a96900e9fba81b2b39f883f3238779e581de55658f9fd6cc6f4ad0e05b014426fa48266ce23

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

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

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

From Hex, SHA1, Take bytes - CyberChef

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

AES Encrypt - CyberChef

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

AES Decrypt - CyberChef

buckeye{DH_1s_s0_h3ck1ng_c00l_l1k3_wh0_w0uldv3_th0ught_0f_th1s?}

writeup by MikeCAT

BuckeyeCTF 2021