Bitcoin Forum

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

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

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.

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

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.

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)

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

To quote the news article:
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.

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

@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

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.

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.

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

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

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

Sell their bitcoins!!!

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.

Agreed.

I'm going to sound like the guy you see on TV that's portrayed to be crazy on TV because of his fear of government.  Well ever since I learned how our monetary system worked and researched the truth about governments I personally know without a doubt that deanonymization is a bad thing.

Just my 2 bit cents that I don't believe anyone will listen to just like when I started telling all my friends and family how the monetary system works.  They are slowly starting to listen as things get worse and worse.  So why go down a path that has been historically BAD!

The 50% mark is not really a tipping point, as you can still get left behind in many potential attacks.  Percentage of network power just means are you ever-more-likely to be able to double-spend while waiting with a chain of length X in the background.  The attack is still very, very difficult and reliant upon probability even at 60%, 70%, etc.

Yeah, but what makes me nervous is that someone with that kind of power could lay in wait for an indefinite period of time...spending whatever it takes to remain substantially ahead of the network...waiting for the most opportune time to reveal themselves and completely undermine bitcoin.

That is one of the reasons why the Satoshi Client includes hardcoded block chain checkpoints.

That could cause a pretty big chaos, but is no real danger of cheating.

That is a simple, practical solution that effectively accomplishes the same result.  What about doing something less manual and less sporadic though?  I've often wondered whether it would make sense to simply not allow reorgs beyond a certain depth at all (which is practically speaking what the exponentially more difficult reorg proposal does).  If you happen to get stuck on a dead branch, you would need to take manual steps to force your client to recognize the chain that the rest of the network recognizes.  Most normal splits/reorgs occur when a couple blocks are generated at nearly the same time.  If the network is well maintained and clients have a handful of well connected nodes they can reliably connect with (and those are well connected to each other), it should be an extremely remote situation where a reorg goes more than a couple blocks deep.  I wonder if you could even be as aggressive as not allowing any reorg of more than 6 blocks deep.

The longest reorg I'm aware of was 25 blocks. Someone correct me if I missed one.

The one after the overflow bug was 54 blocks. If all old clients had ignored the longer chain because the split was too far back, then lots of damage could have been done by the attacker.

In that case, I wouldn't really be comfortable with automatically locking the chain at less than, say, 5000 blocks.

I'm not sure that is a good argument here.

While the current reorg logic was certainly a boon in that situation, and future situations like it are easy to imagine, we should recognize that we are overloading that operation to do something that it wasn't intended to do.

Maybe we should think of a proper mechanism to deal with nodes that are known to have critical bugs, and allow the block chain logic to concentrate on protecting the chain.

I'm not familiar with what happened with that bug...but in such a circumstance, couldn't you issue an update to the client that fixed the bug as well as fixated on the known good chain?  You then have to convince everyone to start running that new version of the client (and other clients would need updating as well).  But in the case of a serious bug, that has to happen anyway.  To me, there doesn't seem to be any legitimate reason to allow deep reorgs to happen.  About the only thing I could think of is when a large section of the network is cutoff for an extended period of time, but how likely is that to happen?  And if it did, isn't some manual intervention a good idea anyway (you could have features in the client that let you see when there are other chains that would cause a deep reorg and let the user choose to take it or not)?

It would be a good idea for the client to enter safe mode when it sees a deep reorg, but it still must switch chains. Otherwise the network can become permanently segmented, and an attacker that gets control for some time can keep control much more easily. Keep in mind that it is not impossibly expensive to take control of the network for several weeks.

My first thought was an alert message.  Presumably Satoshi had the exact same idea years ago.

The maintainers could generate a key pair for each release, with the public key embedded in each client.  If a critical bug is found in some client, the maintainer signs a message telling the node to notify the operator.  If the message is informational only, and has some anti-spam provisions (embed the message in a transaction sig?), it should be pretty widely accepted by the community.  Each node operator then has the choice of how they want to handle the message.

If I was running a store, and the devs found a critical bug that made my client unreliable, I would set up a handler that disabled my store first, and paged me second.  Operators that ignored the messages would do so at their peril.  Having a deep reorg trigger the same exception handler would be good too.

Theymos is right that having a higher barrier for deep reorgs would allow an attacker to maintain control over some nodes for a longer time (or forever), but under my scenario, those are the nodes with careless operators, which is their own fault.  I'm all in favor of protecting all nodes, even those with careless operators, when it happens for free.  But I'd throw half of the network under the bus if it made the remaining half twice as secure.  Hell, I'm almost at the point where I'd be willing to do it just to stop all of the "51%" threads here.

I don't understand this argument...if an attacker successfully generated a few blocks in succession, one of their blocks would indeed become old enough that it is permanently embedded...but so what?  Even if the attacker had 70 or 80% of the processing power, they could only force reorgs say 6 blocks deep...or ~1 hour into the past...and blocks from other miners would still beat out the attacker on occasion (rendering ineffective an attack where legitimate transactions were being ignored).  If this was pervasively happening for some period of time, people could simply start waiting a full 6 (assuming 6 is the point where reorgs are only allowed manually) transactions when dealing with untrusted people (but you could still safely accept transactions immediately when dealing with a counterparty that is trusted).

Alternative algorithms for accepting deep block-chain re-orgs sound like a research project to me. Before changing something that critical I would like to see simulations of how different re-org policies behave under different attack scenarios, and non-attack "what if there is a bug that causes an inadvertent block chain split" scenarios.

And I'd like to see a whitepaper that lays out the issues and summarizes simulation results.  And lots of extra credit if it gets peer-reviewed and published in one of the IEEE or ACM journals.