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

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.

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

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

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!

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

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

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

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?

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

We know and every message here is pointing this out.

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.

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

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

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.

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.

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.

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


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

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.

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.

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?

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