Md5crypt is no longer strong enough | Hacker News Reader

Md5crypt is no longer strong enough

phk.freebsd.dk

176 pointsphkamp136 comments

Please notice that there is _no_ advantage in everybody in the world using the exact same algorithm, quite the contrary in fact.

If your password database is leaked, there are 2 categories of attacks that you need to be concerned with:

1. Brute force

2. A weakness in your implementation

He's right that brute force attacks will require potentially more work if you have a custom scheme as the attacker will have to work out the details of the scheme before using brute force (category 1).

However, many cryptographic compromises are actually due to bugs or weaknesses in the implementation (category 2); i.e. on paper your custom combination of schemes is fine, but you made a bug in implementing it or forgot to handle some case correctly.

How can you have confidence that your scheme is safe from category 2 attacks? Use a scheme that has already been widely reviewed and attacked. If no one has been able to find a vulnerability in it thus far, there's a good chance that your attacker won't either.

So there _is_ an advantage to using the same scheme that many others use. Use something hard, like scrypt, bcrypt, or PBKDF2, but also find an implementation of it that is likely to have been well used, reviewed, and hopefully attacked.

I think what he's suggesting is composing secure hash functions with some simple customisable steps, like xor, negation, so that the final result is as secure as scrypt, bcrypt, what have you, but also customized, so that standard tools won't work, and the attacker would have to do some custom legwork to attack your application. This, done correctly, would increase the cost of attacking to the point of making drive-by, mass-trolling attacks uneconomical, as they're based on pointing an exploit tool at a list of adresses.

It will not deter targeted attacks (spearfishing) by competent attackers, but again, not much would.

Such combinations could end up worse sometimes, just like 2DES has the same strength as DES.

The idea that my customizations would make it appreciably more secure (especially vs. just slightly increasing the work factor) seems questionable to me. On the other hand, it's very plausible that my customizations could accidentally make it less secure. Way smarter folks than me have messed up algorithms they actually put a lot of thought into — I'm not going to go blithely turning knobs in good algorithms and hope their positions weren't important.

Incidentally, what kind of drive-by attack are you thinking? Like, you have your password database sitting out in the open and there are bots crawling the web trying mechanically to crack it? Because that doesn't sound like a common case, but I'm not sure what else you could mean.

[deleted]

This comment was factually incorrect and only served to cloud the issue. The link given in one of the responses provides more than enough information for a developer to understand the options available for password storage.

Apologies for the noise.

You don't know what you're talking about.

Please elaborate for those of us who are not experts on cryptography.

For one, salts prevent using rainbow tables. A random combination of hashes with tweakable knobs, or whatever his suggestion is, is just a complicated way of salting except you have the possibility of weakening your function if you don't know what you are doing (as another has already mentioned, the unexpected behaviour of combining DES should be remembered).

bcrypt in and of itself already uses multiple runs to make it expensive in terms of CPU time to reproduce a given password. Moreover, salts are precisely designed to help against rainbow table attacks by making it infeasible to create rainbow tables including the large number of salts that you tag onto the end of a given password. bcrypt includes a salt as part of its core.

So no, if your scheme is “simply” bcrypt(password), it will not take so short a time for someone to extract passwords from rainbow tables, because they won't be able to have rainbow tables. Proper rainbow tables would need to both account for the salt and the number of encoding runs your bcrypt function has (which, incidentally, is also a configurable value).

Some information on how bcrypt, scrypt and friends apply salting and stretching to resist attacks was in yesterday's post at http://throwingfire.com/storing-passwords-securely/ . It's worth a read.

Yes, you're completely right. I was actually trying to illustrate the "tweakable knobs" concept in bcrypt in my nested example but I can see that my explanation was not helpful, and served to confuse the issue.

Thank you for clarifying!

You must take the next paragraph into consideration:

All major internet sites, anybody with more than 50.000 passwords, should design or configure a unique algorithm (consisting of course of standard one-way hash functions like SHA2 etc)

So he is in fact telling you to use a standard one-way hash function along with whatever custom implementation.

By combining two or more standard functions you're creating a different cryptographic primitive, which must be evaluated accordingly.

For example (while collision resistance is not that important for password hashing), by chaining MD5(SHA1(x)) you've created a better chance of collision than if you just used SHA1(x).

If you use 10 hash functions in any possible combination, you must evaluate the security of every possible combination, or prove that your resulting function is secure with any combination of these 10 functions. And for what? For only a slightly larger, constant, cost of attack, which you can easily get by adjusting a parameter in scrypt.

Not if you use a permutation like a block cipher with a fixed key, rather than an arbitrary function.

Not what? That you've suggested a completely different scheme (single algorithm with a key) to the one described in the comment I replied to (combining multiple algorithms)? :)

(Note that even using a standard block cipher requires a separate evaluation for different purposes -- you can't claim that your hash function/MAC/mode of operation is as secure as AES only because it's based on AES.)

