New vulnerability: know your peer public addresses in 14 minutes

[Sergio_Demian_Lerner]

I really thought this had been fixed, because I commented the problem of using IsFromMe / IsMine to the developers in the github forums (https://github.com/bitcoin/bitcoin/pull/1648), but no. Not fixed, so I'd better alert people before they can be tracked...

The attack requires you to connect and be disconnected from the same node almost 11 times. Nodes do ban DoS offenders for some time, so the attack can take some days mounted from a single IP. Nevertheless, if you can control 11 different IPs (very easy), and you can re-connect to the peer, you cant still mount a successful attack in a few minutes.

The attack allows only to know the Bitcoin public address related to an IP. If a peer is using Tor, then there is no loss of anonymity.

Affected Systems
-----------------

The problem affects all versions of the Satoshi Bitcoin Client.

Summary
---------

The method CTxMemPool::accept() has a protection against 'penny-flooding'. The protection prevents a transaction with very low fees and big size to be forwarded or even stored in the memory pool.

The problem is that this protection tests if a transaction is from a wallet owned by the user, and if it's the case, then the protection is skipped. This fact can be used by the attacker as an oracle.

There are currently around 1M addresses with non-zero balance (an estimation based on http://bitcoin.stackexchange.com/questions/3524/how-many-unspent-transaction-outputs-are-there).

An attacker can discover which of the addresses are owned by a peer by the following procedure:

1. For each address, the attacker choose one unspent output Out(i)

2. Group the 1M unspent outputs in 1632 transactions Tx(j), each one containing 613 previns. Each transaction would be approximately 26999 Kbytes long. Add one output. Put zero fees. (GetMinFee() will return zero)

3. Send each Tx(j) one by one to the victim node.

4. After sending each transaction, the victim node may:

- Reject the transaction because it penny-floods (normally). In this case you will be still able to send more transactions.

- Disconnect you (DoS detection) you since you are not providing the correct signature scripts (this is the case when you have hit an owned address)


5. If you have been disconnected, repeat recursively a binary search grouping the prevouts of this transaction until you find a single one that disconnects you. Note that you may need to add additional dummy previns or prevouts to the transaction if it becomes too small to be blocked by the peer with the penny-flooding protection system.

With a 54 Kb/sec link, sending each Tx takes 1/2 sec so finding the first tx takes in the worst case, 13 minutes. Afterwards each binary search step takes 1/2 seconds in the worst case, so with 10 additional tests you can find an prevout with the desired property in 2^10 prevouts, more than the 613 originally contained, in a few seconds.

I haven´t tested the attack but, check for yourself. The explanation is clear enough. But without testing the attack, I can be mistaken.

You can protect very easily from the attack by rising the "-limitfreerelay" value to something like 1000000. Of course, that will also disable the penny-flooding protection.

Until the next vuln report,
  Yours sincerely,  Sergio.

[Sergio_Demian_Lerner]

I realized that the attack can also be mounted using much smaller transactions, as long as you keep sending them fast enough to trigger penny flooding algorithm.
So just a single disconnection may be required to detect a remote public address.
No need to do any binary search. Just send each Out(i) in a single Tx(j).


Sergio.

[Gavin Andresen]

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

RE: "I better alert people before they can be tracked" :

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year. If you are worried about being tracked, you should be running bitcoin over Tor and connecting to only trusted nodes. We make no anonymity guarantees.

[zvs]

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

RE: "I better alert people before they can be tracked" :

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year. If you are worried about being tracked, you should be running bitcoin over Tor and connecting to only trusted nodes. We make no anonymity guarantees.

i entrust nogleg with all my transactions

[piuk]

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year.

In practice this is difficult to do accurately due to network latency and the fact that many nodes don't accepting incoming connections.

Using Sergio's method you could for example log the first 10 nodes to relay a transaction then pole each node with a penny flood transaction in order to accurately determine which one was the true sender. I may have a go implementing this to improve blockchain.info's relayed by accuracy.

[kjj]

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year.

In practice this is difficult to do accurately due to network latency and the fact that many nodes don't accepting incoming coming connections.

Using Sergio's method you could for example log the first 10 nodes to relay a transaction then pole each node with a penny flood transaction in order to accurately determine which one was the true sender. I may have a go implementing this to improve blockchain.info's relayed by accuracy.

No, the conditional probability that a node was the origin of a transaction given that you first saw it from that node is rather small, even when you have a large number of connections.

I've checked the transactions first seen by blockchain.info from my personal node, and virtually none of the transactions that you first received from me are actually from me.

As an aside, this attack wouldn't find my wallet anyway because I run multiple nodes, and the one node that talks to the outside world has an empty wallet.

[piuk]

No, the conditional probability that a node was the origin of a transaction given that you first saw it from that node is rather small, even when you have a large number of connections.

I've checked the transactions first seen by blockchain.info from my personal node, and virtually none of the transactions that you first received from me are actually from me.

If you look at the propagation data e.g. http://blockchain.info/inv/69d689f000f59d2a9c082e50f8c6e2eb2de3a6e67dc56a13c2e7f0bd78862763 does your ip appear on the list? Sergio's method can be used to fine a list of ip's like this to find the true sender, even if it wasn't the first to relay it. If the node does not have a direct connection at all it still won't work though. In my opinion it is not a very severe issue but does make it easier to track transactions.

[jgarzik]

Using Sergio's method you could for example log the first 10 nodes to relay a transaction then pole each node with a penny flood transaction in order to accurately determine which one was the true sender. I may have a go implementing this to improve blockchain.info's relayed by accuracy.

Doesn't that sort of strip a lot of privacy away from a lot of bitcoin users, without their consent?

[eb3full]

Doesn't that sort of strip a lot of privacy away from a lot of bitcoin users, without their consent?

Eventualities must be embraced sooner rather than later. Running buggy/trackable software is consent enough. ;P

[piuk]

Doesn't that sort of strip a lot of privacy away from a lot of bitcoin users, without their consent?

I was a little hasty proposing to implement it. But perhaps if it is considered a privacy leak without consent then it is probably an issue that should be patched.

[Sergio_Demian_Lerner]

I added additional information regarding this vulnerability:  an additional timing attack to find the Bitcoin address of a peer, using spent outputs (before, I had discussed how to do it using only unspent outputs).

The report is on my blog: https://bitslog.wordpress.com/2013/01/23/new-bitcoin-vulnerability-get-your-peer-public-addresses/

Sergio.

[hackjealousy]

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

Similarly, using the Armory client mitigates this issue.

While this is certainly not a critical vulnerability, it is very important in terms of privacy.  Excellent find Sergio.

The root-cause of this information leak is that large transactions with insufficient fees are not forwarded or stored unless that transaction involves addresses owned by the user.  Perhaps this should be an option and the default should simply be not to forward?

The vast majority of clients will most likely keep the default which makes this essentially equivalent to enforcing transaction fees.  However, this may be a good enough reason to do so.

[Sukrim]

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

If you run (or know) a full node that you trust 100%, there's no need to replicate the block chain - the biggest amount of data you might need is a listing of all unspent outputs, the minimum amount would be probably the unspent outputs of your own addresses (doable now with bloom filters in 0.8 as far as I understood)

I think the main issue with this attack is still that Bitcoin (the "finance application") and bitcoind (the "full network node") started and still are closely interlinked. I guess in the longer run something like the approach by the armory client will emerge, where the node does not know and care anything about a wallet and the finance application won't know anything about the block chain but has to trust a node (most likely on the same PC/installation).

[Luke-Jr]

For reference, this has been assigned CVE-2013-2272

[burnside]

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

Is there an article in the wiki about how to do this?

+1

What would the configs look like for the full network peer and the internal wallet peer?