|
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.
|
|
|
|
Given that update ratio from 0.6.2 to 0.6.3+ has probably passed the 80% (*) barrier for a long time, I decided to publish the full CVE-2012-3789 vulnerability report, since that is my obligation with the community. https://en.bitcoin.it/wiki/CVE-2012-3789I encourage those who are working in the Satoshi client to peer review the report. Also I suggest to people working on alternate clients or derived versions to read the report and see if the attacks apply to other implementations. Best regards, Sergio. (*) Version information in https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures has been frozen for a couple of months, and I have not other source, so I'm extrapolating growth. |
|
|
|
I'm proud of myself  because I saw this kind of bug coming. I posted this line on November 6, 2012 in my blog (bitslog): "The (pseudo) anonymization property of Bitcoin is the easiest property to be lost while modifying the code, since the related code is not encapsulated in a certain class or file, but spread all over the code." |
|
|
|
|
I was thinking that only the winner could publish a block, by signing the data in the block with his private key.
|
|
|
|
Another problem is how a miner can prove that no nonce lies in the interval he has been given to test. There exists zero knowledge proof that a committed number lies on a given internal. How could one construct a proof that there is no number with certain property in an interval ?  |
|
|
|
I'd like to point out that in the thread https://bitcointalk.org/index.php?topic=131230.0 (Proof of Bets) we are analyzing a system where Miners have an incentive to cooperate to achieve greater profits, rather than to compete. I don't know if it can be done, but we're trying... |
|
|
|
Some incomplete thoughts on how to pick the winner:
Each bet i of N_i satoshis includes a secret number M_i hashed into it. Then a fair random number, M = H(M_1 || M_2 || ... || M_n) can be available later on when all n bets, totaling N satoshis, are in. Then M mod N is between N_1 + N_2 + ... + N_k and N_1 + N_2 + ... + N_(k+1) for only one k between 1 and n. This k is the winner, and his odds are exactly proportional to his wager.
There's a problem though when a player doesn't reveal their secret. I'm thinking this could be solved by having a 1-1 function on the secret numbers that's not too hard to invert, but will take enough time for all the bets to have come in. Any thoughts on what this might be? Too insecure/hard to coordinate?
It can be solved this way: 1. Suppose the n bets are N_1 to N_n and M_i are the secret numbers. 2. Let Q = H(M_1 || M_2 || ... || M_n ) 3. The outcome of the bet is computed as M = H( Q || nonce) and nonce = F (Q) . F must be a 1:1 one way function, for example, the discrete logarithm (nonce = F(Q) = DLog2(Q)) . Then there will exists only one nonce value and finding this nonce will be difficult. Also showing the nonce value is sufficient to prove that M is correctly computed, so clients must not perform any work. The network should adjust the difficulty of F so that it takes, for example, 10 minutes to evaluate, for a 1 minute block interval. Miners that try to exclude bets will have a penalty of computing time so the remaining miners will probably win (and have and advantage of 10:1 in speed). Also it's best that miners cooperate to compute the nonce instead of competing for it!! They could divide the search space between them. We've transformed a competing system into a cooperative system! The only problem I see is choosing the right F and dynamically adjusting the difficulty of the problem. |
|
|
|
Couldn't you then decrypt this by testing all known public keys against each message? The proposed method seems stronger to me. Yes, each user should have two different keypairs. And so a pubkey specifically published for encryption. |
|
|
|
My proposal doesn't require sending anything privately. All the necessary information is contained in the transaction itself. At the same time, the transaction looks exactly like the ordinary send-to-address transaction.
You can also send the factor encrypted with the recipient public key, embedded in the input script. This way it works exactly like your proposal. |
|
|
|
|
Can you use Bitcoin block hashes as a source of randomness ?
If Bitcoin is secure, then Burncoin will be, without the need for merged mining.
|
|
|
|
|
Proof of Bet - An alternative to everything else.
I proposing an alternative to proof of anything, that uses bets, and that does not require an external random source.
I'll call it Proof of Bet. (PoBet)
1. The idea is that to mine a block, users send bets. Bets are either awarded or lost (burnt coins)
2. Whenever a user places a bet, the transaction where the coins are bet is linked to a particular chain block, by sotring a hash of the block. Users bet that that a certain chain block will be the finally accepted one.
Bet = normal transaction whose first output evaluates to false, and also specifies < hash(PrevBlock) , hash(user-pubkey), block-height >
Block-height is how many blocks ahead the bet is placed for. Block-height must specify a block number which is some blocks (say 50) ahead of PrevBlock.
2. The bet affects only the block specified block-height in the chain of PrevBlock.
3. If the same coins are bet twice (for different chains), then the bet is considered invalid and the following miner can be awarded the coins by including both transactions in the block. This avoids double-betting. To be considered a double-bet, the block height values present in the bet messages of the two bets must be near (e.g. 100 blocks away from each other, at most). This allows to release some bets, if an old chain is considered dead by the network.
4. If a miner includes a bet referring to a prev-hash whose block is NOT contained in the current branch, he can collect the coins for himself by including the bet.
5. The user that has achieved to higher bet is the winner and he is able to mine the following block. If he doesn't then the second one can claim the prize by mining the following block, etc. Each client application creates a table WINNERS(i) with as an ordered list (over the bet amount) of hashes of user's pubkeys. WINNERS(1) is the one with highest bet.
6. Users are encouraged (by the application code) to wait some time before accepting a block claimed by a non-first winner (and posting bets linking to it).
The minimum time to accept the winner i could be a function like
MinTimeToAcceptWinner(i) = MinTimeToAcceptWinner(i-1)+t/(k^i)
MinTimeToAcceptWinner(1) = t
7. If it's the improbable case that no award is claimed, then miner of the FIRST block of the chain is awarded the block. If he does not claim, then the second miner that appears on the chain, and so on. (Other is to start with the miners of 1000 blocks back)
8. When a block is mined by a miner that wasn't the winner, e.g. WINNERS(2), then all users will know that there is a possibility of a rollback attack by WINNER(1). In that case they will wait for more work as confirmation on the current chain to prevent that attack. The exact number of confirmation work required to prevent any attack of this kind can be dynamically computer by clients, so confirmation work will be VARIABLE and not fixed, for a certain fixed security threshold.
9. I can think of many possibilities regarding the coins bet of users that loose:
a. They are awarded to the winner.
b. Some percentage is lost and some awarded
c. They are awarded to the winner of a the block that will be mined 100 blocks later .
d. Partially or totally returned to the original owners. (This is something like Proof of Auction)
e. They are lost forever. (I like this one most)
10. Also the bet of the winning user could be awarded to the user (returned) or burn. (I have no idea which is best)
11. To compare the work of two different chains, the total number of coins burnt is used. (The amount of burnt coins depends of the rule chosen in rule 9)
12. It's difficult to roll back a chain after n blocks because some new bets have been stored in the last n blocks.
13. If you want to create an alternate chain, the best you can do is place your own bets, and be awarded the same coins you have bet. The pot is limited to your available resources. On the contrary, the remaining users create a pot that is much bigger. The ratio between pots should be similar to the ratio between owned coins.
14. If a rogue miner X tries to prevent the inclusion of bets from other miners in a mined block, the remaining miners will penalize him by betting on an alternate chain. Then the rogue miner will loose the coins bet in his evil chain, since X bets can be awarded to the "good" miners by rule 4.
15. Normal transactions could include a hash of a previous block in the current chain (e.g. the Hash( block(current-50)) ). This will tie transactions to branches and make it more difficult to grab fees from alternate chains. This also make transactions only valid for a specified time window.
16. As in Bitcoin, periodic checkpoints would help avoid a complete re-creation of the chain.
Do you see any pitfalls?
Best regards,
Sergio.
|
|
|
|
|
Interesting...
What if the coin get stuck in a time where nobody has burn enough coins in the past two months?
No new block will appear, and there will be no re-calculation of the target price. Also there will be no more coins burnt since no new block is holding the transaction where coins are burnt.
Wouldn't that be kind of deadlock ?
|
|
|
|
bitcoin-qt tries to randomize the position of the change output, but I believe the code has a flaw:
// Insert change txn at random position:
vector<CTxOut>::iterator position = wtxNew.vout.begin()+GetRandInt(wtxNew.vout.size());
wtxNew.vout.insert(position, CTxOut(nChange, scriptChange));
The problem is that size() is one in the common case of one payee, so GetRandInt will always return 0.The change ends up in the first output.
I think it should be size()+1.
Excellent catch Hal!!!!. It's clear that is very important that programmers/researchers of the community, apart from the core developers, review the code. Some time ago I added to the Weaknesses page of the Bitcoin wiki a section "Security Vulnerabilities and bugs" ( https://en.bitcoin.it/wiki/Weaknesses#Security_Vulnerabilities_and_bugs) regarding the impact of bugs. I will update to reflect this one. |
|
|
|
Who gets to vote? Can't I just make lots of cheap nodes. Operate them honestly so that they are in everyone's good books and then abuse their voting power to double-spend. Swap IP addresses, rinse, and repeat.
True. Maybe only the last x miners with differen prog_ids are able to vote. E.g.: If the last miners were: Block n-5: A SatoshiClient 0.7 Block n-4: B XClient Block n-3: C YClient Block n-2: A SatoshiClient 0.7 Block n-1: C YClient Then a miner working on block n collects votes only from A,B,C. |
|
|
|
|
What about using the P2P network to do the work? It's more like the Bitcoin way.
The protocol would be like this:
1. A Miner X creates a block B with (reduced) PoW = Target / 50 (50 times less PoW). This ensures very few "template" blocks will be broadcast.
2. Miner starts working o the real target difficulty on block B (does not wait for votes)
3. The miner X spreads the block B in the network (with reduced PoW)
4. Nodes emit votes in a new type of message saying whether B is valid/invalid, specifying also their software/protocol version.
Vote = < hash(B), prg_id, True/False > (aprox. 30 bytes long)
5. Votes are relayed for a short period of time after block B was received (e.g. 30 seconds). Afterwards votes are discarded.
6. Miner collects votes and estimates the acceptance ratio.
7. If acceptance ratio is good, keeps working on the target PoW, if not, drops the block B and starts with another block.
The acceptance ratio could be computed filtering for noisy/forged votes (e.g. if for the same prog_id 90% votes are positive, then it's considered 100% positive).
|
|
|
|
If implementations support an efficient block template exchange and mutual verification then it could be cheap for the miner to run several implementations to test block template against before mining work is spent. They could as well run different versions of Satoshi code to ensure backward compatibility.
The actual implementation of such block template exchange would also be the testing interface implementations could challenge each other. I suggested this idea to Gavin about a month ago and he liked it. Now I see a further significant use of it.
Such use would however only be valuable if it is jointly supported across implementations, therefore suggest to evolve it as a BIP for block template challenge/response.
+1 This is the way to go forward. |
|
|
|
We must faithfully reproduce these bugs, to avoid splitting the network. Examples include but are not limited to: - Genesis block is not spendable
- CHECKMULTISIG requires an OP_0 to work around a bug
- Some transactions' hashes duplicate earlier transaction hashes, effectively making those earlier transactions unspendable. Your code must similarly do the same.
Could you create a list of issues that you know and upload it to the https://en.bitcoin.it wiki ? Or if you post the list here, I can edit the wiki. It's very important that this information is made public. |
|
|
|
The point of being vague is that us finding bugs on random code reviews isn't reliable or scalable. With your new codebase you're not solving a problem any of the current core developers have, so there isn't much incentive for us to go finding bugs for you. But if people were to use or mine upon a new implementation with bugs, that would definitely cause problems.
So what's important to demonstrate is that your code can be used without presenting a danger to the network, and that means really solid processes and testing to ensure the behavior matches exactly. If we can find one or two issues, there could well be more, so a rigorous testing and protocol compliance regime is the only way to build confidence.
I disagree with Mike and GMaxwell. Remember when Bitcoin was v0.2 ? The only thing that made it possible to reach 0.8 is by people sending as much information regarding bugs as possible. Developers can never test everything, because resources are always scarce in every software development I've ever seen in the world. With lots of bug reports, the developers can think of the best strategy for testing, concentrate in the common patterns, focus on certain modules, etc. The quality of software will always rely on the development procedures implemented. But Grau is not part of an big organization with statistical information regarding 100 previous projects, nor he has the funding for one. The best way to design the best software engineering procedures and the right testing plans for a software project with limited resources is to have the deepest knowledge about its current bugs. |
|
|
|
|
Show Posts
