How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys

[hhanh00]

If the signing device is offline and the implementation of the deterministic signature trusted to follow the prescribed algorithm, what sidechannels attack do you see?

In other words, the online device transfers the digest and pubkey to the signer. The signer returns (r, s) where k follow RFC 6979. The online device builds the transaction and the user checks that the inputs/outputs are what he expects.
Can something still go wrong?

[gmaxwell]

@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.

Mine are computationally indistinguishable to anyone to anyone but the attacker and the party that knows the key (or I had another version that was only distinguishable to the attacker or someone with the private key and a random nonce from the device; but its not deterministic).   I think your definition of indistinguishable is a bit limited: emitting related nonce values is pretty distinguishable!

[stv]

Mine are computationally indistinguishable to anyone to anyone but the attacker.  

Can you point me to a detailed description of your attack? It seriously interests me.

I think your definition of indistinguishable is a bit limited: emitting related nonce values is pretty distinguishable!

They are related, but in the process of creating the second from the first a PRNG is used, and certain parameters enable the attacker to ensure that his value of k inherits the PRNG's “indistinguishability”.

[tl121]

I think I may be missing something in the discussion here.

You can never test a program as a black box to see if it is correct except by exhaustively testing all possible inputs, and even then only if the program has no internal state.  If you want to trust a bitcoin device that has your private keys you won't be able to test all possible inputs. So you will be forced to rely on a trusted computing base. The TCB doesn't have to include all the bitcoin software, but it does need to include all the hardware and the bootloader, plus there has to be a trusted method of going from vetted source code to load images that doesn't get caught by the Ken Thompson hack.

Using multiple signatures is not going to get around problems caused by untrustworthy software, especially if the software used for multiple signatures is the same and hence contains the same trap doors.  If there are diverse implementations this may help, but the high availability software people have found problems with this approach as regards software bugs.  Multiple signatures deal with issues of untrusted human agents, failing hardware and physical security.  However, they don't eliminate the need for trusted computing platforms and trusted software.  Furthermore, they are complex and hence more likely to provoke "cockpit error" by their users.

IMO the greatest problem with widespread adoption of bitcoin is security in the hands of ordinary users.  This issue dwarfs the scaling issue.

[stv]

I think I may be missing something in the discussion here.

You can never test a program as a black box to see if it is correct except by exhaustively testing all possible inputs, and even then only if the program has no internal state.  If you want to trust a bitcoin device that has your private keys you won't be able to test all possible inputs.

The attacks presented by gmaxwell and me go even further. Even if you would ensure that the inputs and outputs are correct, you cannot detect the malicious behavior, because the outputs provably look like regular outputs, i.e. they are following a statistical distribution that cannot be distinguished by any efficient algorithm.

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)

I don't get how this would prevent the leakage of private keys at all. My attack does not need to know what the message is, and it does not even need to know what the private key is. It just creates a choice of “k” in a way that enables the attacker to extract “k” from two signatures. If one knows how the wallet implementation works, it would be enough for this attack to just inject the right “random numbers” into the wallet's entropy source.

[gmaxwell]

I don't get how this would prevent the leakage of private keys at all. My attack does not need to know what the message is, and it does not even need to know what the private key is. It just creates a choice of “k” in a way that enables the attacker to extract “k” from two signatures. If one knows how the wallet implementation works, it would be enough for this attack to just inject the right “random numbers” into the wallet's entropy source.

Go look at what a blind schnorr signature looks like mathematically.  Without knowing the blinding factor the signer has zero knowledge about the resulting signature... it could literally have any value, so they're unable to grind it or pick it in a trapdoored way.

[dabura667]

Better to just sign twice and compare the results: they should be identical.

I found a company that was having unauthorized transactions from their corporate bitcoin address in small amounts over a long period. I asked to review their code, and the guy they hired to code the system had basically used H( tx ) where H is 281 rounds of sha256 as a "deterministic" k and had secretly stolen the private key by looking at the blockchain. (as the tx was public knowledge and the only secret was the iteration count... which he knew.)

Using your check twice method, signing the same tx twice would give the same k... but still be unsafe.

[gmaxwell]

Better to just sign twice and compare the results: they should be identical.

I found a company that was having unauthorized transactions from their corporate bitcoin address in small amounts over a long period. I asked to review their code, and the guy they hired to code the system had basically used H( tx ) where H is 281 rounds of sha256 as a "deterministic" k and had secretly stolen the private key by looking at the blockchain. (as the tx was public knowledge and the only secret was the iteration count... which he knew.)

