Tell HN: It looks like even air gapped Bitcoin hardware wallets can phone home
https://news.ycombinator.com/item?id=32115693
Interestingly, there was a lot of speculation and misinformation. So even on Hacker News, this topic is still only vaguely understood.
But also some very good information came to light.
The biggest bomb that was dropped in the thread received little attention: The fact that signing a transaction is not deterministic. This means when a hardware wallet is asked to sign a transaction, it can internally do that multiple times and then chose from multiple valid signatures. This means that it can encode data into the signature. For example, it could choose between two signatures with certain properties (say one results in an even checksum of the bits of the signature and one results in an odd checksum) and thereby signalling one bit to the creator of the wallet.
Everytime it signals a bit of your seed phrase home, the security of your coins is cut in half.
Here is an article about the fact that elliptic curve signatures are not deterministic:
https://medium.com/@simonwarta/signature-determinism-for-blockchain-developers-dbd84865a93e
The way I understand it, the wallet can chose from a large number of possible signatures and thereby signal many bits to its creator. In every transaction.
I think a dicsussion about this should be started. The way I understand it, it makes it completely impossible to use Bitcoin in a trustless way. Even with an air gapped hardware wallet, you are always at the mercy of the wallet manufacturer and the delivery chain that gets the wallet to you. If it gets swapped out on the way to you, you are at the mercy of whoever swapped it out.
53 comments
[ 2.9 ms ] story [ 97.1 ms ] threadIf so: The question was if Bitcoin can be used trustless.
If not: How would you check that the hardware wallet in your hand runs the open source code you trust?
The only fix I can think of would be to evaluate the hardware signatures using statistical tests to try to pick up any bias. This would be a burden on the user, but at least feasible.
Interesting idea with the bias checking. Not sure if it is possible. If it is, it would probably need very clever software to do that. One that bombards the hardware wallet with a big number of seeds and transactions and checks if it can find indications of the seeds having an impact on the signatures.
Indeed - and thanks a lot for the link, that was a super interesting reading!
> The way I understand it, the wallet can chose from a large number of possible signatures and thereby signal many bits to its creator. In every transaction.
Isn't it possible to make that deterministic by adding some rank-ordering heuristic? (ex: always prefer the smallest numerical signature, or with the most consecutive numbers etc)
Then if 2 wallets from 2 different providers disagree, you would know there's a problem!
In a way, it would be doing like in reproducible software builts: controlling the randomness, except it would be done ex-post (ranking the possible choices and selecting one) instead of ex-ante (setting the clock etc).
If that's impractical, a simpler way may be to require the wallet to make say 100 possible signatures, but then randomize which one is used in another independent step.
Also, from the article:
>> “deterministic signing” means that at least one deterministic way to generate signatures exist. It does not imply that a signer can only generate one valid signature. Due to the nature of the signing algorithms, an observer cannot detect if a standard algorithm or a customization was used.
The core problem seems to be that the hardware device obfuscates the algorithm, which should be less of a problem with software you can compile.
> Even with an air gapped hardware wallet, you are always at the mercy of the wallet manufacturer and the delivery chain that gets the wallet to you.
That's because of the above: you need to control for different things (ex: good source of randomness, correct implementation of the algorithm etc)
Can you trust your compiler, though? What if it changes the algorithm when it compiles your source code?
(See also "Reflections on Trusting Trust" by Ken Thompson: https://www.win.tue.nl/~aeb/linux/hh/thompson/trust.html)
At the end of the day nothing can be achieved if you don't have a trusted device to compare your untrusted device against. Bitcoin's threat model assumes that the client device is trusted.
https://news.ycombinator.com/item?id=32115693
The question was if it is at all possible to use Bitcoin in a trustless way.
Several hard and maybe impossible to overcome challenges have come up in the thread. The fact that eliptic curve signatures are not deterministic seems to be the most fundamental.
The problem now is that you need a way for the wallet to prove to the user that this has been done, without leaking the nonce or key. There are a bunch of ways to do this, but the most basic idea is to generate a zero-knowledge proof (probably a zkSNARK) that shows correctness of the signature w.r.t. the public key. The user would not put this zkSNARK onto the network -- it might contain a covert channel of its own! -- they would just check it locally and then dispose of that part. (Of course if the wallet was stolen by a malicious user the wallet might be able to exfiltrate the secret key to this thief through the zkSNARK portion.)
I'm assuming that all other transaction information is chosen by the user, so there's no other latitude for the wallet to cheat.
A zkSNARK wouldn't improve random exfiltration, so both of these proofs are statistical unless inputs are tested exhaustivally to result in the pigeonhole principle for some bounded internal state.
RFC 6979 uses HMAC, which would make the proofs pretty painful. You would probably want to swap this for some more efficient primitive. It wouldn't matter for compliance with the network.
> Statically proving an unknown and black box wallet requires a trusted computational (as would verifying any proof) device
Yes, but this trusted computing device does not need to be connected to any network. It can be an airgapped computer (or even several airgapped computers sourced from different vendors and retailers), each running different software. There is still "trust" here but the degree of trust can be arbitrarily reduced, provided that you're willing to spend money and effort.
Verifying proofs using only human computation is pretty challenging.
> A zkSNARK wouldn't improve random exfiltration, so both of these proofs are statistical unless inputs are tested exhaustivally to result in the pigeonhole principle for some bounded internal state.
I'm not sure what you're saying. As I said up above in the thread, the zkSNARK is typically randomized and thus could be itself used as a covert channel, even if the signature is now (verifiably) deterministic.
But that's ok: the model I'm working with assumes that the wallet owner is trustworthy, and that any local computers they use to verify the proof are properly (physically) airgapped. The zkSNARK would be verified by the user first -- using (multiple pieces) of airgapped, trusted hardware -- then discarded. Only the final signature would ever reach a computer connected to the Internet.
If your concern is that the wallet owner and the network are both malicious,* then you're dead. (ETA: removed a note about deterministic ZK proofs, all that would let you do is detect that you're dead after the fact and only if you sent them to the network: it doesn't matter in this extreme threat model.)
* By the time your attacker has stolen the Bitcoin wallet and can force it to make signatures, you're basically toast anyway. So this does not seem like a good threat model to waste time on.
Consider bitcoin wallet M, that erases the private keys after n transactions? Either you trust your wallet does not do this, or you make copies and trust location/security/something else.
Trustless is a misnomer and was originally applied in the context of 3rd parties, nor computational devices in your own control running code you can theoretically verify.
A Bitcoin seed phrase is 128 bit. 32 bit can be easily brute forced. Leaves us with 96 bit. If you can send out 10 per transaction, that is only 10 transactions.
At no point in this process, short of physical access to the offline computer, is the ECDSA nonce ‘k’ known publicly, so I am not sure what you mean by it cutting your security in half with each transaction. If there are 256 bits in a nonce you would need to generate a lot of signatures for this to be a concern, and if you want to mitigate against this you could cycle through new private keys after every Nth signature.
Much more likely attack has to do with how you generated the random value k.
It is about the fact that even air gapped hardware wallets can phone home.
Posting a signature on a public ledger does not give information about nonce k which I think is what you are referring to. Each time a new transaction is signed, the k value will be a new random big integer.
If your wallet is able to leak bits in this way it would imply the value k is not chosen uniformly randomly. This is my understanding of ECDSA at least.
Note that I have very little understanding of blockchain crypto, so I am unable to confirm/deny the information OP gave. However, the way I understand the attack is:
Hardware wallet generates a private key. It keeps this key in internal storage. When a transaction is made, the wallet makes a signature. According to OP, there is a variable here (I'm guessing either multiple private keys, or the ability to choose a signature algorithm, or even embedding a timestamp in the transaction) which the hardware wallet can use to "leak" information.
Let's say the wallet decides to embed a timestamp. Whenever a bit in the private key is 0, the timestamp is even, and when a bit is 1, the timestamp is uneven.
After 4096 transactions, presumably the whole private key is now stored in the blockchain as even/uneven timestamps.
This is of course a very slow way of leaking the private key, but does illustrate the problem of having unverified devices be responsible for crypto results.
Assuming the mode of key signing is not compromised and is producing robust uniform randomness (whether it’s a hardware wallet, airgapped device or your own hand-rolled code) it shouldn’t leak anything per transaction that would lead to your private key being more easily discoverable.
OP's post is that since signatures are not deterministic you have no way to inspect device output and make sure that nothing subvert is going on.
Obviously you should not trust compromised devices, but you cannot know if such a device is compromised.
[1] http://karpathy.github.io/2021/06/21/blockchain/
You cannot necessarily do the same for nondeterministic computations in general. In this case you can easily verify that the signature is valid, but unless you control the rando parameters you cannot verify that a few bits of entropy have been exfiltrated by one or more parties in the computation.
In the simplest case you could with statistical methods but not with slightly more sophisticated attacks.
You can also code your own wallet like I mentioned before if you do not trust a hardware wallet manufacturer, but somewhere along the line you will probably need to trust something (like trusting the room you are doing this in is not bugged).
OTOH, your post also doesn't prove that the mass-manufactured hardware in question is actually malicious. At best, you've shown a way that it could be. Show me an actually malicious hardware wallet that behaves as you've described, and you'll have made your point. Until then, all you have is speculation and improbabilities.
In other words, charitably interpreted, you've shown that the hardware equivalent of the C compiler in "Reflections on Trusting Trust" could exist, just as the paper itself showed that such a C compiler could exist[0]. That is all. There is no evidence either one exists at all in the wild.
---
[0]: Which, I'll admit, is a pretty cool thought exercise, but has precisely zero real world impact.
I'm not the OP and although I agree with you, you may be interested in the corollary for a "stronger" attack than OP defined:
https://bitcointalk.org/index.php?topic=581411.0 and https://github.com/tintinweb/ecdsa-private-key-recovery
Constructing such an airgapped hardware wallet is as trivial as a raspberry pi running a patched bitcoin client. In my opinion the more realistic construction than a that of "Reflections in Trusting Trust".
In fact someone should prove that mathematically secure is a meaningless concept, if your devices are not physically secure.
Why do you think that was even worth posting? It's not a profound concept to say "if you don't follow the secure transaction protocol, your transaction will not be secure."
https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06...
To avoid this vulnerability, the industry best practice is to not generate k with a random-number generator seeded with entropy, but instead to use a deterministic-random process seeded with the transaction data itself. This ensures that each transaction produces a different k. The industry-standard algorithm for deterministic initialization of k is defined in RFC 6979, published by the Internet Engineering Task Force.
> If you are implementing an algorithm to sign transactions in bitcoin, you must use RFC 6979 or a similarly deterministic-random algorithm to ensure you generate a different k for each transaction.
(https://datatracker.ietf.org/doc/html/rfc6979)
But there must still be some source of randomness for k besides just the message data? Otherwise signing the same message twice (like re-connecting to a web3 app via signed message, no transaction involved) would reveal your private key.
> Can we ever trust any system?
Yes, to an extent. There is no such thing as a system that can be trusted completely, but we don't need it to be in 99% of cases. One might say "you can trust crypto primitive XYZ. If you use it, it would take 1 billion years to break". That might be true, but side-channel attacks, leaks, statistical biases and whatnot will always be an issue.
To get as close as possible to trust in a system, it needs to be formally verified with proofs. That's the best we can do program/algorithm wise, but even if we trust the program, it cannot trust the system it resides on.
> How can we achieve trust then?
You know how bitcoin is based on a distributed consensus algorithm? It protects the whole system from collapsing due to a bad actor in the system. Even if thousands of people decides to cheat, it won't have any considerable effect.
Let's say you buy a hardware wallet from a reputable vendor - if they decide to cheat, you will be at their mercy. To combat this, you need a way to verify that what it does, it does so correctly, but also without side effects.
This is again something that needs to be formally verified. Any deviation from the spec will stand out like a sore thumb. To achieve this, we need to introduce a verifier.
The verifiers job is to check if the hardware wallet did it's job, but without being in the possession of the private key. There are lots of ways to do this, but a hot topic today is zero knowledge proofs, where the wallet would need to stand up to scrutiny.
The verifier would also need to check the results on the blockchain. Not just that the result generated is correct, but also that it is without side-effects.
> But then we have to trust the verifier!
Yep, and each time we introduce a verifier for the verifier, we will have made the system more trusted. Let's say we have N verifiers, whos best interest is that your wallet did the right thing.
In a transaction, it is not only in _your_ best interest that the transaction is correct (and without side-effects), but also the other party. We can extend this system to be a small group of people in _any_ transaction. If a small group of verifiers all agree with a certain level of consensus, then we can trust the system beyond a reasonable doubt.
This might sounds familiar to those who work with blockchains - and you would be right. It is eerily similar to how it works today. However, the blockchain covers only the cryptographic guarantees. The system needs to be extended to cover formal verification of the system as well.
> Example
Formal verification is a mostly academic exercise for most, so I'll give a small example for those of you who are unfamiliar with it.
Let's say person A and B make a transaction. Both have super secure hardware wallets and the crypto used it state-of-the-art. It should be secure right?
We can review the code of the system, but it is hard to identify mistakes. Who knows, maybe there will be a new area of vulnerabilities in a few years, and we never saw it coming.
Within the area of "correctness", we first need to make a formal specification. We create some testable properties about the system that needs to hold true, no matter the transaction or who is involved (these are called invariants).
So person A transfers 1 bitcoin to person B, they do so by signing a nonce with a private key. Person A checks the nonce and ensures it is indeed random (test 1). The signature is sent to person B, which then tests if the signature is no different than random data (test 2).
Howe test 1 and 2 are performed are incredibly important and very difficult to do, but not impossible.
If test 1 or 2 happens to be non-random, then we can just reject ...
This is not a new revelation, and a similar vulnerability is discussed in Mastering Bitcoin: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06...
> The way I understand it, it makes it completely impossible to use Bitcoin in a trustless way. Even with an air gapped hardware wallet, you are always at the mercy of the wallet manufacturer and the delivery chain that gets the wallet to you. If it gets swapped out on the way to you, you are at the mercy of whoever swapped it out.
Bitcoin's threat model assumes assumes your client software follows specifications. Airgapped hardware wallets aren't designed to eliminate "Reflections on Trusting Trust". Assuming your scenario, the attack can be tested in a similar way to that outlined in "Fully Countering Trusting Trust through Diverse Double-Compiling" (https://dwheeler.com/trusting-trust/). Under a better defined threat model, a construction can be made to effectively prove any data exfiltration scenario to be false.
In conclusion the issue your proposing is not an issue with bitcoin, but with computation in general. The word trustless in the context of cryptocurrencies has slowly been taken out of the context "trusted third parties" and evolved into an epistemological rather than pragmatic issue.
The only solution seems to be what you propose, you buy an old device from before bitcoins were invented and code a client there from scratch to validate that your wallet is using the proper nonces.
Fountain code: you take your fixed input block and encode it with the fountain code and it generates an endless stream of output blocks. You only need to pick any N blocks from the stream to decode it.
Using a fountain code means you don’t have to retrieve the output blocks in perfect sequence.
https://datatracker.ietf.org/doc/html/rfc6979
That means when you sign a transaction with multiple RFC-6979 compliant wallets, they should return the exact same signature.
So it is possible to tackle the "phone home via the signature" problem.
Wow, just wow! Two threads, 144 comments and we have a complete turn of the situation again!
To sign a transaction without trusting the hardware wallet to not leak your seed phrase or other private data, you have to sign the transaction on multiple RFC-6979 compliant hardware wallets and make sure they return the exact same signature.
Without a careful audit of wallet firmware and/or PC software, doesn't this alone force you to trust the wallet maker?
In fact, I don't even know if there are air gapped wallets on the market.
There are some that claim to be air gapped but then use QR codes to transfer data. Which makes them not air gapped at all. A QR code displayed on one device and scanned on another is no less a communication channel than a cable. If it has a malicious helper software on the computer, the wallet could transfer your seed phrase over the image just fine. But that is a different attack vector than the one discussed here.
The discussion here is about whether an actually air gapped wallet could phone home or not. Independent of the question if one exists.
Isn't a QR code passing through an analog medium, and only when read manually? It's also one way: from the wallet to the external reader. Unless I'm misunderstanding something.
Where signing private keys or the transaction signatures would let people derive the sender’s private key
There are always recurring opportunities to check for