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 multi-signature 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 multi-signature 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^{j-1}$$

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:

1
2
3
4
5

def get_nonce(x,m,i):
    # NOTE: this is deterministic but we shouldn't sign twice the same message, so we are fine 
    digest = int.from_bytes(hashlib.sha256(i.to_bytes(32,byteorder="big")).digest(),byteorder="big")
    m_int = int.from_bytes(m, "big")
    return pow(x*m_int, digest, order)

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:

1
2
3
4

$ rax2 -s 0x47a079e1475de6253faf0730926fbeaaaa317daf7c1639cae181a072cad667e8 > keyfile
$ python decrypt.py keyfile encrypted_flags/deviceA.enc deviceA
$ cat deviceA 
SSTIC{dc3cb2c61cb0f2bdec237be4382fe3891365f81a0fb1c20546d888247dd9df0a}