Using your check twice method, signing the same tx twice would give the same k... but still be unsafe.

The check twice is assuming you use a second independently sourced device ("audited via another offline device"), sorry that wasn't clear. Certainly doesn't protect you against an insider! Wild to hear about that attack.

[hhanh00]

Better to just sign twice and compare the results: they should be identical.

I found a company that was having unauthorized transactions from their corporate bitcoin address in small amounts over a long period. I asked to review their code, and the guy they hired to code the system had basically used H( tx ) where H is 281 rounds of sha256 as a "deterministic" k and had secretly stolen the private key by looking at the blockchain. (as the tx was public knowledge and the only secret was the iteration count... which he knew.)

Using your check twice method, signing the same tx twice would give the same k... but still be unsafe.

The point is to check from two different devices that are supposed to implement the deterministic signature RFC. Blind signatures are good too unless both online & offline devices were compromised.

[stv]

I found some time to look into blinded Schnorr signatures now. It does not prevent my attack, but it indeed makes a practical application of my attack harder. The values “R = kG” and thus information about the private keys are still leaving the offline wallet. But it is not displayed in the transaction any more.

In addition, this solution is not compatible with classic ECDSA, it requires a change to the protocol. This is not required in my proposal of deterministic “k” plus proof.

I think the problem that ZK proofs are comparatively slow is a minor issue in comparison. If a user wants to make a transaction with an offline wallet, it requires time anyway (let alone the time for confirmations). Even if the proof requires minutes to generate and megabytes to store, it does not really matter. The proof is created for the user himself, and he only has to verify it once, he can forget it afterwards. It has NOT to be sent to any other Bitcoin peer and it has not to be stored in the blockchain or anywhere else. If a user transfers his transaction from an offline wallet via a removable medium or something, the size and time is not really that big of an issue. This solution makes sense for some use cases. Note that I don't claim that this is perfect for every Offline wallet setup and use case. Every user* has to decide himself what requirements of security, performance etc.


*) I mean power users who care about offline wallets, e.g. professional users like online merchants or exchanges.

[gmaxwell]

I found some time to look into blinded Schnorr signatures now. It does not prevent my attack, but it indeed makes a practical application of my attack harder. The values “R = kG” and thus information about the private keys are still leaving the offline wallet. But it is not displayed in the transaction any more.

It would require a conspiracy with the host device.  Such a conspiracy can simply not be prevented... e.g. if _Every_ device you have is lying to you about what transaction you're authorizing you could be authorizing anything.

In addition, this solution is not compatible with classic ECDSA, it requires a change to the protocol. This is not required in my proposal of deterministic “k” plus proof.

Yes, it requires schnorr signatures. Which is why it's not in use yet in Bitcoin; though we have soft plans to adopt schnorr signatures for many other reasons in any case.

I think the problem that ZK proofs are comparatively slow is a minor issue in comparison. If a user wants to make a transaction with an offline wallet, it requires time anyway (let alone the time for confirmations). Even if the proof requires minutes to generate and megabytes to store, it does not really matter.

I think it matters greatly... you're certainly not going to see a trezor like device generating such at thing.  And, as you noted... the ZKP has freedom and can create a side-channel.  (and I believe thats inherent if the zero knowledge is perfect). On the plus side, you can prevent the attacker from seeing the proof, which would help.

To create some perspective. The creators of Trezor did not want to use a strong KDF for their user provided keys (which are likely to be brain wallets) or (initially) derandomized DSA all because of performance constraints. Any ZKP for general computation is going to be millions of times more costly in cycles and ram.

I'd love to see someone create it, none the less!

The proof is created for the user himself, and he only has to verify it once, he can forget it afterwards.

Right, so if the users separate computer is in a conspiracy with the device all is lost... which is why multi-signature is a good tool for use today (or blinding would be one, if it were available yet).

[stv]

It would require a conspiracy with the host device.  Such a conspiracy can simply not be prevented... e.g. if _Every_ device you have is lying to you about what transaction you're authorizing you could be authorizing anything.

Depends on what kind of attack you are looking at. As I said, a full attack application on Bitcoin requires some additional steps. But even without that, it is an attack with the “offline property”.

The host does not really have to actively do anything. All information about the keys may eventually be on the host, and only the attacker can know that. It would have to be offline as well.

