Remove IsFromMe() call from bool CTxMemPool::accept() #2178

Because of anonymization loss concerns. Maybe it can be replaced by an argument TxIsFromMe to the accept() method to achieve the same goal.

See this thread for discussion: https://bitcointalk.org/index.php?topic=135856.0

Doesn't exploiting this require you to have the private key in question yourself...?

No. Anyone that can connect to you can check if you're the owner of a wallet address. Even if all the outputs of the address in question have been spent, there is a modification of the disclosed attack that can be used to check if you owned that address, as long as you keep the keypair in your wallet. Maybe my post was not clear enough.

Thanks Sergio, I was about to start working on a patch for this. Is that the only place in the receive-a-tx-from-the-network callchain where network behavior is different for "my" transactions than other-people's transactions?

Is far as I can see, that's the only place IsFromMe() is used in the whole main.cpp file.

I don't understand how own transactions are handled in SendMessages() (see comment "always trickle our own transactions"). Maybe there could be a problem there. I don't know.

Nevertheless it could be possible to achieve the same attack via a timing attack using SyncWithWallets() as an oracle. It is called just after tx.AcceptToMemoryPool(). An attacker could try to measure how much time SyncWithWallets() takes by sending a "ping" right after a transaction.

I really don't know if this last attack is practical.

But SyncWithWallets() does a lot of things that could take measurable time: 1- Loops over all user wallets ( SyncWithWallets()) 2- Loops over mapWallet (CWallet::OrderedTxItems()) 3- Loops over CAccountingEntry entries..(CWallet::AddToWallet()) 4 -Loops over all transaction outputs.(CWallet::AddToWallet()) 5- Loops over all transaction inputs (WalletUpdateSpent())

There are too many cases to analyze one by one for me now, and two loops that the attacker could control the number of executions. It would be a good idea to measure the time SyncWithWallets() takes per previn/prevout/waller/etc. If the measurements show that it can take over 10 msec then we could have an attack vector.

It would be better to detach SyncWithWallets() and execute the method in a different thread in order to prevent to attack more or less "by design". Nevertheless, the attacker could still try to measure the responsiveness of the peer and detect background processing even if SyncWithWallets() runs in another thread. But IMHO trying to protect oneself from this last attack would be a bit paranoic,

This source code looks interesting... it could be the source of another DoS vuln...

bool CWallet::AddToWallet(const CWalletTx& wtxIn) { ... something ... #ifndef QT_GUI // If default receiving address gets used, replace it with a new one CScript scriptDefaultKey; scriptDefaultKey.SetDestination(vchDefaultKey.GetID()); BOOST_FOREACH(const CTxOut& txout, wtx.vout) { if (txout.scriptPubKey == scriptDefaultKey) { CPubKey newDefaultKey; if (GetKeyFromPool(newDefaultKey, false)) { SetDefaultKey(newDefaultKey); SetAddressBookName(vchDefaultKey.GetID(), ""); } } } #endif

The code extracts (and probably generates) a new key from the key pool each time we get a txout with certain script. An attacker could construct a transaction with thousands of outputs similar to scriptDefaultKey, sending 1 satoshi to each one, and force the client app to generate 1000 new keypairs. (Note that scriptDefaultKey is not updated in the inner loop)

It would also bloats the size of the user wallet files and provides still another timing attack (this time much more easy) to discover which is the user's default public key.

So Jackpot! 4 attacks in one! Memory exhaustion, CPU exhaustion, hard disk space exhaustion, and loss of anonymity.

No.

There is no way for the attacker to know what your default key is, unless you tell them. They cannot find it by sending transactions to random addresses, there are 2**160 addresses.

If you do tell them, then yes, they can make you generate a new default key by sending bitcoins to that address. The new default key will be random, and so IT is not guessable unless you tell them.

Pardon. What exactly is the "default key" ? If you used that key once, then an attacker can try all possible existent keys in the blockchain until he hits your default key.

There are around 1M unique addresses in the block chain. They can all be tested against "if (txout.scriptPubKey == scriptDefaultKey)" very quickly.

And per the code you showed above, the default address is changed as soon as a transaction is received to it. So, typically, there will not be any transaction to a default address.

The point is that scriptDefaultKey is not updated in the inner loop even if is changing. So the same address can be stored in 10K prevouts, and tested at the same time, amplifying an time deviation 10K times. A 1 msec deviation will result in a 10 seconds delay.

Good code: BOOST_FOREACH(const CTxOut& txout, wtx.vout) { if (txout.scriptPubKey == scriptDefaultKey) { CPubKey newDefaultKey; if (GetKeyFromPool(newDefaultKey, false)) { SetDefaultKey(newDefaultKey); SetAddressBookName(vchDefaultKey.GetID(), ""); scriptDefaultKey.SetDestination(vchDefaultKey.GetID()); <--- this line must be added? } } }

Now I see. Yes, you're right @SergioDemianLerner. That line would prevent the amplication. It's still something that's hard to exploit nonetheless, IMHO.

Adding that line is a good idea.

Two things on the top of my TODO list right now:

1. Fix the IsMine() check in the penny-flooding-check code

2. Do not add dust-spam transactions from other people to the wallet (avoids all sorts of wallet-bloating attacks).

(2) needs some thought, though, and may make SatoshiDice customers unhappy.

@gavinandresen about 2): WHAT? and let those fill up everyone's UTXO sets forever?

