New Paper: Deanonymisation of clients in Bitcoin P2P network

[ByteCoin]

A new paper called "Deanonymisation of clients in Bitcoin P2P network" by Biryukov, Khovratovich and Pustogarov from the University of Luxembourg has been published on arxiv.org.
In contrast to the usual offerings, it's actually quite good.

The authors explain how to deny the use of TOR to connect to the bitcoin network by sending enough short messages of a particular form to get all the TOR exit nodes banned.
They analyze a method of discovering the 8 peers to which an average node maintains a connection thereby discovering the network topology.
They outline a DOS attack using ADDR flooding
They outline a method of rapidly lowering the difficulty under certain circumstances by constructing an "Alternate Reality". (A bit less exciting than it sounds!)

There are some other substantial chunks of experiment and analysis as well as some pretty graphs.

Probably the best constructed paper I've seen on Bitcoin.

ByteCoin

[ondratra]

I am very confused now - in section 9.2 they are talking about bitcoin severs and clients. WTF is that??? Isn't bitcoind both/none of them?

[dserrano5]

I am very confused now - in section 9.2 they are talking about bitcoin severs and clients. WTF is that??? Isn't bitcoind both/none of them?

You skipped this from page 1:

The number of Bitcoin peers is estimated to be about 100,000 nowadays. The vast majority of these peers (we call them clients), about 90%, are located behind NAT and do not allow any incoming connections, whereas they choose 8 outgoing connections to servers (Bitcoin peers with public IP).

[laurentmt]

Thanks for the link. I've just had a very quick read but it sounds like a good paper indeed.

The principle used for the tor disconnection is really simple and smart ! It's also a good illustration of how hard is the task of core devs. By implementing something to secure the network (against spam in this case), you always have a risk that it's exploited for another kind of attack (tor disconnection in this case).

Several previous works have shown privacy leaks associated to analysis of transaction graph. Projects like dark wallet address this issue and that's good. But researches like this one are useful to remind us that privacy threats also lie at the network level.

This paper also points an interesting subject concerning the network topology. Studies in (social) network analysis have shown that network resilience is strongly related to its topology and that some topologies are more prone to targeted attacks which can lead to a (temporary) fragmentation of the network. For example, a study has shown that a P2P network like gnutella has a scale free topology and is highly prone to planned orchestrated attacks on highly connected nodes. Bitcoin core network is not so huge (8-10k full nodes) and a targeted attack on 3 or 4% of these nodes (300) is enough to create some serious disturbances if it's topology is scale free. By the way, if somebody knows some papers studying this subject or some services trying to monitor the network topology...

[EDIT]
Made some additional searches about Bitcoin network topology. It seems that Bitcoin network topology should be more like a random graph than like a scale free network, implying a greater resilience to targeted attacks.

By construction the nodes in the network form a random graph. When a node joins the network it queries a number of DNS servers. These DNS servers are run by volunteers and return a random set of bootstrap nodes that are currently participating in the network. Once connected, the joining node learns about other nodes by asking their neighbors for known addresses and listening for spontaneous advertisements of new addresses

http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf
https://bitcointalk.org/index.php?topic=26666.msg334840#msg334840

[gmaxwell]

The principle used for the tor disconnection is really simple and smart ! It's also a good illustration of how hard is the task of core devs. By implementing something to secure the network (against spam in this case), you always have a risk that it's exploited for another kind of attack (tor disconnection in this case).

We're aware of that and specifically designed to address that— at least to the extent that we easily can, there is a lot of room for improvement here. You cannot completely disconnect tor peers using the attack they described because we use tor in two distinct ways:  One way is that we use tor via exit nodes, which that attack addresses— the other is that we use tor via hidden services. If you set onlynet=tor your tor-enabled node uses only this second mechanism, otherwise it uses both. Inbound connections from hidden services, if you have enabled them, are exempted from banning. Some nodes are dual stack— they receive connections via both IPv4 and tor hidden services, and thus act as bridges between the tor and non-tor hosts even if no tor exits are working.

It may well be the case that you could actually break Bitcoin on tor by also DOS attacking the HS-accepting hosts, since there aren't enough of them, and the defense above works in part because some of the existing DOS protections are disabled for HS peers so HS accepting nodes are more DOS vulnerable— though it might also be the case that you'd just break the tor network first, and there isn't much we can do about that.

