CTFWriteups/DAMCTF2021/haveibeenpwned

have-i-b33n-pwn3d

In this challenge we are supposed to find all passwords in a private set intersection protocol as described in this paper. To be frank I didnt read the paper. This protocol is based on elliptic curves (more specifically y^2 = x^3 + 486662x^2 + x \mod{2^{255}-19}) however that turns out to be bad.

Relating the 2 polynomials

			for i in range(len(passwords)):
				b = sample_R()
				p = b * base_p

				bs.append(b)

				key = F(md5(passwords[i].encode()))
				# print(passwords[i].encode())
				print(key)

				px, py = p.xy()
				xs.append((key, px))
				ys.append((key, py))

			x_poly = R.lagrange_polynomial(xs)
			y_poly = R.lagrange_polynomial(ys)

			send(str(x_poly))
			send(str(y_poly))

The server creates a list of x,y points where x is md5(pw) and y is a random private key generated by base_p) Then the points are interpolated together using lagrange interpolation Notice that both polynomials have the private keys = P(md5(pw_i)) where P is the polynomial and can be substituted in to the curve equation P_y(md5(pw_i))^2 = P_x(md5(pw_i))^3 + 486662 * P_x(md5(pw_i))^2 + P_x(md5(pw_i)) \mod{2^{255} - 19}

Finding the hashes

To recover the hashes we seed to find for what n P_x(n)^3 + 486662 * P_x(n)^2 + P_x(n) - P_y(n)^2 \equiv 0 \mod{2^{255} - 19}

pol = xPoly^3 + 486662 * xPoly^2 + xPoly - yPoly^2
roots = pol.roots()
len(roots) # 17

This returns 17 roots (your results may vary) some of them have to be fake. Any roots that are 255 bit long are fake since md5 hashes are 128 bit. Before we can try to crack the hashes we first have to check how the hash was converted to an integer.

def md5(msg: bytes) -> int:
	h = MD5.new()
	h.update(msg)
	return int.from_bytes(h.digest(), 'little')

Here we see that the md5() function uses little endianess (ew) so we have to convert the hashes using int(r).to_bytes(16, 'little').hex().

Finishing up

Now we can throw this into an online md5 lookup table (or hashcat if you are feeling fancy) and find

481cf17a2f3a0cfafcedaa0dbea09fdc DDBBFF
476e90c539400f0e2988b32db64ae6bf honolulu-lulu
557d2cd9d61ebd645f0713ca655de1b1 STARK1
db3715c800e019e84c7fea4dc0c71d7d ctnormi
bdc87b9c894da5168059e00ebffb9077 password1234
6a951dee3380abc4b7aa2ccd9bb96d5b FRENCHAMERICANCENTER
2bb051b27a55de60f1b3550022725430 SPHAEROPSOCOPSIS
594dbf2c9321c4424b8e38676dc8ae2f recklessness-inducing
fce4765160cd540d146acd215bcd4a21 MANGO2000
67983c8501b3aae0ba8179426b389d1d STANLEYKARNOW
21fb2e1c8d19182c1602897d7d874018 bnflwmxzqmok
d3040380b07cc31250d18aa64013d613 strange-justice
bcf1bf1fe1b2de521306fad6e714130b SINO-BRIT
8b8037d5ca8f3c84363d7354dac5be05 BENAKOS
9dd530606c2930dd60310d2e9f925e05 jojootis
938b47219ea281812a031694d0954601 TOLDI85

Now we can patch psi_sender.py to recevie one extra line and then run ./psi_sender.py DDBBFF honolulu-lulu STARK1 ctnormi password1234 FRENCHAMERICANCENTER SPHAEROPSOCOPSIS recklessness-inducing MANGO2000 STANLEYKARNOW bnflwmxzqmok strange-justice SINO-BRIT BENAKOS jojootis TOLDI85 and we get back

They've all been pwned?! Really?!?! Please hold my flag while I go change them.
dam{I_DoN'T_KnOw_1f-i-wAs-pwN3D_8U7-1_$ur3-@M-nOW}