8 ms·
One way to fix your rubbish password database
- notmyname 14y agoOn 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."
- healsdata 14y agoIs 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?
- StavrosK 14y agoThat's what the article says.
- tptacek 14y agoNo. 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 14y agoTo nitpick a bit, it's 16 bytes, usually represented by 32 hexadecimal numbers.
- tedunangst 14y agoPedantically, 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.
- tptacek 14y agoSorry; C programmer.
- StavrosK 14y agoWhat'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...
- 14y ago
- __alexs 14y agoIf 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 14y agoWell, 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 14y agoThanks 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 14y agoUnless I missed something you're describing exactly what the linked article suggested to do.
- StavrosK 14y agoDid you get that from here?: http://news.ycombinator.com/item?id=4078751 http://news.ycombinator.com/item?id=4078751
- jgrahamc 14y agoNo, I asked a question yesterday about this (http://news.ycombinator.com/item?id=4080823 http://news.ycombinator.com/item?id=4080823) and spent a long time thinking about it. Great minds...
- StavrosK 14y agoYeah, I guess it's not that amazing a coincidence... Most people would arrive at that.
- jgrahamc 14y agoA more fun instance of this sort of thing on HN is when I suggested that HN might be attackable because of a flaw in random number generation and then someone else who hadn't seen my suggestion went ahead and did it. Me mentioning it: http://news.ycombinator.com/item?id=596126 http://news.ycombinator.com/item?id=596126 The attack: http://news.ycombinator.com/item?id=639976 http://news.ycombinator.com/item?id=639976
- mixmax 14y agoThat was an absolutely amazing hack
- peteretep 14y agoHere's a worked example of a similar technique I wrote up ages ago: https://gist.github.com/1051238 https://gist.github.com/1051238
- jcromartie 14y agoThis 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.
- tedunangst 14y agoThe idea is you do this before the password database is stolen. It's too late for LinkedIn, but not too late for you.
- ams6110 14y agoAs far as you know.... but how do you know?
- tedunangst 14y agoKnow what? Maybe the attacker is logging all the passwords that are entered. Maybe they installed a passwordless backdoor. Maybe they installed spyware on all your users' machines. There's very little point discussing all the imaginary attacks which may have already happened that you don't know about, that could be anything.
- donpdonp 14y agoWhat 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.
- tedunangst 14y agoI 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.
- gioele 14y 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 14y agoTheoretically, 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/STREAM83i/index.htm http://www.robertsradio.co.uk/Products/Internet_radios/STREA...
- ernesth 14y agoIsn't the fact that s/bcrypt is by design costly preventing this idea from being executed?
- tedunangst 14y agoAssuming you use 0.01s per hash settings, you can upgrade somewhere around a million accounts per hour.
- joshrice 14y agoSorta, 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.
- deleted 14y ago[deleted]
- ww520 14y agoIt'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.
- mjschultz 14y agoI'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?
- jgrahamc 14y agoShould have made clear that you can't do 5 if you need 4.
- mjschultz 14y agoAh, 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 14y agoI 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 14y agoOkay, 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.
- joshrice 14y agoIt's how to fix your rubbish password storage, not LinkedIn's or the others who've been compromised. That's the difference.
- mistercow 14y agoIf I'm not mistaken, the first paragraph is wrong. All signs point to LinkedIn having used unsalted hashes.
- aidos 14y agoAccording to their statement, they started salting some time recently. I guess you got a salt when you next logged in?
- danskil 14y agoI was just doing a write up on swapping auth back ends to gain more security http://schneems.com/post/24678036532/zomg-my-passwords-are-insecure-now-what http://schneems.com/post/24678036532/zomg-my-passwords-are-i....
- pdenya 14y agoThe variable names in this article are throwing me off. Is there a special significance to the subscripts and superscripts in the variables?
- kbanman 14y agoThe 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 14y agoIs that called "prime" by most people? I've always heard it just pronounced "dash", as in "s-dash" or "f-dash".
- drivebyacct2 14y ago>Is that called "prime" by most people? yes.
- PaulHoule 14y agoI 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.
- IgorPartola 14y agoRuby 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_ 14y agoEven 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...
- IgorPartola 14y agoI 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_ 14y agoIt 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.
- IgorPartola 14y agoI am no security expert. I can't tell bcrypt from a hole in the ground. All I know is that it's all fun and games until there is a problem with this home-brew implementation and then it's too late. That is why I think it's best to avoid anything like this and instead go with bcrypt/scrypt, etc. and re-evaluate periodically based on latest industry standards. Perhaps an actual security expert on here can evaluate your idea. I seem to remember it being raised many times on here, so there may be an answer to this on one of the discussions of bcrypt vs scrypt or some such.
- yathern 14y agoThe 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.
- IgorPartola 14y agoBrute 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.
- yathern 14y agoI 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.
- IgorPartola 14y agoOh, of course. But it will still take less time than you think. After trying a common dictionary the attacker just starts brute-forcing every single combination and since md5 is so quick and works so well on the GPU that it may take mere hours to find the answer. I've personally had what I considered a secure password cracked out of a sha1 + salt setup. Now I use LastPass and generate random different 32 character passwords for every service I use. LinkedIn leak does not affect me: 32 chars is enough to give me a day or two to change my password and none of my other accounts are compromised even if the attacker gets my LinkedIn password.
- yathern 14y ago
- esbwhat 14y agoI 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.