Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Yes, this is 'yet another client-side hashing' question. But, don't leave yet, I think there is some value here.

I'd like to do something to mitigate the affect on the community as a whole when my password hash database is stolen. (See: LinkedIn, Match.com, Yahoo, etc...)

In those cases, statistical analysis of the leaked passwords have been used to improve the heuristics for targeting cracking of a user's password. I'd like to help stop that from happening.

Here is the idea: Take the user's cleartext password, slow-hash it client-side as many rounds as can be stomached. Then, use the hash as the password passed to the server. Treat the password-client-hash just like a normal password and slow-hash again on the server side.

This should make my password database immune to heuristic attacks. (Well, not actually immune, just extra expensive to use the heuristics.)

My concern, though, is that the reduced entropy in the client-side hashing output might eliminate the gains I found in eliminating the value of heuristics.

How can this trade-off be quantified? Any thoughts on the approach?

Edit

To be clear, I'm trying to make heuristic attacks less valuable. i.e I want to make 'Password1' as good a password as 'tqwe657fdh'. Meaning, an attacker will have to search the same space to crack either one.

Another Edit

The discussion has helped me clarify my thoughts:

With the recent leaks of so many large password databases, and the resulting analysis of common passwords and patterns, I believe that heuristics used in password cracking systems must have been improved.

Recent advances with GPU assisted hash execution (http://openwall.info/wiki/john/GPU) are further shifting the CPU imbalance benefit back towards the attacker. (Anyway, it was already pretty imbalanced. Its a tall order to handle slow-hashing passwords on centralized server hardware once a system approaches internet-scale.)

I want to do two things:

Eliminate the benefit my attacker receives from the heuristics, thus forcing a true brute-force attack.

Decrease the benefit my password database will have to the cracker community once it is stolen from me.

I suspect my idea might help, but I need a way to quantify the tradeoffs.

share|improve this question
    
Do you want to use this for your personal accounts(without modifications to the server), or do you want to integrate this into the standard client of a service? –  CodesInChaos Mar 4 '13 at 15:53
    
@CodesInChaos - I want to improve my service I provide to users. This is me speaking as a software developer, not an end-user. –  brendanjerwin Mar 4 '13 at 16:07
    
If you are passing the hash to the server as a password, aren't you vulnerable to a reply attack? –  Mark C. Wallace Mar 4 '13 at 16:44
    
No, he is using the hash as a randomized long password. Ie, the server is still going to hash it with a (possibly different) salt and make sure that it is the appropriate hash). So the server stores a hash of the hash. –  AJ Henderson Mar 4 '13 at 18:30

3 Answers 3

up vote 5 down vote accepted

On the basis of standard password theory, this shouldn't work as we have to assume the password generation method is known.

I believe what you're asking is this, correct me if I'm wrong.

Your understanding of the standard method.

User 1 - (sent) password1 -> (stored) e38ad214943daad1d64c102faec29de4afe9da3d

User 2 - (sent) Di#aKHn!@ -> (stored) 9187b4dc0f7c7231334546a86984060233304c5e

Dictionary attack on the stored hashes recovers the passwords sent right?

What you want to do is this.

User 1 - (client side) password1 -> (sent) e38ad214943daad1d64c102faec29de4afe9da3d -> (stored) f8fde4f28c22e1a5a6201b6cce363477940cde50

User 2 - (client side) Di#aKHn!@ -> (sent) 9187b4dc0f7c7231334546a86984060233304c5e -> (stored) a893a40df9fc73ab3a9711a34e943f13271170c1

So the password for user 1 is seemingly as strong as the password from user 2, because they are both sending 40 character alpha numeric strings as passwords, and attacks on the final stored hash won't work* because the hash wasn't generated by a dictionary word, but a long hash.

The reason this won't work is again the process is all part of the program logic rather than entropy on the human side. The password cracking simply becomes SHA1(SHA1($pass)) instead of SHA1($pass) or whatever other control you have in place (salting etc). Given the need for repeatability it can't be hashed a random number of times on the client side, it must always be defined.

If I've misunderstood what you're suggesting just let me know.

Edit: To further expand on what I think you're saying re:comments below.

You want to make it so hashing takes X time, where X is the point where it's impractical to run dictionary attacks. You're saying that given the resources of the server, using a slow hash like bcrypt can only achieve a slowdown of time 'Y', which is not enough to get you over the 'X' threshold. You're idea is to use the client CPU as well 'Z', so now you have Y + Z to the point where you are hopefully achieving this 'X' threshold of rendering dictionary attacks useless.

My response would be I doubt there is enough CPU power between the client and server to make this impractical for someone to try a dictionary attack, while still maintaining a usable service. This is because the difference between GPU calculations and CPU calculations are so large.

share|improve this answer
1  
I think this meets exactly the question. One can imagine that an attacker just writes code that first makes the client-side hashing, and afterwards the server-side hashing. The input is still the weak password then and not the sent hash. –  martinstoeckli Mar 4 '13 at 21:23
    
