| With standard (non-pairing) ECC signatures every signature uses a secret nonce. These discrete-log signatures can be understood as a linear equation with one known, the signature itself, and two unknowns, the nonce and private key. You can verify the signature without the secrets because linear systems also hold when projected into an elliptic curve group. The verifier knows the EC image of the private key-- that's the public key--, and the signature includes the EC image of the nonce, so they can check the system by projecting the signature into the EC group and checking that the equation holds there. However, if an attacker knows the nonce they can simply calculate the private key because they will have an equal number of knows and unknowns, like any other exactly determined linear system. (Similarly, if you have multiple signatures with a known linear relation between the nonces and between the secret keys-- again, you can solve for the key.) To make this concrete, here is a r,s schnorr signature: [Notation: lower case variables are elements of finite field, upper case are elements of a cyclic group where the DL problem is presumed hard (elliptic curve points), the group operation is notated as addition, G is any generator of that group, and hash() is some cryptographic hash that produces values in the finite field.] secret-key: x // Hopefully random
public-key: P = xG
signer's nonce: k // Hopefully random
signature: {R,s} where R = kG, s = k + x*hash(R||message)
Verifier checks: R == sG - P*hash(R||message)
The verification equation is simply the signing equation re-orderd to put k on the left and multiplied by G, because the verifier only knows xG (the pubkey) not x-- and they can't 'divide out' G to check the signature because they can't solve the discrete log problem... but they can multiply G by a field element where its missing.Now imagine you don't know x but you have a valid signature {R,s,message} where you happen to know the k being used. You can derive x: x = (s - k) / hash(R||message)
This is literally just rearranging the signing equation to get the x alone on the left hand side. The case for related nonces (e.g. nonce reuse) is hardly any more complicated.ECDSA is equivalent but the formulas are just a little messier. Now, how does the attacker go about knowing k? If they control the signing software, it's easy. The attacker picks a secret x_2 and computes a pubkey Q = x_2 G and embeds his pubkey in the malicious signer. Instead of making k random, set k = hash(xQ || message), x being the user's secret key. The attacker computes k = (x_2 P || message). Both k's are the same value because both xQ and x_2P are equivalent to x * x_2 * G-- this is just ECDH. So the attacker, and _only_ the attacker, knows your k... yet k is different and random looking for each message. If the attacker wants to be extra lazy, they can skip the ECDH but then someone who reverse engineers a compromised signer will also know all the Ks. This attack is slightly aided by the existence of the de-randomized nonce procedure of RFC6979 or EdDSA, because in those k is supposed to equal effectively hash(x || message), instead of being actually random-- which looks a lot like our tampered equation and to someone who doesn't know x they're indistinguishable-- if you sign the same message multiple times you'll get the same signature. It's not at all surprising for a signer to behave 'non-randomly' in this manner. The attacker can also leak out some additional data-- say up to 32-bits per signature-- by making the signer's k not be identical to their computed k but merely close to it. Then they can subtract off their computed kG from R and look up the discrete log in a precomputed table (and with a meet in the middle the table can be made small, for fun). Because k is necessarily private its very hard to determine if k was set faithfully or instead was the product of some malicious process. There are ways to guard against a malicious hardware token by using a marginally trusted host to help randomize the nonce, but no one implements them. |