Bitcoin Forum
April 17, 2014, 07:46:23 AM *
News: ♦♦ A bug in OpenSSL, used by Bitcoin-Qt/Bitcoin Core, could allow your bitcoins to be stolen. Immediately updating Bitcoin Core to 0.9.1 is required in some cases, especially if you're using 0.9.0. Download. More info.
The same bug also affected the forum. Changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: New vulnerability: know your peer public addresses in 14 minutes  (Read 4712 times)
Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
January 11, 2013, 03:27:19 AM
 #1

I really thought this had been fixed, because I commented the problem of using IsFromMe / IsMine to the developers in the github forums (https://github.com/bitcoin/bitcoin/pull/1648), but no. Not fixed, so I'd better alert people before they can be tracked...

The attack requires you to connect and be disconnected from the same node almost 11 times. Nodes do ban DoS offenders for some time, so the attack can take some days mounted from a single IP. Nevertheless, if you can control 11 different IPs (very easy), and you can re-connect to the peer, you cant still mount a successful attack in a few minutes.

The attack allows only to know the Bitcoin public address related to an IP. If a peer is using Tor, then there is no loss of anonymity.

Affected Systems
-----------------

The problem affects all versions of the Satoshi Bitcoin Client.

Summary
---------

The method CTxMemPool::accept() has a protection against 'penny-flooding'. The protection prevents a transaction with very low fees and big size to be forwarded or even stored in the memory pool.

The problem is that this protection tests if a transaction is from a wallet owned by the user, and if it's the case, then the protection is skipped. This fact can be used by the attacker as an oracle.

There are currently around 1M addresses with non-zero balance (an estimation based on http://bitcoin.stackexchange.com/questions/3524/how-many-unspent-transaction-outputs-are-there).

An attacker can discover which of the addresses are owned by a peer by the following procedure:

1. For each address, the attacker choose one unspent output Out(i)

2. Group the 1M unspent outputs in 1632 transactions Tx(j), each one containing 613 previns. Each transaction would be approximately 26999 Kbytes long. Add one output. Put zero fees. (GetMinFee() will return zero)

3. Send each Tx(j) one by one to the victim node.

4. After sending each transaction, the victim node may:

- Reject the transaction because it penny-floods (normally). In this case you will be still able to send more transactions.

- Disconnect you (DoS detection) you since you are not providing the correct signature scripts (this is the case when you have hit an owned address)


5. If you have been disconnected, repeat recursively a binary search grouping the prevouts of this transaction until you find a single one that disconnects you. Note that you may need to add additional dummy previns or prevouts to the transaction if it becomes too small to be blocked by the peer with the penny-flooding protection system.

With a 54 Kb/sec link, sending each Tx takes 1/2 sec so finding the first tx takes in the worst case, 13 minutes. Afterwards each binary search step takes 1/2 seconds in the worst case, so with 10 additional tests you can find an prevout with the desired property in 2^10 prevouts, more than the 613 originally contained, in a few seconds.

I haven´t tested the attack but, check for yourself. The explanation is clear enough. But without testing the attack, I can be mistaken.

You can protect very easily from the attack by rising the "-limitfreerelay" value to something like 1000000. Of course, that will also disable the penny-flooding protection.

Until the next vuln report,
  Yours sincerely,  Sergio.



1397720783
Hero Member
*
Offline Offline

Posts: 1397720783

View Profile Personal Message (Offline)

Ignore
1397720783
Reply with quote  #2

1397720783
Report to moderator
1397720783
Hero Member
*
Offline Offline

Posts: 1397720783

View Profile Personal Message (Offline)

Ignore
1397720783
Reply with quote  #2

1397720783
Report to moderator
Private Internet Access™ - No logs, Unlimited Bandwidth, PC Magazine's Editor's Choice
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1397720783
Hero Member
*
Offline Offline

Posts: 1397720783

View Profile Personal Message (Offline)

Ignore
1397720783
Reply with quote  #2

1397720783
Report to moderator
1397720783
Hero Member
*
Offline Offline

Posts: 1397720783

View Profile Personal Message (Offline)

Ignore
1397720783
Reply with quote  #2

1397720783
Report to moderator
Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
January 11, 2013, 04:08:33 AM
 #2

I realized that the attack can also be mounted using much smaller transactions, as long as you keep sending them fast enough to trigger penny flooding algorithm.
So just a single disconnection may be required to detect a remote public address.
No need to do any binary search. Just send each Out(i) in a single Tx(j).


Sergio.
Gavin Andresen
Hero Member
*****
qt
Offline Offline

Activity: 1330


Chief Scientist


View Profile WWW

Ignore
January 11, 2013, 04:38:45 AM
 #3

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

RE: "I better alert people before they can be tracked" :

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year. If you are worried about being tracked, you should be running bitcoin over Tor and connecting to only trusted nodes. We make no anonymity guarantees.

Will I see you in Amsterdam?
  http://bitcoin2014.com/
zvs
Hero Member
*****
Offline Offline

Activity: 854



View Profile WWW

Ignore
January 11, 2013, 02:13:12 PM
 #4

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

RE: "I better alert people before they can be tracked" :

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year. If you are worried about being tracked, you should be running bitcoin over Tor and connecting to only trusted nodes. We make no anonymity guarantees.

i entrust nogleg with all my transactions

This is no job for the police. It's something I'll have to do. Only a ninja can stop a ninja.

DOGE P2Pool 0% nogleg.net:9555
piuk
Hero Member
*****
expert
Offline Offline

Activity: 910



View Profile WWW

Ignore
January 11, 2013, 02:38:47 PM
 #5

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year.

In practice this is difficult to do accurately due to network latency and the fact that many nodes don't accepting incoming connections.

Using Sergio's method you could for example log the first 10 nodes to relay a transaction then pole each node with a penny flood transaction in order to accurately determine which one was the true sender. I may have a go implementing this to improve blockchain.info's relayed by accuracy.

kjj
Hero Member
*****
Offline Offline

Activity: 1022


Bitcoin Foundation - Lifetime Member


View Profile

Ignore
January 11, 2013, 02:49:57 PM
 #6

Dan Kaminsky demonstrated that it is pretty easy to tie bitcoin addresses to IP addresses by watching the network last year.

In practice this is difficult to do accurately due to network latency and the fact that many nodes don't accepting incoming coming connections.

Using Sergio's method you could for example log the first 10 nodes to relay a transaction then pole each node with a penny flood transaction in order to accurately determine which one was the true sender. I may have a go implementing this to improve blockchain.info's relayed by accuracy.

No, the conditional probability that a node was the origin of a transaction given that you first saw it from that node is rather small, even when you have a large number of connections.

I've checked the transactions first seen by blockchain.info from my personal node, and virtually none of the transactions that you first received from me are actually from me.

As an aside, this attack wouldn't find my wallet anyway because I run multiple nodes, and the one node that talks to the outside world has an empty wallet.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
piuk
Hero Member
*****
expert
Offline Offline

Activity: 910



View Profile WWW

Ignore
January 11, 2013, 03:00:15 PM
 #7

No, the conditional probability that a node was the origin of a transaction given that you first saw it from that node is rather small, even when you have a large number of connections.

I've checked the transactions first seen by blockchain.info from my personal node, and virtually none of the transactions that you first received from me are actually from me.

If you look at the propagation data e.g. http://blockchain.info/inv/69d689f000f59d2a9c082e50f8c6e2eb2de3a6e67dc56a13c2e7f0bd78862763 does your ip appear on the list? Sergio's method can be used to fine a list of ip's like this to find the true sender, even if it wasn't the first to relay it. If the node does not have a direct connection at all it still won't work though. In my opinion it is not a very severe issue but does make it easier to track transactions.

jgarzik
Staff
Hero Member
*****
qt
Offline Offline

Activity: 1260


View Profile

Ignore
January 14, 2013, 12:58:29 AM
 #8

Using Sergio's method you could for example log the first 10 nodes to relay a transaction then pole each node with a penny flood transaction in order to accurately determine which one was the true sender. I may have a go implementing this to improve blockchain.info's relayed by accuracy.

Doesn't that sort of strip a lot of privacy away from a lot of bitcoin users, without their consent?


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
eb3full
VIP
Full Member
*
Offline Offline

Activity: 192


View Profile

Ignore
January 14, 2013, 01:32:09 AM
 #9

Doesn't that sort of strip a lot of privacy away from a lot of bitcoin users, without their consent?

Eventualities must be embraced sooner rather than later. Running buggy/trackable software is consent enough. ;P

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
piuk
Hero Member
*****
expert
Offline Offline

Activity: 910



View Profile WWW

Ignore
January 18, 2013, 12:45:38 AM
 #10

Doesn't that sort of strip a lot of privacy away from a lot of bitcoin users, without their consent?

I was a little hasty proposing to implement it. But perhaps if it is considered a privacy leak without consent then it is probably an issue that should be patched.

Sergio_Demian_Lerner
Sr. Member
****
expert
Offline Offline

Activity: 467


View Profile WWW

Ignore
January 23, 2013, 06:00:07 PM
 #11

I added additional information regarding this vulnerability:  an additional timing attack to find the Bitcoin address of a peer, using spent outputs (before, I had discussed how to do it using only unspent outputs).

The report is on my blog: https://bitslog.wordpress.com/2013/01/23/new-bitcoin-vulnerability-get-your-peer-public-addresses/

Sergio.
hackjealousy
Jr. Member
*
Offline Offline

Activity: 53


only uses COBOL version of bitcoind


View Profile

Ignore
January 23, 2013, 09:25:12 PM
 #12

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

Similarly, using the Armory client mitigates this issue.

While this is certainly not a critical vulnerability, it is very important in terms of privacy.  Excellent find Sergio.

The root-cause of this information leak is that large transactions with insufficient fees are not forwarded or stored unless that transaction involves addresses owned by the user.  Perhaps this should be an option and the default should simply be not to forward?

The vast majority of clients will most likely keep the default which makes this essentially equivalent to enforcing transaction fees.  However, this may be a good enough reason to do so.
Wolf0
Sr. Member
****
Offline Offline

Activity: 448


View Profile

Ignore
February 24, 2013, 10:55:38 AM
 #13

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).


Is there an article in the wiki about how to do this?

BTC.sx - For an easy way to trade Bitcoin, using Bitcoin.
Buy cheap GPUs with GPU Coin
Win a video card! - Drawing/Contest
Sukrim
Hero Member
*****
Offline Offline

Activity: 994


View Profile

Ignore
February 24, 2013, 07:31:07 PM
 #14

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).

