Topic: How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys (Read 6237 times)

Thanks for trying, I appreciate it.

ECDSASigner is a bouncycastle class that accepts an optional provider for the nonce https://github.com/bcgit/bc-java/blob/master/core/src/main/java/org/bouncycastle/crypto/signers/DSAKCalculator.java.

The implementation of ECDSASigner will pass the secret to the k calculator.
It's done in

Then it comes to DSAKCalculator through
which is Scala for

The rest is RFC6979.

I wrote this wallet because there is no implementation that fits my need and that I feel confident enough with. Basically for the same reasons that you mention. The most popular wallets don't have the features I want and the others are not reviewed enough to qualify either. I tried to reduce risk as much as I could by using standard libraries where possible. It leaves BIP32, RFC6979 and tx serialization to write. It's hard but I wouldn't call this impossible to do. I welcome as much review as possible. Maybe you could take a look?

Thanks,
--h

I tried to give it a quick glance at least, but I'm unfamiliar with the language... and when I couldn't even tell how the private key was being passed to the nonce generation function I gave up.

Though it is the case that whatever glance I would have given it wouldn't really be enough to de-risk it compared to widely reviewed code... I figured a glance would be the least I could do. Well, seems not, a failed glance was the least I could do.

I think he meant code revision in general, not just for this single potential bug. You can't just review a Bitcoin wallet by reading it once or twice, it's way too complicated. So better stick with known code that has some user base actually testing it.

If someone would like to review my code, I'd be glad - https://github.com/hhanh00/offlinesig - but it's not easy to get someone to do it.
I didn't rewrite a crypto library. I used bouncycastle and provided a generator for k following the RFCxxxx. The only values exchanged are (r, s) and I don't see any other sidechannel since it works offline.

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.

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

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.

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.

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.)
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”.

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

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.

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.

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.

Interesting.

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.

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.

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.

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 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!

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

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.

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.

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.

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.

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.

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.



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.