Last year I proposed a novel approach using asymmetric storage costs to discourage hosts from connecting out to many peers concurrently, though since there have been no attacks (at least none that have risen to a sufficient level of irritation) there hasn't been a lot of interest in developing the idea further. Basically the idea has the outbound connecting host do a moderate amount of POW to precompute a table per peer they are connecting to that allows them to rapidly answer queries that the remote peer can efficiently compute (without storage), the remote peer continually challenges them, so that they must either constantly be doing a ton of POW work, or retain a fair amount of storage per peer.  I'd envisioned this to be an optional thing peers could signal at their connection time ("I'm willing to use up to 1GB storage to get priority access"). All of these "make connections costly" approaches open new attack avenues, however— e.g. what happens when you start a lot of useless nodes for the purpose of just making peers waste effort to connect? The best answer I had is that nodes would only perform the costly work to secure their connections with a small number of their 'favorite' peers (e.g. randomly selected peers which have proven themselves to be helpful in the past), but this only requires the attacker to make their misbehaving nodes good for a while before they start misbehaving. Using sustained local storage as the costly thing instead of one time POW has the useful property that the storage can be freed if a peer stops being useful, but sadly my approach still requires the initial setup be somewhat computationally expensive or otherwise an attacker can skip the storage and just redo the setup for every challenge.

WRT topology, we've worked to keep the wiring random in order to make the topology likely to be an expander graph. Concern about not screwing up the topology is why we don't yet have peer rotation— the first and most obvious way to do it that I came up with broke the topology in simulation (resulted in clustering that had a smallish min-cut). I'm reasonably confident that I know ways that won't, but it's always scary to change something which is hard to analyze.

[laurentmt]

@gmaxwell
Thanks for the details ! Very informative.

What was the rationale for disabling ddos protections against Tor hidden services ? I was specifically designed as a solution to attacks like the one described in this paper or is there another reason ?

WRT topology, it seems you've made a wise decision. You can't prevent people to try an attack, but this kind of topology significantly raises the cost of an effective attack.
I guess the main "threat" would be an alternative client with different networking rules (non random selection of peers) combined with an incentive to connect to specific nodes (higher bandwith, ...) which would lead to a more "centralized" topology. But that seems very hypothetical for now and I'm sure that network resilience is a very good incentive to prevent this kind of evolution.

[genjix]

thanks for the paper. my view is that nodes should encrypt and sign every connection, and user's should interact with the main bitcoin topology using overlay networks encrypted end to end. also we can do more privacy stuff on the bitcoin nodes.

[Mike Hearn]

Encrypting individual Bitcoin connections with overlay networks isn't as helpful as encrypting other kinds of connections, unless you're willing to waste large amounts of bandwidth and time. The problem is an observer who can watch traffic in and out of the encrypting server can watch a transaction-sized packet arrive over an encrypted connection and the decrypted transaction get relayed on to the P2P network a moment later. Given the highly predictable packet sizes and timings involved you can probably match them up very reliably. Delaying things doesn't really help - there aren't many transactions even across the whole Bitcoin network, so the anonymity set would be extremely small even if batched, and people want instantaneous response for things like in person transactions.

This could be solved by encrypting the entire P2P network (but then, it would be trivial for an adversary to connect to you and get the traffic unencrypted again), and by sending lots of cover traffic so it's harder to tell when a tx is being relayed. But that's very expensive, probably too expensive.

Privacy against privileged network observers is one thing. DoS is something else. As far as I know, nobody has ever built a P2P network that is really DoS resistant. It's not even clear it's possible with current technology. This may make Bitcoin technically unviable in the long run. However our current anti-DoS strategy is not that great and this is no news - e.g. banning an IP address because it sent an 81 byte message that cost almost nothing to process doesn't make a whole lot of sense (it would be better to put that IP at the bottom of a priority queue instead).

[bitsmichel]

Nice paper. However one point:

We show how to prohibit the Bitcoin servers to accept connections via Tor and other anonymity services. This results
in clients using their actual IP addresses when connecting to other peers and thus being exposed to the main phase of
our attack, which correlates pseudonyms with IP addresses