Yes, it requires schnorr signatures. Which is why it's not in use yet in Bitcoin; though we have soft plans to adopt schnorr signatures for many other reasons in any case.

Interesting.

I think it matters greatly... you're certainly not going to see a trezor like device generating such at thing.  And, as you noted... the ZKP has freedom and can create a side-channel.  (and I believe thats inherent if the zero knowledge is perfect).

Yes, it is not suitable for an embedded wallet, but that is not the only offline wallet. For a disconnected PC this wouldn't be a problem.

On the plus side, you can prevent the attacker from seeing the proof, which would help.

Yes, but that is no different to your blind-signature solution. If your host successfully keeps the messages from the protocol secret, it would be fine. And both (my proof or your protocol messages) don't have to be stored after once used/verified.

[gmaxwell]

Yes, but that is no different to your blind-signature solution. If your host successfully keeps the messages from the protocol secret, it would be fine. And both (my proof or your protocol messages) don't have to be stored after once used/verified.

Yup agreed. But multisignature works today, and is secure under basically the same assumptions (that one of the two is not evil), and can protect against some additional failure modes e.g. someone steals the offline signer. So thats what I currently strongly recommend.

[stv]

So thats what I currently strongly recommend.

I second your recommendation as a current solution, together with the obvious recommendation to always prefer verifiable implementations.

But it does not make me stop thinking about new solutions, and the fact that the two of us are searching in different directions will only make us richer.

[youngmike]

I don't know anything about development. Tell me about it

[stv]

In other words, the online device transfers the digest and pubkey to the signer. The signer returns (r, s) where k follow RFC 6979. The online device builds the transaction and the user checks that the inputs/outputs are what he expects.
Can something still go wrong?

Yes. “k” can be deterministic, but it has to be unknown, otherwise you can extract the private key “d” from “(r, s)”. In RFC6979, the choice of “k” depends on the private key “d”, it (hopefully) cannot be reproduced without it.

tl;dr thread summary:

gmaxwell's proposal based on blind Schnorr signatures prevents that by replacing the “r” component of a signature with a different value “r'” which depends on two random choices, only one of which is made by the offline wallet itself. “r” is still generated in the process, but not published into the blockchain.
Problems:
-- The original “r” has to be kept secret.
-- Schorr signatures are not compatible with ECDSA, so this solution requires a change of the Bitcoin protocol.

In my proposal using ZK proofs, the offline wallet outputs a proof “p” together with the signature “(r, s)”, where “p” proves the following statement: (“Q” is the public key, “m” the message.)

Code:

There exist integer numbers “d”, “x”, “k” such that: Q=dG AND k=H(m||d) AND (r, x) = kG.

Since the formula has only existentially quantified variables, it is an NP statement and we know that there exist ZK proofs for it. Since the wallet knows the witnesses “d” and “k”, it has all the knowledge necessary to generate such a proof “efficiently”.
Problems:
-- How to make sure that the wallet does now leak secrets through the proof, as most ZK proofs require lots of random choices by both parties (prover and verifier).
-- Alternatively the proof has to be kept secret like the original “r” in the blind Schnorr signature scheme.
-- How to make the proof efficient enough for practical applications, especially the part “k = H(m||d)” for a complicated cryptographic hash function “H”.

[hhanh00]

Thanks, I trust my offline wallet implementation of the rfc as much as I can. Under this condition, is there an attack?

I know about binding signatures from open transaction and zkp from zerocash but it seems to be accademic for the moment.

[stv]

Thanks, I trust my offline wallet implementation of the rfc as much as I can. Under this condition, is there an attack?

The whole attack scenario here is about malicious wallet implementations. If your wallet implementation is doing what it is supposed to do, everything is fine, even if it is not deterministic.

Note that there is no way to tell that from looking only at the resulting transactions, as the attacker hides the leak well. You have to make sure that you (or a person you trust) know the code, understand the code and actually know that the source code you have actually matches the code that is running on the offline wallet.

This is a theoretical/technical discussion about a potential attack and suitable counter-measures. There are no documented cases of this attack being done.

[hhanh00]

Ok. I wrote my wallet app partly because I thought about this vulnerability too. One can't be too careful.

[gmaxwell]

Writing your own software has its own risks. I wouldn't trust crypto code that hasn't been peer-reviewed, even if I wrote it myself.