The challenge is about a method developed by the author to check if his passwords have been leaked, with constraints to avoid the storage of these passwords in plaintext.
This is an echo of the web site Have I Been Pwned, in which any user can check if credentials have been leaked for a given email address.
Challenge Discovery
The source code of the server and the client are given to the challengers. They are written in Sage (a Python framework used for doing mathematical stuff in a more abstract way). Here is what it looks like:
Server


Client


Utilities


Algorithm analysis
Diffie Hellman over Elliptic Curve
This part is not necessary for understanding the overall resolution. Therefore, if you do not understand everything, no worry, you can skip it (or you can PM me if you wish to have more details).
All the operations are done on an elliptic curve defined over a finite field. I spent quite a lot of time to see if there was any flaw (especially why the author did not use a classic curve). Apparently it was a rabbit hole, as the same curve was used in another challenge (so it probably has no trivial vulnerability to exploit). However, it is interesting to see that the order of the curve (the number of points defined on this curve over the finite field) is a product of 8 and a larger factor. As it could induce some major flaws if the numbers are badly chosen, it is necessary to ensure that they are a multiple of 8 (by using 3bit shifting). This condition ensures the numbers chosen are not in the smallest subfield.


The application uses the elliptic curve to transmit secrets in a public environment, between two parties. In order to do that, it uses the Diffie Hellman key exchange over Elliptic Curves.
The Diffie Hellman algorithm allows parties to agree on a common secret thanks to the Discrete Logarithm Problem. In Elliptic Curves defined over finite fields, this problem works as follows: Let’s imagine the secret is the number b. Let’s use an arbitrary point P on the curve. If one transmits the new point Q = b*P
, an attacker can intercept Q. As P is also public, In order to retrieve b, the attacker must find it by calculating it such that b*P = Q
This problem is, still nowadays, hard to solve, as there is no easy way of “dividing” Q by P (which would let the attacker find b).
As a result, the Diffie Hellman protocol over Elliptic curves works as follows: the two parties A and B agree on the Elliptic Curve to chose (and the Finite Field used for defining points over it). They also agree on a base point P on this curve. Then, they chose random numbers in the finite field (a for A and b for B). They transmit to each other Pa = a*P
and Pb = b*P
. Finally, they calculate S = a*b*P = a*Pb = b*Pa = b*a*P
An attacker can get Pa and Pb but, in order to get S, they must retrieve either a or b, which means they have to solve the Discrete Logarithm Problem.
The hard and technical part is finished, let’s dive into the challenge.
Communication analysis
By analyzing these files, it is possible to understand how the check of the passwords works:
The public data of the algorithm is:

The finite field F of size p = 57896044618658097711785492504343953926634992332820282019728792003956564819949

The curve curve25519 defined by the equation E:
y**2 = x**3 + 486662*x**2 + x
over F 
The point base_p on curve curve25519, of coordinates x = 9, y = 43114425171068552920764898935933967039370386198203806730763910166200978582548
The protocol is:
 First, the client choses a secret a and transmits the point
m = a*base_p
 The server receives the point m
 For each password:
 The server choses a secret b_i and calculates
p_i = b_i * base_p
 The server calculates
key_i = bytes.to_int(md5(password), "little endian")
 The server calculates
m_i = b_i * m
 The server calculates
el_i = sha256(password  str(m_i))
with  the string concatenation operator andstr(m_i)
a string representation of the point p_i
 The server choses a secret b_i and calculates
 Once in possession of the list of keys and secrets, the server calculates two Lagrange polynomials (over the finite field F):
 x_poly, such that for each i,
x_poly(key_i) = p_i.x
 y_poly, such that for each i,
y_poly(key_i) = p_i.y
 x_poly, such that for each i,
 The server sends the two polynomials to the client
 for each password given by the client:
 The client calculates
key_i = bytes.to_int(md5(password), "little endian")
 The client calculates the points
p_i
by using the fact thatx_poly(key_i) = p_i.x
andy_poly(key_i) = p_i.y
 The client calculates
Q_i = a * p_i
 The client generates the hash
k_i = sha256(password  str(Q_i))
with  the string concatenation operator andstr(Q_i)
a string representation of the point Q_i
 The client calculates
 The client sends all the k_i hashes
 The server receivers the k_i hashes.
 The server checks the intersection of the k_i hashes and the el_i hashes.
 If both sets are equal, it sends back the flag.
 If the intersection is not empty, the server sends back a message of “passwords being compromised”
 If the intersection is empty, the server sends back a safe message.