Yes, SHA1(SHA1($pass)) instead of SHA1($pass), but its not SHA1. I'm thinking a slow-hash here. The idea is that we can make the double-hashed version so slow as to eliminate the value of the heuristics, thus forcing the attacker to revert to a straight-up brute-force attack. –  brendanjerwin Mar 4 '13 at 23:12
    
If we're already using a slow-hash like bcrypt, what is the point of a hashing a second time? –  Stephen Touset Mar 4 '13 at 23:58
    
@StephenTouset - To slow it down enough that it renders attacking the source password impractical. There is no way I can afford enough rounds on the server side, but if I involve the client-side CPU perhaps I can force my attacker to have to attack the second stage, thus rendering heuristics useless. –  brendanjerwin Mar 5 '13 at 2:57
1  
Okay. From my understanding this is still a dictionary attack. Dictionary is a fancy way of saying "predefined list of possible passwords", regardless of how they were derived. –  Peleus Mar 5 '13 at 3:21

For the resulting database, whether the hashing occurs client-side or server-side does not really matter. The attacker sees a hash, and tries passwords.

Client-side hashing has the following main consequences:

  • CPU is spent on the client, not on the server; since a server may have to manage 100 clients at a time, while the client will log on only one server at a time, this looks like an efficient usage of available CPU.
  • However, CPU on the client means, in a Web context, Javascript. This is more like 1% of the CPU, due to the overhead of Javascript (even with JIT compilation, Javascript is really not good at CPU-intensive tasks).
  • Since hashing requires knowledge of the salt, you have to change the protocol: the client sends the user name, the server responds with the salt, and only then the client does the hashing. This may or may not be easy to apply on a given protocol; it involves an extra roundtrip.

Thus there will not be a great security increase that way. Things change if you can have storage on the client. That way, you could store a key (something secret) on the client, and use a MAC computed over the user password (as typed) as the "password" to be sent to the server. Since an attacker who hacked into a server got the database but not whatever is stored on the client, this brings the "community service" you are after. On the other hand, key storage on the client brings its own set of issues (in particular, the user can no longer switch machines easily; the key must somehow be transported from machine to machine). A dedicated storage server can be used to help with these storage issues. To a large extent, this solution is the KeePass model.

share|improve this answer
    
Lets assume I can use Silverlight or Chrome Native Client or something just as awesome to compute the hash. –  brendanjerwin Mar 4 '13 at 16:08
    
I don't mind the additional round-trip to deliver the client-side salt. –  brendanjerwin Mar 4 '13 at 16:09
    
I still intend to hash on the server-side as well. The only gain is in the total number of rounds required to go through if heuristics are to be employed in cracking the hashes. –  brendanjerwin Mar 4 '13 at 16:11
    
If you are salting your passwords and using a slow hash, like bcrypt, then your goals are already met. The attacker can't merely crack "password1". He has to attempt it for each user, given their salt. –  Stephen Touset Mar 5 '13 at 0:00
    
@StephenTouset - The defender (me) is at a CPU disadvantage. With GPU accelerated slow-hash cracking making matters worse. And heuristic cracking, recently improved by these large password database leaks, again shifts the situation in the attacker's favor. –  brendanjerwin Mar 5 '13 at 3:02

There is no particular gain being on the server or the client, effectively, it sounds like you are just using an intermediate result as a hand-off point between client and server side hashing. You gain a performance savings to make an otherwise cost prohibitive level of hashing available, but ultimately, since the client is returning the intermediate hash as a valid input, the attacker still only has to counter the server version.

Say I run 1000 iterations of a hash locally on "mypassword" to get a value of "jdqfr3bt". The client then has to supply that to the server and the server does the 10 iterations that it can afford to do to get "91jf35j" which matches the DB, so it lets it in.

Now as an attacker, I get 91jf35j from the DB and look until I find that value "jdqfr3bt" matches it. I then simply supply that as the "result" of my client side hash without bothering to actually do anything. The server sees it as valid. It does make it more expensive to start from a dictionary, but a pure rainbow table isn't going to be impacted.

share|improve this answer
    
Right, I'm not actually looking to increase the security against a 'pure' brute force attack. I'm attempting to eliminate the value of dictionaries and other heuristics when my database is being cracked. –  brendanjerwin Mar 4 '13 at 18:38
    
Also, lets assume the passwords are salted when hashed... I wouldn't want to allow a rainbow table lookup at all. –  brendanjerwin Mar 4 '13 at 18:46
    
@Brenanjerwin - I think that it would make the password "Password1" a little more secure if there was a significant client side overhead, but it still wouldn't be as secure as having a well chosen password, since there is still less entropy and there is still technically a better chance of them guessing. It's only a linear gain and probably isn't going to make it expensive enough without a significant client side delay. It still does seem like a gain though. –  AJ Henderson Mar 4 '13 at 18:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.