SSTIC challenge 2023  Step 2.a
This is the solution of the step 2.A of the SSTIC 2023. It was a nonce generation flaw of an implementation of a multisignature scheme called MuSig2.
Description
The full description in french is given in a file info.eml of backup.tgz
Details
Category: Cryptography
Author: Ledger Donjon
Solution
The previous step of the challenge gave us two archives: backup.tgz and devices.tgz.
The archive devices.tgz contains a folder per devices a.k.a per challenges. It was possible to solve the challenges in parallel but at the end the four flags were needed to go a step forward to the step 3. We are here interested by devices A.
The folder deviceA
contains a file musig2_player.py
. This is an implementation of MuSig2, a a multisignature scheme producing Schnorr signature. It means that group of signers can produce a joint signature of a message without having the private key exposed at any point. It also provides a log of the transactions between a signer and the aggregator.
In MuSig2, the final signature is computed from all the signers signatures with: $$s =\sum_{i=0}^4 s_i$$
The signature of a signer is given by the formulas: $$s_i = c \cdot a_i \cdot x_i + \sum_j r_{i,j}b^{j1}$$
Where $r_{i,j}$ are nonces which should be generated randomly. However, in the code the nonce generation is not properly done. Here is the code doing the nonce generation:


Thus the nonce value is $r_{i,j} = (x_i*m)^{\mathrm{SHA_{256}(j)}}$
Lets say that we have the log of the signer 0. Then we have: $$s_0 = c \cdot a_0 \cdot x_0 + r_{0,1} + r_{0,2}b + r_{0,3}b^3+r_{0,4}b^4$$
If we replace in the formula the nonce generation we obtain: $$s_0 = c \cdot a_0 \cdot x_0 + x_0^{\mathrm{SHA_{256}}(1)} \cdot m^{SHA_{256}(1)} + x_0^{\mathrm{SHA_{256}}(2)} \cdot m^{SHA_{256}(2)} \cdot b + … $$
From the log we know the value of the signature $s_0$, $m$ and we can compute $c$ and $a_0$. Thus for each signature we have a linear dependency on variables $x_0, x_0^{\mathrm{SHA_{256}}(1)}, x_0^{\mathrm{SHA_{256}}(2)}, x_0^{\mathrm{SHA_{256}}(3)}, x_0^{\mathrm{SHA_{256}}(4)}$. By change we have 5 signatures in the log thus we can solve the linear equation by writing the system with all the signatures. I have written a Sage script to do that and solve the system.
This output the value of $x_0$ then we can verify that the value generate the correct public key $X_0$.
Finally to have the flag I modified the script given in the backup archive to decrypt the flag:

