Nonce Reuse and ECDSA

As part of a CTF challenge I completed recently, I needed to break ECDSA. I was given two signatures and their plaintexts, and had to sign an arbitrary value - this, obviously, means I need to recover the private signing key.

But how?

Let's take a step back, and look at how ECDSA works. It's similar in concept to DSA, but relies on the Elliptic Curve Discrete Logarithm problem to provide its computational hardness, as opposed to the classic Discrete Logarithm (In multiplicative groups).

Firstly, three public parameters are chosen: The curve itself, a point G, which acts as a generator over the curve, and n, the order of that point, such that \(G * n = (0, 0)\)

The signing party generates a private integer \(d_{A}\), randomly selected from \(1..n-1\), and a public curve point \(Q_{A} = d_{A} * G\). Note that it is hard to recover \(d_A\) given \(Q_{A}\) as a result of the ECDL problem.

Now, let's get to actually signing a message, \(m\):

  • Compute \(e = H(m)\), where \(H()\) is a cryptographic hash
  • Define \(z = L_{n}(e)\), where \(L_{N}(x)\) where \(L_{v}(x)\) is defined as the \(v\) leftmost bits of \(x\), and \(N\) is the bit-length of \(n\) - for example, in the CTF challenge, which used NIST P-192 with SHA1, we took the whole hash as its length (160 bits) was less than N, 192 bits
  • select a random integer nonce, \(k\) from \([1..n-1]\)
  • Calculate the point \((x_{1}, y_{1}) = k * G\)
  • Calculate \(r = x_{1}{\bmod} n\). If \(r = 0\), pick a new \(k\) and try again.
  • Calculate \(s = \frac{z + rd_{A}}{k}{\bmod} n\). If \(s = 0\), pick a new \(k\) and try again
  • The signature is (r, s)

(Note that when computing s, z is treated as an integer, rather than a string of bytes)

I'm sure you noticed the emphasis on the third stage. This is because it's critically important. Why?

If \(k\) is repeated when signing two different messages, \(m, m'\), we end up with two signatures, \((r, s), (r, s')\). Given these values, we can solve for the shared value of \(k\), and in turn solve for the private key \(d_{A}\).

Firstly, the attacker computes \(k = \frac{z - z'}{s - s'}{\bmod} n\). This can be derived pretty easily (All calculations are mod n here): $$s - s' = \frac{z + rd_{A}}{k} \frac{z' + rd_{A}}{k}$$ $$s - s' = \frac{z - z'}{k}$$ $$\frac{s - s'}{z - z} = k ^{-1}$$ $$k = \frac{z - z'}{s - s'}$$

Once we have \(k\), we can then solve in a similar way to get \(d_{A}\), the private key!
$$d_{A} = \frac{sk - z}{r}{\bmod} n$$

This is just a pretty simple rearrangement from the definition of s, I've left it out for brevity's sake

Okay, you've gone on and on about maths, but where's the code?

This one had a few tricky details to remember when I was implementing, which caught me out. Firstly, I had to determine the format of the signatures (raw (r, s) in this case). Secondly - and this too far long to realise, is that when you're working modulo n, division doesn't actually mean division - rather, multiplication by the divisor's inverse modulo n.

Fortunately, we can hand off a lot of these details to Python's ecdsa module, which reduces the work a fair bit.

def recover_key(m1,s1,r1,m2,s2,r2):  
    # see http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
    assert(r1 == r2)
    n = 6277101735386680763835789423176059013767194773182842284081
    r = r1
    z1 = string_to_number(sha1(m1))
    z2 = string_to_number(sha1(m2))
    sdiff_inv = inverse_mod(((s1-s2)%n),n)
    k = ( ((z1-z2)%n) * sdiff_inv) % n
    r_inv = inverse_mod(r,n)
    da = (((((s1*k) %n) -z1) %n) * r_inv) % n

    recovered_private_key_ec = SigningKey.from_secret_exponent(da)
    return recovered_private_key_ec.to_pem()

That's the code for recovering the key. We first verify that the two r parts of the signatures are equal - that we have a shared K. We then compute our integer values of z - in this case, we use a quick wrapper over hashlib.sha1. Next up, we use the formulae we just described in order to recover the private key, using python's ecdsa module to create a PEM representation of the key

Once I'd recovered the private key, the rest of the challenge was trivial: just use it to sign the data given with a trivial script, then submit it to complete the challenge.

This was certainly an interesting challenge, and a reminder of the importance of detail in cryptography; one small detail, like the randomness of a nonce, can bring the entire cryptosystem tumbling down.