# have-i-b33n-pwn3dIn this challenge we are supposed to find all passwords in a private set intersection protocol as described in [this paper](https://eprint.iacr.org/2021/1159). 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```python			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 interpolationNotice 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 hashesTo 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}$```pythonpol = xPoly^3 + 486662 * xPoly^2 + xPoly - yPoly^2roots = 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.```pythondef 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 upNow we can throw this into an online md5 lookup table (or hashcat if you are feeling fancy) and find```481cf17a2f3a0cfafcedaa0dbea09fdc DDBBFF476e90c539400f0e2988b32db64ae6bf honolulu-lulu557d2cd9d61ebd645f0713ca655de1b1 STARK1db3715c800e019e84c7fea4dc0c71d7d ctnormibdc87b9c894da5168059e00ebffb9077 password12346a951dee3380abc4b7aa2ccd9bb96d5b FRENCHAMERICANCENTER2bb051b27a55de60f1b3550022725430 SPHAEROPSOCOPSIS594dbf2c9321c4424b8e38676dc8ae2f recklessness-inducingfce4765160cd540d146acd215bcd4a21 MANGO200067983c8501b3aae0ba8179426b389d1d STANLEYKARNOW21fb2e1c8d19182c1602897d7d874018 bnflwmxzqmokd3040380b07cc31250d18aa64013d613 strange-justicebcf1bf1fe1b2de521306fad6e714130b SINO-BRIT8b8037d5ca8f3c84363d7354dac5be05 BENAKOS9dd530606c2930dd60310d2e9f925e05 jojootis938b47219ea281812a031694d0954601 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}```