TCPサーバの接続情報と、サーバのプログラム server.py
が与えられた。
server.py
は以下のような処理をするものだった。
p
と定数g = 5
を用意し、出力する。a
を用意する。g
のa
乗をp
で割った余りA
を計算し、出力する。1
より大きくp - 1
未満の整数B
を入力させる。B
のa
乗をp
で割った余りshared_secret
を計算する。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
の値を求めることができる。
サーバに接続すると、例えば以下が出力された。
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
の値はサーバに接続する前に用意しておくとよい。
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のデータは不要である。
ciphertextの後ろに得られたパディングのブロックを追加し、AES Decrypt を行うと、flagが得られた。
writeup by MikeCAT