Bitcoin Forum
March 29, 2024, 03:47:18 PM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: The trasaction fetch memory exhaustion attack (TFMEA)  (Read 3962 times)
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 08, 2013, 06:25:54 PM
Last edit: January 08, 2013, 08:47:58 PM by Sergio_Demian_Lerner
 #1

The trasaction fetch memory exhaustion attack (TFMEA)

I'm publishing this attack since:

1. It's not truly practical (only if it's government-sponsored)
2. I'm unsure if it can be really done, since I haven't tested it.
3. The network can recover by simply installing a new version that offers some kind of protection.


Overview

Suppose most Bitcoin clients are installed in Windows operating systems. Suppose most people that use Windows does not compile the source code,
but download the 32 bit executable from Sourceforge, which is a 32-bit application. This assumptions seems probable in practice.

To process a transaction the Satoshi client loads all referred transactions inputs into RAM (see CTransaction::FetchInputs()).

The Attack

The attacker mines 2000 blocks. Each one containing a 1 Mbyte transaction.
Then the attacker can construct a transaction that requires 2 Gb of RAM to be processed, be linking to each one of 2000 big transactions.
All Windows clients processing this transaction will segfault. Nodes must update to recover.

How long it takes?

The fastest the attack can be made is by mining 2000 blocks as fast as possible. 2000 blocks in 10 minute intervals represents 14 days.
Because difficulty is re-computer every 2016 blocks, the attacker can also increase the total hashing power to reduce the block interval.

How much it cost to attack?

Current Bitcoin hashing power is 20000 GHash/s.
Take the Bitforce Single 'SC', which makes 60 GH/s for 1300 USD. Then 50% of the hashing power can be bought for
20000/60*1300 = 433K USD.

With 50% of the hashing power, the first 2000 blocks will contain half of the attacker's blocks, and will be mined at 2x speed.
That's 7 days. The remaining 2000 blocks (containing the other half) will be mined at a normal 1x speed.
The total atack time is therefore 21 days.

If the attacker is willing to invest more?

Investing four times that amount, or 1.7M USD, the attacker gets 80% of the hashing power.
The first 2000 blocks will contain 80% of the attackers blocks, mined in only 2.8 days.
The remaining 400 attacker blocks will take an additional 3 days.
The total atack time is therefore 5.8 days.

What if the attacker is a miner who already has 10% of the network hashing power?

We suppose the miner has already amortized his mining hardware.
We suppose than mining fees are very low compared to the 25 BTC block reward.
If we suppose that mining is profitable, then mining each block costs, on average, less than 25 BTC.
Then the attack has no cost, and it takes 140 days to store 2000 1Mb transactions in the blockchain.

Proposed Solutions

1. Limit the number of transaction bytes that a transaction can request (TxSizeRequested(Tx)<1 Mb).
 TxSizeRequested() can be computed as  
   TxSizeRequested(Tx) = Sum( for each distinct tx2 in tx.previns: Size(Tx2.Size) )
   
(this is a hard fork, but is likely that there is a  transaction in the current block-chain whose TxSizeRequested(Tx)>10 Kbytes)

OR    

2. Free older transactions while fetching new transactions in as in a sliding window, in FetchInputs().
   Reload transactions in ConnectInputs(), and dispose after verifying script.

Comments welcomed!

Edit: Piuk has discovered a worse problem: the attack could be executed during a blockchain download, where the difficulty is lower. not tested, yet.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711727238
Hero Member
*
Offline Offline

Posts: 1711727238

View Profile Personal Message (Offline)

Ignore
1711727238
Reply with quote  #2

1711727238
Report to moderator
1711727238
Hero Member
*
Offline Offline

Posts: 1711727238

View Profile Personal Message (Offline)

Ignore
1711727238
Reply with quote  #2

1711727238
Report to moderator
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1072
Merit: 1170


View Profile WWW
January 08, 2013, 08:22:35 PM
 #2

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.

I do Bitcoin stuff.
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 08, 2013, 08:31:50 PM
 #3

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.





piuk
Hero Member
*****
expert
Offline Offline

Activity: 910
Merit: 1005



