Quote from: vectorvictor on July 02, 2011, 06:32:31 AM

Many of the passwords that *have* been cracked look pretty damn strong. Like, 14 characters long with alpha/numeric/symbol and no obvious patterns or weaknesses. Scads of them are 12-characters long. It's pretty scary, actually.

Indeed...

Code:

# Pairs of hash, password from http://www.nanaimogold.com/microlionsec.txt
$1$etIDyZ49$n26Qa/PPbQ5f3I8GIJhQM. \(]|A>9{&jp013
$1$77SRs6hW$XCXcyCNwraMZ3QY8L2eRT. hkjkGR^&$EOI(*&T
$1$WCha0X9J$71nHggA.X8/RhAB.gjY//1 vfp7U0fdl"v"LgK
$1$e/mzYsP.$H5DNwD4Njp6JNt1Kv2N.Y0 Y!m4g6s3j*

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.