Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

As we know, one should use a slow password hashing algorithm instead of a fast one for storing passwords, to hinder brute force attacks when the database is compromised. The problem with this is that for every login we also need to run this slow password hashing algorithm, which for remote logins could be a considerate CPU load on the login server if many people try this at the same time.

This night, I had an idea on how to solve this (in a new protocol for password authentication):

  • The user types in his username
  • The client sends the username to the server.
  • The server sends a salt (and maybe other parameters) to the client
  • The user types in its password
  • The client calculates a slow hash (bcrypt-like) from this password, using the salt (and maybe the security parameter, e.g. iteration count) provided by the server
  • The client sends this hash value to the server
  • The server calculates another cheap salted hash (SHA-2-like) of the sent hash value, and compares it with the value stored in the database.
  • (Optional, to avoid remote brute-forcing and DOS: wait a small time before sending back the answer, and limit the number of parallel connections for each user/IP.)

The communication should be encrypted, of course (as the sent hash value is the effective password).

(Add the obvious way of generating and storing the passwords.)

I'm assuming this:

  • The output of the first hash is not really recognizable as such, e.g. there is no cheap way to iterate only the possible outputs of the first hash instead of all strings of this size. If I understand right, bcrypt has this property (if we only look on the actual ctext part of the output, having length of 192 bits).

    (A comment from ZoFreX seems to indicate that this is not the case. Any details on this?)

  • The second hash is preimage-resistant, e.g. there is no significantly better way of finding a preimage fitting to a given hash than brute-forcing the input space.