If you run (or know) a full node that you trust 100%, there's no need to replicate the block chain - the biggest amount of data you might need is a listing of all unspent outputs, the minimum amount would be probably the unspent outputs of your own addresses (doable now with bloom filters in 0.8 as far as I understood)

I think the main issue with this attack is still that Bitcoin (the "finance application") and bitcoind (the "full network node") started and still are closely interlinked. I guess in the longer run something like the approach by the armory client will emerge, where the node does not know and care anything about a wallet and the finance application won't know anything about the block chain but has to trust a node (most likely on the same PC/installation).

https://bitfinex.com <-- leveraged trading of BTCUSD, LTCUSD and LTCBTC (long and short) - 10% discount on fees for the first 30 days with this refcode: x5K9YtL3Zb
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf | https://just-dice.com/ <-- Bitcoin gambling done right!
Luke-Jr
Hero Member
*****
expert
Offline Offline

Activity: 1204



View Profile

Ignore
February 26, 2013, 10:25:01 PM
 #15

For reference, this has been assigned CVE-2013-2272

burnside
Hero Member
*****
Offline Offline

Activity: 672



View Profile WWW

Ignore
February 28, 2013, 07:39:36 AM
 #16

While we ponder this, if you are worried about this, there is a fairly straightforward workaround that will make you immune from this.

Run two bitcoin daemons.  One that is a full peer in the network, but has an empty, never-used wallet.

And another with a full wallet that connects to the full peer. You could even run them both on the same machine (you'll use double the CPU and disk space, unfortunately).


Is there an article in the wiki about how to do this?

+1

What would the configs look like for the full network peer and the internal wallet peer?

Creator of the late BTC Trading Corp / LTC-GLOBAL -- burnside's LTC Mining Pool: http://ltc.kattare.com -- Kattare: http://www.kattare.com
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!