BitCoin Deanonymization

[dakami]

Hi!  I was trying to respond to https://bitcointalk.org/index.php?topic=34383.0 , but as a newbie I can't.  So, maybe someone can quote this (or even move this) to that thread.

I'm Dan Kaminsky.  I'm the reason there's ASCII text that's returned if you run:

strings --bytes=20 .bitcoin/blk0001.dat

As reported, I've got a BitCoin deanonymization mechanism.  It's not complicated.

Connect to every node in the cloud, discoverable via sweeping/IRC/get_peers messages.  The first IP to consistently relay transactions for a given identity, is the given identity.

Of course the entire BitCoin cloud doesn't allow inbound connections (although you can do rather evil stuff with UPNP to force that open too).  But this isn't a problem -- there's only about 3000 to 8000 IPs that are BitCoin nodes that accept inbound connections.  Since everyone else depends on them, you just need to create your own mass cluster of IPs that are a decent chunk of the P2P network.  Nodes on average have seven outbound connections, so it should take only a few hundred unique to be one of the first-hop peers even for the outbound-only set.

Now that I think about it, it might even be possible to do this from a single IP, with lots of ports.  I remember seeing some code in there to try to distribute peers across Class B's though so this can be interesting bug #9 that BitCoin manages to smush.

(As a note, I have a tremendous amount of respect for BitCoin; I count it in the top five most interesting security projects of the decade.  Entire classes of bugs are missing.  But it's just not an anonymous solution, and the devs will say as much.)

[spruce]

I quoted it there for you. Thanks for the details.

[dakami]

Thanks!  Here's another small followup:

"Unfortunately, it won't help anybody investigating past crimes, since you would have to be monitoring the network in this way when the crime happened."

It's possible to link pseudonyms (all sources in a transaction are almost certainly the same identity, since they have to coordinate the contents of the destinations for all the coins.  So an IP on today's psuedonym is linkable to the IP from last week's.

"Also, is Dan claiming he put text in the genesis block? Maybe I don't understand correctly, or maybe it was a joke . . . "

There's a block containing a transaction with 78 outputs.  The outputs are not actually hashes of public keys.  They're twenty arbitrary bytes, and they happen to be a tribute to a friend.

"Hopefully a mod can whitelist Dan so he can chat in this thread."

Happy to answer any questions.

[camosoul]

tor

You're using it to shop on Silk Road anyway... Just point your bitcoin client at your tor proxy... Then, tumble while using tor...

Yay anon!

Your theory works on stupid people. Kidna like macro viruses... It isn't a flaw in bitcoin/anon any more than FireFox has anon 'problems.'

You either make the effort to be anon, or you don't... If you're not that bright, you shouldn't be doing things that need to be hidden... The digital version of watching a TV show about dumb criminals...

I'm not knocking your efforts to expose this. Only demonstrating that you can make your Bitcoin client just as tor/anon as your browser... You just have to rub a few brain cells together, if you have them...

[JoelKatz]

Connect to every node in the cloud, discoverable via sweeping/IRC/get_peers messages.  The first IP to consistently relay transactions for a given identity, is the given identity.

There are many ways to defeat this. The simplest is:
1) Never relay local transactions to nodes that connected to you.
2) Only make outbound connections to semi-trusted nodes.
3) Always send transactions to the same node.

[Gavin Andresen]

I whitelisted Dan and moved this thread here.

(yes, I'm beyond-a-reasonable-doubt-certain dakami is Dan Kaminsky, we had an email discussion about interesting-but-smushed-bug#8 earlier in the week)

[kjj]

Connect to every node in the cloud, discoverable via sweeping/IRC/get_peers messages.  The first IP to consistently relay transactions for a given identity, is the given identity.

There are many ways to defeat this. The simplest is:
1) Never relay local transactions to nodes that connected to you.
2) Only make outbound connections to semi-trusted nodes.
3) Always send transactions to the same node.

4) Always send transactions to a different node (just one).

[drawoc]

To quote the news article:

Kaminsky announced a new tool called BlitCoin that unmasks one or both ends of a BitCoin transaction.

