How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys

[stv]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

I think this is some kind of a technical issue, so I put it into this sub-forum.

As most of you should know, (regular) Bitcoin transactions are authenticated through ECDSA signatures. An ECDSA signature is a pair “(r,s)” of two numbers, where the first one “r” is completely independent from the signed message and the signing user's (public or private) keys. It is dependent solely on a random number “k” chosen at the time of signature generation, and on the underlying elliptic curve and its generator (secp256k1 in the case of Bitcoin).

Due to how ECDSA works, this value “k” has to stay secret, because the knowledge of “k” for a single signature already enables an attacker to compute the private key. Various security issues arouse from the fact that this secret “k” has to be chosen during signature generation. Poor wallet implementations selected “k” in a predictable way and enabled attackers to steal coins. Another known weakness arises if the same number “k” is used in two different signatures. If this happens, an attacker is able to compute the private key as well, even if the value of “k” is not known to him. Note that it is easy to detect whether “k” has been used twice, because it results in two signatures with the same value of “r”.

I want to draw your attention to another attack, that (to my knowledge) has not been discussed in the context of Bitcoin yet, which also arrives from the fact that the wallet implementation freely chooses “k”:
a) It is possible to leak secret information about the private keys.
b) This can be done in such a way that is impossible to detect by anybody other than the attacker himself.
c) Two signatures from the same private key are sufficient to leak the full key.

This enables a malicious implementation of a Bitcoin wallet to leak private keys, even in an offline setting which actually guarantees that no information except compliant transactions leave the wallet.

Note that this attack does not only affect closed-source wallets with potentially malicious features. Every implementation of ECDSA that cannot be verified by the user is a potential risk. This includes huge libraries like OpenSSL because its sheer hugeness, as well as any implementation optimized for performance or timing-attack resistance. One could argue that it would be the best for offline wallets to use a completely easy implementation of ECDSA. Due to its offline nature, timing attacks are irrelevant, and performance is not that important as well as you don't need millions of signatures per second in the Bitcoin protocol.

I wrote down the details of this attack in a paper, which you can find here:
https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/

Comments are very welcome, I am looking forward to an interesting discussion of this attack.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)

iF4EAREIAAYFAlSBvPIACgkQzNQUeKMPfH9fTAD+IOxTzXlP+j6UsKYMCH4AP+eF
qXxHKdcn5By67EY8cg8A/3G62zp55OMVXzsLFzNCcA5PfvKpYu2KgM/1XRkPV5Gq
=bKDi
-----END PGP SIGNATURE-----

[1714957429]

1714957429

[1714957429]

1714957429

[1714957429]

1714957429

[gmaxwell]

I want to draw your attention to another attack, that (to my knowledge) has not been discussed in the context of Bitcoin yet, which also arrives from the fact that the wallet implementation freely chooses “k”:

It's been discussed several times. E.g. https://bitcointalk.org/index.php?topic=285142.msg3077694#msg3077694 and http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02721.html

