MtGox salted passwords cracked
pastebin.com
pastebin.com
you start with a dictionary. a good dictionary combines multiple passwords, slang, common patterns of keys on the keyboard, and old, known, passwords (so all the entries here will be added, for example).
but that's just the start. the cracking programs also have rules. in simple terms these can be "shift to upper case" or "combine two words from dictionary" or "reverse word" or "replace "e" with "3". and there are common sets of rules that people develop (and test) that do standard transformations like automatically making passwords "leet", or extending with common sequences (123), etc.
and you can automate this. so something like hashcat will generate random rules and apply them to the dictionary. because the rules are written so that they can be composed this is surprisingly powerful and probably explains some of the "harder" cracks on this list.
the only way to beat this, then, is to use random passwords (for example, as generated by keepass) and to make them large enough that just running through every combination doesn't work.
on size: what is important is the number of available combinations. systematic cracking - trying every possible combination - still uses common characters first so "size" is a combination of character variety and number of characters. again, something like keepass makes this easy.
finally, note that on some old or poorly maintained systems, you may be restricted (perhaps without knowing) to 8 characters. then using a wide range of characters is critical.
i know this is obvious to many, but some of the comments about "hard" passwords made me think it might be useful...
It's only technically "buying some time." In reality it's keeping it completely secure.
And what use would a hacker have attacking a whole database full of them? It would take too long to do it, even with less secure passwords. It takes your fruit out of the "low hanging" category, which is a bit of security in itself.
My question: is there an intrinsic weakness in storing these passwords at a central location? E.g. would it be feasible that LastPass gets targeted by a complicated blackhat attack, and then instead of losing just one of my passwords I lost them all? Or is the manner in which they are encrypted and transmitted secure enough to prevent this?
Thanks.
That's the weakness of services that are supposedly "Host-proof". If the host is sending you the webapp/javascript/webpage in which your data is decrypted, each and every time you visit their website, you have to trust that they wont (or someone else wont) modify it in a malicious way in order to gain access to your data.
The only way to be safe from this kind of attack is to use the same trusted copy of the code, and not use any new versions until you trust that it is also safe, or to somehow verify that the webpage sent to your browser is exactly what you expect it to be.
Cortesi has a very good write up on this issue: http://corte.si/posts/security/hostproof.html
An alternate option to reduce some of this: http://www.rakkhis.com/2011/06/i-was-hacked-mtgox-bitcoin-3-...
a dictionary + rules + time. yes (i assume - i have no inside knowledge).
[...] passwords which were randomly generated are, and are likely to remain, safe?
it depends on the length and range of characters. random passwords are still vulnerable if they are short and/or use a restricted range of characters. they can be found "by accident" when using rules and dictionaries. they can also be found by simply trying all combinations ("a", "b", ..., "aa", ..., "ab"...). length and character range protects against both of these.
it's likely that attackers will use all available approaches, including simple brute force. i focused on dictionaries + rules above because (1) that's generally more efficient and (2) some people don't seem to realize how powerful it is.
Also, if there is no restricted range of characters, and a solid, random password is used, how can the attacker know when they have broken it, short of trying them all against the actual server?
Edit: Forget that last bit. I'm confusing myself.
You just keep going in bruteforce and build bigger rainbow tables / variant dictionary attacks. Given a large number of GPU's you will get all passwords.. time though could be a number of years to thousands of years.
I guess if this ever actually became a relevant concern, you'd simply keep adding a few extra chars to the hashing algorithm output to keep it beyond the range of reasonable.
9 = 58.5-bits
10 = 65.0-bits
11 = 71.5-bits
Edit: Spelling & Grammar
WTF. some fuckwit downvoted this? i wrote the text i am correcting. screw you. why do i bother to write useful comments? this place gets worse.
Also, some downvotes are cast in error. This is very easy on touch-screens, and occasionally a problem elsewhere. Since totals are no longer displayed, a person may not even realize their intended upvote registered as a downvote.
So assume it was a mistake. Or a hopelessly grumpy person whose bad attitude is best ignored, rather than amplified with curses and complaints. Brush off the first downvote or two, and well-considered upvotes follow soon enough.
so what's D? i imagine most people would use common words, so let's take the most popular 1 percent of "dict/words" on my computer. that's 4,000 words. log2(D^N) = N * log2(D) = N * 12 (since log2(1000)~10).
now in another thread here there's an article saying that 9 characters drawn from an alphabet of 100 (lower+upper+symbols) is around the current limit. the equivalent number of bits there is log2(100^9) = 60. so you'd need about 5 words (5*12=60) for the same level of security.
tl;dr: you need more than 5 words (very) roughly. i am not 100% sure i have the maths right, either :o)
in more practical terms, i don't know of a program that actually does this. the programs i know about typically only combine a few words. but i am no great expert, and it would be fairly easy to write such a program.
[edit: actually, you are less safe than i estimate above if the attacker is smart, because the words probably aren't independent (most people will use meaningful sentences). so you can use markov chains to hugely reduce the search space (in more general terms: "the" will be followed by a noun phrase, etc). so you need significantly more than 5 words. heh. if someone wants to pay me to write such a program, please get in touch... ;o]
This is not the case.
These are crypt(3) strings and the $1$ at the beginning signifies the hash scheme used, not the salt--$scheme$salt$hash. The 1 means that FreeBSD-MD5 is the algorithm used, which is basically MD5 with the salt iterated 1000 times.
/*
* and now, just to make sure things don't run too fast
* On a 60 Mhz Pentium this takes 34 msec, so you would
* need 30 seconds to build a 1000 entry dictionary...
*/
for(i = 0; i < 1000; i++) {
MD5Init(&ctx1);
if(i & 1)
MD5Update(&ctx1, (const u_char *)pw, strlen(pw));
...
config.stretches = Rails.env.test? ? 1 : 10
Most of the longer ones seem to be simply combinations of a couple dictionary words, or a word and a number, or similar fairly low entropy combinations that would come early in a brute forcer's search.
Most of the ones that aren't like that are based on simple patterns on the keyboard, which would also be in a brute forcer's list of things to check early.
My password isn't on the list—it's a randomly generated 17-char string of alphanumeric and mixed case character.
Btw, you should all check out 1Password. Automates the process, syncs with all my devices and dropbox, and integrates with all the major browsers.
Mac is the first platform listed.
KeePassX + Dropbox is a great way to go, but it's kind of more "DIY"-ish. Still not hard to set up, keeps all my passwords in sync, and KeePassX has some great features like "auto-type" which basically is a one-click website login.
I now use the max-length passwords on all the sites I use, and they're all crazy random ones. I don't memorize any of them because it's so easy to reset a password if I lost my KeePassX access (unlikely since it's on Dropbox + 4 computers + CrashPlan backups).
I always use unique passwords so I don't care that much if it gets broken.
123456 -> 199 results. password -> 118 results.
Who would use such weak passwords for an account with potential monetary value?
If I were to sign up for MtGox, I don't know if I'd use anything above my standard "don't care" password, at least until I decided to get serious about it. Typing "shifty3rd" is easier than generating a LastPass password - and I only use it for accounts when I don't care if they're compromised.
While I'm glad I do not have a account there they would not have been able to crack my password :-)
Edit:
I am a fool, salted hashes are probably not in anyones rainbow tables :)
For example, for "$1$JVf3ep..$uvo634QwxDsAuHMOZlKws1:riprip" the salt is "$1$JVf3ep..$" (although those periods may just be padding, IIRC).
Not really a surprise considering they were hashed using one of the fastest/weakest common hashing algorithms.
Nice. I think it's time to upgrade all my passwords.
"ZXasqw12!@" was about as random as it got from a quick scroll-through, and even that is basically just keys directly next to each other.
I assume randomness doesn't mean as much as sheer password length does when it comes to crackability, but I wonder if there's anything to be learned from this. Maybe only that random password generators tend to default to a safer (longer) length? :)
These are salted FreeBSD MD5s (iterated hash); even with a powerful GPU, you're probably only going to be able to check a few hundred thousand per second at best.
It goes to show that the old rules - non-dictionary word, mixed case, etc - really don't cut it anymore. Psychologically, picking a password that has high entropy is quite difficult, and the crackers are only going to develop better algorithms in the future. I think using a good random generator is the only way to ensure you have a decent password these days.
I wasn't aware they could crack passwords that long though -- wasn't that supposed to take years, even with a GPU?
I pick passwords based on easy things to type and the memorize the pattern / commit it to muscle memory. I also try to use obscure but pronounceable patterns somewhere in the pass.
this list is just the low hanging fruit
And because of this, if you choose a weak crypto method to hash your passwords (which is what MtGox did), then an attacker conveniently has the 3 things they need to attempt to crack the password: The algorithm, the salt and the hashed value all in the same place.
However, if a strong crypto is used (IE a computationally intensive and slow hash), then the fact that the algorithm, salt and hashed value are in the same place doesn't really weaken the passwords. With an expensive enough hash, even if the attacker has all the information about how to crack the password right in front of them, actually performing the necessary computation would be so expensive that a brute force attack is effectively protected against.
You can see more details about the format of the password strings and where the 3 parts of data are stored here: http://php.net/manual/en/function.crypt.php (the PHP page had the best explanation of my quick search, though this isn't just PHP specific)
Using one salt defeats rainbow tables. Using multiple salts does not defeat it any better.
Using multiple salts would seem to help defeat brute forcing or dictionary attacks, but that is only true if the salts are secret... the problem is that they are not secret because the at this point the attacker access to everything, including the salts.
> Using multiple salts would seem to help defeat brute forcing or dictionary attacks, but that is only true if the salts are secret
If I have a dictionary of common passwords, I need to hash this with the salt used by MtGox and then I can test the hashes against all the passwords from MtGox.
Had they used a different salt for each password, my work would be n times as expensive (n being the number of passwords to test against).
Better encryption, e.g. bcrypt http://en.wikipedia.org/wiki/Bcrypt attempts to make it impossibly expensive to crack passwords. Part of their technique is to use per-password salts to increase the time for all passwords, but the key is to have an encryption algorithm that takes an "impossibly" long time per password as well. Key is that it is "an adaptive hash: over time it can be made slower and slower so it remains resistant to specific brute-force search attacks against the hash and the salt."
Rainbow tables are O(1). Salts are O(n). Bcrypt is O(big), where "big" can be increased to keep it bigger than a "practical" attack will be willing to attempt.
Why would you post this? If someone really wanted to pair them up, they could have but that at least would have taken -some- determination.
Obviously you knew you were pushing it since you even went out of your way to create a new handle. For the "lulz"? Troll.
releasing the cracked passwords at first was stupid and doesn't show any skill. it only shows that you have a strong cpu.
Consumer-grade GPUs are better at this than even the highest end CPUs.