If you read my replies in this thread, I emphasize the point that if you really need a custom function with secret parameters, use a single algorithm with a secret key (I even gave a link to one such scheme with HMAC.)

You missed my point. I was saying that this scheme AES(key, SHA256(password|salt)) is at least as secure as this scheme SHA256(password|salt).

No, it can be worse.

If 'key' must be kept secret in order to achieve its stated security properties now the system is much more unwieldy for the defender. He now has a key distribution problem that he didn't have before. If the defender can reliably solve the key distribution problem then the attacker wouldn't have gotten a copy of the password key database.

On the other hand, if 'key' is public, then the incremental computational cost added with AES raises the cost for the defender, but not the attacker. The attacker can just un-AES a password hash once and remember the result whereas the defender must perform the AES on every password validation.

Consider the possibilities: (1) if the key is captured by the attacker the system is just as strong as SHA256, (2) If the key is not captured by the attacker then the system is as unbreakable as AES.

Many of the attacks that lead to password hash exposure involve a SQL injection that dumps the password table. If you store the password in the source code an attacker must then capture both the source code and the hashes. Furthermore, if they leak your key, you learn that they have gained access to your source code.

I agree that this is a less than ideal system. My point was not to design a better system, but to point out that composing permutations with a secure hash function is at least as strong as that secure hash function. If you disagree consider the identity permutation. Really you'd want to implement it like SHA256(AES(key,SHA256(password|salt)).

If I wanted to design a better system this is what I would do. Put the hashing system on a dedicated box that maps passwords to hashes. To compromise the hash key an attacker must compromise your hashing box and your database. Locking-down a box that performs only one action, hashing, is significantly easier than locking down a complex web application.

> (1) if the key is captured by the attacker the system is just as strong as SHA256

This is the part that I think is subtly invalid. Coincidentally, I was having this mailing list discussion the other day: http://lists.randombit.net/pipermail/cryptography/2012-May/0...

It has to do with the fact that the defender is obligated to pay the cost of the AES every time (because he follows the rules of the algorithm by definition). But the attacker is free to bend the rules however he can and one thing he can do is perform the AES once on the entire data file, a negligible amount of computation.

So even though AES is an identity transformation, it makes the function more costly for the defender than for the attacker. Wncrypting one's database may be an acceptable tradeoff for other reasons, but when we're considering the work factor for cracking passwords this is worse.

Think about if instead of just one iteration of AES it were iterated a zillion times in order to make it expensive. That would be a complete failure.

>Think about if instead of just one iteration of AES it were iterated a zillion times in order to make it expensive. That would be a complete failure.

I agree, and I don't think AES (or any easily invertible function) should be used to increase the work factor.

We have been arguing past each other. I was responding to a post that said ~'if you compose two functions and the second function is insecure, than the composition is insecure'. While such a statement is correct for compression/hash functions, it does not hold for permutations.

Do you agree that keys or peppers decrease the risk of passwords being revealed if the key or pepper can remain secret from the attacker? Assuming that keeping a key secret is much easier than keeping a bunch of hashes secret, which is a fair assumption, shouldn't such a method increase the security of the system?

> Do you agree that keys or peppers decrease the risk of passwords being revealed if the key or pepper can remain secret from the attacker?

I'm not familiar with this term 'pepper'. I take it to be a key with which you encrypt a password has as in your construction?

> Assuming that keeping a key secret is much easier than keeping a bunch of hashes secret, which is a fair assumption,

I don't know that it's such a fair assumption. For example, where does the server software get the key when it boots? From the hard drive? Is it something that is chosen or typed in by admins? If so, how do you ensure this key isn't itself simply derived from a weak password? If it's a password, how likely is it to be the same as the root login password or master database password? If the app developer re-uses this key or password in multiple contexts it's an additional exposure.

> shouldn't such a method increase the security of the system?

I think it could help and might even be a good idea overall.

That said, I don't think we should consider it an intrinsic part of password hashing security because:

a) It might help some with pure SQL injection exploit scenarios but anything beyond that it probably won't help at all. So any security benefit it brings is very hard to quantify.

b) It could apply equally to any sensitive database field that didn't require join capabilities.

c) It imposes a work factor to the defender which can be bypassed by the attacker.

Pepper is like a salt but secret. http://barkingiguana.com/2009/08/03/securing-passwords-with-...

I think the most secure method would be to store a random string in the persistant memory of a hardware dedicated device that performs the encryption on your behalf (like a smart card or trusted computing module). If that is not possible you could still put the key inside the hash program and give the app only execute privileges for that program (the key is safe unless the attackers get root).

a). If it protects against a very common attack or attacker why not do it. Security should be layered.

b). agreed

