Upbit hack's Occam's razor

and ECDSA's fragility

South Korea’s biggest exchange lost ~$30M. Allegedly, “a security vulnerability existed that allowed private keys to be estimated by analyzing multiple wallet transactions publicly disclosed on the blockchain.” Local media attributed this to the CEO’s official statement, though the updated version now seems to omit that line.

Little public information has been released about the root cause or attribution. But in case of a doubt, blame Pyongyang.

As others have already speculated, my first thought was: “ECDSA repeated nonces.”

Any cryptographer knows this well, and we all remember the PlayStation 3 disaster. But many crypto(currency) “experts” know surprisingly little crypto(graphy), and more than one person I talked to was shocked when they learned this. Here’s the issue:

Given the hash h of the message, ECDSA computes a signature using the private key x and a randomly chosen nonce k as follows:

• First, it computes the “public nonce” by multiplying k with the generator G (an elliptic-curve point), and extracts its x-coordinate r.

\(R = kG = (r, \_)\)

• Then ECDSA computes the core of the signature, s.

  \(s = \frac{h+xr}{k}\)

The signature returned is then the pair (r, s).

The problem is if you sign two messages using the same nonce. You then get two s values:

\(s_1 = \frac{h_1+xr}{k} \text{ and } s_2 = \frac{h_2+xr}{k} \)

It’s now trivial to recompute the nonce k as

\(k = \frac{h_1 - h_2}{s_1 - s_2}\)

From which you compute the private key x:

\(x = \frac{s_1 k - h_1}{r}\)

The nonce is a ~256-bit random number, so unless your RNG is broken, you won’t reuse a nonce, even after signing a very large number of messages. Basic probability tells us that if you sign N messages with a random 256-bit nonce, the probability that any nonce gets reused is approximately:

\(1 - \exp{- \frac{N(N-1)}{2\times 2^{256}}}\)

(as long as N isn’t too large; this approximation holds for billions and trillions of signatures.)

Even if you don’t repeat the exact same nonce, leaking any relation between two nonces can be enough to recover the key, or even leaking part of the nonce.

EdDSA and Ed25519 don’t have this problem, because they derive the nonce deterministically from the message and the private key. And ECDSA can be tweaked to work without randomness. No randomness, no bad randomness.

Feature image: my cats.