Sony PlayStation 3 ECDSA random number reuse

The Sony PlayStation 3 (2006) uses Elliptic Curve DSA (ECDSA) to sign executable binaries.

ECDSA takes a private key \(d_A\) and a random number \(k\) with public parameters \(G\), \(n\) and public key \(Q_A = d_A G\), and computes the signature \(r,s\) on hash \(z\) as:

\[ \begin{align} r &= (kG)_x \\ s &= \frac{z + rd_A}{k} \end{align} \]

It is imperative that a random \(k\) is used for every signature. However, the PlayStation 3 uses the same value of \(k\) for each signature. Therefore:

\[ \begin{align} k &= \frac{z + rd_A}{s} \end{align} \]

will be a constant for every signature, and so will \(r = (kG)_x\).

Therefore, obtaining signatures \(s_1\) and \(s_2\) for different messages hashes \(z_1\) and \(z_2\), we observe that:

\[ \begin{align} \frac{z_1 + rd_A}{s_1} &= \frac{z_2 + rd_A}{s_2} \\ \frac{rd_A}{s_1} - \frac{rd_A}{s_2} &= \frac{z_2}{s_2} - \frac{z_1}{s_1} \\ d_A &= \frac{\frac{z_2}{s_2} - \frac{z_1}{s_1}}{\frac{r}{s_1} - \frac{r}{s_2}} \end{align} \]

Oops, private key!

Nintendo Wii strncmp

The Nintendo Wii (2006) uses the RSA signature scheme with SHA-1 in a number of places, including to protect its boot images.

However, firstly, the Wii discards the bytes used to pad the SHA-1 hash for signing and compares only the hash. Secondly, when comparing the signed SHA-1 hash with the hash of the payload, the Wii uses strncmp, which is a string comparison function.

Even though strncmp accepts a length parameter n, strncmp will compare only up to n bytes of its input strings, and being a string compare function, will return early if it encounters a null byte in either string.

It is a property of RSA that a zero byte in the hash results in a zero byte in the signature, so an all-zero RSA signature will equate to an all-zero SHA-1 hash. And by producing a payload with a SHA-1 hash that begins with a null byte, strncmp will compare only this single byte and report that the two hashes are equal.