More Privacy Vulnerabilities in Bitcoin

anonIf you plan to stay anonymous while using Bitcoin, then you have to take many precautions, and you may even have to compile your own fork of the Satoshi client. During the Bitcoin Conference 2013 (which, BTW, was terribly fun),  I found two new problems with Bitcoin privacy. I call them “vulnerabilities” but you may choose not to, whether you believe that Bitcoin should take any possible precaution to preserve user’s privacy or you believe that Bitcoin privacy is just a byproduct of the original design. The vulnerabilities are not critical, but may be used in conjunction with other vulnerabilities to strengthen an attack.  As I generally do, I privately disclose these problems with the core dev team, but apparently they think they shouldn’t solve these kind of privacy issues, since it’s not worth the trouble. Gavin has many times said he is waiting for someone to build an anonymization layer on top of Bitcoin, so the privacy problem magically goes away. But it turns out that providing anonymity to any cryptocoin is technically challenging, and nobody wants to take the legal risk of providing a Bitcoin Mixing service, often called a laundry service. So you either build the coin with the anonymity property right from the start, as Appecoin or Zerocoin do, or you may never achieve that property.

Tracking a node, forever
During the initial block chain download, a malicious user may send the newcomer node a block with low PoW specially created for him, in order to “fingerprint” the node forever. The block can be a child of the genesis block, or any other low PoW block. This poison block will obviously not be part of the best chain, but nevertheless, the Satoshi client will hold that block forever in its inventory. Even if the node shuts-down and connects again to the network at another time, and even if it does it with Tor, it will still remain fingerprinted and so it will be traceable. So if you generally connect to the network using Tor for maximum privacy but some day you connect to the network directly, the malicious user could track the geo-localtion of your IP, and associate any previous or future activity of yours with that location.  The easiest way to test if a node has an specific block is to send an INV command containing the hash of the block, and check if the victims node responds asking for the block data. If the node already has the block, it would not try to fetch the block again. There are other ways to achieve the same test remotely.

This vulnerability alone does not seems to cause much trouble, since the attacker should also try to guess which transactions are going to you, or coming from you. But this is the easiest part, since many vulnerabilities of this kind have been found (by me), and the next vulnerability I present in this post also does exactly that.

I suggested the core developers two possible patches, which are so simple that I was quite shocked they didn’t planed to implement them :
1. When a checkpoint is reached all blocks that do not belong to the best chain are removed forever from the block chain (or from the inventory)
2. All block hashes up to the last checkpoint are stored inside the Satoshi client so that no unknown block can be sent.

I’ve always thought that the best way to download the block chain for the fist time would be to do it backward from the last checkpoint to the genesis block, and then forward from the last checkpoint to the current block. If this algorithm were used, then there will be no possible “cheap” fingerprinting.

Associating a node with owned Transactions

This vulnerability allows a malicious peer to detect with much higher probability than random guessing which transactions are being produced by a node.  The description of the problem is much more technical, and its related to the fact that the Satoshi client rebroadcasts the transactions in the users wallet if it detects they have not been included in a block for some time. It is related to the execution of ResendWalletTransactions() for each newly connected peers in SendMessages(). The probability to be sent the pending wallet transactions immediately when you connect to a node every fifteen minutes is as low as 1/6 (*). Nodes do not send the wallet transactions always because there is a time randomization involved.
So the attack works like this: the attacker keeps a connection to the victim’s  node, and many connections to other nodes of the network (e.g. 1000).  Whenever the attacker receives an INV from the victim’s node that he has never seen in the network the attacker may suspect it is transactions originating from the victim’s node. He can confirm his hypothesis by connecting to the victim’s node using another peer. Obviously the victim’s node must accept incoming connections. Each time you connect to the node you may receive some INVs almost immediately.  With probability around 1/6 (every 15 minutes)  the attacker will receive the victim’s wallet transactions that were not yet included in a block. The attacker can check this against the suspected transactions to see if they match.
Note that if you receive an “addr” message, then you know you are the trickle.  Depending on trickle, the INVs of the wallet transactions can take a round-trip time to arrive or 100 msec more (it doesn’t really matters).

One simple solution would be not to send wallet transactions to nodes that have just connected, but instead wait 10 minutes before sending them any wallet transaction. But again, the core developers think it’s not worth implementing this fix.

These two vulnerabilities are of low criticality for companies, since they generally surround their more secure nodes that contain the company wallets with some other owned nodes that act as gateways to the network, in order to prevent DoS attacks and direct connections to the high-security nodes.

I’ve have another way to test which transactions belong to a wallet, but requires an attack that takes much more time, and a bit more resources. Finally with this post I want to alert Bitcoin users that Bitcoin privacy is still weak. If you want these problems to be fixed in the next release of the Satoshi client, please ask the core developers to keep supporting privacy as a community right.


(*) The exact probability could be a bit higher or lower, as more analysis and probably simulations are required. Disclaimer: I have not exploited these vulnerabilities and the actual exploits could be harder to implement, making the vulnerabilities less critical.

Advertisements

, ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: