Countermeasures against eclipse attacks #5941

sipa · 2015-03-24T00:26:14Z

This implements countermeasures 1, 2, and 6 from the http://cs-people.bu.edu/heilman/eclipse/ paper.

Give each address a single fixed location in the new and tried tables, which become simple fixed-size arrays instead of sets and vectors. This prevents attackers from having an advantages by inserting an address multiple times. This change was suggested as Countermeasure 1 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015. It is also more efficient.

This change was suggested as Countermeasure 2 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015.

This change was suggested as Countermeasure 6 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015.

sipa · 2015-03-24T11:59:50Z

Someone should test how long it takes to find peers with this, when DNS seeding and the built-in seeds are disabled. I'm not able to test the next ~3 days or so.

sipa · 2015-03-24T13:00:59Z

This is running on bitcoin.sipa.be, with -DDEBUG_ADDRMAN enabled.

laanwj · 2015-03-24T13:54:19Z

Going to test this.

Someone should test how long it takes to find peers with this, when DNS seeding and the built-in seeds are disabled.

OK, disabling those.

jgarzik · 2015-03-24T13:57:03Z

Typically, (a) less than 11 seconds if you have a fresh addrman, or (b) sometimes hours or longer, if not.

Current code skips DNS seeds & built in seeds automatically, if it manages to connect to some peers within a short amount of time.

sipa · 2015-03-24T14:05:08Z

@jgarzik I mean after this patch. Reason is the bias changes in peer selection. If you have very few tried peers, the new code will likely very actively keep retrying those (as there is a 50% chance to pick a previously tried peer), and there is no bias towards more recently learned addresses anymore. Both probably slow down initial connection, but likely don't have that much impact in a working system.

laanwj · 2015-03-24T14:06:06Z

It instantly found a peer on start:

2015-03-24 13:55:51 init message: Loading addresses...
2015-03-24 13:55:51 Loaded 14669 addresses from peers.dat  664ms
...
2015-03-24 13:55:51 receive version message: /Satoshi:0.9.2/: version 70002, blocks=346129, ...

gavinandresen · 2015-03-24T20:18:53Z

Ran this with -dnsseed=0 and a peers.dat from a bitcoind that I stopped 23 hours ago:

2015-03-24 20:15:18 Loaded 12904 addresses from peers.dat  512ms
   ...
2015-03-24 20:15:30 connect() to 93.143.11.182:8333 failed after select(): Connection refused (61)
2015-03-24 20:16:15 connect() to 85.199.110.252:8333 failed after select(): Connection refused (61)
2015-03-24 20:16:16 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349059, us=...., peer=1
 ...
2015-03-24 20:16:28 receive version message: /Satoshi:0.9.1/: version 70002, blocks=349059, us=..., peer=2
...
2015-03-24 20:17:09 receive version message: /Marilyn:0.9.99/: version 70002, blocks=30160, us=..., peer=3
...
2015-03-24 20:17:15 connect() to 82.130.103.162:8333 failed after select(): Connection refused (61)
...
2015-03-24 20:17:44 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349059, us=..., peer=4

... so just under one minute to connect to first peer, and it looks like it is finding about a peer a minute.

ghost · 2015-03-24T22:21:46Z

utAck. The paper does not specify a countermeasure "6" in Section 7.

We've still got a bit to go (the symptoms being #5886, #5397, #5352, #5299), but great to see the attention on P2P. Let it remind us that P2P is at the (decentralized) core of Bitcoin Core as much as transactions are; arguably more so.

sipa · 2015-03-24T23:01:37Z

21E14: there are further countermeasures listed in the appendix.

ghost · 2015-03-25T00:11:50Z

It's worth pointing out.

This may also be a good opportunity to tilt the balance of preprocessor directives vs "magic" values, e.g. ADDRMAN_TRIED_BUCKETS_PER_GROUP (2 occurrences) vs 24 * 60 * 60 & 60 * 10.

Interestingly, P2P is not very well reflected in the ongoing libification. As it stands, libbitcoin_server is its closest anchor, but the two are arguably distinct. A large subset of the protocol is arguably entirely P2P (ver, verack, ping, pong, inv, getheaders, ...).

fanquake · 2015-03-26T03:35:45Z

Running with -dnsseed=0

2015-03-26 03:21:39 init message: Loading addresses...
2015-03-26 03:21:39 Loaded 12984 addresses from peers.dat  94ms
2015-03-26 03:21:39 DNS seeding disabled
2015-03-26 03:21:40 connect() to 199.167.100.226:8333 failed after select(): Connection refused (61)
2015-03-26 03:21:52 receive version message: /Satoshi:0.9.3/: version 70002, blocks=349268, us=..., peer=1
2015-03-26 03:21:58 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349268, us=..., peer=2
2015-03-26 03:22:05 receive version message: /Satoshi:0.9.2.1/: version 70002, blocks=349268, us=..., peer=3
2015-03-26 03:22:16 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349268, us=..., peer=4

Removed peers.dat

2015-03-26 03:28:42 init message: Loading addresses...
2015-03-26 03:28:42 Loaded 0 addresses from peers.dat  1ms
2015-03-26 03:28:42 dnsseed thread start
2015-03-26 03:28:44 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349269, us=..., peer=1
2015-03-26 03:28:45 72 addresses found from DNS seeds
2015-03-26 03:28:45 dnsseed thread exit
2015-03-26 03:28:46 receive version message: /Satoshi:0.8.6/: version 70001, blocks=349269, us=..., peer=2
2015-03-26 03:28:47 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349269, us=..., peer=3
2015-03-26 03:28:56 receive version message: /Satoshi:0.9.3/: version 70002, blocks=349269, us=..., peer=4

sipa · 2015-03-27T18:41:14Z

I tried a few times with -dnsseed=0 and a copy of bitcoin.sipa.be's peers.dat, and always had an initial connection between 15 and 30 seconds later.

laanwj · 2015-03-30T14:44:16Z

Works for me - tested ACK

gmaxwell · 2015-03-30T16:31:56Z

ACK.

jgarzik · 2015-03-30T16:38:22Z

ut ACK

My only nit: I wonder if we could replace that '%' with a shift. Could be, if the powers [of two] are aligned.

sipa · 2015-03-30T17:05:42Z

At -O2, gcc does strength reduction which should turns the modulo operations into bitmasking.

jgarzik · 2015-03-30T17:22:13Z

@sipa should, agreed. With our 256 bit C++ implemented integer type, I wonder if that is true?

sipa · 2015-03-30T17:37:03Z

There are no uint256's involved in the modulus operations. Hashing is performed, then the lower 64 bits are extracted, and then a modulus is applied. Besides, uint256 does not even offer arithmetic operations anymore. It's just an encapsulated 256-size bit vector.

1d21ba2 Scale up addrman (Pieter Wuille) c6a63ce Always use a 50% chance to choose between tried and new entries (Pieter Wuille) f68ba3f Do not bias outgoing connections towards fresh addresses (Pieter Wuille) a8ff7c6 Simplify hashing code (Pieter Wuille) e6b343d Make addrman's bucket placement deterministic. (Pieter Wuille) b23add5 Switch addrman key from vector to uint256 (Pieter Wuille)

Conflicts: src/addrman.cpp Rebased-From: b23add5 Github-Pull: #5941

This change was suggested as Countermeasure 2 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015. Rebased-From: c6a63ce Github-Pull: bitcoin#5941 (cherry picked from commit 0c6f334)

This change was suggested as Countermeasure 6 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015. Rebased-From: 1d21ba2 Github-Pull: bitcoin#5941 (cherry picked from commit aa587d4)

Even though the format of `peers.dat` was changed in a backwards incompatible way, it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin#5941 will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it.

Even though the format of `peers.dat` was changed in an incompatible way (old software versions <0.21 cannot understand the new file format), it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin#5941 (<0.11.0) will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it.

38ada89 addrman: ensure old versions don't parse peers.dat (Vasil Dimov) Pull request description: Even though the format of `peers.dat` was changed in a backwards incompatible way, it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin/bitcoin#5941 will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it. ACKs for top commit: jnewbery: ACK 38ada89 laanwj: Code review ACK 38ada89 MarcoFalke: re-ACK 38ada89 🥐 Tree-SHA512: 550bd660c5019dba0f9c334aca8a11c4a0463cfddf11efe7a4a5585ffb05549c82b95066fba5d073ae37893e0eccc158a7ffea9b33ea031d9be4a39e44f6face

38ada89 addrman: ensure old versions don't parse peers.dat (Vasil Dimov) Pull request description: Even though the format of `peers.dat` was changed in a backwards incompatible way, it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin#5941 will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it. ACKs for top commit: jnewbery: ACK 38ada89 laanwj: Code review ACK 38ada89 MarcoFalke: re-ACK 38ada89 🥐 Tree-SHA512: 550bd660c5019dba0f9c334aca8a11c4a0463cfddf11efe7a4a5585ffb05549c82b95066fba5d073ae37893e0eccc158a7ffea9b33ea031d9be4a39e44f6face

38ada892ed0ed9aaa46b1791db12a371a3c0c419 addrman: ensure old versions don't parse peers.dat (Vasil Dimov) Pull request description: Even though the format of `peers.dat` was changed in a backwards incompatible way, it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin/bitcoin#5941 will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it. ACKs for top commit: jnewbery: ACK 38ada892ed0ed9aaa46b1791db12a371a3c0c419 laanwj: Code review ACK 38ada892ed0ed9aaa46b1791db12a371a3c0c419 MarcoFalke: re-ACK 38ada892ed0ed9aaa46b1791db12a371a3c0c419 🥐 Tree-SHA512: 550bd660c5019dba0f9c334aca8a11c4a0463cfddf11efe7a4a5585ffb05549c82b95066fba5d073ae37893e0eccc158a7ffea9b33ea031d9be4a39e44f6face Former-commit-id: 216ac49972c98b79220e1f955dc7112157aaa70b

Even though the format of `peers.dat` was changed in an incompatible way (old software versions <0.21 cannot understand the new file format), it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin/bitcoin#5941 (<0.11.0) will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it.

Summary: ``` Even though the format of `peers.dat` was changed in an incompatible way (old software versions <0.21 cannot understand the new file format), it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin/bitcoin#5941 (<0.11.0) will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it. ``` Backport of core [[bitcoin/bitcoin#20284 | PR20284]]. Depends on D9201. Test Plan: ninja all check-all Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Subscribers: majcosta Differential Revision: https://reviews.bitcoinabc.org/D9202

Even though the format of `peers.dat` was changed in an incompatible way (old software versions <0.21 cannot understand the new file format), it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin#5941 (<0.11.0) will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it.

036d7ea doc: Correct description of CAddrMan::Create() (Amiti Uttarwar) 318176a doc: Update high-level addrman description (Martin Zumsande) Pull request description: The high-level description of `addrman` has outdated information with respect to the eviction behavior, both for the New and Tried tables (at least since #5941) - this has confused me in the past. This PR corrects this and also adds basic info about the bucket size and position. ACKs for top commit: amitiuttarwar: reACK 036d7ea jnewbery: ACK 036d7ea Tree-SHA512: 3f0635d765f5e580a1fae31187742a833cef66ef2286d40eeb28f2253521260038e16e5f1a65741464a2ddfdbeb5c0f1bc38bf73841e600639033d59c3c534e4

036d7ea doc: Correct description of CAddrMan::Create() (Amiti Uttarwar) 318176a doc: Update high-level addrman description (Martin Zumsande) Pull request description: The high-level description of `addrman` has outdated information with respect to the eviction behavior, both for the New and Tried tables (at least since bitcoin#5941) - this has confused me in the past. This PR corrects this and also adds basic info about the bucket size and position. ACKs for top commit: amitiuttarwar: reACK 036d7ea jnewbery: ACK 036d7ea Tree-SHA512: 3f0635d765f5e580a1fae31187742a833cef66ef2286d40eeb28f2253521260038e16e5f1a65741464a2ddfdbeb5c0f1bc38bf73841e600639033d59c3c534e4

Even though the format of `peers.dat` was changed in an incompatible way (old software versions <0.21 cannot understand the new file format), it is not guaranteed that old versions will fail to parse it. There is a chance that old versions parse its contents as garbage and use it. Old versions expect the "key size" field to be 32 and fail the parsing if it is not. Thus, we put something other than 32 in it. This will make versions between 0.11.0 and 0.20.1 deterministically fail on the new format. Versions prior to bitcoin#5941 (<0.11.0) will still parse it as garbage. Also, introduce a way to increment the `peers.dat` format in a way that does not necessary make older versions refuse to read it.

sipa added 6 commits March 23, 2015 17:00

Switch addrman key from vector to uint256

b23add5

Simplify hashing code

a8ff7c6

Do not bias outgoing connections towards fresh addresses

f68ba3f

This change was suggested as Countermeasure 2 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015.

Always use a 50% chance to choose between tried and new entries

c6a63ce

This change was suggested as Countermeasure 2 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015.

Scale up addrman

1d21ba2

This change was suggested as Countermeasure 6 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015.

laanwj added Priority High P2P labels Mar 24, 2015

laanwj added this to the 0.10.0 milestone Mar 24, 2015

laanwj merged commit 1d21ba2 into bitcoin:master Apr 1, 2015

sipa added a commit that referenced this pull request Apr 1, 2015

Switch addrman key from vector to uint256

b788994

Conflicts: src/addrman.cpp Rebased-From: b23add5 Github-Pull: #5941

reddink added a commit to reddcoin-project/reddcoin-3.10 that referenced this pull request May 27, 2020

update release notes after bitcoin#5941

878521f

vasild mentioned this pull request Nov 2, 2020

addrman: ensure old versions don't parse peers.dat #20284

Merged

mzumsande mentioned this pull request Jul 28, 2021

doc: Update high-level addrman description #22576

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Countermeasures against eclipse attacks #5941

Countermeasures against eclipse attacks #5941

Uh oh!

Conversation

sipa commented Mar 24, 2015

Uh oh!

sipa commented Mar 24, 2015

Uh oh!

sipa commented Mar 24, 2015

Uh oh!

laanwj commented Mar 24, 2015

Uh oh!

jgarzik commented Mar 24, 2015

Uh oh!

sipa commented Mar 24, 2015

Uh oh!

laanwj commented Mar 24, 2015

Uh oh!

gavinandresen commented Mar 24, 2015

Uh oh!

ghost commented Mar 24, 2015

Uh oh!

sipa commented Mar 24, 2015 via email

Uh oh!

ghost commented Mar 25, 2015

Uh oh!

fanquake commented Mar 26, 2015

Uh oh!

sipa commented Mar 27, 2015

Uh oh!

laanwj commented Mar 30, 2015

Uh oh!

gmaxwell commented Mar 30, 2015

Uh oh!

jgarzik commented Mar 30, 2015

Uh oh!

sipa commented Mar 30, 2015 via email

Uh oh!

jgarzik commented Mar 30, 2015

Uh oh!

sipa commented Mar 30, 2015 via email

Uh oh!

Uh oh!