Topic: The trasaction fetch memory exhaustion attack (TFMEA) (Read 4012 times)

Large Multi-sig tx may wish yo have very large transactions.
Say if we had a 'bitcoin bank' where 9K out of 10k shareholders have to vote to pass a motion?

IMHO, there is no drawback.

The only purpose I can imagine for 1Mb transactions to be created is for mixing coins from 20K different sources, to anatomize them. But the same could be accomplished by 10 smaller transactions. Maybe 1 Mb transaction could be used for crowdfunding by 10K users, in an all-of-nothing funding, although I don't know if currently the Bitcoin protocol allows such a thing.

The pros for limiting the Tx size are many, apart from the memory consumption issue during Tx processing:

- Reduce network latency, allowing the verification of partially received blocks.
- Reduce the DoS surface, by limiting the amount of data that has to be sent in order to detect an invalid Tx.
- Reduce the DoS surface, by limiting the memory required for the in-memory pool.
- Reduce the DoS surface, by reducing the maximum number of signature verifications required by any Tx.


No, they don't have to be. Everything can be serialized. A clever re-design of the tx processing code could use a prevout cache to store only a small subset of of them in memory at any time. Pieter's 0.8 code is the right direction.

But why force any implementation ever made or future Bitcoin client to make such a twisted design choice if we can correct this today with very little effort?

I have to say that most other variables that can consume resources have been tightly limited (such as the maximum number of signature verifications, the properties of "standard" transactions, etc.)

I'm a total newb in terms of core internals, so allow me to ask if there would be a drawback in reducing tx-size to your proposed value.
Another perhaps dumb question is, why do all these transactions have to be in RAM?

Thanks, if you take the time to enlighten me a bit .

Dia

I have reviewed the current Master branch (which is the base of the 0.8 release) and I found that the vulnerability is still present.
- tx.HaveInputs(view) in CTxMemPool::accept() retrieves the compressed format of all transactions referred by prevouts.

The main difference is that referred prevouts must not have been spent.

None of the 4 possible attacks listed requires prevouts to be spent. Since the attacke is prepared by sending big transactions, and these transactions contain many outputs to make them big, they are almost incompressible with the CTxOutCompressor class.

The only drawback is that in 0.8, if the attacker wants to redo the attack, a new attack could required a new preparation stage (since the attacking transaction could have spent the prepared prevouts).  

Pieter's 0.8 code is based on the assumption that transactions get shorter as outputs gets consumed in time.
The TFMEA attack uses a transaction that refer to parent transactions that have none of their outputs spent, so basically no compression can be applied.
Even if a transaction is dissected into independent cached prevouts (instead of a single CCoins for the whole transaction), then the attacker could create a non-standard transaction with a single prevout with a huge output script. This reduces the 4 TFMEA attacks to an attacker capable of issuing non-standard transactions in blocks (which is possible today using direct connections to miners).

My conclusion: a completely proactive and formally provable protection measure against memory exhaustion attacks in transaction processing would be to reduce the maximum transaction size to 100 Kbytes or so. That would reduce both the RAM required to load each prevout and the number of prevouts a transaction may request, totaling to 200 Mbytes.

We are still capable of doing it now, using the delayed hard fork feature Gavin has added.

EDIT: Apparently reducing the max  Tx size is NOT a hardfork but a softfork ("changes which strictly reduce the set of acceptable things" (gmaxwell, 2013))

Keep in mind that there will be many people who will implement the Bitcoin protocol in a variety of languages, and most of them will not pay attention to memory consumption.

I urge people to vote for reduction of the maximum transaction size from 1 Mb to 100 Kbytes.
"That's one small step for Bitcoin now, one giant leap for its future"

Right


Version 0.8 of the Satoshi client uses a different method to handle transactions, so FetchINputs() is not present anymore.
And it's probably protected against this specific attack. I'm going to review the new code.

I created a small patch, that allows bitcoin-qt.exe on Windows to use up to 3GB RAM on x86 Windows and up to 4GB RAM on x64 Windows. This will not prevent the attack but should make it more expensive, right?

https://github.com/bitcoin/bitcoin/pull/2167

Edit: Where is CTransaction::FetchInputs in current master ? Seems there are just 4 comments refering to it (in main.h).

Dia

Interesting questions you make here Sergio. I, as a non techie user, appreciate all the thinking you made and warns about vulnerabilities.

Yes your are right. Whenever I said 488 Kbytes, read 245 Kbytes. It doesn't change much the situation. Or use 488 Kbytes transactions and double the fees paid.


Ok, good point.

Yes, please do a proof-of-concept on testnet.

I suspect this code in CTransaction::GetMinFee() makes the attacks either slower or more expensive than you estimate because fees increase for transactions larger than 250Kbytes:


I don't think these vulnerabilities are serious enough to warrant Official CVE Numbers, because I think if we create CVE numbers for every expensive-to-mount, easy-to-recover-from DoS vulnerability we will be denial-of-service-ing the attention span of users, and they might start ignoring warnings.

Ok. I will, when I have some spare time. Prepare your Windows to trash! 

It's cheaper than invalid transactions that crash most/every node how?