Then we have:

  • The first (slow) hash avoids (or rather slows down) brute-force/dictionary attacks over the password space. (It is salted to avoid rainbow tables.)
  • The second (fast) hash avoids that an attacker which gets somehow read access to the database can immediately use the data to login into the system: The attacker will need to brute-force the (in the bcrypt example 192 bit large) output space of the first hash to find a preimage (which then would be usable as a password).

    If we think it is needed to slow this down even more, we could use a second (low-factor) bcrypt here instead of a really fast hash.

  • Since the slow hash is done on the client-side, the server load is not as high as for server-side slow hashing. (I'm assuming a quite high work factor for bcrypt.)

Here are my questions:

  • Is there already a protocol which works similar to this? (From the comments, this seems off-topic here. Feel free to mention it anyway if you happen to know one, but concentrate on the next question.)
  • Are there any weaknesses of this protocol idea compared to a usual server-side slow password hashing?
share|improve this question
    
I'm not totally sure whether this is good here or should be better on security.stackexchange.com. Comments? –  Paŭlo Ebermann Jul 14 '11 at 11:06
2  
I would say that your first question ("is there already such a protocol ?") is security.SE stuff, while your second question ("is there any weakness in this protocol ?") belongs to crypto.SE. –  Thomas Pornin Jul 14 '11 at 12:39
    
@Paŭlo Ebermann I'd go security.stack... –  woliveirajr Aug 3 '11 at 17:50
    
Is there a reason why you salt the second cheap hash? –  CodesInChaos May 12 '12 at 21:38
    
@CodeInChaos: I don't quite remember what I thought then inventing the protocol, but I suppose it was to avoid attacking the stored password table with a rainbow table or similar. I suppose it is not really necessary here, but can't hurt, either. –  Paŭlo Ebermann May 12 '12 at 22:17
add comment

3 Answers

up vote 14 down vote accepted

There exists something which is one step further than your idea. Look up SRP: this is a Password-Authenticated Key Exchange protocol; the two parties (client and server) who run the protocol end up with a newly generated shared key (which can be used to derive encryption and integrity-check keys), with mutual authentication with regards to a shared statically known secret which can be of relatively low entropy (say, a password).

In your system, this would mean that the password is first derived into the shared secret with something slow (bcrypt), and then use the result as the "password" in SRP. SRP has been designed so that the server stores only what amounts to a hash of the "password", not the password itself, so obtaining a copy of the server database does not allow an attacker to log in; it only makes him able to run an offline dictionary attack on the password, at which point the initial bcrypt hits him hard.

The beauty of PAKE protocols is that they are inherently immune to offline dictionary attacks from eavesdroppers: the protocol can be run "in the clear" and this still does not give a passive or even active attacker any way to learn enough to "try" passwords at his leisure. Only an attacker who hacks into the server may get such data, and even then he does not have the password (the password-derived-value-through-bcrypt, in the setup we envision here), just a hash thereof. So there is no need to establish a SSL/TLS tunnel beforehand. Even better, it is possible to use SRP as the initial handshake for a SSL/TLS tunnel; this is standard, and GnuTLS is an opensource implementation of that. A particular appeal of TLS-with-SRP is that client-server authentication is then mutual with regards to the password, which implies that there is no certificate whatsoever.

A possibly troublesome issue is that the number of iterations in bcrypt must be set so that it is slow (for the attacker) but still tolerable (on whatever machine bcrypt is to be executed). If you want bcrypt to run on the client, and also accommodate a variety of clients, some of which being possibly quite anemic (e.g. a 3 years old netbook, like mine: old mono-core Atom clocked at 800 MHz; also think about smartphones), then you have to tune the bcrypt iteration count accordingly. The patience of the average user being, let's say, somewhat limited, this prevents you from setting a bcrypt iteration count as high as you would like. On the other hand, you can muster 100% of the client CPU resources for that (client might be multitasking, but the user is unitask), which probably compensates much of that effect.

Summary: use bcrypt on the client, then use the result as "password" in TLS-with-SRP.

share|improve this answer
    
Thanks for the answer. I already thought that my idea can't be such new :-). –  Paŭlo Ebermann Jul 14 '11 at 13:14
    
Could we make the work factor user-definable, so the user can decide how much work to spend (and how long to wait on his typical devices) for each login, with according security gain? (Of course, with some sensible minimum value.) –  Paŭlo Ebermann Jul 14 '11 at 13:16
2  
@Paũlo: it can be made user-definable, but such information will be stored on the server, so it must be transferred to the client sufficiently early in the process -- which entails transmitting the user name first, so there will be an extra message, which can induce latency, or a modification of the TLS-with-SRP protocol, which is (on a general basis) a bad idea. I would recommend using the "sensible minimum" for every user, and hardcode it in the client. Also, this allows running the bcrypt-thingy before doing the network connection. –  Thomas Pornin Jul 14 '11 at 13:22
1  
Wouldn't we need the extra message anyway to provide the salt to the bcrypt (assuming we don't store it in the user's device in some cache - there we could also store the work factor)? Without salt (or with hardcoded salt), the attacker can use a rainbow table and only try the the images of bcrypt here. –  Paŭlo Ebermann Jul 14 '11 at 13:32
1  
@Paũlo: mmh... you are right. Unless you use the user name (and server address) as salt, something which I have previously advocated against, on the basis that it does not handle password change. So yeah, you are up for an extra initial message (and response) with the user name as request, and the salt and iteration count as response. –  Thomas Pornin Jul 14 '11 at 13:48
add comment

Server needs to store the username received from client. Its vulnerable to DOS attack. however, on (Optional: To hinder remote brute-forcing, maybe wait a small time before sending back the answer, and limit the number of parallel connections for each user/IP.) it's possible to prevent this attack, but it's not necessary that username and passwords sent separately.

share|improve this answer
    
The DOS attack danger is the same with the server-side slow hash calculations, isn't it? –  Paŭlo Ebermann Jul 14 '11 at 12:09
    
The separate sending of username and password is to allow user-specific salting (against rainbow tables/dictionaries to attack accounts on different servers at once). –  Paŭlo Ebermann Jul 14 '11 at 12:12
    
The server-side slow hash is NOT vulnerable to DOS if (wait a small time before sending back the answer, and limit the number of parallel connections for each user/IP.) but it's vulnerable to DDOS. –  ir01 Jul 14 '11 at 12:44
add comment

The problem with this is that for every login we also need to run this slow password hashing algorithm, which for remote logins could be a considerate CPU load on the login server if many people try this at the same time.

This is a non-problem. Yes, bcrypt is 'slow' - but that's compared to things like SHA, which are very, very fast! It should be possible to find a suitable work factor for your hashing that allows logins to complete quickly but would still throw a significant spanner in the works for anyone wanting to brute force your database. Remember - the number of hash operations required for breaking in is going to be much, much larger than normal operation of your site.

As for your idea, by doing the hashing client-side you are turning that hash into a password. If an attacker compromised your database, they would only need to break past your fast SHA-2 hash to find values such that SHA-2(value) = the hash stored in the database. They could then send that value as part of the login process, and merely claim they have that hash as a result of running the slow hash algorithm on the actual password.

However, the entire point of using something like bcrypt is to mitigate an attack where the attacker possesses your database - a protection you no longer have with your proposed scheme.

To reiterate: They do not need to retrieve the user's actual password, nor do they need to go through your bcrypt hashing process, in order to break into accounts - so yes, by doing that hashing client-side you would make it a lot easier to attack.

share|improve this answer
    
About the slowness: If I imagine the server having some millions of users, the time for all of them to log in once is about the same as the time to brute-force an average one of them (if they have not too good passwords), regardless of work factor. –  Paŭlo Ebermann Jul 14 '11 at 12:03
2  
About you are turning that hash into a password: yes. But this effective password space is large enough (assuming a sufficient hash output length) to make brute-forcing it infeasible. (Of course, this assumes that the second hash algorithm still is secure (e.g. with no preimage attack significantly better than brute-forcing), even if it is fast.) –  Paŭlo Ebermann Jul 14 '11 at 12:08
1  
On speed: Currently, you hash passwords so fast on login that it contributes zero to load. If you increase that to even adding 1% to overall server load, you will have made it orders of magnitude slower for attackers to break into accounts at the same time. It's a clear win. Hashing passwords is such a small, easy, and relatively infrequent thing for a web application to do that I absolutely refuse to believe any website needs the full speed of SHA-1 or MD5. –  ZoFreX Jul 14 '11 at 12:11
    
On turning the hash into a password: I don't see why it would be significantly harder to brute-force a SHA-1 hash given the constraints that the input must be a valid bcrypt hash. You still have the same probabilities of a collision, the same number of expected passwords to hash to see a result - you just place some arbitrary restrictions on the format of the input. –  ZoFreX Jul 14 '11 at 12:14
    
I was assuming that there is no easy (e.g. fast) way to see if a given string of right length is a bcrypt hash of a password or not. I.e. the fastest way to enumerate all valid bcrypt hashes would be to actually hash these passwords. –  Paŭlo Ebermann Jul 14 '11 at 12:27
show 5 more comments

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.