c). The work factor of a single AES encryption is negligible for both the attacker and the defender and can be ignored. Furthermore it can be removed entirely if you hash both the input and the output as I proposed in a previous message, SHA( AES(K, SHA(password) ) ). Now the attacker has to run AES for each try as well (but it doesn't matter since any reasonable work factor will be orders of magnitude larger than a single AES operation).

Collision resitance is not really a worry for a password scrambler, until the probability gets into the 1e-6 range or above.

Yes, that's what I said in parentheses.

That reminds me of the sage advice Bruce Schneier wrote in Secret and Lies, "Anyone who creates his or her own cryptographic primitive is either a genius or a fool. Given the genius/fool ratio for our species, the odds aren't very good."

He's saying to build a custom function out of well established cryptographic primitives.

I don't think that's a good idea either. There's still a ton that can go wrong that won't be apparent at all to someone who knows how to analyze entropy flows through the internals of hash functions. There's a reason why we have a PBKDF2 that's favored over the original PBKDF.

Excellent points. From a practical perspective not every website is going to get into the game of cryptography but its trivial to get into the game of salting. The fact that places like linkedin don't salt doesn't mean our algorithms are bad, it means the kinds of people who built the system there are bad.

>All major internet sites, anybody with more than 50.000 passwords, should design or configure a unique algorithm for their site

He probably means to use some combination of well known/tested algorithms rather than inventing your own crypto, but I think his wording is ambiguous enough to be dangerous. While there is some benefit to using a unique algorithm for your site, it's almost certainly more risky than using a secure algorithm (i.e. bcrypt/scrypt/etc) even if every other site was using it too.

Also, if that's what should be encouraged, someone might as well put together a simple framework for automating it. Basically, you hard code a list of salts and a list of hash function names (which could also be automatically generated by a tool), and it gives you a new hash function which is the composition of those other functions. There's no reason for everyone to try to do it by hand and risk messing it up in some simple way. And if there were an easy to use framework for doing it, there would be no reason for only larger sites to use it. Using a custom hash function could simply be a best practice.

But honestly, I'd be pretty happy if we could get all sites with 50,000+ users to salt and hash their passwords with any algorithm.

The PBKDF2 protocol allows you to safely brew your own password scrambler using any hash functions you choose. It is equivalent to bcrypt for common purposes, assuming the hash functions you pick are decent.

Here's a question for the people here who actually know wtf they're talking about: if I choose to iterate through a set of hash functions with each pass of PBKDF2 rather than using the same one each time, what effect does that have on the entropy of the system and so on? Would it make it easier to crack, or harder?

There is no per se answer to that question. Cryptanalysis is hard, you can't assume things like commutativity and orthogonality.

This whole line of thought is at best a waste of time, and at worst dangerous.

PBKDF2-HMAC-SHA-256 is a vetted NIST approved standard with an adjustable work factor. It has been subject to professional attention for many years.

BCrypt, while not subject to nearly as much analysis nor approved by NIST, was designed by very competent cryptographers, has an adjustable work factor and is based on blowfish -- which has been subject to substantial professional attention.

Use one of the above with the highest work factor you have the processing power for and call it a day. Don't try to roll your solution.

I tend to agree, which is why my whole comment was conditional on "if it's a good idea for everyone to use custom hash functions". Basically, if we're going to have custom hash functions, we want to reduce the "roll your own" aspect of that to a minimum.

I hope nobody thought I was suggesting they actually do that. It was purely a matter of personal curiosity. Entropy is perhaps the most interesting thing in the universe.

I'm far too lazy to do anything other than slap bcrypt on it, unless there's a pressing need to do something else, which there never is.

(Not an expert) The entropy doesn't change. What you get by adding another hash function is a slightly larger die area (and thus the cost) required for brute force attacks. By using scrypt instead of PBKDF2, you can adjust the die area required for attacks in a more flexible and safe way by just giving it a different parameter.

Hash functions have different requirements than key stretching functions, but if you're interested in the security of combining cryptographic hashes, Google for "combining hash functions" and "chaining hash functions" -- there's a lot of interesting research.

>The entropy doesn't change

Yeah, that now seems obvious. The input string is the same, so the information entropy is the same. I'm struggling to think of the concept that I need here, I want to say kolmogorov complexity but I know that's wrong too.

> The PBKDF2 protocol allows you to safely brew your own password scrambler using any hash functions you choose. It is equivalent to bcrypt for common purposes, assuming the hash functions you pick are decent.

NO! Bcrypt in particular is designed to resist GPU brute forcing.

Yes, that's why I said "common purposes." If you're seriously worried about people bringing racks of GPUs to bear against you then what you're doing probably isn't "common," although I accept that this is rapidly changing.

You can calculate billions of SHA-1 hashes per second on a single $100 graphics card using standard software. That's pretty common. There's AFAIK no implementation of bcrypt for GPU.

Yes, but an opportunistic blackhat will just go and attack one of the millions of sites which don't need GPUs to crack instead. It's a margins game, like anything else.

If you're being attacked by anyone other than opportunists, you have bigger problems than your hash function. As soon as someone attacks you specifically, you're in a "trust no-one" situation, and suddenly it's time for anonymous meetings in basement carparks and the like.

I don't understand. If your "opportunistic blackhat" is willing to attack something, what are the chances that he doesn't have a pretty normal standard graphics card for this in his PC?

He probably does. What I'm saying is, why would he put that to work cracking n PBKDF2-HMAC-SHA-256 hashes per hour for n dollars per hour, when he could put it to work cracking >n MD5 hashes per hour for >n dollars?

If the answer is "my hashes protect something that is particularly valuable," then the attacker probably isn't going to hack your hash function, he's going to hack your secretary or your garbage disposal or something like that which is more effective.

Of course, in practice you should just use bcrypt anyway.

Ok, sorry for the harsh response, but i don't think that anyone is using it for "common purposes." Everyone should be using strong crypto, because it is inexpensive to do right.

I would argue that almost everyone that is storing passwords should start worrying about people bring racks of GPUs to bear against you, because it is so cheap. At 33.1 Billion MD5 hashes/s with 4 dual-linked GPUs (one machine), you can eat through all 8-digit alphanumerics very quickly for a few thousand dollars. (of course that is using PBKDF1 or less). I had done the calculations in a spreadsheet and forget how long it would take, but it is way shorter than you'd thik.

Such a toolkit would probably be a good idea.

Tie a card-carrying cryptographer to a chair until he delivers it ?

>Tie a card-carrying cryptographer to a chair until he delivers it ?

Alternatively, implement it very, very simply and put it on github, and ask card-carrying cryptographers to vet it. That one is harder on the ego though.

I'm pretty sure no cryptographer will vet it.

I read 'vet' as "tear it to bits"

Yes, exactly. After several phoenix iterations of that kind, you might have something approaching usable.

One, often over-looked reason, that website designers chose simple MD5 or SHA1 hashing (and why many still do) is for portability. Years ago this was more of an issue than it is today. They may wish to change web frameworks, programming languages, service providers, etc. and when doing so they want a simple, easy way to use the hashes they have.

Also, many big service providers still use MD5 or SHA1. I saw a company migrate to Google Mail from an old legacy mail system and part of that was integrating some authentication services too. This was several years ago, but at that time, Google accepted hashes in two formats only... MD5 or SHA1.

It's pretty easy to migrate users from one hashing algorithm to another when they next log in:

  if( user has an old style hash ){
    if( password verifies against old style hash ){
      add a new style hash
      delete the old style hash
      log them in
    }
  } else {
    if( password verifies against new style hash ){
       log them in
    }
  }

But if you have code to run the old style hash you don't need the new one. (Although it's useful to upgrade the work factor.)