How does this unmask both sides of a transaction? I see that it can get you the IP of a sender, but not how it can show the identity of someone on the receiving end (unless you're just waiting for the receiver to send those coins themself).


The talk about IP spoofing in the slides got me thinking - what if we were to open up a UDP port and allow connecting to that for broadcasting transactions? Then if someone wanted to send coins, they could easily spoof their own IP. It's not like you get any useful reply from a node you relay your transactions to anyway. The error checking of TCP isn't needed because changing any few bytes in a transaction is practically guaranteed to make it invalid (I think? Haven't looked into that part of the code yet. I assume so because otherwise any transaction you relay to me, I could simply modify a few bytes of and screw it up for you.) It could potentially make things more anonymous.

[theymos]

How does this unmask both sides of a transaction? I see that it can get you the IP of a sender, but not how it can show the identity of someone on the receiving end (unless you're just waiting for the receiver to send those coins themself).

The recipient will rebroadcast it if it doesn't get into a block quickly enough.

[bcearl]

@dakami:

In your slides* you mention the myth that some security properties are based on the assumption that nobody gets 50 % of hashing power. That's not accurate. It is just that some certain probabilities have been calculated from that assumption. With more than 50 % there is not much change - it's not a tipping point.

Or have you been thinking about a different attack?



*) 16th slide: http://www.slideshare.net/dakami/bitcoin-8776098

[JoelKatz]

@dakami:

In your slides* you mention the myth that some security properties are based on the assumption that nobody gets 50 % of hashing power. That's not accurate. It is just that some certain probabilities have been calculated from that assumption. With more than 50 % there is not much change - it's not a tipping point.

Or have you been thinking about a different attack?

It is a tipping point. With more than 50% of the hashing power, an attacker can always choose which of two conflicting transactions makes it into the hash chain. If the wrong transaction gets into the chain, no matter how many confirmations it has, with 51% of the hashing power the attacker can build off a chain from before the transaction, including the conflicting transaction, and eventually his chain will be longer than the public chain. With 45% of the hashing power, even reversing a transaction with just four confirmations becomes very unlikely to succeed.

[kjj]

There are two ways for an attacker to do a 51% attack.

The first is a "live" attack, where the attacker publishes his blocks as soon as he gets them.  In this version, his chances are not very good, even with 51% or 60% or 70% of 80% of the network hashing power, because the odds calculation is %^Blocks.

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

This attack can be countered by changing the calculation for deciding which chain is valid.  An exponential function would solve the problem.

[bcearl]

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

But this attack is so easy to detect that it makes no sense to try it.

[kjj]

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

But this attack is so easy to detect that it makes no sense to try it.

You mean like everyone would notice if 7 blocks get swapped all at once?  Yeah, we would notice, but they would be the correct chain then, so what would we do about it?

[paraipan]

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

But this attack is so easy to detect that it makes no sense to try it.

You mean like everyone would notice if 7 blocks get swapped all at once?  Yeah, we would notice, but they would be the correct chain then, so what would we do about it?

+1 would be nice to know

[bcearl]

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

But this attack is so easy to detect that it makes no sense to try it.

You mean like everyone would notice if 7 blocks get swapped all at once?  Yeah, we would notice, but they would be the correct chain then, so what would we do about it?

I didn't say that you can't. You can. But it is obvious. And you needed more computing power than the rest of the net - and can reverse transactions that are just "confirmed".

[BitcoinBug]

You mean like everyone would notice if 7 blocks get swapped all at once?  Yeah, we would notice, but they would be the correct chain then, so what would we do about it?

+1 would be nice to know

Blockchain correction already happened:
https://en.bitcoin.it/wiki/Incidents#Value_overflow

[Steve]

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

But this attack is so easy to detect that it makes no sense to try it.

You mean like everyone would notice if 7 blocks get swapped all at once?  Yeah, we would notice, but they would be the correct chain then, so what would we do about it?

Sell their bitcoins!!!

This attack can be countered by changing the calculation for deciding which chain is valid.  An exponential function would solve the problem.

Interesting idea.  IIUC, this makes it such that the deeper the reorg, the higher the barrier for it to be accepted.  Which means that you effectively force the >51% attacker out into the open (they have to publish their blocks or their private chain will quickly become virtually impossible to get accepted) and basically force them to periodically build off of other's blocks...and you effectively require miners (and all nodes really) to take steps to ensure blocks get widely distributed.  However, if there is a temporary split in the network, doesn't this run the risk of a temporary split becoming permanent?  I suppose you could come up with a non technical means of resolving such a split should it ever occur...it might be an acceptable trade off considering that this proposal might have a huge benefit (in the sense that it would severely inhibit the damage that could be done by a miner with >50% could do).

[kjj]

The other attack is the offline attack, where the attacker does not publish his blocks until his chain is at least X blocks longer than the public chain.  In this attack, 51% is indeed a tipping point, because once he reaches 51% he is assured that if he waits long enough, he will eventually have enough blocks saved up to perform the chain reversion.

But this attack is so easy to detect that it makes no sense to try it.

You mean like everyone would notice if 7 blocks get swapped all at once?  Yeah, we would notice, but they would be the correct chain then, so what would we do about it?

Sell their bitcoins!!!

This attack can be countered by changing the calculation for deciding which chain is valid.  An exponential function would solve the problem.

Interesting idea.  IIUC, this makes it such that the deeper the reorg, the higher the barrier for it to be accepted.  Which means that you effectively force the >51% attacker out into the open (they have to publish their blocks or their private chain will quickly become virtually impossible to get accepted) and basically force them to periodically build off of other's blocks...and you effectively require miners (and all nodes really) to take steps to ensure blocks get widely distributed.  However, if there is a temporary split in the network, doesn't this run the risk of a temporary split becoming permanent?  I suppose you could come up with a non technical means of resolving such a split should it ever occur...it might be an acceptable trade off considering that this proposal might have a huge benefit (in the sense that it would severely inhibit the damage that could be done by a miner with >50% could do).

Yup, you understand correctly.  If you require reorgs with more than X (six might be a good value for X) blocks to require 2^(Y-X) difference in difficulty, a recipient can wait 12 blocks and know that unless the attacker has 64 times more power than the rest of the world, the transaction won't be reversed.  Or they can wait 26 blocks and know that an attacker would need more than a million times as much.  After a day, I would be pretty confident that not even ET could reverse it.

The risk of splits isn't as great as you might imagine.  If the network was cut in half (weighted by hashing power), we would have about 2 hours to notice the problem and fix it.  If the network was cut 90/10, we would have 10 hours.  The less even the network break, the more time we have until it becomes a problem, and also the less effort will be needed to fix it.

And yes, resolving a permanent split would require human intervention.  Essentially, the minority network would be forced to discard all blocks since the split if they wanted to rejoin the global network.  Personally, I think the potential cost to individual miners and nodes is a small price to pay to protect the network as a whole.

[Steve]

And yes, resolving a permanent split would require human intervention.  Essentially, the minority network would be forced to discard all blocks since the split if they wanted to rejoin the global network.  Personally, I think the potential cost to individual miners and nodes is a small price to pay to protect the network as a whole.

Agreed.