This is questionable, users could be behind multiple VPNs. At least, those who are very serious about privacy will not only rely on Tor. In addition, they could use a network which is not theirs;

[ivan.pustogarov]

Thanks for the interesting comments.
We wrote a brief and simplified description of the attack and
also tried to answer questions raised during the discussion.
More comments, questions are welcome.
https://www.cryptolux.org/index.php?title=Bitcoin&oldid=1257

[Baitty]

Nice and interesting read and some very good points stated.

[gmaxwell]

What was the rationale for disabling ddos protections against Tor hidden services ? I was specifically designed as a solution to attacks like the one described in this paper or is there another reason ?

Yes, — since we can't distinguish tor clients from each other banning them would just ban all tor peers, which isn't helpful so we don't do that.

I'd like to have some costly resource peers can optionally use to get themselves a preferred position, see the link I gave for some thinking about that... but absent any smarts it's still best to not increase an attackers power by letting them ban other nodes.

WRT topology, it seems you've made a wise decision. You can't prevent people to try an attack, but this kind of topology significantly raises the cost of an effective attack.
I guess the main "threat" would be an alternative client with different networking rules (non random selection of peers) combined with an incentive to connect to specific nodes (higher bandwith, ...) which would lead to a more "centralized" topology. But that seems very hypothetical for now and I'm sure that network resilience is a very good incentive to prevent this kind of evolution.

Right, most 'smarter' topologies are highly vulnerable... And bitcoin only requires one of its peers to be working well for the node to work well, so connecting to a couple nodes should provide  pretty reasonable performance most of time without further intelligence.

[laurentmt]

@gmaxwell : Thanks !

[bitpop]

This is stupid

Guess who's behind this fud? The dark coin pump and dump fraud

[niniyo]

Why do addr messages propagate for nodes who don't accept incoming connections?  If you know you're outgoing-only, you should be able to indicate so in your version message, so that the peer doesn't share any information about your IP address to others.

[gmaxwell]

Why do addr messages propagate for nodes who don't accept incoming connections?  If you know you're outgoing-only, you should be able to indicate so in your version message, so that the peer doesn't share any information about your IP address to others.

They don't, what you're describing isn't how the Bitcoin protocol works at all.

Other peers don't share information about you, you broadcast it— or  you don't. If your node is not configured to accept incoming connections (e.g. listen=0), knows its not in sync with the network, or is unable to determine a plausible external IP it won't broadcast an addr message for itself.

[niniyo]

Why do addr messages propagate for nodes who don't accept incoming connections?  If you know you're outgoing-only, you should be able to indicate so in your version message, so that the peer doesn't share any information about your IP address to others.

They don't, what you're describing isn't how the Bitcoin protocol works at all.

Other peers don't share information about you, you broadcast it— or  you don't. If your node is not configured to accept incoming connections (e.g. listen=0), knows its not in sync with the network, or is unable to determine a plausible external IP it won't broadcast an addr message for itself.

My understanding from the paper is that they were able to collect thousands of IP address of "clients" who were doing outbound connections only (apparently 90% of peers).  Is this because those client's don't have listen=0 set?

What about SPV nodes on peoples phones - I'm assuming they wouldn't / shouldn't advertise their addresses?

So to rephrase my question - why are so many nodes advertising their IP addresses if they can't accept incoming connections?

[gmaxwell]

There are a healthy amount that are configured to accept connections— its a default in full nodes— but simply don't because some NAT/FW prevents it. SPV nodes do not advertise themselves.

It's not completely clear to me that the nodes in question there actually weren't accepting connections either, but in any case it's expected that there be a large number of advertising nodes which are actually unreachable.

[Liquid71]

This is stupid

Guess who's behind this fud? The dark coin pump and dump fraud

So just stick to your credit card like a good sheep so the government can control where and what you spend your money on.  Online gambling in the U.S. land of the free has been shut down by using money as a weapon so in order to de weaponize money you need a level of anonymity. Other wise a government that can't directly control Bitcoin can go after users and control them.

[BITCOINDENMARK]

Are there any example where one known identity has managed to link a bitcoin address to a physical address - and made the whole thing publicly available ?