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.

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.

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.

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.

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

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.

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

+1

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