ECDSA and Schnorr signatures from the same private key

It has been warned that you should not use the same private key to generate both ECDSA signatures and Schnorr signatures. That is because there may be a method for people to extract secret data when the two of them are combined. While there isn’t a confirmed attack that uses this method, as is the case for the nonce-reuse attack, it also has not been proved that such an attack is impossible. The problem is NP-hard – unless you are generating the nonce deterministically or reusing it.

What is Nonce Reuse?

In simple terms, it is when you use the secret nonce k for two or more signed messages, and the same private key.

Nonce reuse might happen because a wallet uses the same value of k over and over again – these are considered the least secure systems. They can also happen because they use a standard such as RFC 6979, which calculates the nonce using the following formula (assuming SHA256 message hashes and 256-bit private keys):

$H = SHA256(message)$
$V_{0} = concat(0x1, 256)$
$k_{0} = concat(0x0, 256)$
$k_{0} = HMAC{\text -}SHA256(k_{0}, V_{0} || 0x00 || bytes(x) || bytes(H))$
$V_{0} = HMAC{\text -}SHA256(k_{0}, V_{0})$
$k_{0} = HMAC{\text -}SHA256(k_{0}, V_{0} || 0x01 || bytes(x) || bytes(H))$
$V_{0} = HMAC{\text -}SHA256(k_{0}, V_{0})$
$k_{i+1} = HMAC{\text -}SHA256(k_{i}, V_{i} || 0x00)$
$V_{i+1} = HMAC{\text -}SHA256(k_{i+1}, V_{i})$
$\dots$

Where $H$ is the hash of the message, $concat(b, n)$ concatenates the byte $b$ to itself $n$ times, $x$ is the private key in bytes, and $i$ starts from 0 and increases by one on every iteration until a valid nonce for $k$ is found. It nearly always needs only one iteration to get a valid $k$ .

The nonce must never be re-used to generate cryptographic signatures, whether for trasactions or for signed messages, because the private key can be cracked by rearranging the message signing equation $s = (h+xr)/k \mod n$ ( $r$ and $s$ represent the ECDSA signature), and solving $(h_{1}+xr_{1})/s_{1} = (h_{2}+xr_{2})/s_{2}$ by rearranging the equation:

$\frac{h_{1}+xr_{1}}{s_{1}} = \frac{h_{2}+xr_{2}}{s_{2}}$
$s_{2}(h_{1}+xr_{1}) = s_{1}(h_{2}+xr_{2})$
$s_{2}h_{1}+xs_{2}r_{1} = s_{1}h_{2}+xs{_1}r_{2}$
$xs_{2}r_{1}-xs{_1}r_{2} = s_{1}h_{2}-s_{2}h_{1}$
$x(s_{2}r_{1}-s{_1}r_{2}) = s_{1}h_{2}-s_{2}h_{1}$
$x = \frac{s_{1}h_{2}-s_{2}h_{1}}{s_{2}r_{1}-s{_1}r_{2}}$

A similar analysis can be done against RFC 6979 deterministic nonce generation by obtaining the raw transactions or message bytes, and attempting to work on the HMAC-SHA256 inputs and results to find an equation for the two nonces $k_{1}$ and $k_{2}$ . For example, observe what happens when the nonces form a linear equation $k_{1} = mk_{2} + c$ :

$\frac{h_{1}+xr_{1}}{s_{1}} = m\frac{h_{2}+xr_{2}}{s_{2}} + c$
$s_{2}(h_{1}+xr_{1}) = ms_{1}(h_{2}+xr_{2}) + cs_{1}s_{2}$
$s_{2}h_{1}+xs_{2}r_{1} = ms_{1}h_{2}+xms{_1}r_{2}+cs_{1}s_{2}$
$xs_{2}r_{1}-xms{_1}r_{2} = ms_{1}h_{2}-s_{2}h_{1}+cs_{1}s_{2}$
$x(s_{2}r_{1}-ms{_1}r_{2}) = ms_{1}h_{2}-s_{2}h_{1}+cs_{1}s_{2}$
$x = \frac{ms_{1}h_{2}-s_{2}h_{1}+cs_{1}s_{2}}{s_{2}r_{1}-ms{_1}r_{2}}$

Thus, a private key with a linear nonce equation $k_{1} = mk_{2} + c$ can be computed using $x = \frac{ms_{1}h_{2}-s_{2}h_{1}+cs_{1}s_{2}}{s_{2}r_{1}-ms{_1}r_{2}}$ . Similar formulas might be possible to derive for $k_{1} = a^{k_{2}}$ , $k_{1} = SHA256(k_{2})$ , and so forth.

What does all this have to do with Schnorr?

You see, Schnorr signatures use the same kind of cryptographic operations (point addition, point multiplication, modulus etc.), although the algorithm is completely different from ECDSA. ECDSA’s algorithm is comparativly simple and therefore it is relatively easy to equate two nonces together and solve for the private key, as I have just demonstrated. But Schnorr’s algorithm is very complex and uses tagged hashes in many cases. A tagged hash is simply SHA256(SHA256(prefix_bytes) || SHA256(prefix_bytes) || data), where data is the actual data being hashed. This protects the resulting hash from preimage attacks. Since there is no known solution for $a = SHA256(b)$ , it is extremely difficult to equate the two nonces as for ECDSA, since you’d have to break SHA256 by finding a collision.

To be specific, the r,s signature of Schnorr has $r = kG$ and $s = k + ex$ , where $e$ is some super-strong number generated from doing a bunch of tagged hashes. So even if you knew the nonce $k$ , you can’t find $e$ because Taproot signatures reveal $r$ and not $e$ .

But even that cannot protect you when ECDSA and Schnorr signatures are used with the same private key. That is because, the raw transaction hex for Taproot and other kinds of addresses are predictable, since their format is explicitly described in several BIPs. And since private key recovery is possible against ECDSA signatures (see above), if the nonce is generated deterministically using something like RFC 6979, this will be a mortal blow to the Schnorr signature’s security: you can simply craft a message that is the corresponding Taproot raw transaction hex for the non-taproot transaction, and from there, all you have to do is break the hash function guarding the nonce – and you already have the second nonce from ECDSA. There could be multiple layers of hashing, but it won’t matter when a pre-image attack is being carried out.

So when (not if) a SHA256-breaking computer is invented, your private key will immediately be compromised, as the attacker will have a nonce equation and can solve for the private key. Such attacks are not practical today, but you should not unnecessarily leave your funds vulnerable to such careless mistakes. After all, it’s common to leave bitcoins untouched for years.

The takeaway from all this is to generate your nonces properly; with random bytes, from a CSRNG. Deterministic nonces are a security risk.

Ali Sherief

Editor-in-chief and serial coder & blogger.

Subscribe our latest updates

Don't miss out. Be the first one to know when a new guide or tool comes out.

Support Us ❤

Creating learning material requires a lot of time and resources. So if you appreciate what we do, send us a tip to bc1qm02xguzxxhk7299vytrt8sa8s6fkns2udf8gjj. Thanks!