Gimme a testnet address I'll send you 16000 TN BTC, feel free to see if you can actually trigger it there. (Edit: On seeing this message again it seemed to me that I might have sounded dismissive there— it wasn't my intention.  I'm just offering to help out with PoCing it on testnet)

To summarize, four related attacks have been proposed:

- TFMEA Miners attack (https://bitcointalksearch.org/topic/the-trasaction-fetch-memory-exhaustion-attack-tfmea-135388)
This attack hangs every Windows/Linux-32Bit node in the network. It costs of 500K USD. Takes 21 days. 6 days if willing to waste 1.7M USD in hardware.

- TFMEA block download attack
(https://bitcointalksearch.org/topic/m.1442235)
This attack hangs a peer Windows/Linux-32Bit node. Cheap.

- TFMEA peer attack
(https://bitcointalksearch.org/topic/m.1442218)
This attack hangs a peer Windows/Linux-32Bit node. Costs 240 BTC. Money can be reused so cost can be amortized.

- TFMEA Fee-sponsored attack
(https://bitcointalksearch.org/topic/m.1442807)
This attack hangs every Windows/Linux-32Bit node in the network, with a cost of 4000 BTC).

Well, there is a variant of this attack that does not involve mining orphans.
Instead of becoming a miner, just broadcast 4000 transactions of 500 KBytes each with enough fees to make them into any block.

Currently, 1 BTC fee for each transaction would be enough for miners to accept the attackers transactions instead of any other, since the average fee per 500 Kbytes of transactions is around 0.6 BTC (this is an estimation).

So with only 4000 BTC you can execute an attack that disconnects all Windows clients at once. The attack takes 14 days to be prepared, so that gives enough time for users to upgrade (or if the core dev develops a patch fast enough)

This is the cheapest attack to the whole network ever seen.

No, thats not the security model we seek to have for obvious reasons.

In general, there are many dos attack vectors which are possible but which are not interesting because they are not transitive— and so get no amplification e.g. the attacker sends 10gigabytes to waste 10gigbytes of one nodes bandwidth (something which can't be prevented no matter how the software is written); or which are potentially transitive but require mining large number of malicious blocks that extend the current chain (which has a very high computing cost, and under a situation were a malicious party were mining lots of best blocks we'd be lucky if all they did was a dos attack).

Attacks that involve mining orphans are good to reduce, but they don't form transitive attacks so the attacker tends to get no amplification.

I remember some hero member that said that the first connection (from which the Satoshi client downloads the blockchain) should be trusted, or many other vectors of attack are possible.

Proposed solution #3, just make sure the 64 bit binaries are just as easy to get as the 32 bit ones, so most clients won't be 32 bits, and the attack won't be worth the attempt.

What about the checkpoints? When are they verified?

I don't know if transactions are verified before or after the checkpoint is reached.
If transactions are verified before, then we may have a serious problem.

Could the 2000 blocks be mined at a lower difficulty to crash clients during the initial blockchain download?

Oops.

The attack can be performed as a DoS attack to a single node without using the block chain at all.
The attack cost is 240 BTC (but probably the BTC can be reused for another attack).

Suppose the attacker is connected to the victim.

This are the steps to execute the attack:

1. The attacker has 240 BTC in a specific prevout that he owns.
2. The attacker spreads the 240 BTC in 4000 tiny outputs (Out(j)), each containing 0.06 BTC.
This will cost some additional BTC in fees. An additional 10 BTC will pay for them. The attacker may use several transactions (e.g. 100) to reduce fees.
3. The attacker builds 4000 transactions Tx(i), each of size 488 Kbytes. Each Tx(i) contains a single input Out(i) and enough outputs to fill the remaining space of 488 Kbytes. The attacker builds Tx(i) so that they will not be included in a block because of low fees.
4. The attacker sends Tx(i) one by one to the victim.
5. The victim accepts this transaction to the memory pool since GetMinFee() returns 0.0501 BTC:
(note 488 Kbytes = 499999 bytes)

 nBaseFee = (mode == GMF_RELAY) ? MIN_RELAY_TX_FEE : MIN_TX_FEE = MIN_RELAY_TX_FEE = 0.0001 BTC
 nBytes = 1000+ 498999   = 499 999
 nMinFee = (1 + (int64)nBytes / 1000) * nBaseFee = (1+499999/1000)*0.0001 = 0.0501 BTC
 if (nMinFee < nBaseFee) ( 0.0501 BTC < 0.0001 BTC ? ) NO.
 if (nBlockSize != 1 && nNewBlockSize >= MAX_BLOCK_SIZE_GEN/2) (499999 >=500000 ?) NO.
 returned -> 0.0501 BTC

6. The victim virtual address space for the application is filled and the application segfaults.

The time required for the attack, given a connection of 50 Kbytes/sec, is 11 hours.

Is this correct? Did I computed GetMinFee() correctly?

Best regards, Sergio.

Have a look at the CCoinsViewCache stuff currently in git head.

Only pruned version of transactions (= their unspent outputs + some metadata) is kept in memory, and necessary for validation. They are also kept in memory for much longer than one block, if possible.

That doesn't solve the problem, but it may make it somewhat less bad, and probably easier to deal with.