Because of it I pushed very hard for embedded hardware implementations (which make the ECDSA inherently somewhat unaudiable to use derandomized dsa... which helps but not completely since it could choose to leak only very infrequently such that a random audit wouldn't catch it.

To convince them, I created an implementation of ECDSA signing with the following fun properties:

(1) A single signature leaks the private key but only to the attacker and no one else even if they know about the back door.
(2) If you collect slightly more than 16 signatures, with different or identical keys, from a single victim the attacker (and no one else) can, with exponentially increasing probability, recover an additional 256 bit secret, such as a master private key.
(3) The signing was stateless (didn't require additional memory outside of the ecdsa signing function, and determinstic-- would always give the same signatures for the same key,message regardless of repetition or which order they were input.

An obvious path for improvement would be to use a blinded signature, but doing so would prohibit the signing device from verifying the message, which is something we usually want, without an additional ZKP.

[CIYAM]

I had thought that the idea of making k deterministic rather than random was a better solution all around (and from memory there is already an RFC that describes exactly how this can be done).

[gmaxwell]

I had thought that the idea of making k deterministic rather than random was a better solution all around (from memory there is already a RFC that describes how this can be done).

Just "deterministic" is not a complete fix though it can help.. because while it's deterministic someone who doesn't know the private key cannot tell if the procedure has been followed. You can use two independently created signers that both know the private key and compare their outputs, however... which is past of why I was trying to get people to use a canonical implementation and not some adhoc construction for derandomization.

[CIYAM]

...use a canonical implementation and not some adhoc construction for derandomization.

Isn't that exactly what the point of the RFC is (i.e. every implementation should have exactly the same result if they have followed the RFC correctly)?

[gmaxwell]

Isn't that exactly what the point of the RFC is (i.e. every implementation should have exactly the same result if they have followed the RFC correctly)?

Yes.  But the RFC makes a (IMO) strategic error of using a convoluted explanation motivated by showing that the construction is identical to a pre-existing standardized CSPRNG.  As a result, some implementers in the Bitcoin space vomit all over it and just implement something adhoc like H(key || message). Arguably people who do this have no business authoring cryptographic software for other people to use, but we live in a world where-- for various reasons-- people who have no business writing cryptographic software for others to use sometimes do.

Still, the solution is not complete... since how many users are going to use two independent implementations and compare all their outputs just to check for side-channels?

[CIYAM]

Still, the solution is not complete... since how many users are going to use two independent implementations and compare all their outputs just to check for side-channels?

Perhaps a better RFC might help (or maybe a BIP)?

IMO having a "standard" is the key thing (provided it works as expected and being deterministic can be easily tested for conformance).

Being a big fan of "regression tests" I have found ECDSA sigs to be a bit of a PITA.

[gmaxwell]

Perhaps a better RFC might help (or maybe a BIP)?
IMO having a "standard" is the key thing (provided it works as expected and being deterministic can be easily tested).

A standard is important. And yes, we could restate RFC6917 in a way more people would find easy to implement from a BIP... and that might be wise. But really in the bitcoin space far far too many people are writing their own cryptographic code, and are making little to no effort to implement best practises in other ways either.  E.g. prior to libsecp256k1 I am aware of no implementation for secp256k1 which has even attempted to close the timing sidechannels.  Ideally, there should exist a good, well reviewed, library of the systems work that other people are not going to bother making a best-practises implementation of...

From the discussion, It's not clear to me if I'm clearly explaining why I keep saying it's not enough:  The problem is that your evil device can follow the RFC until asked to sign a transaction paying a particular destination or every 1000th time at random and never in the first 100 signatures... and so you cannot test for non-evilness unless you test every output.  It's possible to test every output (assuming the implementation uses a standard), but basically no one will.   It ups the bar, narrows the exposure, etc... but without additional magic it doesn't eliminate the risk. This is also one reason that offline signing isn't a replacement for multi-signature.

[CIYAM]

It's not clear to me if I'm clearly explaining why I keep saying it's not enough:  The problem is that your evil device can follow the RFC until asked to sign a transaction paying a particular destination or every 1000th time at random and never in the first 100 signatures... and so you cannot test for non-evilness unless you test every output.

Yes - I understand that - I wasn't concerning myself with "evil implementations" but just wrong ones (that might leave you open to more simple attacks).

This is also one reason that offline signing isn't a replacement for multi-signature.

Also understood (and perhaps Shamir's is another method when one is considering protecting large amounts of offline funds).

[stv]

Deterministic choice of “k” unfortunately does not solve the issue, because you cannot verify that choice without knowledge of the private key. Since the whole point of an offline/embedded wallet is that the key never leaves the wallet, there is no way for a user to verify that “k” has been chosen according to RFC6979 or anything alike. Since “k” has to be secret, there is no way to solve this. This is discussed in the paper as well.

Classic ECDSA:
Knowledge of “k” implies knowledge of (private key) “d”, but not the other way around.

Deterministic ECDSA:
Knowledge of “k” equals knowledge of “d” and vice versa.

[CIYAM]

Deterministic choice of “k” unfortunately does not solve the issue, because you cannot verify that choice without knowledge of the private key.

Understood - but the offline device does have the private key and presumably could display that, and if it can do that then it could also display the "k" value that could then be audited via another offline device.

[stv]

Understood - but the offline device does have the private key and presumably could display that, and if it can do that then it could also display the "k" value that could then be audited via another offline device.

Yes, but that only shifts the trust from one offline device to the next. You have to know that any of them is properly doing their job. Looking whether the “offline verification device” is doing its job is not any easier than looking whether the offline wallet does implement ECDSA according to the standards.

[CIYAM]

Yes, but that only shifts the trust from one offline device to the next. You have to know that any of them is properly doing their job. Looking whether the “offline verification device” is doing its job is not any easier than looking whether the offline wallet does implement ECDSA according to the standards.

So do you think that multisig or Shamir's would solve the issue (as I am not clear how you could ever create a *perfect* system - maybe such a thing is not actually possible)?

[stv]

(1) A single signature leaks the private key but only to the attacker and no one else even if they know about the back door.
(2) If you collect slightly more than 16 signatures, with different or identical keys, from a single victim the attacker (and no one else) can, with exponentially increasing probability, recover an additional 256 bit secret, such as a master private key.
(3) The signing was stateless (didn't require additional memory outside of the ecdsa signing function, and determinstic-- would always give the same signatures for the same key,message regardless of repetition or which order they were input.

Very interesting. I will take a look at your attack.

[gmaxwell]

Deterministic choice of “k” unfortunately does not solve the issue, because you cannot verify that choice without knowledge of the private key.

We know and every message here is pointing this out.

Since the whole point of an offline/embedded wallet is that the key never leaves the wallet, there is no way for a user to verify that “k” has been chosen according to RFC6979 or anything alike.

That may be the point for _you_, but really the point is to be offline, transfering a key between two offline devices is an option for some.. it's certainly an option for testing... and even simply testing increases your assurance, though its not a complete assurance for the reasons enumerated.  E.g. without determinism every device off the factory line may be leaking your keys in every signature, and no one could tell short of a successful reverse engineering of the device.  With determinism, the evil could only be intermittent and escape discovery ... since just a single user loading a static test key and checking the output would catch the case where device device leaks in every signature.

If your offline device is just a HSM that signs everything then there is an obvious solution: blind the signatures. It's trivial with schnorr but even for ECDSA there is a scheme which should work for this.  Otherwise, multisignature seems to be the only reasonable fix.   Any of the ZK proofs are too complex and expensive in the prover.  Your paper suggests the device create the proof, but thats likely out of the question complexity wise for many signers (running a k*G under a ZKP is a very expensive computation), better would be to blind the signature and then use the ZK proof to prove to the device that the blinded signature is something it wants to sign... this works better because existing constructions have fast verifiers.

You have to know that any of them is properly doing their job

Yes, if you have no trustworthy devices you are simply out of luck. No system can save you.  If _all_ of your devices are concurrently bad they can just emit your key instead of a signature and your online hosts can simply call home to report it.

There must be some assumption of honesty.  A reasonable one is that you will use multiple devices and at least one of your devices will be honest, or at least not serving the same evil master.  Under that assumption secure systems can be built, without it no secure system can be built.

Understood - but the offline device does have the private key and presumably could display that, and if it can do that then it could also display the "k" value that could then be audited via another offline device.

Showing K doesn't seem prudent.  Better to just sign twice and compare the results: they should be identical.  If you really wanted to show K, better to show H(K).  Otherwise someone could just use the revealed K to immediately compromise the security if they could see the device's screen.

[CIYAM]

Showing K doesn't seem prudent.  Better to just sign twice and compare the results: they should be identical.  If you really wanted to show K, better to show H(K).  Otherwise someone could just use the revealed K to immediately compromise the security if they could see the device's screen.

Indeed one does have to worry about nasties like cams taking shots of your offline computer's screen.

[stv]

So do you think that multisig or Shamir's would solve the issue (as I am not clear how you could ever create a *perfect* system - maybe such a thing is not actually possible)?

I haven't looked into those yet. The best solution I can imagine so far would be a combination of the following:

1.) Deterministic choice of “k” given a certain Standard (RFC6979 or maybe EdDSA's way of doing it)
2.) Zero-knowledge proof of the fact that “k” has indeed been chosen according to the procedure.

This would be perfectly possible, as the statement “there exists an skey such that: k equals H(skey||message||salt) and pubkey equals generator point multiplied by skey” obviously is an NP statement and there exist non-interactive zero-knowledge proofs for any NP statement.

Note that this would not change anything for the Bitcoin protocol. The proof is just for the user himself to verify that his wallet is working properly, it does not have to be sent into the Bitcoin network.

But a new problem arises: How to implement the proof in a way that ensures that we don't create new side channels for leakage?

[gmaxwell]

But a new problem arises: How to implement the proof in a way that ensures that we don't create new side channels for leakage?

Any system that has sound zero knoweldge is going to have a random input.  E.g. the CRS SNARK construction which is the only remotely practical implementation for NP available that I'm aware of is freely rerandomizable. Maybe a unique proof is possible if you give up soundness on the ZK but then a cryptographic break in the ZK system could make it leak your private key.

This complexity is part why I'd previously proposed the alternative where the online requesting device blind the signature request,  then give the signing device a ZKP that the blinded message being signed is the message being signed...  The result is the that the sidechannel is reduced to 1 bit (sign/don't sign) unless the requesting device and the offline device conspire. (also the aforementioned fact that it's much easier to verify a proof than create it)

From your writeup,

Another counter-measure would be to strictly not use any address more of-ten than once

This doesn't solve it: The key can be leaked in a single signature, and the attacker can race the user in the network; and 'future' keys, if they're known to the device can also be leaked at the same time using the techniques I've described.

[CIYAM]

It seems to me that using multisig or Shamir's would be technically much simpler than trying to use complicated (and not very well battle tested) stuff like zero-knowledge proofs (admittedly those are beyond my current technical skills to really understand).

For any organisation that has a lot of offline BTC to protect I am pretty sure they'd always want to have those funds locked up by several offline devices rather than one anyway.

(so I am not really sure if the problem needs to be solved at all - i.e. why is this actually needed?)

[stv]

@gmaxwell:
I agree with you that ZK is very expensive and hard to secure. With “best I can imagine so far” I wanted to express that I am very unsatisfied with any proposed solution so far.



Btw: Can you point me to a text where you argue why your (second) attack is undetectable?

Update: Pardon, you never claimed that. You just said that only the attacker can decrypt the leaked data. Then this is a difference between our attacks, since my malicious signatures are provably indistinguishable from regular ones.