The issue is you don't always have the ability to do the old style, that's why people prefer a hash that they can be assured will be found everywhere.

You mean you're sending unhashed passwords from the client?

Yes. That is the standard behaviour that nearly all sites use, and is perfectly fine.

It's not great, though - it means that someone who hacks your server can get users' passwords a lot easier. I read a couple of weeks ago that Blizzard's games don't send the passwords to the server, they send a hash. Things are necessarily crappier on the web, of course.

Edit: there's more detail at the link below. It looks clear that in at least some of their schemes they deliberately do not send the client password to the server, which sounds like a decent idea.

http://www.skullsecurity.org/blog/2012/battle-net-authentica...

If the server is hacked, then all bets are off. They can just modify the webpage if they want the un-hashed password.

Exactly - "Things are necessarily crappier on the web, of course."

I wonder, though. Could there be a "code has changed" warning from the client? I mean, authentication should be pretty damn stable, and maybe even universal. If someone does modify the page, it'd be nice to know if that change was reflected on other sites, and it'd be nice to know that someone I trust had signed off on it (cryptographically).

A simple alternative is to build it into browsers. A password field could generate a salt per-domain and automatically encrypt any queries to password-fields. The server doesn't even need to know about it. You'd have to be more than a little careful building it, obviously, and you'd have to find a way to deal with passwords used on more than one site, but it could work.

Sending a hash is no different than sending a plain text password. Because the attacker has complete control at their end and can just hack a client that sends that same hash even if they don't know the original password.

Would it not be an aid to users in cases where they are reusing the same password on multiple sites?

Note that getting the client to send only the hashed password is incredibly silly. If there's a leak, the hackers do not even have to crack those passwords.

How many web login forms (as an example) are doing client side hashing? The only ones I know are of the recent 'test your password in the linkedin leak' variety.

How do you degrade for NoScript users?

And where's the harm in that anyway (assuming TLS)?

Graceful degradation is pretty easy. Override the form submit handler to hash the password, set a flag that the password is hashed, empty the original password, and submit the form. Users with JS blocked will just submit the unhashed password as usual.

