Threat Analysis and Possible Mitigation of a Sybil Attack

[phantomcircuit]

There is potential for a well organized attacker to allocate a significantly number of ipv4 addresses and effectively isolate peers from the network.

x = % of network by ip/port combinations attacker controls
y = number of outbound connections made by the client
z = % of peers attacker can isolate

x^y=z

An attacker who controls 75% of the network would currently be able to isolate approximately 10% of the network. Currently there are approximately 4000 nodes ( an over estimate ), currently this would require approximately 12000 unique ips. The client currently mitigates against this attack by requiring each outbound connection to be in a unique /16, however a well organized dedicated attack could potentially pull off an attack like this.

To prevent a sybil attack against a (very) well organized and (very) well funded attacker with high confidence requires periodically cycling to new peers.  Given that blocks are not confirmed by the client until there have been more than 6 blocks, and each block takes 10 minutes to generate, a fairly slow peer rotation could significantly mitigate against this form of attack with minimal overhead.

Further the rate at which peers are cycled could be controlled by each client individually based on their confidence level requirements.

[1714839036]

1714839036

[1714839036]

1714839036

[1714839036]

1714839036

[Matt Corallo]

There have been a lot of questions by devs about how we should work on defending these kind of attacks.  I think, for the sake of simplicity, we should assume that ALL incoming connections are from an attacker (perfectly reasonable if an attacker controls enough nodes to do this kind of attack).  Thus, we should work to make sure we have enough diversity in outbound connections to ensure Sybil attacks cannot happen. 

I think 75% of the network is about all that we reasonably need to protect against.  Any more and the attacker has enough resources to create their own block chain or at least purchase the hardware to do so.  I think we should only really focus on such attacks.  For an individual client, to have the chance of one of the outbound connections to be "legitimate" to be 99.9% (reasonable, IMHO), one would need 25 outbound connections (assuming we don't rotate clients).  Under the current client, that would mean 25% of -maxconnections go to outbound (a good number IMHO).  I think a solution would thus be to simply replace MAX_OUTBOUND_CONNECTIONS with 25% of -maxconnections, with a hard lower limit. 

A variation on this attack, suggested on #bitcoin-dev a couple of weeks ago, is to fill ALL nodes' incoming connection slots with your nodes so that new nodes cannot make any outbound connections (they will be rejected everywhere) unless they are to the attacker.  I think this is too hard to do (quite a bit of bandwidth and you have to be very quick to fill new node's connection slots), but maybe someone could do some actual math and maybe even try it on the testnet?

[theymos]

Resources would be wasted working on that, since in the future there will be backbone nodes that everyone connects to. By always connecting to a few of the same backbone nodes, the problem is solved.

[Matt Corallo]

Resources would be wasted working on that, since in the future there will be backbone nodes that everyone connects to. By always connecting to a few of the same backbone nodes, the problem is solved.

Both gavin and jgarzik have expressed concern over the potential for Sybil Attacks.  I think if we can keep things in a peer2peer fashion and not depend on a central backbone and authority it is a much better system.

[Gavin Andresen]

RE: 25 outbound connections instead of 8:

If I recall correctly (and I probably don't), the percentage of nodes currently on the network that are accepting incoming connections and the -maxconnections limit isn't great enough to support every node trying to make 25 outbound connections.

The major merchants and exchanges should accept incoming connections, so they have many more than 8 connections.  That will make them basically immune to Sybil attacks (e.g. the Faucet has 55 connections right now).

I like the idea of major merchants and exchanges (also) communicating with each other over an invitation-only, trusted "backbone."  That would be in addition to the mostly-randomly-connected p2p network we have now, not instead of it.

I'm concerned about Sybil attacks as a denial-of-service technique (attacker "surrounds" an 8-connection node and then drops all of their transactions just because they can).  Randomly disconnecting and re-connecting seems like a good approach.

Detecting that you're being subjected to a Sybil attack seems like it might also be a good approach.  You don't really care if you're seeing a bogus version of the block chain unless you're in the middle of confirming one or more transactions; perhaps if transaction confirmation is taking significantly longer than expected the client should find some fresh peers.

[Mike Hearn]

Yes, this is a larger problem for client mode implementations that want to show 0/unconfirmed transactions in the UI so have to rely on trusted third party nodes.

For now it seems sufficient to rely on network level security. For instance, if you are trading using a client-mode node on a mobile phone, just forcing the phone to use 3G instead of wifi would be good enough as it's not presently possible to tap or hijack 3G connections. So you can assume that if you try to connect to A.B.C.D you actually will do.

As an additional layer of protection, non-client nodes could (optionally?) generate a keypair for themselves at startup and then send a <pubkey><sig> pair during the initial handshake. The client would be happy to download blocks from any node as they are self proving. Showing unconfirmed transactions would require receiving the invs from multiple nodes that have been seen before, and have established a reputation of relaying transactions that later do show up in blocks.

[phantomcircuit]

A variation on this attack, suggested on #bitcoin-dev a couple of weeks ago, is to fill ALL nodes' incoming connection slots with your nodes so that new nodes cannot make any outbound connections (they will be rejected everywhere) unless they are to the attacker.  I think this is too hard to do (quite a bit of bandwidth and you have to be very quick to fill new node's connection slots), but maybe someone could do some actual math and maybe even try it on the testnet?

Heh, that was me. And actually the amount of bandwidth to pull of an attack like that is minimal (aka i could do it from my home DSL right now).

A version message is 106 bytes, a verack 24 bytes, so 130 bytes for a full open connection. Set the tcp receive window to it's minimum (can be zero if you do this with raw sockets) which is 256 bytes on linux and well you can trivially hold open a practically infinite number of connections from any kind of connection.

[phantomcircuit]

If I recall correctly (and I probably don't), the percentage of nodes currently on the network that are accepting incoming connections and the -maxconnections limit isn't great enough to support every node trying to make 25 outbound connections.

The major merchants and exchanges should accept incoming connections, so they have many more than 8 connections.  That will make them basically immune to Sybil attacks (e.g. the Faucet has 55 connections right now).

I like the idea of major merchants and exchanges (also) communicating with each other over an invitation-only, trusted "backbone."  That would be in addition to the mostly-randomly-connected p2p network we have now, not instead of it.

I'm concerned about Sybil attacks as a denial-of-service technique (attacker "surrounds" an 8-connection node and then drops all of their transactions just because they can).  Randomly disconnecting and re-connecting seems like a good approach.

Detecting that you're being subjected to a Sybil attack seems like it might also be a good approach.  You don't really care if you're seeing a bogus version of the block chain unless you're in the middle of confirming one or more transactions; perhaps if transaction confirmation is taking significantly longer than expected the client should find some fresh peers.

I hadn't thought about the % of connectable peers, you seem to be right though, 25 * 4000 / 500 = 200, and as time goes on there will probably be fewer connectable nodes not more.  All the more reason to use peer cycling instead of more connections.

I agree with BlueMatt that avoiding a network that relies on large backbones to function is probably a good idea.  And I dont know how you'd be able to detect that you were being attacked if an attacker simply controlled a large % of the connectible peers. (which reminds me you could actually control 75% of the current network with just 1500 ips because only about 500 peers are connectible)

[Gavin Andresen]

And I dont know how you'd be able to detect that you were being attacked if an attacker simply controlled a large % of the connectible peers. (which reminds me you could actually control 75% of the current network with just 1500 ips because only about 500 peers are connectible)

Well, imagine an attacker did manage to surround your node.
What can they do?

a) Dropping outgoing transactions-- a send-coins denial-of-service.
b) Dropping incoming transactions-- a 0-confirmation-receive-coins denial-of-service

Can these be exploited somehow to the attacker's advantage?  Maybe if attacker and attackee were competing on a bidding site or the site being attacked was a bidding site and the attacker wanted to squash competing bids.  Rounding up thousands of IPs to try to get a better deal on biddingpond hardly seems worth it.  And an old-fashioned DDoS attack can probably take out any one particular node anyway, with or without bitcoin involved.

c) Dropping new block announcements (that would be a 1+-confirmation-receive-coins DoS)
d) ... and maybe feeding the attacked node attacker-generated blocks

(d) is more serious, because the attacker could generate bogus N-confirmation transactions.  But it should be detectable; assuming the attacker doesn't have as much hashing power as the rest of the network, blocks will be generated much more slowly (either much more slowly after the last compiled-in block checkpoint if you're downloading the block chain, or much more slowly since the last time your node connected to the network).

[Matt Corallo]

I hadn't though about % of nodes connectible.  That is ultimately a problem because we don't support UPnP/NAT-PNP (should we work on doing that, or is a satoshi-vetoed feature as well?).  However, as we move towards cellular clients (which are more often than not behind a large-scale nat and can never accept incoming connections) and IPv4 depletion (more ISP-level NAT, even if its several years away) this will continue to be more of a problem. 

This leaves us with some kind of peer-rotation implementation.  How should we decide when to drop a connection and make a new one?  Should we drop from the inbound connection pool, outbound connection pool or both?  Should we simply rotate nodes on a regular basis (ie one new node / minute?).  Or should we do something like Gavin's idea where we total time it took for the last X blocks and if it is much lower than one / 10 minutes we make Y new connections.  That leaves the question of what X and Y should be.  I'd assume we average something like all the blocks since the last restart (is that easy in the current code base?) and if it falls to something like one / 15 minutes we act (assuming we have >Z blocks averages, how many?).  Then how quickly do we make new connections (1 / minute?)?  Also might we do both Gavin's idea and phantomcircuits? 

[phantomcircuit]

And I dont know how you'd be able to detect that you were being attacked if an attacker simply controlled a large % of the connectible peers. (which reminds me you could actually control 75% of the current network with just 1500 ips because only about 500 peers are connectible)

Well, imagine an attacker did manage to surround your node.
What can they do?

a) Dropping outgoing transactions-- a send-coins denial-of-service.
b) Dropping incoming transactions-- a 0-confirmation-receive-coins denial-of-service

Can these be exploited somehow to the attacker's advantage?  Maybe if attacker and attackee were competing on a bidding site or the site being attacked was a bidding site and the attacker wanted to squash competing bids.  Rounding up thousands of IPs to try to get a better deal on biddingpond hardly seems worth it.  And an old-fashioned DDoS attack can probably take out any one particular node anyway, with or without bitcoin involved.

c) Dropping new block announcements (that would be a 1+-confirmation-receive-coins DoS)
d) ... and maybe feeding the attacked node attacker-generated blocks

(d) is more serious, because the attacker could generate bogus N-confirmation transactions.  But it should be detectable; assuming the attacker doesn't have as much hashing power as the rest of the network, blocks will be generated much more slowly (either much more slowly after the last compiled-in block checkpoint if you're downloading the block chain, or much more slowly since the last time your node connected to the network).

If you can isolate a node from the network you could trivially double spend against them, all you'd have to do is generate blocks faster than they can.

[wb3]

Bypass the IP, to a VPN in another area. Or run it over a Tor network changing identities ever minute.

It would seem like a lot of work to restrict a node, when the node can evade the attack fairly simply.  Not to mention, you would spend more money in acquiring the IP's than the transaction is probably worth.

[theymos]

If you can isolate a node from the network you could trivially double spend against them, all you'd have to do is generate blocks faster than they can.

You still need to work against main-network difficulty, so it takes a very long time to accumulate confirmations on your double-spend. The target is likely to notice. A future version of Bitcoin will probably detect this.

[phantomcircuit]

If you can isolate a node from the network you could trivially double spend against them, all you'd have to do is generate blocks faster than they can.

You still need to work against main-network difficulty, so it takes a very long time to accumulate confirmations on your double-spend. The target is likely to notice. A future version of Bitcoin will probably detect this.

We are likely to notice, that doesn't mean most people are and the solution of peer rotation is trivial to implement.