No need to "split the internet". The attacker simply withholds the forked blocks, on the pool's server, that are being solved by the miners. Remember that these miners are not connected to the Bitcoin peer-to-peer network. There is no need to isolate them.

But in my attack, the attacker doesn't have to start "far back" in the chain. He starts forking it from the last known legitimate block... (sorry for my multiple edits, this is complicated)

No. Run the math. Run the sample Poisson code provided in the whitepaper. An increasing number of confirmations only protect Bitcoin for q < 0.5.
For q >= 0.5, no amount of confirmations can protect anything.

No, you won't notice a reduced hashrate that lasts for as little as 2h. I showed in the example that it happens all the time, eg. today. Did you find this suspicious? No. Did anyone else? No.

Also, as pointed out by DamienBlack, no pool miner checks that their blocks are in the legit block chain. No one verifies the 80-byte block header they are hashing.

You don't have to maintain the forgery sequentially.

You misunderstand the math that explains why this specific number of confirmations was chosen by some exchanges/merchants.

Read the original Bitcoin whitepaper http://bitcoin.org/bitcoin.pdf (section 11). If an attacker possesses 10% of the global hashrate (q = 0.1), in order to reduce the probability of a double spend to less than 0.1%, you should wait for 6 confirmation, ie. force the attacker to fork the chains from 5 blocks behind, that's the z=5 quoted in this section. These are the design parameters that the 6 confirmations are supposed to protect against.

If an attacker has 50% of the hashrate (q = 0.5), then the math is completely off. No amount of confirmations is going to protect you against that.

As a side node, I think there is an approximation error, or rounding error when running the sample code with q = 0.5, because it shows the attacker would have a 100% success rate (it should be 50%).

Be creative: you could double your gains by robbing the pool and performing a double spend on this money!

No. The probability of outpacing the legitimate chain after N blocks, no matter what N is, is always 50%.

Think about it. You don't need to outpace every single block. Only the last one matters.

No. The probability of outpacing the legitimate chain with exactly 50% of the hashrate is 50%.

Correct. The 500 BTC txfer to the exchange would need to be in the "legit" chain. I fixed my original post.

DamienBlack: I wrote this as a counter-example to your comment in another thread that a 50% attack would be statistically noticed in the global hashrate.

I doubt Tycho keeps tens of thousands of BTC on his online infrastructure. His pool profits (~3% fee) only amount to ~100 BTC per day. But my counter example was also to illustrate that Deepbit, with its size, is now a valuable target to any attacker out there. The fact a pool owns ~50% of the hashrate is bad not only for Bitcoin, but also because it concentrates risk. My advice to users is to not keep any significant amounts of BTC in their Deepbit account.

Well, many (most?) pool users automatically withdraw their BTC balance to their wallet. If the attacker diverted the blocks to keep the BTC he would not be able to honor these withdrawals and would be noticed very quickly, perhaps after mining only a few hundred BTC.

Whereas my attack works with any amount of BTC (I should have picked a few thousand BTC as an example). The only limit is your budget to purchase the initial amount. And withdrawal restrictions on the exchanges. But there are ways to bypass them (register multiple accounts, sell your USD balance on bitcoin-otc, etc).

No problem. I also quickly resell this remaining 500 BTC right after my attack.

A double spend attack may be detectable after the fact, but is not likely to be stopped on time to prevent BTC theft. Pool owners with a significant hashrate are not the only persons capable of using it to their advantage. Here is an example: I am Malory, the proverbial malicious attacker, and I want to attack the Deepbit pool, managed by Tycho.

(Edit: Fixed the chain on which the BTC needs to be spent - thanks kjj/DamienBlack).
(Edit: Replaced fictional "500 BTC" amount with "10k BTC").
(Edit: Removed mentions of "50% hashrate" to emphasize that it is not required to perform a double spend.)

Step 1: I buy 10k BTC and transfer them to my wallet.