Of course, if you're salting the hash uniquely for each user, then this approach isn't very helpful.

Finally, if your server will accept hashed passwords, then getting the hash is as good as getting the password for access to your site. The only benefit is that the password is hidden so you may avoid compromising security on other sites.

> Of course, if you're salting the hash uniquely for each user, then this approach isn't very helpful.

I've seen this advised a lot. However, where are you going to put the per-user salt? I presume in your users table, or somewhere in your db. Does this not mean that the salts are just as likely to be hacked as the encrypted passwords?

Are you not better off with either a single salt that's stored somewhere outside your db or with some other scheme for algorithmically picking a salt based on the user id?

Salts aren't meant to be secret (or rather, no more secret than the password hashes themselves). The goal is to prevent a precomputed brute force attack.

If you store straight unsalted hashes, you can precompute the hash for every likely password, store the precomputed hash -> password mappings in a nice efficient data structure (http://en.wikipedia.org/wiki/Rainbow_table) and use the same precomputed tables to reverse every hash in the system with a very fast lookup. And every other system using the same unsalted hash scheme.

If you have a salt, this doesn't work -- you'd need a set of precomputed tables for each salt value, which rather defeats the object of precomputation.

If you take it a step further, and use a storage scheme like bcrypt or PBKDF2, not only are you protected from the precomputation attacks, but testing each password candidate takes much longer than a straight cryptographic hash -- so brute force attacks becomes much slower, too.

To put it differently, hashing without salting lets an attacker crack the entire database at once. Try a password, see if the hash is in the database, repeat.

With salts, the attacker can only attack a single user at a time. Try a password with one user's salt, see if the hash is in the database, try the next user's salt, see if that hash is in the database, repeat.

Salts don't need to be secret to work.

My point was that sending the hash the server doesn't work if the hash is salted per user since you don't know what the salt is. (I suppose you asynchronously fetch the salt value after the user puts in a username, but at the solution as a whole starts to fall apart.)

There's no real point to doing this. If you want to stop them being sniffed, send them over SSL.

What would be the point of hashing on the client? Let's say you're using md5, and you hash the password before you send it. Chances are, that un-salted hash can be easily decrypted by any number of reverse-lookup tables around online. You can't salt the hash client side, because anyone can look at your JS and find your salting tactic.

The best approach to securing information going from client to server is SSL.

It doesn't matter that they know your salting tactic, it still stops reverse-lookup tables with common passwords online.

However any salting tactic that can be pushed and used on the client side would have a tough time using a salt that is on a per-user basis. This means that if you could salt it client side, you would need to have a static salt, which is significantly less secure than a unique salt per user.

> However any salting tactic that can be pushed and used on the client side would have a tough time using a salt that is on a per-user basis.

How so? Surely the client would know their username too?

Eh, why not just bcrypt the SHA1/MD5 hashes? Your auth check will just become bcrypt(SHA1(pass)) rather than bcrypt(pass). You can convert all passwords right away and I don't see any significant downside to it.

Will there not be a time lapse whilst you run bcrypt on all the existing hashes to update your users table? Given that bcrypt is intentionally 'slow', this might be a problem for applications with large numbers of users (albeit a one-off cost).

I agree that for small sites, changing the auth check and updating all the existing rows (and deleting/overwriting the old hashes) is probably the best solution though.

> Will there not be a time lapse whilst you run bcrypt on all the existing hashes to update your users table?

No, just SHA1 the password and check, and then bcrypt(SHA1) and check, until the encryption process finishes. Or just check the length, or store the hash type along with the hash, a la Django. These problems are trivial, really.

If you assume 6 million users and one second to compute a password hash, that's a couple of months on a single CPU. Takes a while, but no big deal, and it can proceed while your site stays live.

That would be fine if you wanted to retain the legacy hashing function. I was describing a migration from one hashing algorithm to another. You're describing modifying the existing hashing algorithm, which is something different.

It depends if your goal is to have security for everyone right away or if it's to only use one hashing function. I don't see anything wrong with a round of SHA1 in your setup, especially when it allows you to secure everyone's password immediately...

I like this idea for sites that e.g. use Microsoft ASP.NET Membership where all you can do is set a machineKey attribute about what kind of password hashing to use, and don't support any "old hash vs. new hash" alternatives for changing. Anyone know of an implementation that would do this and "drop in" to an existing ASP.NET site? Or pointers to how to approach developing this?

Don't use ASP.NET membership? I can't get over how much effort they put into MVC ASP.NET and they still carry that cludgy mess around.

Sometimes you have to deal with what you are given.

That's fair, my snark doesn't help with that, as I was in that same position about a year ago and opted to just leave it and pretend it wasn't there.

I'm sure there is a way to improve it, but I don't know how, sorry!

Why not do both then?

    1. bcrypt(SHA1(pass)) right now to secure all pws
    2. check against that, then update to bcrypt(pass) on login

That's probably the correct thing to do but since you're unlikely to ever achieve 100% migration, it doesn't help a whole lot.

The problem is that you may have to keep this code for a VERY long time (people don't log into sites for 3+ years and expect their old passwords to still work). Lugging around legacy code is never a good idea.

I agree that lugging around legacy code but whats the alternative? (Note I'm not a security expert)

AFAIK its this

1. Continue using legacy, less secure hashing algorithm

2. Upgrade your password storage scheme and carry around some extra code and/or fields in your db.

3. Crack you own users passwords and convert them

Its all kind of smelly but 2 seems like the only option (unless I'm missing an option?)

4. Expire all passwords and ask your users to come reset them. - No legacy code necessary

Regular users should have no problems if there's an accompanying blog post Non-regular users might just remember about your site/service and come back :)

5. Use bcrypt/password stretching. Store the work value alongside the password and upgrade it as people log in. To me that's not really keeping legacy code around; just an extra variable...

" … at that time, Google accepted hashes in two formats only... MD5 or SHA1."

That's, ummm, _concerning_…

I don't suppose anyone knows how securely Google are storing my gmail password? I _hope_ it's not unsalted MD5 or SHA1. (Especially since google search is probably the best general purpose md5 hash reverser most people have access to.)

Google could store passwords in plain text if they want, because they're never going to leak. I'm only partially joking.

Famous last words :)

Then at least you are only partially an idiot.

Last migration I did (maybe 12 months ago), google only accepted passwords as an sha1 hash IIRC. I was told however, that was only an intermediary step, and google runs that hash through another KDF for internal use. The sha1sum of the password is really only used for transport to their API, as an alternative to sending it in plain-text which is what your browser does when you login to google services, so I don't see it as a huge problem. Sure it could be more secure, but interoperability and keeping a relatively low barrier of entry are very important to them too.

I thought Google logon defaulted to SSL for all services.

It's still sent in plain text. Your browser doesn't do any hashing before sending your password to Google.

But you're right, as far as anybody but you and Google are concerned, it's encrypted.

There's no point in hashing the password before you send it, is there? A MITM could just as easily grab the hash and send it to Google instead.

For MITM attacks, sure. But it's a fairly portable, inexpensive way to make it more difficult to use your password with other protocols. For example, intercepting a plaintext Google password has a decent chance of making someone's bank account vulnerable.

But in that case the password has only been compromised on that one website, as opposed to every other website where it's being used (likely a non-zero number of them given the average user's password habits). I'm no security expert but I think client-side password hashing with the domain name as the salt seems like a pretty good idea, especially for sites without HTTPS logins (but it also helps in the case of a database leak even for sites with HTTPS logins). Of course, for non-HTTPS logins a network attacker could modify the HTML form code to remove the client-side hashing without the user's knowledge, but it's still at least as secure as the alternative, modulo 'false sense of security' type arguments.

Edit: never mind the last parenthetical; it pretty much wouldn't help in a database leak at all (just adds one extra hashing step to the cracking process), sorry. Still helps for non-HTTPS logins though.

Edit 2: ... though maybe if the client-side hash were something strong like bcrypt, it would help in the case of database leaks on HTTPS sites that refuse to use strong hashing on the server side for performance reasons. Sorry for the rambly disorganized post.

Right. If someone is able to infect the browser with malware, MitM your HTTPS connection, or even just load mixed HTTP/HTTPS content, then they are able to run Javascript in the login page. If they are able to run Javascript in the login page, then they are able to monitor the keystrokes as it is typed in.

This is not theoretical. This is what Tunisia did to Facebook and it's what online banking trojans (e.g. Zeus) do every day.

> Google accepted hashes in two formats only... MD5 or SHA1.

It's not surprising that they don't support importing custom formats. They support two formats to bulk-import and then surely convert to their standard from there.

Isn't salting a canonical way to vary the output for the same input, thus reducing feasibility of precomputed attacks like rainbow tables? What are the benefits of some extra mangling, besides security through obscurity?

The point is that computers are really fast now. There's no need to precompute anything, just crack hashes on the fly. The extra mangling slows things down.

If an attacker gets access to a database of user names/hashes, a salt prevents him from simply checking the hashes against a precomputed list because each hash is totally unique.

The attacker would have to recompute all hashes for each user using their individual salt.

At least that's what I remember from Computer Security ha

Salting means that you must crack each key individually. It slows things down marginally in the long-run and at least precludes someone form using Google as your rainbow table. Have you ever tried searching for MD5 hashes of things like 'password' or 'pass123'? It's terrifying.

Looks like it wasn't clear that my question was rhetorical. My point was that some secret mangling on top of a standard hashing algorithm doesn't offer more protection than salting.

I've been offline for some hours, and just wish to add a few concluding thoughts here:

No, I'm obviously not proposing that people do something stupid with crypto, we've had enough of that in recent days already.

But I am trying to provoke one or more card-carrying cryptographers to realize, that while password protection may be a problem we have good and strong theoretical solution for, those solutions will not protect any passwords until somebody turn them into Open Source code we can use.

I only wrote md5crypt because nobody else had done so, and nobody else wanted to do so at the time, and FreeBSD needed an ITAR exportable password scrambler.

If more cryptographers wrote more code under liberal Open Source licenses, instead of bitchy complaints against the people who do write code, then the world might gradually become a better place

I have been dreading this announcement for a couple of years, knowing full well that the majority of the world can't tell MD5 from md5crypt.

It is a credit to hackernews that you could, much appreciated.

Ah, the good old "secret algorithm" thing.

If you really want a "custom algorithm", the better advice would be to use a known algorithm with a secret key.

For example,

https://wiki.mozilla.org/WebAppSec/Secure_Coding_Guidelines#...

Why? See http://en.wikipedia.org/wiki/Kerckhoffs_principle

In most case, you don't need this, though. Can you prove that your construction is secure? How many hashing algorithms are there? Remember that big O thing. Just increasing the workfactor for scrypt will be much better than using a combination of 5 or so hash functions.

There is no mention in the article of secret algorithms.

"Unique algorithm ... in order to make development of highly optimized password brute-force technologies a "per-site" exercise for attackers" for KDF/password hashing is similar in principle to secret algorithm for ciphers: consider that the attacker already has an optimized brute-force technology for your combination of primitives (for ciphers: consider that the attacker knows your algorithm); replace this unique algorithm with the work factor/secret key to have fewer moving parts.

I think a clearer way to express the author's position is to consider the case where a feasible attack is discovered on (say) SHA1. If you consider the probability of an attack on SHA1 and blowfish to be of independent probability, then the author's scheme allows you to "hedge your bets", as in theory your algorithm is as strong as its strongest component, even if the strengths of its components change in the future due to new discoveries.

This line of reasoning assumes A) that the probabilities of attacks on the algorithms are independent, and B) that the algorithms in use do not substantially reduce their input entropy, both of which are potential attacks.