This algorithm works thanks to the Diffie Hellman key exchange algorithm. Indeed, for each password, Q_i = a * p_i = a * b_i * p = b_i * a * p = b_i * m = m_i
.
The Lagrange polynomials are here to send the public points corresponding to each password. Indeed, a Lagrange polynomial P is a polynomial defined by couples (x_i, y_i), such that for each i, P(x_i) = y_i
. In this case, the Lagrange polynomials x_poly and y_poly are defined by the following couples: for each key_i derived from the passwords, for each p_i associated to the password, x_poly(key_i) = p_i.x
andy_poly(key_i) = p_i.y
. This allows to transmits the coordinates x and y of each point separately.
Therefore, the client will be able to calculate the right SHA256 sums only if they find the right coordinates of each point, and this is doable only if they find the right keys derived from each password.
By the way, the Lagrange polynomial degree is defined by the number of couples used for its generation. Here, the degree is 15, meaning 16 passwords are tested.
Spot the flaw
In order to find the vulnerability, the first step is to eliminate the possible rabbit holes.
examinate the SHA256 sum
The final hashes are defined by sha256(password  str(Q_i)
.
This means that, in order to find it, the user must already have the right password. Plus, the string representation of each point is hard to calculate without finding the associated points.
As a result, there is no vulnerability here.
Retrieving the public points
In order to retrieve the public points, the user must get the right md5 sums corresponding to passwords. As a result, retrieving the points means the user has already found the MD5 sums.
Once the rabbits holes identified it is possible to focus on the main point of the program: the Lagrange polynomials.
Exploiting the Lagrange Polynomials
It is interesting to see that every operation is done over the finite field F. This means that operations on the polynomials and on the elliptic curve can be combinated.
This leads to an hypothesis: is it possible to abuse the Lagrange polynomials and the curve equation to retrieve the points ?
Indeed, as defined, the Lagrange polynomials give valid points on the curve for the different MD5 hashed passwords. This means that, for any z in F, by settingx = x_poly(k)
and y = y_poly(k)
, these satisfy the equation y**2 = x**3 + 486662*x**2 + x
especially in the case of k = md5(password)
.
Therefore, by defining the polynomial k_poly(k) = x_poly(k)**3 + 486662 * x_poly(k)**2 + x_poly(k)  y_poly(k)**2
, it is possible to retrieve the MD5 hashes by looking at the small roots of k_poly.
This can be done by slightly modifying the client script:


The result of the program is:
Breaking the MD5 hashes
The program above gives the following small roots:


Converted into bytes (little endian), it gives the following hashes:


All these hashes can be cracked using Crackstation:
Hash  Type  Result 

481cf17a2f3a0cfafcedaa0dbea09fdc  md5  DDBBFF 
476e90c539400f0e2988b32db64ae6bf  md5  honolulululu 
557d2cd9d61ebd645f0713ca655de1b1  md5  STARK1 
db3715c800e019e84c7fea4dc0c71d7d  md5  ctnormi 
bdc87b9c894da5168059e00ebffb9077  md5  password1234 
6a951dee3380abc4b7aa2ccd9bb96d5b  md5  FRENCHAMERICANCENTER 
2bb051b27a55de60f1b3550022725430  md5  SPHAEROPSOCOPSIS 
594dbf2c9321c4424b8e38676dc8ae2f  md5  recklessnessinducing 
fce4765160cd540d146acd215bcd4a21  md5  MANGO2000 
67983c8501b3aae0ba8179426b389d1d  md5  STANLEYKARNOW 
21fb2e1c8d19182c1602897d7d874018  md5  bnflwmxzqmok 
d3040380b07cc31250d18aa64013d613  md5  strangejustice 
bcf1bf1fe1b2de521306fad6e714130b  md5  SINOBRIT 
8b8037d5ca8f3c84363d7354dac5be05  md5  BENAKOS 
9dd530606c2930dd60310d2e9f925e05  md5  jojootis 
938b47219ea281812a031694d0954601  md5  TOLDI85 
Getting the flag
The last step is just to send the passwords to the server, which then gives back the flag:
And here is the flag:
dam{I_DoN'T_KnOw_1fiwAspwN3D_8U71_$ur3@MnOW}