You are an "evil genius", Ken. For the record, I understand that some Bitcoin fanatics despise you -- because you keep yanking the covers off their magical little world and exposing the innards. And as you've demonstrated, the innards are a bit dodgy.
This attack was rumored to be run by some Russian hackers for "lulz", using a "known vulnerability" - known to very few people. It caused quite a stir.
I'm not so sure Bitcoin fanatics despise Ken. He's incredibly informative and unbiased. His views on Bitcoin are not negative, either. I think you might be projecting or imagining things.
Wonderful content, please keep it coming!
February 15, 2014 at 11:07 AM
Anonymous said...
Why do you think Bitcoiners despise Ken? Quite to the contrary, every single Bitcoin supporter I know (including myself) think his blog posts are awesome!
There's been a dearth of good information on the Bitcoin protocol available on this low level, and many of us are totally eating it up.
Keep it up, Ken! I've been passing your links around to all the engineers and devs interested in Bitcoin that I know.
February 15, 2014 at 12:08 PM
Anonymous said...
Changing the script would invalidate the signature, no?
February 15, 2014 at 12:22 PM
Peter Todd said...
Did you only look for PUSHDATA2, or did you look for any instance of a PUSHDATA where the shortest possible encoding was not used? If you didn't do the latter, you probably have missed some examples of malleability.
Secondly the two "weird" transactions you mentioned are perfectly valid, if non-standard, transactions. The first, with OP_RETURN, was simply spending a odd P2SH output that does nothing other than pushing a large string to the stack. The second is a valid multisig output, and can be spent by providing 14 signatures with the "correct horse" pubkey.
February 15, 2014 at 12:40 PM
Anonymous said...
"Since the OP_PUSHDATA2 attack didn't start until Feb 9, this attack can't be responsible for the Feb 7 problems. One possibility is there was a different type of malleability attack that affected Mt.Gox."
I read somewhere it's also possible to malleate a tx by changing the represantional form of the signature.
Peter Todd: following your suggestion, I also looked for OP_PUSHDATA1 and OP_PUSHDATA4. I found a small number of unnecessary uses of OP_PUSHDATA1 for bulk deposits to (vanity?) address 1KiTTY2sRjPRdobHdNTzBVv7rBiNG1tX2E, but it doesn't look like malleability.
If the "correct horse" transaction I found earlier is valid, then I guess .022 BTC are up for grabs.
This Bitcoin culture is a hacker culture. We value accurate information openly and honestly presented. Where there are flaws, we want them discussed and, hopefully, fixed. We know that Bitcoin is an ongoing experiment. Ken represents the best of that culture.
Suggested edit: "Up to 25% of the RECORDED transactions" I assume that more than 25% of the transactions could have been modified, but it some cases the original transaction was recorded, not the modified one. Does anyone have an idea how many modified transactions were injected in to the network?
February 15, 2014 at 4:31 PM
Anonymous said...
Peter Todd: I'm not sure but There are actually 20 public keys for correct horse listed but only 14 pushed into the stack. Is that still a valid transaction? If it is I must have been doing something wrong...
An actual insightful, useful analysis of what happened. Well done! Of course it got buried under all the sensationalist crap on Reddit.
Nice observation that the malleability abuse DOS only started *after* MtGox discovered having problems. I remember someone on reddit asking for a 'malleability bot' shortly after the MtGox press release, so it's likely multiple people got the same idea at the same time.
And indeed: the type of malleability used 'against' MtGox was different. Their software was creating transactions with extra padding in the DER encoding of the signatures (#2 in https://gist.github.com/sipa/8907691). 0.8.0 added canonization rules to forbid these to restrict malleability. So all the 'attackers' did was remove this extra padding and their version of the transaction was accepted. No need for pushdata mutations.
February 16, 2014 at 1:05 AM
Anonymous said...
Ken can you look for all transactions that _don't_ use PUSHDATA? You should be able to set up a pretty good regex to find every "odd" transaction.
February 16, 2014 at 1:43 AM
Anonymous said...
Blockchain.info displays non-standard scripts incorrectly in many cases. If you use bitcoind decoderawtransaction you'll see the script does have "20" in the right places. The 0.022BTC are up for grabs, along with a few other non-standards - just a little encouragement to those new to cryptocurrencies to dig under the surface and learn.
Anonymous: I also scanned for "odd" transactions in the blockchain. There are roughly a zillion of them, in a huge variety. It's hard to conclude anything except people do a lot of crazy stuff with the Bitcoin protocol.
Hi Ken. This is really interesting, although I don't really have the knowledge to fully understand it all. The question I'm left with is: Can you figure out how much money Mt Gox was conned out of?
Andy: I can't figure out what MtGox lost for two reasons. First, if signature malleability is their problem, the "bad" transactions will drop out of the system leaving only the "good" transactions, so there's nothing unusual to find in the blockchain. Second, I don't know what addresses MtGox uses.
MtGox transactions have failed often in the past due to a bunch of issues (missing fee, transactions too large, double spends) as well as invalid signatures. So it seems like there's a long history of faulty transactions.
Doesn't this analysis prove that Gox's/SR2's claim that this transaction malleability attack is bs? If you add up all the transactions that were malformed the total isn't anywhere near the 750k from Gox + whatever went "missing" some SR2
Mt Gox addresses are pretty well known. To determine the quantity of coin Mt Gox lost to tx ID malleability scan the chain for non-padded DER signature encoding originating from a Mt Gox on-line wallet address then look for recent txs with identical outputs from Mt Gox with padded DER encoded signatures. The BTC value in the output will be lost from the wallet. If no duplicate is found then correlate the outputs with a refund in the Mt Gox internal transaction log.
Mr. Ken, you've explained the whole vague topic of malleability to me very smoothly. I'm actually conducting a research on the crash of Bitcoins and the factors responsible therein. as a conclusion i've to put up the probable solutions that could bring btc right back on track and make it a risk-free currency instead of a medium of internet vice. i would really appreciate if you could state your suggestioms and recommendations to improve the working of BTC.
April 16, 2014 at 11:38 PM
Anonymous said...
Hey Ken, can you provide information where you got your data (especially for the graph) from? Thanks!
Anonymous: you asked where I got the data. I wrote a slow, hacky Python script to go through the blockchain data, parse the transactions, and look for OP_PUSHDATA2.
July 5, 2014 at 2:31 PM
I have a new Bitcoin article:
Hidden surprises in the Bitcoin blockchain
The Bitcoin network was subject to a strange attack this week. Up to 25% of the recorded transactions were modified using a technique called transaction malleability. By examining the Bitcoin blockchain, I've created an hour-by-hour look at the attack.
For details on how transaction malleability works, see my article Bitcoin transaction malleability: looking at the bytes.
As a quick summary, the attacker takes a new Bitcoin transaction, modifies it in a trivial way that changes the transaction hash, and sends it back into the Bitcoin system.
The modified transaction functions exactly the same (transferring the bitcoins between the same addresses), but results in two slightly different versions of the transaction in the system.
However, if client software or exchange software depends on the transaction hash, temporarily having two different hashes for the transaction can cause a variety of problems.
The reason malleability is possible is that inside a Bitcoin transaction is a tiny program that provides the signature data. This script pushes the (hex) 48 byte signature by using the instruction 48. An attacker can change the script to use the OP_PUSHDATA2 instruction (4d) followed by a two-byte length (48 00). The modified transaction is still valid, since the script has exactly the same action.
Tracking the malleability attack
I created the graph below, which shows the hourly progress of the attack: the blue line is the total number of Bitcoin transactions, and the green line is the number of transactions that were modified by the malleability attack.
[Image]
Graph of Bitcoin transactions suffering from malleability attack, Feb 2014.
The attack started off affecting a fairly small number of transactions on Feb 9.
The malleability attack itself appears to have started in block 284980 (Feb 9, 8:12 PST), which contains 36 modified transactions.
Since the number of affected transactions in this block and following blocks was small, I wonder if this was a test phase for the attack.
The attack really took off the morning of February 10. At the peak, up to 25% of Bitcoin transactions were modified.
The attack ended fairly abruptly the morning of Feb 11. I made a bunch of transactions that evening, hoping to see a modified one, but I was disappointed that they all went through untouched.
A few modified transactions continued to trickle in for the next few days, with some even today (Feb 14). Some of these are older transactions that were mined very slowly because they didn't include any fees. For example, this transaction was modified on Feb 10, but not mined until Feb 14.
History of OP_PUSHDATA2 usage
I wanted to find out if there were any precursors to the malleability attack, or any similar attacks earlier.
I scanned the entire blockchain looking for transactions using the OP_PUSHDATA2 opcode, which is used in the malleability attack. (As an aside, the Bitcoin data is a pain to parse for several reasons.)
Up until the attack, OP_PUSHDATA2 was very rare.
I saw OP_PUSHDATA2 used in July 2013 here for a strange - but not modified (malleated?) - transaction. OP_PUSHDATA2 was used again in November 5 (here)when someone used OP_PUSHDATA to include a joke signature in the transaction:
I should not run the washing machine while listening to WZBC. I managed to convince myself that the machine was slowly failing -- that a rythmic, squeaking noise it had been making had gotten a little worse. Ten minutes later, though, the machine had paused. But the noise was still there. All that text is stored inside the Bitcoin transaction. There are a bunch of ways to "hide" text messages in the blockchain, and this transaction used an unusual one.
On Feb 4, this transaction used OP_PUSHDATA2 in a strange broken transaction that wasted 0.001 BTC. Interestingly, the sibling transaction wasted 0.03201 BTC in a broken MULTISIG transaction with the "correct horse battery staple" public key. I conclude that someone was trying out strange things on Feb 4, including the rare OP_PUSHDATA2 instruction. Was this debugging for the malleability attack a few days later or was this unrelated experimentation?
Some conclusions
There has been some speculation that the malleability attack directed the modified transactions to a specific miner. However, I looked at the blocks containing these transactions, and they come from a variety of well-known miners. So there's nothing miner-specific about this attack. The attackers don't have their own mining pool.
There's a 100-millisecond sleep in the Bitcoin peer's message processing loop. There has been speculation that the attacker could beat regular peers by avoiding this loop: regular peers would wait 100ms to pass along messages, while the attacker could get a transaction, modify it, and send it to a miner immediately. This seems plausible to me.
One puzzle is that Mt.Gox announced their difficulties on Feb 7, and then explained Feb 10 that they were stopping withdrawals due to a malleability attack. Since the OP_PUSHDATA2 attack didn't start until Feb 9, this attack can't be responsible for the Feb 7 problems. One possibility is there was a different type of malleability attack that affected Mt.Gox. It would be interesting to get the hash for one of the affected transactions from before Feb 7, to see what was going on.
Around the same time as the malleability attack, many people received tiny payments from 1Enjoy and 1Sochi addresses. I believe all these payments were rejected by miners as junk and remain unconfirmed. As far as I know, there is no connection between these tiny spam payments and the malleability attack, but the timing is suspicious.
"The Bitcoin malleability attack graphed hour by hour"
23 Comments -
You are an "evil genius", Ken. For the record, I understand that some Bitcoin fanatics despise you -- because you keep yanking the covers off their magical little world and exposing the innards. And as you've demonstrated, the innards are a bit dodgy.
This attack was rumored to be run by some Russian hackers for "lulz", using a "known vulnerability" - known to very few people. It caused quite a stir.
http://siliconangle.com/blog/2014/02/12/bitcoin-weekly-2014-february-12-bitcoin-wide-transaction-malleability-attack-apple-blocks-bitcoin-wallets-fiverr-accepts-btc-and-more/
http://www.informationweek.com/security/attacks-and-breaches/bitcoin-exchanges-buckle-under-ddos-attacks/d/d-id/1113809
http://www.forbes.com/sites/andygreenberg/2014/02/13/silk-road-2-0-hacked-using-bitcoin-bug-all-its-funds-stolen/
February 15, 2014 at 1:30 AM
I'm not so sure Bitcoin fanatics despise Ken. He's incredibly informative and unbiased. His views on Bitcoin are not negative, either. I think you might be projecting or imagining things.
Wonderful content, please keep it coming!
February 15, 2014 at 11:07 AM
Why do you think Bitcoiners despise Ken? Quite to the contrary, every single Bitcoin supporter I know (including myself) think his blog posts are awesome!
There's been a dearth of good information on the Bitcoin protocol available on this low level, and many of us are totally eating it up.
Keep it up, Ken! I've been passing your links around to all the engineers and devs interested in Bitcoin that I know.
February 15, 2014 at 12:08 PM
Changing the script would invalidate the signature, no?
February 15, 2014 at 12:22 PM
Did you only look for PUSHDATA2, or did you look for any instance of a PUSHDATA where the shortest possible encoding was not used? If you didn't do the latter, you probably have missed some examples of malleability.
Secondly the two "weird" transactions you mentioned are perfectly valid, if non-standard, transactions. The first, with OP_RETURN, was simply spending a odd P2SH output that does nothing other than pushing a large string to the stack. The second is a valid multisig output, and can be spent by providing 14 signatures with the "correct horse" pubkey.
February 15, 2014 at 12:40 PM
"Since the OP_PUSHDATA2 attack didn't start until Feb 9, this attack can't be responsible for the Feb 7 problems. One possibility is there was a different type of malleability attack that affected Mt.Gox."
I read somewhere it's also possible to malleate a tx by changing the represantional form of the signature.
February 15, 2014 at 12:43 PM
Inside Job IMHO
February 15, 2014 at 1:25 PM
Peter Todd: following your suggestion, I also looked for OP_PUSHDATA1 and OP_PUSHDATA4. I found a small number of unnecessary uses of OP_PUSHDATA1 for bulk deposits to (vanity?) address 1KiTTY2sRjPRdobHdNTzBVv7rBiNG1tX2E, but it doesn't look like malleability.
If the "correct horse" transaction I found earlier is valid, then I guess .022 BTC are up for grabs.
February 15, 2014 at 4:00 PM
This Bitcoin culture is a hacker culture. We value accurate information openly and honestly presented. Where there are flaws, we want them discussed and, hopefully, fixed. We know that Bitcoin is an ongoing experiment. Ken represents the best of that culture.
Suggested edit: "Up to 25% of the RECORDED transactions" I assume that more than 25% of the transactions could have been modified, but it some cases the original transaction was recorded, not the modified one. Does anyone have an idea how many modified transactions were injected in to the network?
February 15, 2014 at 4:31 PM
Peter Todd: I'm not sure but There are actually 20 public keys for correct horse listed but only 14 pushed into the stack. Is that still a valid transaction? If it is I must have been doing something wrong...
February 15, 2014 at 7:54 PM
This guy also warned of the attack scheme, but not much attention was paid it seems i_think_i_may_have_caused_the_bitcoin_attack
February 15, 2014 at 9:23 PM
An actual insightful, useful analysis of what happened. Well done! Of course it got buried under all the sensationalist crap on Reddit.
Nice observation that the malleability abuse DOS only started *after* MtGox discovered having problems. I remember someone on reddit asking for a 'malleability bot' shortly after the MtGox press release, so it's likely multiple people got the same idea at the same time.
And indeed: the type of malleability used 'against' MtGox was different. Their software was creating transactions with extra padding in the DER encoding of the signatures (#2 in https://gist.github.com/sipa/8907691). 0.8.0 added canonization rules to forbid these to restrict malleability. So all the 'attackers' did was remove this extra padding and their version of the transaction was accepted. No need for pushdata mutations.
February 16, 2014 at 1:05 AM
Ken can you look for all transactions that _don't_ use PUSHDATA? You should be able to set up a pretty good regex to find every "odd" transaction.
February 16, 2014 at 1:43 AM
Blockchain.info displays non-standard scripts incorrectly in many cases. If you use bitcoind decoderawtransaction you'll see the script does have "20" in the right places. The 0.022BTC are up for grabs, along with a few other non-standards - just a little encouragement to those new to cryptocurrencies to dig under the surface and learn.
February 16, 2014 at 6:51 AM
Anonymous: I also scanned for "odd" transactions in the blockchain. There are roughly a zillion of them, in a huge variety. It's hard to conclude anything except people do a lot of crazy stuff with the Bitcoin protocol.
February 16, 2014 at 9:11 AM
Hi Ken. This is really interesting, although I don't really have the knowledge to fully understand it all. The question I'm left with is: Can you figure out how much money Mt Gox was conned out of?
Thanks, Andy
February 20, 2014 at 8:05 AM
Andy: I can't figure out what MtGox lost for two reasons. First, if signature malleability is their problem, the "bad" transactions will drop out of the system leaving only the "good" transactions, so there's nothing unusual to find in the blockchain. Second, I don't know what addresses MtGox uses.
MtGox transactions have failed often in the past due to a bunch of issues (missing fee, transactions too large, double spends) as well as invalid signatures. So it seems like there's a long history of faulty transactions.
February 21, 2014 at 8:46 AM
I can confirm the multisig transaction was in fact valid. As nobody else did until now, I just claimed it.. :-)
Here the tx I created to spend the multisig tx:
https://blockexplorer.com/rawtx/da738e29f64e90ae46dcc3e6b4154041d6324abbe7919e722d486a4a3148b7dc
February 23, 2014 at 12:59 PM
Doesn't this analysis prove that Gox's/SR2's claim that this transaction malleability attack is bs? If you add up all the transactions that were malformed the total isn't anywhere near the 750k from Gox + whatever went "missing" some SR2
February 25, 2014 at 5:43 AM
Mt Gox addresses are pretty well known. To determine the quantity of coin Mt Gox lost to tx ID malleability scan the chain for non-padded DER signature encoding originating from a Mt Gox on-line wallet address then look for recent txs with identical outputs from Mt Gox with padded DER encoded signatures. The BTC value in the output will be lost from the wallet.
If no duplicate is found then correlate the outputs with a refund in the Mt Gox internal transaction log.
March 23, 2014 at 9:52 PM
Mr. Ken, you've explained the whole vague topic of malleability to me very smoothly. I'm actually conducting a research on the crash of Bitcoins and the factors responsible therein. as a conclusion i've to put up the probable solutions that could bring btc right back on track and make it a risk-free currency instead of a medium of internet vice.
i would really appreciate if you could state your suggestioms and recommendations to improve the working of BTC.
April 16, 2014 at 11:38 PM
Hey Ken,
can you provide information where you got your data (especially for the graph) from? Thanks!
June 25, 2014 at 6:41 AM
Anonymous: you asked where I got the data. I wrote a slow, hacky Python script to go through the blockchain data, parse the transactions, and look for OP_PUSHDATA2.
July 5, 2014 at 2:31 PM