It does _NOT_, however, assume that the scheme be kept secret.

Excellent idea, a hash scheme per site. A multi language framework to help you build your own scheme, one which can be validated by many cryptography-knowledgeable eyes, would improve the chances of this actually happening some day.

It's a pity that seemingly trivial changes on an crypto algorithm can totally obliterate its security.

Here's a (potentially stupid) idea:

The app provides a fixed 'secret key' that defines (somehow) a sequence of hashing and scrambling functions to apply to the password. So, for example, the secret key "df8dfuhuejew3" (or whatever) might be interpreted as '3 iterations of md5 hash followed by rotate hash 5 places to the left followed by 2 iterations of bcypt etc..'.

So, in effect, each app (with a different secret key) will have a different hashing process, but with the advantages that its repeatable and cross platform (reference implementations could be available in the major languages).

Of course, if your secret key is hacked you are in trouble, but at that point the hacker can probably get your source code for whatever hash system you use, and anyway, the combined hashing process is probably slow enough to prevent brute force attack.

Any thoughts?

Edit: Probably better to just use bcrypt with a larger work factor.

Why is this any more secure than keeping a salt in your code?

bcrypt(password + hardcoded application salt + db-stored user salt) is far less complex and arguably just as secure, since your argument is predicated on "assume the source code is safe". bcrypt is tunable to be as slow as you want, even to account for hardware progress.

