How crackers ransack passwords like “qeadzcwrsfxv1331”

http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/

by co_pl_te • 13 years ago

254 118 13 years ago

The punchline:

> The list contained 16,449 passwords converted into hashes using the MD5 cryptographic hash function.

Edit: I'm removing all my snarky nitpicking. This is a good article. Yes, the MD5 case they present is a poor case, but it's really about demonstrating the tactics of attack selection, rather than teaching someone how to make crack-resistant password schemes.

grecy• 13 years ago

> the MD5 case they present is a poor case

If guys using vanilla hardware get that kind of success in 1 hour with MD5, you only need to increase hardware and the time required to see it's still completely doable for other hash functions.

eksith2• 13 years ago

The issue is practicality. Which is why pbkdf2 (and increasing the rounds each year) + bcrypt or scrypt is still a better option.

nknighthb5• 13 years ago

Which is why passwords just shouldn't be stored with simple hash functions. Even a naïve salt+iteration method would have drastically slowed the attack.

jevin• 13 years ago

That's why the Blowfish algorithm is the best choice for password hashing.

The algorithm uses CPU cycles to generate the hash. So there is no way to speed it up, just by using a faster computer.

mturmon• 13 years ago

Right. The dialog with the crackers, showing how they use Markov chains, recombination of already-found passwords, and other adaptive techniques was new to me. They were able to turn up lots of seemingly obscure passwords very fast.

Basically, the strength of passwords can look really good on paper (96^12 possibilities or whatever), but in practice the entropy is much less: individual characters are not as independent as we'd like to think, and your clever word or phrase may be in a dictionary already (or may be a short Levenstein distance from something in a dictionary).

tomku4• 13 years ago

Enjoyable read, but I question the bit near the end claiming that salts wouldn't help much against this kind of attack.

From my understanding, per-user salting does substantially slow down this kind of attack because it forces you to calculate a different hash for each user/plaintext combination rather than hashing a suspected plaintext once and comparing the hash against the whole list. What it doesn't slow down is the brute-force cracking of a single targeted hash.

Am I missing something there, or is the article wrong?

chm3• 13 years ago

Where/how do you store the salts?

tomku4• 13 years ago

Right next to the hashed passwords. The point of salting isn't to add an additional level of secrecy, it's just to prevent the reuse of hashing work for attacking other users.

markdown3• 13 years ago

Right there in the same field as the password:

The pepper on the other hand shouldn't be in the db. Hardcode that into a config file.

theboss• 13 years ago

Salting would definitely make a difference. The point of salting is to increase the complexity and overhead of generating rainbow tables.

The first mistake here is the use of MD5. MD5 is flat out broken. Do Not use md5. Do use bcrypt.

In your db, you can store the salt right there....next to the hash...

How a salt increases the complexity is quite simple. If a attack has a giant rainbow table, the salt causes him to increase the size of his rainbow table and the space required to hold it and the pre-processing time to generate it. For example

Here is what your database might look like with a 3 byte salt

password : salt

hunter2 : 100

qwerty1 : 101

Here is what the attacks rainbow tables will have to look like

qwerty1 : 101

hunter2 : 100

qwerty1 : 100

hunter2 : 101

hunter2 : 103

qwerty1 : 102

...

That's about it. There are other purposes of the salt too but other people talked about those ones.

lbarrow• 13 years ago

The article clearly explained that using more salts was preferable to using a global salt and did a good job of explaining why. They didn't come out and say that a per-user salt is best, but that's the natural conclusion of the argument they developed.

tomku4• 13 years ago

Maybe we read different articles, but the one I read seemed intent on strongly downplaying the amount of extra security that salting provides. It actually uses the phrase "minimal amount of protection" to describe a salt's effect on cracking attempts.

That seems like a strange choice of words when salting would've completely changed the outcome of the cracking attempts described in the article.

Edit: To be clear, I'm aware that salting doesn't protect against targeted attacks, but the attacks discussed in the article weren't targeted. One of the major reasons[1] they were able to crack 16,000 passwords in a few hours was due to the lack of salting.

[1]: The other being the choice of MD5 rather than bcrypt/scrypt/PBKDF2/etc, naturally.

_b8r05• 13 years ago

I'm in the middle of researching re-evaluating rainbow table attacks in light of Moore's law, GPUs and Crack (lookup) tables, I've also looked into countermeasures.

What you're describing is partially correct. When you crack passwords (either with rainbow tables or by brute force) you generate an iterator or use a dictionary and work through this generating hashes (with rainbow tables this works via a series (or chain) of what are called hash reduction functions instead of a plain iterator).

You then compare the hash you've generated against all the hashes being subjected to the crack. Where there's a match, you win!

If you're targeting a single hash and it's unsalted, rainbow tables will work as they're precomputed. It's inefficient, but it'll work.

If you're using a salt, rainbow tables need to be pre-computed for the salt - I actually did this years back with a team for oracle 10g SYS and other default user passwords as the username was used as the salt.

If you're targeting a single hash and it's salted then the iterative or dictionary approach will still work in roughly the same time as the salt is known. Separating the salt means you have to brute force it which is a PITA but generally because the way hashes tend to be stored (remember we're talking about a mechanism that shouldn't really be used anyway) the salt needs to be accessible by that system so you can dump the salt out regardless.

Depending on where my current research goes it looks like some salting mechanisms may be feasibly pre-computable now beyond those that use predictable salts. GPUs allow you to create and traverse enormous chains in rainbow tables and while having to precompute per salt will be a PITA it looks like it is possible with sufficient storage and GPU power.

csense• 13 years ago

What if a site uses 128-bit salts generated by a good (perhaps hardware-based) RNG?

chiph3• 13 years ago

If you're targeting a single hash

I was going to mention this. If your user record has a column called "IsSuperuser", then an attacker is going to concentrate on those users, since the reward for cracking them is so much higher. Individual salts or not, with multi-GPU based brute-forcing, they won't stand long.

eksith2• 13 years ago

'Taekwondo1983' Was the password a fellow admin of an old forum I used to run. Wander if it was still him.

yk• 13 years ago

Probably not, 'Taekwondo1983' sound like a password some percentage of people who practice a certain sport and are born in a certain year would choose.

vinhboy• 13 years ago

I think my favorite part of this is learning that after I finish with my bitcoin mining rig, I can use it to crack passwords. Awesome...

davedx• 13 years ago

If it's a specialised rig then it'll only be good for MD5 I think. Most sensible websites don't use MD5 anymore.

gizzlon• 13 years ago

Most sensible websites don't use MD5 anymore

What makes you say that? Do you mean new sites or all site? Got anything to back it up?

I would guess most sites in existence use MD5, SHA1 or similar with 1 round, because it was (is?) very popular.

maxerickson• 13 years ago

The work function in bitcoin is based on SHA-256.

But vinhboy is almost certainly talking about some computers with some GPUs in them.

talloaktrees• 13 years ago

I don't know too much about crypto. Would using something like salsa20 stop this?

jacques_chester4• 13 years ago

A password-derivation function has two requirements:

1. Obscure the password in a one-way fashion.

2. Be fast enough for humans, but very slow in computer time.

Hash functions can be used to produce an obscured copy of data, but they are also by design very fast.

If you wish to protect passwords, don't use a naked hash algorithm. Choosing a different hash algorithm doesn't fix the problem.

Instead, use a password-derivation function. These are designed both to obscure and to take significant time. Bcrypt, Scrypt and PBKDF2 are the standards.

lisper• 13 years ago

And of these three, scrypt is by far the best choice because it's the hardest one to speed up with specialized hardware.

jd0072• 13 years ago

The article explains how all the passwords were revealed except for "qeadzcwrsfxv1331". Maybe I missed it but could anybody point out to me which method revealed this password? The letters seem to not form any words that I know, and although is appended with a number and consists of only lower case letters, it's still 12-letters long, longer than any brute-forced in the article. Edit: They tried all the keyboard typing patterns I suppose, I just realized the pattern of the string when typed on the keyboard.

kenbot• 13 years ago

Try looking at the pattern the letters form on the keyboard...

jd0072• 13 years ago

Yeah thanks, I literally realized that as I hit reply on that comment lol

simias• 13 years ago

Good catch, but it could also simply be that the password had been collected during a previous hack.

The article mentions it at the end but I think they should have insisted more on this point: if you have a very strong password that you reuse everywhere and it gets leaked at some point it has a high probability to end up in rainbow tables everywhere and might not be more secure than "h4x0r1234".

So using hard to guess passwords is the easy part, the hard part is using different hard to guess passwords everywhere.

stitchintime• 13 years ago

Related: Stitcher (still) stores passwords in plain text https://news.ycombinator.com/item?id=5778367

oskarth• 13 years ago

Cue a test-how-strong-your-password-is service where security conscious individuals can test how their particular password stands up against these new attacks.

anonymouz• 13 years ago

And have their password added to a word-list.

roryokane2• 13 years ago

There is a site that pretends to do just that, though I can’t find its URL. It asks you to enter your password for strength checking, then takes you to a page saying “estimated strength: 0. Because you have typed the password into an untrusted web page, you must assume it is compromised.”

roryokane2• 13 years ago

zxcvbn (https://dl.dropboxusercontent.com/u/209/zxcvbn/test/index.ht..., https://github.com/lowe/zxcvbn) basically has this aim. It might be missing some patterns exploited in attacks, but it’s extensible enough that they shouldn’t be too hard to add.

JDGM3• 13 years ago

It's not really what you described, but this is quite jolly: https://howsecureismypassword.net.

fencepost• 13 years ago

LastPass includes a "security check" that does some level of checking, but they don't appear to provide details on their "strength of your password" check - it runs in the browser so presumably they're only doing some low-level checks.

TwoBit• 13 years ago

Well the bonehead hashcat program is limited to 15 character passwords, so it can't possibly crack mine.

The hashcat program software in general is powerful, though pretty crappy from a design standpoint. The current version crashes if any input is not what it expects, and it has just about zero help for what it expects. Actually I can't even get it to work, as executing hashcat-lite.exe with arguments causes it to just immediately exit without doing anything nor printing any output.

reeses2• 13 years ago

    *Well the bonehead hashcat program is limited to 15 character passwords, so it can't possibly crack mine.*

One of the main themes of the article is that the sites are the weak point, not necessarily the users. The first boo-boo is storing passwords in an easily discoverable format (plaintext, md5, sha1, etc.).

Another massive annoyance is when a site has an insipid constraint on passwords. No longer than 8 chars because that's what they put in their db last century or based it on passwd, minimal symbols, and basically just alpha-numerics.

That's why your password manager has the controls on length, number of symbols, digits, etc. It's not to "smarten up" your passwords but to dumb them down for sites that give no priority to security.

knightsamar• 13 years ago

How about passwords not English words but written using Latin alphabet ? Like mer@s@nket!k$habd (Hindi for "my password") ?

Bet that would be harder to crack and still easier to remember for a multi-lingual person.

In fact if non-latin alphabet is widely supported for entering password, it would make them a bit more secure I feel.

sirclueless• 13 years ago

Yes, the non-latin alphabet in particular probably helps a great deal, if you use a substantial portion of it. The Hindi words probably less so, since they are just as likely to end up in dictionaries of common password fragments.

xioxox• 13 years ago

It's dangerous to choose anything someone else might choose. My favourite technique for good passwords is to think of a memorable phrase (preferably with numbers) and take the initial letter of each word.

"I can sleep at Nandos, providing I pay $100 for that"

Ics@N,pIp$100ft

deathanatos• 13 years ago

Anyone know where the article's author got the "MD5.txt" file (the list of hashes he ended up cracking)? I'd like to take a crack at this (pun intended) myself.

PwdRsch3• 13 years ago

Here's what it says in the "How I became a password cracker" article (http://arstechnica.com/security/2013/03/how-i-became-a-passw...) on Ars from March:

"Dan suggested that, in the interest of helping me get up to speed with password cracking, I start with one particular easy-to-use forum and that I begin with "unsalted" MD5-hashed passwords, which are straightforward to crack. And then he left me to my own devices. I picked a 15,000-password file called MD5.txt, downloaded it, and moved on to picking a password cracker."

My guess is that the forum he mentions was the insidepro.com web site, since it is a popular password hash sharing site. A quick search there found several attached files named MD5.txt, but none seemed to be the right size or have the right hashes. However, a search for hashes mentioned in the article found this file (http://forum.insidepro.com/download.php?id=12783&sid=160...), which contains 16,880 (instead of the 16,449 hashes listed in the Ars article) and at least 3 of the MD5 hashes specifically mentioned in the article.

There's a good chance this is the same file or close to it, but you'd have to try matching it with more of the hashes from the article to know for sure.

Corrado• 13 years ago

My big takeaway from this article is that passwords, in almost any form, are a bad way to secure your information. The only acceptable way to use a password nowadays is to use a password manager to build huge passwords that a human could never remember or type in reliably. Even then, as machines get faster and crackers get smarter, these behemoth passwords will fall.

I've been using 2-factor authentication (Google Auth) lately and I'm fairly impressed with it. I only have to whip out my cell phone a couple of times a day/month so It's fairly convenient, and it seems very secure. Then again, I thought my password was fairly secure, but after reading this story and the HN comments, I can say that I'm just like everyone else when it comes to passwords. Ignorant. :/

gradstudent• 13 years ago

The "exponential wall" means the longer your password is the less likely it is to fall. A 10 letter password is in a 26^10 keyspace. Add one more letter and it takes 10 times longer to crack -- assuming of course your password is not part of some of some combination of short common dictionary words.

What I find really interesting is that the same kind of attack vector (combinations of common words) is being used as the basis for some really sophisticated search techniques in Artificial Intelligence. I remember reading an abstract a few years ago from a student of Rich Korf @ UCLA. In it the authors use this kind of approach to attack the 24-Sliding-Tile Puzzle.

Here's a link; it's pretty cool! http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/349...

rdl2• 13 years ago

not 10x longer, 26x longer (and that's assuming lowercase a-z only)

aidenn02• 13 years ago

Even then, as machines get faster and crackers get smarter, these behemoth passwords will fall.

This is fairly trivial to show is false. A 256-bit password that can be checked at one clock-cycle per iteration with 1 million cores running at 30GHz will take 1.2e53 years to crack[1]. If you generate it by base-64 encoding a random 256-bit string you will end up with only a 12 character password (hardly a "behemoth").

[edit] It's 1.2e53 years to exhaust the search space; you can expect to crack X% of the passwords in X% of the time (or have an X% chance of cracking a single password in X% of the time)

[1] https://www.google.com/search?q=2%5E256%2F(1e6*30e6%2Fs)#scl...

traplens• 13 years ago

One note here - base-64 encoding a 256-bit string would result in a 44 character password (43 without padding).

It would be pretty cool if a 12 character password gave you 256 bits of entropy though :)

mrgoldenbrown• 13 years ago

I don't understand the statement that salts get less effective after you've broken other passwords:

"But the thing about salting is this: it slows down cracking only by a multiple of the number of unique salts in a given list. That means the benefit of salting diminishes with each cracked hash."

A proper salt for user Joe's password does not have any relation to any other user's salt. Cracking Bob's password should not help you crack Joe's. Am I missing a technique that exploits one salt to attack another? Or are they assuming crappy salting methods? As in, if you have 2 bits of salt, then after the attacker has hashed your entire passwd file with those 4 salts, you might as well not have salted anything.

makira• 13 years ago

If the original list had x salts, and you crack half of the entries, then you only have x/2 salts left to check, hence cracking goes twice faster.

shawabawa3• 13 years ago

I think what he means is that every password you crack is one less salt you have to hash with. Once you've cracked half the passwords, there are only half as many salts you need to hash with.

However I think he's underestimating how much strength this adds, it would have delayed that 1 hour to get 62% of the passwords to probably a few thousand hours.

jameshart• 13 years ago

I think they misphrased that a little, unless as you say there really are people commonly using non-unique salts. The krux of the argument is that each cracked hash removes one hash from the list of hashes you need to check. So, say you've got 16000 uniquely salted MD5 passwords. 8000 of them are, though, salted MD5s of 'password'. If you start off by checking weak passwords, your first pass requires you to calculate 16000 hashes, but if your first candidate password is 'password', then it yields 8000 passwords. Your next pass only has to calculate 8000 hashes for each candidate password. So in that case, cracking Bob's weak password does help you crack Joe's strong one.

jokoon2• 13 years ago

Maybe we should tell users to use passphrases instead.

The 8 char limit is very low now. The limite should be raised to 30 characters.

PwdRsch3• 13 years ago

Telling people to use passphrases is a great recommendation, but you still have to spend some time teaching them how to use passphrases effectively. In the article they list several passphrases that were cracked, such as "sleepingwithsirens", "gonewiththewind1", and "momof3g8kids". So if a user chooses "ijustbluemyself" thinking that it's a great choice they are likely to be disappointed if a skilled cracker gets access to their password hash.

My basic suggestions are to choose 4+ words that are not a common phrase, song name, quote, etc. And make sure you still use both lowercase and uppercase letters, plus throw in some symbols in non obvious places (e.g., don't convert your a's into @ signs). It doesn't need to be as random as a shorter password, but it still shouldn't look like a normal sentence.

jokoon2• 13 years ago

well it's either that or security cannot really be guaranteed.

Maybe one day password will just be 1MB files kept on people's computer instead of remembering a short string.

tibbon• 13 years ago

That's pretty interesting. It makes me even happier that I've switched over to using passwords like .!a7&Xn2\#ZRS]!:`\.H2j;{7 for everything (unique per-site, password manager). I'm guessing that such a password, when properly generated, isn't going to be cracked without a quantum computer...

But hey, maybe someone can prove me wrong. Anyone care to take a crack (pun intended) at 1a323a3185b1dbee3a0ba1f4c3c9f674

I'll send an entire shiny bitcoin to anyone who can get it right.

chasb• 13 years ago

Combinator attacks guess "the square of the number of words in the dict" when the password is just the combination of two words, correct? So a 3-word pass would require dict^3? This all seems to come back to length.

Millennium• 13 years ago

Pretty much, yeah. This is really just a generalization of the principle we see in the length of a binary password. The complexity is s^l, where s is the number of symbols you can possibly draw from, and l is the number of symbols in the password.

Consider a binary string. There are two symbols in binary (1 and 0) and the number of symbols you use is the number of bits in the string. This gives us the familiar password length calculation: the complexity is 2^l.

When you start using words as the basic unit, you gain many more symbols: if you use the full Oxford English Dictionary, you have about 600,000 of them. But when you do this, your symbol is no longer a single byte: it's a word. That word can be represented as a string of bytes, yes, but it's guaranteed that this string will be one of the 600,000 byte strings that represent English words, and you can eliminate all of the others. So you can't measure your password in bytes anymore; you have to measure it in words instead. A one-word password is, therefore, of complexity (600,000^1).

Six hundred thousand possibilities sounds like a lot, but computers can crack that in seconds. Even if you restrict yourself to just printable ASCII, you can do better than that in only three characters. I don't recommend actually doing a three-character printable-ASCII password, because you'd have just under 900,000 possible passwords: still well within crackable range.

But because the complexity increases so fast as you increase the length of the password, that's how you can gain complexity back. If you use four words instead of one, you have (600,000^4) possibilities: some 130 sextillion. You'd need 70 random bits, or 11 printable ASCII characters, to do better.

And that, my friends, is why "k[0" is a better password than "antidisestablishmentarianism". But it's also why "correct horse battery staple" is better than either one (or would be, if xkcd hadn't made it so famous).

wyck• 13 years ago

The best part of the article is the last part about Intel password strength "guessing".

The other day some devs on reddit were using google to find password strength and posted stuff like my password would take "1 billion years to crack", without realizing these sites have garbage algorithms for measuring strength, the Microsoft one is a joke.

If developers are falling for these strength indicators, I'm certain average users are getting a very false sense of security.

jpalomaki• 13 years ago

In addition to per user salt, it would be good to also add "per application" salt. A random, long string, that is stored somewhere in the application code and not in the database.

Obviously this does not help if the whole site is compromised, but it may help against SQL injection attacks where the attacker gains access to just data from database.

yashg2• 13 years ago

How about this - User's password is a single letter "a". I MD5 it and get a 32 char string, now I append a GUID as salt - another 32 chars - and I MD5 that 64 char string again and store it. How difficult would it be to crack it? If the cracker knew my process he might crack it, but what if the process is not known to a cracker? Also I can store the hashed string and the salt in a way that a crakcer merely by looking at the string can't figure out it's actually salted.

Say my final salted hash is 1234 and the salt I used was ABCD. I can splice the two and store it as 1A2B3C4D. That would throw a cracker who does not know how the value was generated off the hook won't it?

Unless the crakcer also gets access to my code, it will be impossible for him to find head and tail of such hashes.

spiffytech2• 13 years ago

Well, you're hashing and salting, which is at least a good start. But you shouldn't use MD5- if the cracker does find your secret formula, you're hosed compared to pbdfk2/bcrypt/scrypt. Not only for the speed, but because MD5 has exploits that make it easier to produce a specific desired hash than the other options, so your attacker doesn't have to make as many guesses.

You should use a per-user salt, though, instead of a static salt (the 32-char nonce). The static nonce means the attacker can generate a rainbow table during their attack of all possible passwords. The hash of the password does not count as a suitable salt, because if User A uses the password 'a', and so does User B, both users' hashes come out the same. Finding User A's password means you can compare its hash against the rest of the compromised hashes and note that you grabbed User B at the same time. With a per-user salt, the users will have different hashes despite using the same password, so the attacker has to attack each hash separately, with no "quick wins". A randomly-generated salt will do, and I expect simply prepending the username or something to the password before hashing would do as well, singe it's still unique per user.

yashg2• 13 years ago

Yes of course I meant per user salt. And if I store a 64 char string it will be very difficult for an attacker to figure out MD5 was used.

And since the string that I MD5ed is 64 chars in length (32 of original MD5 + 32 of salt) it should make it near impossible to crack.

How crackers ransack passwords like “qeadzcwrsfxv1331”

Related Stories