@sipa The UTXO bloat can be addressed by only including them when confirmed. The penny flood breaking things can be addressed by excluding the dust in the primary coin selection but then adding them back into transactions with change as a post-processing step. ... but the incentivize the latter we need a different priority rule.

@gmaxwell Excluding them from the coin selection process is very different from not adding them to the wallet.

(regarding the exploitness of the previous vuln) It takes only 24 days, sending transactions a full 50 kbytes/sec bandwidth to test for 1M addresses (with amplification 50x) in order to discover a single default key. If generating a new keypair takes 2 msec, 50x amplification requires the attacker to be able to remotely detect an additional 100 msec from a normal round-trip delay of a message, which seems possible.. So this attack is much worse than the timing attack I published a couple of days ago (14 minutes vs 24 days)

Nevertheless, if we monitor all the output transactions of a peer, then we probably don't need to test for the 1M existent addresses but for only each new address we watch going out of the peer, then the attack becomes completely realistic.

For each new address we see, it takes only 35 milliseconds to check if it was the default key that was used!

@SergioDemianLerner : the default key is generated randomly (because keypool keys are generated randomly).

If there are ever bitcoins sent to it (thereby revealing it in the blockchain), then it is changed. That is what this code does.

So, again, unless you tell the attacker what your default key is, there is no vulnerability. You would have to send 2**159 transactions on average to guess a default key.

Ok. Thanks Gavin. I didn't know that. In CWallet::CommitTransaction() first AddToWallet() is called and then wtxNew.AcceptToMemoryPool() is called, so there should be not even a window of time for an attack.

Sorry!

Aside: Does anyone even use this default key, or can it be deprecated? I removed the functionality in bitcoin-qt because users were annoyed and confused that adresses were automatically being created.

I went back to the source code to see if SyncWithWallets() could be used as an oracle for transactions with IsMine()=true. I found that the only two timing differences from a transaction sent to me over another not sent to me are:

1. wtx.WriteToDisk() in CWallet::AddToWallet()

I haven't measured how much it takes to write to the WalletDB a 1 Mbyte tx, but its seems that the BerkleyDB has now the DB_TXN_WRITE_NOSYNC flag set, so it won't try to sync. (a 1 Mbyte sync takes 50 msec aproximately in my computer, which can be detected from a peer).

Nevertheless, if the wallet becomes constantly modified, then the backup thread (BackupWallet) that runs every 100 msec, may lock the DB for a noticeable time (say more than 100 msec), and so this could theoretically be detected from a peer. Can anyone research on this? My understanding of the WallletDB -> CDB interface is very limited.

1. BOOST_FOREACH(const CTxOut& txout, wtx.vout) in CWallet::AddToWallet()

Again, I have not tested this loop performance, but I don't think that 1M empty Txouts[] can make this loop last for more than 1 msec.

So my last word is that SyncWithWallets() seems safe.

This can be closed, as the patch got merged.