>bcrypt is tunable to be as slow as you want, even to account for hardware progress.

I did not know that. Can you expand on this point?

Part of the bcrypt process includes a "work factor", which is, crudely, "how many times do I run this?" What you can do is tune your work factor so that it takes a reasonably long time to hash a password (say, 0.05 sec on your webserver = 20 passwords/sec), which won't necessarily heavily impact the performance of your website, but which would be a significant impediment to anyone trying to brute-force those passwords.

As hardware improves, you just implement a system wherein when the user submits login information, you verify their password with your old work factor, and if it passes, re-hash with your new (slower) work factor and store the updated hash. This allows you to effectively use a progressively slower algorithm over the lifetime of your application to compensate for Moore's Law.

You obviously don't want to pick a work factor that's too high for your web server hardware, since that opens you up to DOS attacks, but a reasonable work factor can easily mitigate the weaknesses of MD5 and SHA1 - notably, that they can be computed by the hundreds of millions of second on the right harware.

Ok, got it. Thanks. Yes, much better. I was under the impression bcrypt was also a fixed cost operation.

If anyone else is wondering how to implement bcrypt with a cost parameter in PHP, see http://php.net/manual/en/function.crypt.php under CRYPT_BLOWFISH.

It's probably prudent for most developers to instead use phpass [0] rather than attempt to roll their own implementation.

