Black Alps 2023 - Schnorr Signatures
This is the solution of the challenge “Schnorr Signatures” from Black Alps 2023 CTF. It was Schnorr signatures with a known prefix of 128 bits set to zero.
Details
Category: Crypto
Author: Alexandre Duc
Solution
We were given a Schnorr signature script using the P-384 curve and the file parameter.txt contains four messages, four signatures and the corresponding public key.
The flaw was quickly found, the nonces $k_i$ are generated with SHA-256 which gives nonces with a prefix of 128 bits set to zero. The goal is to transform the signature into an instance of the Hidden Number Problem (HNP), to solve it and to recover the private key $x$. It turned out to be not that easy to me and I was not able to finish the challenge during the competition but I explain here the solution which finally worked for me.
We have signatures $(r_i, e_i)$ such that: $$r_i = k_i - e_i x + l_i q$$ Where $q$ is the order of the curve and $l_i$ integers and with $|k_i| < B = 2^{256}$. Or express differently: $$k_i = r_i + e_i x - l_i q$$ We can express it as a linear system: $$\begin{pmatrix} k_0 \\ k_1 \\ k_2 \\ k_3 \end{pmatrix} = (l_0,l_1,l_2,l_3,x) \begin{pmatrix} q & 0 & 0 & 0 \\ 0 & q & 0 & 0 \\ 0 & 0 & q & 0 \\ 0 & 0 & 0 & q \\ e_0 & e_1 & e_2 & e_3 \\ \end{pmatrix} - (r_0, r_1, r_2, r_3) $$
This system can be solves with an algorithm solving the Closest Vector Problem to find the vector of nonce since it gives a small difference. However, a more efficient way is to embed the matrix into a larger lattice:
$$\begin{pmatrix} q & 0 & 0 & 0 & 0\\ 0 & q & 0 & 0 & 0\\ 0 & 0 & q & 0 & 0\\ 0 & 0 & 0 & q & 0\\ e_0 & e_1 & e_2 & e_3 & B/q\\ -r_0 & -r_1 & r_2 & -r_3 & B\\ \end{pmatrix}$$
The solution of the shortest vector problem (SVP) of this lattice should be the vector $(k_0,k_1,k_2,k_3, Bx/q, B)$ since it is small compared to other vectors. Thus I applied the LLL algorithm on the matrix and I search which vector ends by the value $B$ and the first value of the vector gives the value of $Bx/q$ (up to the sign). Since LLL gives an approximation of the shortest vector problem, the solution needs to be incremented until it match the public key. The full working script is available here.