PlaidCTF 2016 tonnerre (crypto200) Writeup

public_server_ea2e768e20e89fb1aafbbc547cdb4636.py

We can leak the verifier by putting the following query in ID(Finding db name and table name must be preceded):

' union select verifier from users limit 1#

If \( c=g^2 \mod N \) then

\[ \begin{align} \mbox{session_secret} & =(g^2)^\mbox{random_server} \mod N \\ & =(g^\mbox{random_server})^2 \mod N \\ & =\mbox{public_server}^2 \mod N \end{align} \]

public_server can be easily computed by \( \mbox{residue} - \mbox{verifier} + N \). To find out which public_client makes \( c=\mbox{public_client} \times \mbox{verifier}=g^2 \mod N \), we need to compute \[ \mbox{public_client}=g^2 \times \mbox{verifier}^{-1} \mod N \].

from Crypto.Hash import SHA256
from socket import *

def mul_inv(a, n):
	if n == 1: return 1
	
	b0 = n
	x0, x1 = 0, 1
	
	while a > 1:
		q = a / n
		a, n = n, a%n
		x0, x1 = x1 - q * x0, x0
	if x1 < 0: x1 += b0
	return x1

N = 168875487862812718103814022843977235420637243601057780595044400667893046269140421123766817420546087076238158376401194506102667350322281734359552897112157094231977097740554793824701009850244904160300597684567190792283984299743604213533036681794114720417437224509607536413793425411636411563321303444740798477587L
g = 9797766621314684873895700802803279209044463565243731922466831101232640732633100491228823617617764419367505179450247842283955649007454149170085442756585554871624752266571753841250508572690789992495054848L
verifier = 0xebedd14b5bf7d5fd88eebb057af43803b6f88e42f7ce2a4445fdbbe69a9ad7e7a76b7df4a4e79cefd61ea0c4f426c0261acf5becb5f79cdf916d684667b6b0940b4ac2f885590648fbf2d107707acb38382a95bea9a89fb943a5c1ef6e6d064084f8225eb323f668e2c3174ab7b1dbfce831507b33e413b56a41528b1c850e59
public_client = mul_inv(verifier,N)*g**2 % N

def H(P):
	h = SHA256.new()
	h.update(P)
	return h.hexdigest()

def tostr(A):
	return hex(A)[2:].strip('L')

s=socket(2,1)
s.connect(("tonnerre.pwning.xxx",8561))
print s.recv(1024)
s.send("get_flag\n")
s.send(hex(public_client).strip("0x").strip("L")+"\n")
print s.recv(1024)
residue = int(s.recv(1024), 16)
public_server = residue - verifier
while public_server < 0:
	public_server += N
session_secret = (public_server)**2 % N
session_key = H(tostr(session_secret))
s.send(H(tostr(residue) + session_key)+"\n")
print s.recv(1024)
print s.recv(1024)

FLAG: PCTF{SrP_v1_BeSt_sRp_c0nf1rm3d}