[0] http://www.openwall.com/phpass/

PHK is not concerned with preventing precomputed (rainbow table) attacks. A salt is fine for that. He wants to make it harder to create special-purpose hardware for brute-forcing. Combining many different types of hashes is only intended to eat up die space.

Again, if you really need to use a secret algorithm, instead use a secret key with the known proven algorithm (see for example https://wiki.mozilla.org/WebAppSec/Secure_Coding_Guidelines#...)

That the security of a cipher system should depend on the key and not the algorithm has become a truism in the computer era, and this one is the best-remembered of Kerckhoffs's dicta. ... Unlike a key, an algorithm can be studied and analyzed by experts to determine if it is likely to be secure. An algorithm that you have invented yourself and kept secret has not had the opportunity for such review.

http://en.wikipedia.org/wiki/Kerckhoffs%27s_principle#Implic...

Moreover, you made the security of your system "key"-dependent: what if I generate such "key" that will only use 5 iterations of MD5 and 1 iteration of SHA-1? This would be a major failure. Imagine if the security of AES was not 2^128, but varied between 2^10 to 2^128 depending on what key you supplied -- would you use it?

>Moreover, you made the security of your system "key"-dependent: what if I generate such "key" that will only use 5 iterations of MD5 and 1 iteration of SHA-1? This would be a major failure. Imagine if the security of AES was not 2^128, but varied between 2^10 to 2^128 depending on what key you supplied -- would you use it?

Agreed. The unpredictability of the work factor would be a problem.

BTW COTS means Commercial off-the-shelf. (I've always known that abbreviation as just OTS, and was trying to figure out if the C stood for "Custom".)

I've never seen just OTS, but then I work in an area where it is necessary to distinguish COTS from GOTS ("government..."). If you have no reason to encounter government software, then I suppose there's no reason to specify that you mean commercial.

I read it as Cheap Off The Shelf.

I usually parse it as common-off-the-shelf

Yes, of course. I have clarified the text now on this point.

What is this a reply to?

He was replying to http://news.ycombinator.com/item?id=4078418

For server-side, how about password DB implemented as hardened information appliances? This would make the acquisition of the password database harder. White-box techniques could be used to hide a modified salting technique, making cracking much more labor intensive. Such a service could be offered by cloud and virtual server providers, perhaps for a small additional fee. (Which would still be almost all profit.)

It's very telling that hardware is outpacing our own cryptographic techniques. I remember reading an article that stated that all passwords will someday be crackable due the advances in Quantum computing.

By that time we'll all know that your password is "I Love Care Bears 123" :P

Hardware is not outpacing our cryptographic techniques. Go spin up an AWS GPU cluster to break an AES-256-encrypted file and let me know what the bill runs you.

md5crypt is a "poor man's" crypto system, simply because it's built on MD5, which is intended to verify data integrity more than it is designed to hide information. We've known that md5 was broken since 2004, so at this point, anyone actually using MD5-based systems for password hiding really has no excuse.

Quantum computing is a whole 'nother ballgame, and while it does offer the promise of making current encryption schemes more or less obsolete, it's an entirely different ballgame than "chain together a few Radeon cards and crack a DB full of MD5 hashes".

The way forward for nontechnical users seems clear: avoid giving websites sensitive information and letting them store it for you. How long before Facebook is hacked?

Keep sensitive information on your own storage media, not on some website's servers connected to the internet.

How about this for security MD5(SaltFromDB + Password + ApplicationConstantSalt)? How would that be affected by something like this? Given the user you'd their salt, their paassword but not the application salt. Still really insecure?

Just found this if any PHP developers wants an easy to use bcrypt password library. https://gist.github.com/1053158

Not exactly an expert on cryptography, but how different is the description of the "next" crypto-algorithm provided by Kemp different from what bcrypt can do today?

That this is upvoted to #1, in 2012, on a site called Hacker News, is probably more notable than the article itself.

I reinforces my belief in humanity that it did happen, I have been pondering for a long time how to do a "People of Earth, your attention please..." which would reach the necessary audience.

Inertia. The fact that it works and has been tested extensively in production means more to many managers than security does.

(pause for collective gasp from the nerds)

Until it becomes a crime of some sort to use these simple, well-tested hashes to store passwords and the world police begin locking-up CIOs because of it, then don't expect anything to change.

You're responding to an argument I never made. I'm not surprised MD5 is used in the wild, nor confused about the reasons why. And hell, it's a step up from plain text, which is probably even more common.

I'm just surprised to read about its deficiencies on Hacker News as if it were news.

Um. Haven't we known not to use MD5 for years now?

MD5 is not vulnerable as used in md5crypt.

In my very first internship/job, I implemented user management in ASP and Access database in backend. I chose MD5 for password hashing and I was so proud of myself. Of course this was about 10 years ago. :)

Reply on news.ycombinator.com