Programming Errors Weaken bcrypt Hashes of Ashley Madison Passwords

Ashley Madison encrypted users' passwords using the bcrypt function. It's a secure password-encryption function, but two implemention programming mistakes allow millions of passwords to be easily decrypted. Ars Technica explains the problems.

Posted on September 14, 2015 at 6:26 AM • 31 Comments

Comments

ramriotSeptember 14, 2015 6:46 AM

Like all security mistakes, when you see it there is a real world DOH! moment. Gotta go now and change the userToken class in all my security products Doh!

edwCSeptember 14, 2015 8:59 AM

@Sam

a large amount of those could well be because Ashley Madison is full of fake accounts (regardless of what the company's selfpromotion says).

zSeptember 14, 2015 9:04 AM

I am reminded of this essay Bruce wrote in 1998: https://www.schneier.com/essays/archives/1998/01/security_pitfalls_in.html


"What happens with most products is that someone reads Applied Cryptography, chooses an algorithm and protocol, tests it to make sure it works, and thinks he's done. He's not. Functionality does not equal quality, and no amount of beta testing will ever reveal a security flaw. Too many products are merely 'buzzword compliant'; they use secure cryptography, but they are not secure."

deLaBoetieSeptember 14, 2015 9:34 AM

One of the problems with commentary on this story is that they may imply that strong passwords were useless. Of course, some of the long passwords were email addresses and so on, but the weakness is not (of itself) with the passwords - these seem to exhibit the usual dismal fails - but that the implementation was weak. IOW, the normally strong passwords (evaluated presuming modern KDF), were actually exposed because of the implementation and ability to brute-force the MD5.

It also irritates me that the presumption is that all-lowercase passwords are necessarily weak. What's important is the entropy, which can be gained with suitable number of diceware words for example, all nicely lower case.

SamSeptember 14, 2015 10:10 AM

@deLaBoetie

The article talks a bit about how all the recovered passwords are the simple ones. Ars says:

"By virtue of being cracked, all of the 11.7 million passwords recovered so far were weak. Had they been long, randomly generated strings continuing upper- and lower-case letters, numbers and symbols, they'd be among the 3.7 million cryptographic hashes that still haven't been deciphered."

So in this case having a good password is something the users can do (or rather, could have done) to help mitigate implementation errors made by the developers.

deLaBoetieSeptember 14, 2015 11:07 AM

@Sam - I think the weakness is mostly true, the examples contain the usual suspects...

But I don't think most thoughtful people plan their password strength on the basis of MD5. So those with moderately good passwords, adequate with bcrypt, will have been exposed. And they specifically admit that they would not have been able to get so many so quickly had it only been bcrypt.

DanielSeptember 14, 2015 12:08 PM

In the bigger picture this is one of the major reason why "Crypto Wars" is so much silly nonesense. Crypto doesn't hamper the security agencies one bit because all they need to do is attack the implementation, and the implementations are always buggy.

Clive RobinsonSeptember 14, 2015 12:15 PM

@ Bruce,

Your statment,

but two mplemention programming mistakes passwords to be easily decrypted.

Brings up an issue of "ambiguity of meaning" of words we use, within the field of endevor, "decrypted" is now used in so many ways it almost has no information content, and thus "recovered" would be slightly more accurate...

rgaffSeptember 14, 2015 12:18 PM

@Daniel

So you might as well not try, just walk down to your local prison and check yourself in...

Clive RobinsonSeptember 14, 2015 1:20 PM

@ Daniel,

Crypto doesn't hamper the security agencies one bit because all they need to do is attack the implementation, and the implementations are always buggy.

Whilst the last part of your statment is true, the first part is not true.

Crypto not only slowes them down, the implementation weaknesses don't always get them anything.

For instance you build a "high entropy true random number generator" that only gives output suitable for One Time Pad generation, it prints out OTPs in an environment unavailable to monitoring by the security agencies. You hand encipher / decipher messages and only the ciphertext gets onto the computer used to send/receive messages. It does not realy matter what kind of access the security agencies have to that computer through implementation issues, they learn no more than they see on the network.

But you also have to consider what an implementation issue gets them. Unless they can get the OS / App developing organisations to send out an attack as an update to all computers, in a way that leaks keymat or plaintext to the network, security agencies will have to target individual computers and this has significant issues for them least of which is "tipping off" the targets.

So crypto realy does put a dent in the security agencies activities, unless, of course you use an OS like Win10, or Apps like those from Google that have hallmarks indicative of what Comey and Alexander, et al want from a "front door".

Green SquirrelSeptember 14, 2015 2:04 PM

@Sam

"Another Ars article: The researchers found just 4.7m unique passwords from the 11.7m they recovered, "

Actually, I dont think its that bad if around 40% of the passwords are unique as it means you'd need a fairly large dictionary to attack this full set. (Unless, of course, you went for the weaker implementation and not forgetting the big dictionary hits ALL the accounts).

DanielSeptember 14, 2015 2:08 PM

@Clive

Unless they can get the OS / App developing organisations to send out an attack as an update to all computers, in a way that leaks keymat or plaintext to the network, security agencies will have to target individual computers and this has significant issues for them least of which is "tipping off" the targets.

Yes. If the user has some type of intrusion detection. But then you have people like Joanna Rutkowska who repeatedly insists that such things are unnecessary because they are unnecessary.

So yes, in theory an effective security design and subsequent implementation will increase the costs to security agencies that engage in targeted "legalized hacking." In practice, however, I stand by my statement.

As Bruce put it, "We know, on the internet today, that attackers have the advantage. A sufficiently funded, skilled, motivated adversary will get in. And we have to figure out how to deal with that."

DanielSeptember 14, 2015 2:12 PM

@rgaff

So you might as well not try, just walk down to your local prison and check yourself in...

No because the one advantage that everyone has today is the security agencies do not have unlimited resources. So people shouldn't walk down to their local police station..what they should do is cross their fingers, consult their crystal ball, and examine the motions of stars.

GweihirSeptember 14, 2015 2:20 PM

This is an excellent example that using strong mechanisms is not enough. You also have to understand how they work, and why they offer the protection they do. Otherwise, utterly demented mistakes like this one will happen. My guess is that this is yet another example for a person implementing security mechanisms that does not have any real insights into how to use crypto.

Of course, everyone with a strong password is still secure, even the lc() will not have degraded it much and reversing MD5 for strong passwords is still infeasible. The while point of key derivation functions like bpkdf2, bcrypt, and the new Argon2 is to protect users that have passwords weak enough to be brute-forced (individually) or successfully break with rainbow-tables (in bulk).

david x callawaySeptember 14, 2015 2:32 PM


@deLaBoetie:
"...What's important is the entropy, which can be gained with suitable number of diceware words for example, all nicely lower case..."

with diceware the case doesn't matter because it effectively has an alphabet of 7776 if you think of the words as characters, hence an 8 word diceware passphrase has an entropy of about 103.2 bits, about the same as a 22 char all lower case password, but a lot easier to remember.

djnSeptember 14, 2015 2:47 PM

Is bcrypt a shorthand for 'BruceScript'? :-)

I feel that the title about a weakened bcrypt is pure linkbait... The cracking team did not broke or weaken bcrypt, they didn't ever try to.

A honest and easy to get summary would be: "Ashley Madison coders did the right thing and properly hashed passwords with bcrypt, then went on to do the worst of things and hashed the same password with MD5."

rSeptember 14, 2015 10:03 PM

@djn, I agree.
I too feel that the title is a misrepresentation of what is happening, the database would still be protected vs exfiltration in this case BUT the architects apparently made grievous errors implementing the company's backend. Therefore rending the use of bcrypt moot?

Prior to this md5 hack I saw a blog about someone recovering 4000~ user passwords thus far from the bcrypt'd database with a 3 card ATI rig.

The other side of the coin: http://www.patrickosinski.blogspot.com.br/2015/08/when-hackers-released-password-data-for.html

JonSeptember 15, 2015 1:23 AM

Oh, testing.

So many people try it once, it works, they're done. Nope.

I had a hand-coded assembler password verification routine rewritten in C by another programmer. His code worked - You put in the correct password, it checked it against the stored password (this was not a highly secure widget) and if it matched it let you into higher level menus.

He tested it, input the correct password, and it let him in.

What he didn't test was putting in the wrong password. His code let *any* password work, and it was MONTHS before this was discovered because all the testing staff knew the passwords and carefully input them correctly.

It was only by a sheer fluke of the compiler that it worked in the first place. It happened to re-use the registers that the password was loaded into to compare them, and naturally, they always matched.

Reverting to the old assembler routines, my code did indeed reject bad passwords, and I was able to score quite a triumph there.

Once more: Test against bad inputs. Steve Jackson (of Steve Jackson Games) said as much with the original design of 'Ogre' (about the wildly overpowered GEV unit), "If you make a Civil War game and your rules give the victory in battle to the side that charges uphill against an entrenched position, you don't have much of a game. But if you playtest with Civil War experts, you'll never find out, because none of them will ever be dumb enough to try.".

But you still have to test against things like that (The rules for Ogre were rewritten). 's what they pay you for.

J.


golpherSeptember 15, 2015 2:41 AM

>security agencies will have to target individual computers and this has significant issues for them least of which is "tipping off" the targets.

Computers and individual targets I suspect its cheaper and safer to send in the humint, mi8 style. But its quite laughable who would attract such a posse whatever they think they are after.

Clive RobinsonSeptember 15, 2015 4:02 AM

@ golpher,

Computers and individual targets I suspect its cheaper and safer to send in the humint...

That also is a "tipping off" danger, some high end "home security" systems are more sophisticated than those used in banks and high value repositories these days. All thanks to the rapidly droping price of technology.

As I've pointed out a number of times technology is agnostic to it's use, it cares not if it's been designed and built by a "Pimply Faced Youth (PFY) in a basement" as a way to become a new tech wave billionaire or some "down at heal bone dome bureaucratic drudge" crawling to a desk in some corner of an oh so secret government lab and who's primary work occupation is counting the days to their pension.

The price of "new tech" is so low and moving so fast that even smart twelve year olds are doing at home what was not possible with a million dollar budget on the day they were born.

The simple fact is what the NSA et al want is a "no risk target rich environment" for their "oh so secret" "collect it all" policy, and they are slow and thus finding that such places are already getting occupied by those more fleet of foot and fast to build who have already not just staked out the territory but have put up store front's and hung their "keep off my turf" shingles up.

Back in the day of stethoscope safe cracking, black bag jobs were relatively safe, intrusion detection devices were simple, large, visable, and few in number, thus avoidable unless biological. These days tech is complex, microscopic, effectivly invisable and effectivly infinate in variety and the safes impossible to open without the likes of a five dollar wrench or 10,000 dollar suited lawyer, either way the target is tipped off.

So instead of tipping off the target they go have a less than friendly chat with the targets Email provider etc in the hope the target is not using crypto and anti traffic analysis technology...

Gerard van VoorenSeptember 15, 2015 4:18 AM

@ Jon,

I am probably being pedantic here, but a password should also be tested against buffer overflows (esp with C) and XSS kinda attacks. This is why design by contract is important.

fajensenSeptember 15, 2015 6:20 AM

Maybe - It is just easier to not store all that much information in the first place?

Maybe - One should really invert the current IT-paradigm that IT-people write code to do centralised transactions on people's data, thereby acting "on" people in ways defined by the programmers.

If the information was encrypted and "I" have the key(s), then "I" will be the one to authorise transactions and usage of the data on my behalf. "I" should be the only one able to add / revoke access and in general decide what can be done with my data and by whom.

JonSeptember 15, 2015 7:22 PM

Always a good point, Mr. van Vooren, but in this case the password was not entered with a keyboard into a field at all. Think of it as sorta an electronic version of one of those multiple-rotor suitcase locks (not exactly protecting nuclear secrets here) so putting in too many numbers (or indeed anything that wasn't a number) was already prohibited by sheer input inability.

The whole widget only had six pushbuttons and a screen, and that was it for user interface (aside from tearing it apart and forcing voltages on pins and rot like that. Even the RS-232 debugging interface didn't have the RX pin connected to anything). You could increment the number, decrement the number, move on to the next number, or backspace to the previous number. That was about it. When all the numbers were set and in, you 'moved on' to testing if you got it right.

There's something to be said for simplicity, although I think that gadget took it a bit too far. I'd have been happier (and I suspect the users would have been too) with at least a 10-key numeric pad.

Annyhow... Not my design decision.

Have fun,
J.

UhuSeptember 16, 2015 6:17 AM

@djn

Worse than just using MD5, they actually converted the passwords to lower case first. Thus not only was the hash function faster (more tests per time unit), the attack space was reduced (less tests required)!

JonSeptember 16, 2015 7:12 AM

I can almost see using a miserably bad hash function for a purpose it was never any good at as the work of an incompetent programmer with a bad hangover that morning, but changing it to lower case? That reeks of deliberate malice.

On my widget I went to some effort to define my threat model as "merely people poking around the menus" not a determined attack effort. When the project manager asked about hardening it further, I replied, "Well, first you'd make the case out of steel and weld it together", which shut down discussions along those lines entirely (it was supposed to be an inexpensive widget).

Cheap, secure, useful. Pick any two.

J.

(There weren't that many numbers in the combination lock. If it were taken apart and the keypad replaced with a fake one that could do scripting, you would have the password in not more than a couple of days. Pushing the buttons by hand would have taken much longer and been stupidly tedious but would have worked too.)

JohnPSeptember 16, 2015 2:21 PM

As an end-user, the only thing I can control for a site like that, assuming I decided to use it, is the length and complexity of my password.

Why haven't people started using 55+ character, random, computer generated, passwords and a password manager? I just don't get it. Try it for a week - you'll discover it is MORE convenient AND more secure.

Of course, none of this will fix a coding mistake, but it is the best we got.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.