Category: misc

Points: 493 (15 solves)

Challenge Description

I want to check if any of my passwords have been stolen, but I don't want to risk sending them to Have I Been Pwned. I want a stronger guarantee than the k-anonymity that they provide. You can help me by submitting any leaked passwords you may find to a private set intersection protocol.

Usage: ./psi_sender.py password1234 notthepassword fall2021

Solution

In this challenge we are supposed to find all passwords in a private set intersection protocol from this paper. The exact workings of the protocol are not terribly important since we exploit the fact that the polynomials are related.

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()))

	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 two list of points $(key_i, x_i)$ and $(key_i, y_i)$ where $key_i$ is the md5 hash of the $i$th password and $x_i, y_i$ are the $x$ and $y$ coordinates of a random private key.

Then the points are interpolated together using Lagrange interpolation into polynomials $P_x$ and $P_y$. Notice that all $key_i$ are a root of both polynomials.

Finding the hashes

This protocol operates over the curve Curve25519, which is a elliptic curve defined by $y^2 = x^3 + 486662 x^2 + x \pmod{2^{255} - 19}$.

The points $(x_i, y_i)$ must obey the curve equation, therefore $y_i^2 = x_i^3 + 486662x_i^2 + x \Rightarrow P_y(key_i)^2 = P_x(key_i)^3 + 486662 P_x(key_i)^2 + P_x(key_i) \pmod{2^{255} - 19}$. So to find the hashes we just need to find the roots of this equation.

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

Since md5 has a 128 bit output, any root equal to or larger than $2^{128}$ can not be a password hash. Then the only thing left to do is to convert it from little endian integer to a string and then feed it to hashcat. We find that

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 recieve 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

It then returns 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}