Bitcoin is a decentralized digital currency, which main advantage, compared to other e-currency protocols, is the absence of need for a trusted issuing authority such as a central bank. Bitcoin works as a distributed network, where all the transactions are kept public on a ledger called the block chain. Each transaction is verified by performing difficult computations, for which those who perform them, called the miners, are rewarded in Bitcoin.
Despite the popular belief, Bitcoin is not an anonymous network. Although users’ IP addresses are not public, their pseudonyms, derived from public cryptographic keys, are for everyone to see on the block chain. For this reason, anyone can see, which pseudonymous user paid whom and when. This possibility makes users susceptible to metadata analysis, which could possibly link a person with their pseudonym.
However, such type of analysis relies on either external information or on unusual user behavior on the network. Unusual patterns can be easily distinguished and correlated with other available information on the possible target. But three researchers at the Luxembourg University – Alex Biryukov, Dmitry Khovratovich and Ivan Pustogarov – have devised a method to deanonymize Bitcoin users by identifying their public keys with IP addresses without the requirement that users behave unusually.
The method uses the fact that on any distributed network a user must first connect to an entry node that forwards the connection to the rest of the network. One client can connect to eight nodes at most, but it suffices to know three of them to uniquely identify the client. The three entry nodes can be obtained by exploiting Bitcoin’s address propagation system: when a client connects to the network, its entry nodes send its address to pairs of their neighboring nodes, thus propagating the information across the network. However, if some node already sent an address to another node, it can not re-send the same information to the same target again. This fact allows an attacker to statistically analyze the entry and distribution pathways, thus determining the entry nodes.
The researchers have performed an attack on a test network, where they managed to collect 6 out of 8 entry nodes per client on average. They could also link 60% of Bitcoin transactions to the sets of entry nodes, thus linking transactions to users.
Another novelty by Biryukov, Khovratovich and Pustogarov is a method to disconnect users of Tor anonymization network from the Bitcoin network. Tor is a distributed cryptographic network, providing strong anonymity to its users by layering the encryption process across three chosen nodes in the network.
The method proposed by the researchers exploits the countermeasures against denial of service attacks in the Bitcoin network: the network penalizes users who send malformed information, and when a limit of 100 penalty points is reached, the user is banned from the network for 24 hours.
Since the connections, which were anonymized through the Tor network, reach the users from the end of the aforementioned encryption pathway – that is, from what is called an exit node – an attacker has no need to exclude the users of Tor, but only its exit nodes, of which there are only a little more than a thousand. Since it is possible to be banned due to one heavily malformed connection, an attacker may do as many such Tor connections as there are exit nodes, and by this ban all of them for the following 24 hours.
The important aspect of this deanonymization method in particular is the small computational resources needed to perform the attack. The researchers estimate that the cost of the attack on the full Bitcoin network to be about €1,500 per month. At the same time, it is an attack on generic Bitcoin users with no unusual behavior. For this reason the research contributes to the overall pressure on researchers to develop strong anonymization measures to protect Bictoin users’ privacy.
Original research article: arXiv:1405.7418v2 [cs.CR] 3 Jun 2014