Step 2: I attack Deepbit's infrastructure to surreptitiously gain administrative control of the servers (eg. via a compromise of Tycho's workstation). Optionally, I also rob the pool of its BTC to further maximize my gains (using the pool's computational power to double spend its own money - hah!)

Step 3: I select a period of time of 2 hours during which Tycho is offline/sleeping. 2 hours is all I need because his pool, Deepbit, controls about half of the global Bitcoin network hashrate. Note that controlling exactly 50% or more is not necessary; if less than 50%, the probability of the attack being successful is simply lower.

Step 4: During these 2 hours, I send pool users work items to start forking the block chain, from the current legitimate block, but without broadcasting the forked blocks to the global Bitcoin network. The only visible effect is that the global network appears to solve ~6 blocks (instead of ~12) during these 2 hours; but no one notices because it happens all the time due to expected statistical variation. As a matter of fact, it is happening right now: in the last ~110 minutes only 6 blocks have been solved (135104-135109), and there is no reason to find this suspicious whatsoever.

Step 5: In the legitimate block chain (built by miners not in the pool), I include a transaction to transfer 10k BTC from my wallet to my TradeHill/Bitcoin7/MtGox account.

Step 6: TradeHill/Bitcoin7/MtGox detects my txfer after the legitimate block chain grows by 6 blocks (6 confirmations). I sell the 10k BTC.

Step 7: Profit! I have plenty of USD in my account. I quickly sell it on bitcoin-otc (eg. using MtGox's merchant API), or transfer it to my Dwolla account, or multiple accounts to bypass typical withdrawal limits.

Step 8: During this time, my forked chain should have grown 1 more block than the legitimate chain (if the attack was successful). I broadcast it to the network, which instantly invalidates the 10k BTC I transferred to TradeHill/Bitcoin7/MtGox. The 10k BTC automatically "reappears" in my original wallet (which I can now double-spend). The exchange is short on BTC and is screwed. An investigation later in the day reveals that Tycho's pool was compromised. Tycho's reputation is ruined. People switch to another pool, which gains 50% of the hashrate. I repeat the same attack on the other pool, and double spend again the BTC stolen from previous pools. Rinse and repeat.

cypherdoc: Correct. But cracking the hashes is still valuable due their re-use on other sites (Paypal, MyBitcoin, etc).

A few passwords of length 22 or more have been discovered (none of them are yours):


The first 3 passwords are concatenations of simple words with simple mangling rules (digits/symbols appended, and a capitalization) which could have been bruteforced somewhat easily. If your password was similar, then it was weak.

However, if your password was similar to the others more complex ones, then one of these 3 possible explanations is true: http://forum.bitcoin.org/index.php?topic=24727.msg317542#msg317542

As one of the few users with ~1k posts on this forum, therefore a likely valuable Bicoin-rich target, I think you should envisage the possibility that you have been the victim of a targeted attack (not necessarily via an MtGox flaw). You wouldn't be the first one --you remember allinvain and his 25k BTC stolen... Even Snort + fw + browsing in a VM would not have protected you against, say, a tabnabbing phishing attempt. (I mention this example again because of how deceptively efficient it is...)

On the other hand, I have no idea how security-proficient you really are. You know Snort and firewalls, but the fact you exaggerate (few sites/apps accept "random >60characters password") makes it difficult for me to evaluate you. You say your MtGox pw was shorter than usual; would you mind sharing its exact length?

The question of AMD or Intel platforms basically doesn't matter. But AMD almost always comes out a few bucks cheaper, and Bitcoin miners are tightwads, so that's one reason they favor it :-)

Also, the cheapest AMD processors ($38 Sempron 140, or half the price of your Intel G620) can be used in both entry-level motherboards with x1 slots (for someone who wants to connect his GPUs with PCIe extenders) as well as high-end motherboards with 4 or more x16 slots (for someone who doesn't want to mess with extenders). On the other hand, Intel artificially segment the market: the cheap motherboards typically take LGA775 processors, whereas high-end ones require more expensive processors. AMD's more flexible upgrade path is definitely one more aspect favored by miners who frequently rebuild/upgrade their GPU farms, as they can re-use the same processors and RAM.

Attackers don't need to tie identities. Previously broken passwords are added to dictionary lists and are blindly tried against all newly leaked accounts.


This contradicts your first post which says "my password was not the most secure". So which is it?

Don't be so negative with me. I am just trying to help you understand how your account was hacked. Multiple possibilities:
1) The majority of MtGox users who were hacked were knowingly using insecure passwords. Not your case.
2) A smaller but still considerable fraction of users had a misconception of what a secure password is. May be your case.
3) Finally, a minority were using perfectly secure passwords (see examples in my last post). These users either shared passwords with other sites that have been hacked, or were phished (eg. even experienced IT security professionals may fall for tabnabbing!), or were the victim of targeted attacks on their personal computers (eg. malware installing a keylogger). May be your case.

Indeed...


There is no way the passwords above have been bruteforced by conventional mechanisms. MD5-based crypt() can be theoretically attacked at 10 Mpw/s on an HD 6990 (the best public bruteforcer, oclHashcat, only achieves 5 Mpw/s on this card). Given a search space of length 10 and random printable ASCII chars (and the passwords above are even stronger), and a private tool doing 10 Mpw/s, it would take on average 948 years on a cluster of 100 HD 6990 to bruteforce only one of them! Therefore, there are only a few possible theories:

• Theory 1: The attacker compromised MtGox.com and logged the passwords on the server side, for every authentication attempt. This would be very serious. MagicalTux has not hinted this was a possibility. (But who knows? He doesn't seem very good at investigating breaches, eg. he first denied evidence of SQL injection, then confirmed there was one, etc).
  
• Theory 2: The attacker phished passwords or keylogged them in targeted attacks against specific individuals. This seems possible given previous reports of individuals having had their Bitcoins stolen from their personal computers.
  
• Theory 3: Inside Job. MtGox had to scale up very rapidly these past few months. They may have hired one individual, without proper background checks, who is stealing passwords and money from the MtGox infrastructure.
  
• Theory 4: The MtGox password hashes were compromised before April 2011, when raw MD5 hashing was in use (MagicalTux said he started migrating to salted MD5-crypt only 2 months ago). This would have made bruteforcing 1000x faster for a single password, and doable in parallel on all hashes instead of one at a time (thanks to the absence of a salt). It would have taken the same cluster of 100 HD 6990 described above about a year to cover a 10-char random printable ASCII search space. However, given the large number of hashes (65k), a fraction of them would have been broken after 2 months of bruteforcing. However theory 3 is not very likely, after all the passwords shown above are even longer than 10 chars.
  

This statement indicates that your password was insecure.

If all it takes to risk guessing your password is to know your password generation logic, then the breach of any of the dozens of websites on which you have a password-protected account, may have helped the attacker in guessing your password. What happens when a password hash leak occur is that attackers generate candidate passwords based on bruteforcing results from previous leaks (Gawker, phpbb, MySpace, etc). They read them, try to understand how users picked them, and they adjust the mangling rules in their bruteforcers.

Also you would not be the first one to think your password was relatively secure when in fact it turned out to be complete crap (this guy claimed his password was secure, and even lied about its length, when it was in fact "rascal101").