View Profile WWW
January 08, 2013, 08:38:23 PM
 #4

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

Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 08, 2013, 08:42:42 PM
 #5

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

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.
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
January 08, 2013, 08:44:01 PM
 #6

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 08, 2013, 08:52:59 PM
 #7

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

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
January 08, 2013, 09:37:59 PM
 #8

I remember some hero member that said that the first connection (from which the Satoshi client downloads the blockchain) should be trusted,
No, thats not the security model we seek to have for obvious reasons.

Quote
or many other vectors of attack are possible.
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.
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 09, 2013, 01:29:00 AM
 #9

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

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.



Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 09, 2013, 01:55:24 AM
 #10

To summarize, four related attacks have been proposed:

- TFMEA Miners attack (https://bitcointalk.org/index.php?topic=135388.0)
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://bitcointalk.org/index.php?topic=135388.msg1442235#msg1442235)
This attack hangs a peer Windows/Linux-32Bit node. Cheap.

- TFMEA peer attack
(https://bitcointalk.org/index.php?topic=135388.msg1442218#msg1442218)
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://bitcointalk.org/index.php?topic=135388.msg1442807#msg1442807)
This attack hangs every Windows/Linux-32Bit node in the network, with a cost of 4000 BTC).
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
January 09, 2013, 03:40:16 AM
Last edit: January 09, 2013, 04:23:22 AM by gmaxwell
 #11

This is the cheapest attack to the whole network ever seen.
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)



Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 09, 2013, 02:53:56 PM
 #12

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)
Ok. I will, when I have some spare time. Prepare your Windows to trash!  Smiley
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652
Merit: 2164


Chief Scientist


View Profile WWW
January 09, 2013, 04:17:56 PM
Last edit: January 09, 2013, 04:35:36 PM by Gavin Andresen
 #13

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:

Code:
   // Raise the price as the block approaches full                                                                                              
    if (nBlockSize != 1 && nNewBlockSize >= MAX_BLOCK_SIZE_GEN/2)
    {
        if (nNewBlockSize >= MAX_BLOCK_SIZE_GEN)
            return MAX_MONEY;
        nMinFee *= MAX_BLOCK_SIZE_GEN / (MAX_BLOCK_SIZE_GEN - nNewBlockSize);
    }

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.

How often do you get the chance to work on a potentially world-changing project?
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 09, 2013, 08:45:39 PM
 #14

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:
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.

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, good point.
Polvos
Hero Member
*****
Offline Offline

Activity: 597
Merit: 500



View Profile
January 09, 2013, 09:19:32 PM
 #15

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

Diapolo
Hero Member
*****
Offline Offline

Activity: 769
Merit: 500



View Profile WWW
January 10, 2013, 01:37:15 PM
 #16

Quote
Then the attacker can construct a transaction that requires 2 Gb of RAM to be processed, be linking to each one of 2000 big transactions.
All Windows clients processing this transaction will segfault. Nodes must update to recover.

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 Smiley? Seems there are just 4 comments refering to it (in main.h).

Dia

Liked my former work for Bitcoin Core? Drop me a donation via:
1PwnvixzVAKnAqp8LCV8iuv7ohzX2pbn5x
bitcoin:1PwnvixzVAKnAqp8LCV8iuv7ohzX2pbn5x?label=Diapolo
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 10, 2013, 02:09:09 PM
 #17

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?

Right

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

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

Dia

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.
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 10, 2013, 06:15:28 PM
Last edit: January 10, 2013, 11:30:04 PM by Sergio_Demian_Lerner
 #18

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 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"

Diapolo
Hero Member
*****
Offline Offline

Activity: 769
Merit: 500



View Profile WWW
January 10, 2013, 08:52:13 PM
 #19

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 Smiley.

Dia

Liked my former work for Bitcoin Core? Drop me a donation via:
1PwnvixzVAKnAqp8LCV8iuv7ohzX2pbn5x
bitcoin:1PwnvixzVAKnAqp8LCV8iuv7ohzX2pbn5x?label=Diapolo
Sergio_Demian_Lerner (OP)
Hero Member
*****
expert
Offline Offline

Activity: 549
Merit: 608


View Profile WWW
January 10, 2013, 09:39:56 PM
 #20

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.

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.

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 Smiley.
Dia

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.)
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!