Pages:
Author

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

sr. member
Activity: 467
Merit: 267
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
Code:
    val kGen = new RFC6979KCalculator
    val signer = new ECDSASigner(kGen)

    val params = new ECPrivateKeyParameters(secret.bigInteger, Bitcoin.ecDomain)

Then it comes to DSAKCalculator through
Code:
  override def init(q: BigInteger, x: BigInteger, m: Array[Byte]): Unit
which is Scala for
Code:
    /**
     * Deterministic initialiser.
     *
     * @param n the order of the DSA group.
     * @param d the DSA private value.
     * @param message the message being signed.
     */
    void init(BigInteger n, BigInteger d, byte[] message);

The rest is RFC6979.

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

staff
Activity: 4242
Merit: 8672
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. Smiley

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.
full member
Activity: 168
Merit: 103
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.

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.
sr. member
Activity: 467
Merit: 267
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.
staff
Activity: 4242
Merit: 8672
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.
sr. member
Activity: 467
Merit: 267
Ok. I wrote my wallet app partly because I thought about this vulnerability too. One can't be too careful.
stv
newbie
Activity: 27
Merit: 0
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.
sr. member
Activity: 467
Merit: 267
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
newbie
Activity: 27
Merit: 0
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”.
sr. member
Activity: 252
Merit: 250

I don't know anything about development. Tell me about it Smiley
stv
newbie
Activity: 27
Merit: 0
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. Smiley
staff
Activity: 4242
Merit: 8672
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
newbie
Activity: 27
Merit: 0
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.

Quote
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. Smiley

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

Quote
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.
staff
Activity: 4242
Merit: 8672
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.

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

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

Quote
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
newbie
Activity: 27
Merit: 0
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.
sr. member
Activity: 467
Merit: 267
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.

staff
Activity: 4242
Merit: 8672
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.
sr. member
Activity: 475
Merit: 252
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.
staff
Activity: 4242
Merit: 8672
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.
stv
newbie
Activity: 27
Merit: 0
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.
Pages:
Jump to: