One way to fix your rubbish password database

http://blog.jgc.org/2012/06/one-way-to-fix-your-rubbish-password.html

by jgrahamc • 14 years ago

101 89 14 years ago

blog.jgc.org

notmyname2• 14 years ago

On step 3, where you say "scrypt(s'i, md5(si, password))", don't you actually need "scrypt(s'i, md5(s0, password))", where s0 is the original salt? In other words, you still need to know the original salt you were using to successfully migrate.

Therefore, if you are storing the per-user salt as the first bytes in the hashed password field, then you have to be careful when you "throw away the old weak hash hi and forget it ever existed."

jgrahamc4• 14 years ago

The original salt is s_i which you do need to keep around. The new salt is s^'_i.

notmyname2• 14 years ago

Ah. my mistake. I completely missed the "'" as I was reading it.

healsdata2• 14 years ago

Is there a security disadvantage to taking the MD5 hashes you already have and running those through bcrypt? It seems like that would let you get to a salted bcrypt implementation in one day as opposed to waiting for all your users to log in. Perhaps you could do the mix (md5 + bcrypt) until the user logs in and then switch them solely to bcrypt?

StavrosK7• 14 years ago

That's what the article says.

healsdata2• 14 years ago

Thanks for pointing that out. For some reason, when I read it earlier, I missed the bullet point about the conversion process.

tptacek6• 14 years ago

No. I don't believe there's any disadvantage to this. An MD5 hash is a 128 bit random number; it's 16 fully random characters, better than almost any human password.

pilsetnieks• 14 years ago

To nitpick a bit, it's 16 bytes, usually represented by 32 hexadecimal numbers.

tedunangst6• 14 years ago

Pedantically, it's 16 random bytes. You aren't going to lose much entropy from an upper/lower/number password unless it's at least 20 characters, or even longer if it's a pass phrase.

StavrosK7• 14 years ago

What's your opinion on SuperGenPass and the like? I'm sure it would still get cracked, but I feel that it would take a lot of effort to crack the provider's hash, even if it were md5, and then less effort to crack the SuperGenPass hash, so hopefully nobody would recognise it or bother...

lukeschlather• 14 years ago

An MD5 hash is not a random number; it is generated from some text string. It's possible that bcrypt(salt + MD5(text)) opens you up to collision attacks that are not possible with bcrypt(salt + text). It seems unlikely that it would open you up to attacks that are not possible with md5(text) but MD5 is not a random number so I'm not too sure.

cheatercheater2• 14 years ago

Red light coming up in the back of my head. Wouldn't the MD5->scrypt pipeline expose new attacks that scrypt doesn't have? Maybe there's a higher collision probability or some known-text attack, but I'm really shooting in the dark here.

__alexs• 14 years ago

If you were on MD5 your passwords all have at most 128-bit of entropy. A user with a password of say, 30 random bytes from [a-ZA-Z0-9] will be getting some entropy truncated in the hashing process. If you now move to say, bcrypt your hashes are 448-bits long. So you are throwing a way a lot of the keyspace by using a shorter hash function first. So yes, it's weaker, in one sense, it's just massively more difficult to attack already and you can still upgrade to pure bcrypt as users log-in in future.

bmelton• 14 years ago

Well, I mean there's always the possibility that you'll have users that won't log in any time soon, and you don't want them to be vulnerable in the mean time, right?

If it were me doing it, I'd take the article's approach as the first whack, and then as each user logs in, validate their password (as per the article), and then also set their password to scrypt('salt', 'password') vs. scrypt('salt', md5('password')), so that they were current. Then just set a flag on the user record like "new_password=True" or something.

That gets you the stopgap without having to muck around with scrypted hashes forever. Send out a few emails to your user population with a note that you've upgraded your password strategy and that they should log in. You're still not going to get 100% coverage, but at least for whoever you don't get to log in, their passwords aren't 'in the wind', so to speak.

Edit: I'm not sure if you edited yours, or if I just read it poorly, but I think we're saying the same thing. Note, the article's strategy is basically your first scenario -- just bcrypting (or scrypting in the article) the existing md5 hash.

RyanMcGreal• 14 years ago

Thanks to reading lots of articles on HN about password security, I upgraded my site's passwords from salted MD4 to bcrypt about a year and a half ago (a bit late to the party, but still). Here's what I did:

I added a second password column to the users table, then ran a script that queried the table for the existing hash, generated a bcrypt hash from that value and wrote it into the new password column. Then I removed the old password column. No need to wait for the user to log in.

When people log in today, the code takes their password, runs it through the old hash routine, runs the output through the new hash routine, and compares that to the password on file.

Yeroc• 14 years ago

Unless I missed something you're describing exactly what the linked article suggested to do.

StavrosK7• 14 years ago

Did you get that from here?: http://news.ycombinator.com/item?id=4078751

jgrahamc4• 14 years ago

No, I asked a question yesterday about this (http://news.ycombinator.com/item?id=4080823) and spent a long time thinking about it. Great minds...

StavrosK7• 14 years ago

Yeah, I guess it's not that amazing a coincidence... Most people would arrive at that.

peteretep• 14 years ago

Here's a worked example of a similar technique I wrote up ages ago:

https://gist.github.com/1051238

jcromartie• 14 years ago

This is a good step, but unfortunately all of the actual passwords are still out there, so they need to be changed.

I think a better idea would be to establish an easily implemented pattern for "password bankruptcy" that companies could follow in the case of a leak.

tedunangst6• 14 years ago

The idea is you do this before the password database is stolen. It's too late for LinkedIn, but not too late for you.

ams6110• 14 years ago

As far as you know.... but how do you know?

donpdonp• 14 years ago

What would a password bankruptcy pattern look like?

One thought is to invalidate all passwords and fall back on email password recovery when a login is attempted.

This leads me to an idea I've tried once - if access to the inbox is equivalent to password credentials, why not use an email to login? By this I mean the web site login is a single field - email address. The system emails a one-click-login URL to the user that can be re-used (possibly with a month expiration time). The user can look up the URL in their inbox when they want to login again, or use a long-lived cookie.

tedunangst6• 14 years ago

I have lots of logins tied to email addresses no longer in use. As a real world example, people sign up for services with work emails. The day they get fired, they suddenly lose access to that email and all of the email login services tied to it. Not good.

desas• 14 years ago

Emailing a link to login was one of two supported login methods for redhats mugshot social network. The other was sending the link via xmpp.

In practice I end up doing this for little used sites because I use either my phone, tablet, and two laptops for browsing the internet.

It's annoying if you work somewhere that doesn't allow access to personal email accounts and you want to log-in to something.

gioele• 14 years ago

> 4. If, like last.fm, you were also allowing third-parties to authorize users...

... then you should stop doing that and you should start using OAuth, so the client application never sees your user's password.

alexmuller• 14 years ago

Theoretically, sure. But I can't think of a nice way to authorise users on something like [1]. They'd then need a computer with the radio to provide some kind of access code, I guess?

[1] http://www.robertsradio.co.uk/Products/Internet_radios/STREA...

ErrantX• 14 years ago

One time passwords (feed the radio your generated password & let it use that to negotiate authorisation/api keys).

dfc• 14 years ago

Why do you write/footnote like that? Is there a geographical disparity in how to footnote?

ernesth• 14 years ago

Isn't the fact that s/bcrypt is by design costly preventing this idea from being executed?

tedunangst6• 14 years ago

Assuming you use 0.01s per hash settings, you can upgrade somewhere around a million accounts per hour.

joshrice2• 14 years ago

Sorta, but chances are you'll be generating way less then an attacker would need to do. More importantly, you owe it to your users to keep their passwords secure.

ww520• 14 years ago

It's unlikely that you have more users than the enumeration of the 128-bit key space (if MD5 was used). The slowness of bcrypt prevents the brute force attack through the key space for EACH user. That's N x 2^128 for N users, whereas to upgrade, you only have to do it N times.

mjschultz2• 14 years ago

I'll admit, I must be the only one that doesn't quite get the jump from step 4 to step 5.

In step 4, we make the assumption that their API is out in the wild, in use, and sends the md5(s, p) in the request. I get that we take that value, run it through scrypt and match against our stored value to authenticate. So the database has:

    scrypt(s', md5(s, p))

No problem authenticating the API requests with that.

Step 5 says once the user logs in with their actual password, we update entirely to the new scheme of scrypt(s'', p) and store just that. Now the database only has:

    scrypt(s'', p)

But the API user still sends md5(s, p) to authenticate, right?

So then what happens when that same user goes back to the API-using app? It's still uses the API so it'll send the MD5(s, p) and fail since we've discarded the transitional scrypt value when they logged in via the web interface.

Is there a deprecation period that supports both types while API using apps updated to a new API for the new scheme?

jgrahamc4• 14 years ago

Should have made clear that you can't do 5 if you need 4.

mjschultz2• 14 years ago

Ah, okay. So step 5 is the else condition from the "if" that begins step 4. At least, until the API is upgraded to the new improved edition and most/all API apps are using the new version.

pbreit• 14 years ago

I had trouble following along as well. I think the gist is, 1) immediately re-compute strong hashes for all of your existing weak hashes. 2) when someone attempts to log in, try both hash computations. 3) if you used the old weak computation, re-compute a new strong hash.

nateabele• 14 years ago

Okay, I must really be missing something here.

If your original database contains a bunch of unsalted SHA1 (or worse, MD5) hashes, what good does securing the hashes themselves do if the means to generate the corresponding plaintext has already been released into the wild?

Someone please tell me I'm missing something obvious.

joshrice2• 14 years ago

It's how to fix your rubbish password storage, not LinkedIn's or the others who've been compromised. That's the difference.

mistercow• 14 years ago

If I'm not mistaken, the first paragraph is wrong. All signs point to LinkedIn having used unsalted hashes.

aidos• 14 years ago

According to their statement, they started salting some time recently. I guess you got a salt when you next logged in?

danskil• 14 years ago

I was just doing a write up on swapping auth back ends to gain more security http://schneems.com/post/24678036532/zomg-my-passwords-are-i....

pdenya• 14 years ago

The variable names in this article are throwing me off. Is there a special significance to the subscripts and superscripts in the variables?

kbanman• 14 years ago

The subscript i denotes that the variable belongs to a single user i. The tick at the top is pronounced 'prime' and is used to differentiate between versions or iterations.

Ineffable• 14 years ago

Is that called "prime" by most people? I've always heard it just pronounced "dash", as in "s-dash" or "f-dash".

PaulHoule• 14 years ago

I used this strategy years ago (2002) to migrate plaintext passwords in a site with 50k+ users. In fact, I built this into the system so I could do arbitrary migrations between password encodings whenever I felt it was necessary.

It works well.

IgorPartola5• 14 years ago

Ruby and Django could do well to have this type of strategy baked in. This way you update your configuration and the passwords are immediately upgraded.

rb2k_3• 14 years ago

Even if you run a bad codebase that just uses unsalted MD5 and you don't want to add a new crypto algorithm:

Couldn't you just run your whole database through X more rounds of MD5 and do the same in your authentication function?

That way, script kiddies couldn't use precomputed rainbow tables they downloaded somewhere off Bittorrent.

Each additional round will also reduce the speed of a brute force attack while still keeping the changes to the codebase will be pretty small.

Unless there are rainbow tables for a certain number of MD5 iterations, it would be a start...

IgorPartola5• 14 years ago

I think the conventional wisdom is that you should not re-invent security. I am slowly learning this, but the give-away seems to be questions that start with "Couldn't you just..."

rb2k_3• 14 years ago

It also was conventional wisdom that banks were too big to fail ;)

Are there any actual arguments against using this as an 'easy' fix to the precomputed rainbow tables scenario? Multiple rounds of a cipher seem to be a relatively common operation in crypto and have helped other old ciphers. One of the more prominent ones would probably be the move from DES to triple DES.

I guess dictionary attacks on GPUs would still be easy enough, even with more iterations, but anything that isn't directly in a dictionary might benefit quite a bit from multiple iterations.

It's not as good as actually using proper crypto rather than hashing algorithms that were designed to be fast, but it seems like an easy to implement low-risk solution.

heretohelp2• 14 years ago

Pretty easily detected. This is a bad idea. Amateurs need to stop attempting their own patchwork solutions to their already bad fuck-ups.

rb2k_3• 14 years ago

Is the "easily detected" part really a problem? The idea isn't to try security by obscurity.

The main advantage is that it would still keep people from using precomputed rainbow tables and slow down brute force attacks with a minimum of additional code, wouldn't it? (similar to the switch from DES to triple DES back in the day)

pbhjpbhj3• 14 years ago

One would just check against a top10[000…] list of passwords on which various multiple hash combinations had been applied md5(md5(md5(md5('password')))) is going to be easy to reveal.

Your system would seem to be practical if you know there are no weak passwords or if you dont care if only some of the accounts are compromised.

You've also got to watch you don't DoS yourself.

yathern3• 14 years ago

The article states that LinkedIn was using salted SHA-1 hashes, but I thought that wasn't the case. Either way, aren't salted hashes essentially uncrackable by all means except full out brute force?

If my password is "password", and I change it to "#b1@password%3dy", and then hash it, isn't it secure from basic dictionary/rainbow table attacks?

I'm a bit new to cryptography, so please forgive me if I'm not understanding some of this correctly.

IgorPartola5• 14 years ago

Brute force is sometimes all you need. The problem is that using GPU's you can compute so many hashes a second that a short password simply cannot withstand such an attack for long. The salt helps a bit, but if someone is brute-forcing the hashes all it means is that once they have your password they don't have the other person's who happens to use the same one.

yathern3• 14 years ago

I see, but isn't brute-forcing "aecd8c83718c381cpassworda3802..." going to take far, far longer? Even on some huge botnet clusters, I still don't imagine how it could be possible to crack that very quickly.

esbwhat• 14 years ago

I always wondered why people don't just use rainbow tables to get all the raw passwords, and then hash them with the better algorithm. The ones that are left, you just change upon login.

One way to fix your rubbish password database

Related Stories