8

I was trying to design an authentication system that would make it much harder to guess a password via brute force, and reduce the risk to a user if the hashed password was stolen through a snooping based attack. Also, since my client side code will be easily view-able by those wishing to see it (it is in an interpreted language, however, I do encrypt and obfuscate the distributed client), I wanted to be able to prevent an attacker looking at the source to impersonate a user easily. Security through obscurity is NOT security.

Here is the algorithm I thought up. I wanted to submit it to public examination because cryptography algorithms always work better when subjected to as many opinions as possible, IMHO.


(All hashes are computed with the SHA-2 and a 512 bit block size. This algorithm is not known to be vulnerable to any collision or pre-image attacks, and is a secure cryptographic hash function.)

[CLIENT SIDE]

  1. The user provides an any-character/symbol/number username less than 30 characters and an any-character/symbol/number password that is between 8 and 200 characters long.

  2. The username is hashed.

  3. The hash of the username is added onto the end of the users password as a salt.

  4. The salted password is hashed, and then that hash is hashed.

  5. The current date and time are requested from the authentication server, and are then hashed.

  6. The hash of the timestamp is added to the username/password hash as what I'll call a 'time dependent salt'. This last combination is then hashed to produce the final authentication hash.

  7. The username, the timestamped hash, the salted password, and the time used to generate the time dependent salt are sent to the server via a TLS/SSL connection.

[SERVER SIDE]

  1. The server verifies that the recieved timestamp is in the last minute. If it is not the server will indicate that the authentication failed.

  2. The server hashes the username/salted password and compares that against the stored database salted/password hash. If they do not match the authentication fails. (To clarify, the server has a hash of salted password hash. It verifies that against a hash of the salted password hash given by the client.)

  3. The server calculates a hash of the timestamp sent by the client.

  4. The server hashes together the generated timestamp hash and the salted password hash to form the authentication hash.

  5. It compares the authentication hash it produced with the authentication hash sent by the client. If they are the same, it reports authentication. Otherwise it reports a failure to authenticate.


If I am correct, I believe this authentication scheme does indeed make brute forcing a password nearly impossible, and makes a password stolen through snooping only useful for a full minute.

However, what it does not protect against, as I think it is impossible, is passwords stolen from the user as they are input into the client. Spyware would be able to steal the actual username and password.

EDIT 1 :: Fixed the authentication process so that the server does not store the salted password hash, only a hash of that value. This prevents an attacker with access to the database from knowing the original password. The reason this has to be done is the hashed value of the salted password hash is the password from the server's point of view. Storing the salted password hash in the database would be the same as storing all user's passwords in plaintext.

EDIT 2 :: Fixed the scheme so that the authentication relies on the server's time, not the client's.

EDIT 3 :: Made the password length less restrictive, but kept it reasonable.

7
  • 2
    Whomever -1 this, may I ask why? Or at least an explaination.
    – Josh
    Aug 2, 2011 at 12:23
  • You got -1'ed? That question is valid.
    – ixe013
    Aug 2, 2011 at 14:03
  • I flagged it for the moderator to move.
    – Josh
    Aug 2, 2011 at 15:09
  • Why limit the length of the user's password to less than 50 characters?
    – Steve
    Aug 2, 2011 at 15:57
  • I don't have to I guess. But doesn't >50 characters seem ridiculous?
    – Josh
    Aug 2, 2011 at 16:51

8 Answers 8

11

If it goes through SSL/TLS, which ensures server authentication (the client is sure that it is talking to the right server) and confidentiality and integrity of the transmitted data, then there is no snooping to fear -- or, rather, if snooping occurs, then it must be right on the client or the server, at which point you have bigger problems (if an attacker can read sent data on the client directly, then he can probably log keystrokes as well).

If we consider your password-hashing scheme by itself (i.e. without taking SSL/TLS into account), then it has a few problems:

  • You include your "salt" by simply appending it. There is no proof that this will not cause problems with SHA-512. SHA-512 is a Merkle-Damgård hash function, which means that it is a bit less than ideal; it has some structure (e.g. the "length extension attack"). This does not mean that SHA-512 is broken; only that you handle it as if it was a Random Oracle whereas it is "just" resistant to collisions and preimages.
  • You do not iterate through enough invocations of the hash function. This makes the process too fast: an attacker observing the resulting hash may "try" potential passwords, and will be able to do so at high speed (millions of passwords per second, with a simple PC). This is called a "dictionary attack" and it tends to work because users are bad at choosing and remembering good passwords.
  • You use SHA-512 instead of SHA-256. You talk about an "interpreted language": if that is Javascript, then that language is grossly inefficient with 64-bit operations (SHA-512 is full of them), so using SHA-512 instead of SHA-256 severely limits the number of iterations you could perform on the client system; this correspondingly boosts efficiency of the dictionary attack.

Usual recommendations for password hashing are PBKDF2, bcrypt and scrypt (my personal favorite being bcrypt; PBKDF2 was not initially designed for that, and scrypt is still too new to be generally trusted).

There are authentication protocols which are, by design, immune to offline dictionary attacks: they are called Password-Authenticated Key Exchange. PAKE protocols allow for mutual password-based authentication between client and server, in such a way that a snooping attacker, or even an attacker who impersonates the client or the server, cannot learn anything which would allow him to "try passwords" on his own systems. The attacker is restricted to online dictionary attacks: each password guess involves interaction with either the client or the server. The most known PAKE protocol is SRP which has been integrated into SSL/TLS. With TLS+SRP, you get a secure data tunnel in which the server and the client are mutually authenticated with regards to the password, without any certificate at all (that's the most brilliant part of it). As a bonus, the server doesn't need to store the password in cleartext, only a value derived from it (as if it was hashed) so an attacker dumping the server database does not learn the passwords (he does learn enough to perform an offline dictionary attack, though). GnuTLS is a library implementing SSL/TLS with SRP support.

2
  • I think I'll mark this as an answer. Your post brings up several good points, and I think that relying on TLS with properly hashed passwords should be more than appropriate.
    – Josh
    Aug 2, 2011 at 17:46
  • Re "if that is Javascript, then that language is grossly inefficient with 64-bit operations" is correct, so if you want good crypto in JS be sure to take a look at David Dahl's DOMCrypt API proposal for exposing native crypto support to JS in browsers. Aug 3, 2011 at 17:01
9

At a glance this sounds like anybody who gets your password table can login as the user. He simply skips client steps 1-4 and substitutes the hash he obtained from the db. So your scheme is very weak in this scenario.

Why don't you just use standard password hashing? Most interception attacks are already prevented if you use SSL/TLS and validate the fingerprint of the server against a whitelist.

Or if you're paranoid use a good implementation of SRP. But don't implement it itself. It's very easy to produce a bad implementation of it that appears to work but is insecure.

4
  • That is a good point about the database access. That totally defeats one of the main purposes of hashing the passwords. Good catch. I'll make an edit to adjust for that vulnerability. And it makes me nervous to just completely rely on one security tool, like TLS. It goes against the idea of robust security.
    – Josh
    Aug 2, 2011 at 14:29
  • 6
    Inventing your own protocols goes against the idea of robust security too.
    – CodeInChaos
    Aug 2, 2011 at 14:30
  • 1
    No, inventing your own mathematically bound cryptological concept is an insane idea and not secure. If I was asking 'Is this hashing algorithm I invented secure?' it would be a problem. but using pre-establish recognized cryptological paths in a configuration is the definition of how secure systems are organized.
    – Josh
    Aug 2, 2011 at 14:43
  • 3
    Inventing, modifying, tweaking, hacking, extending, optimizing, or just about anything else you can do to a cryptographic protocol, hash, algorithm, PRNG, key agreement, or cryptographic technique is a very bad idea. Do not use your work to protect anything of value. Security is a vast and difficult problem. Many experienced, knowledgeable, and careful security practitioners have made painful mistakes. The prime example is the recent RSA breach. You wouldn't build a car using someone's proven engine and your experimental brake system. Don't invent security protocols.
    – this.josh
    Aug 3, 2011 at 0:51
5

I fail to see what you're trying to accomplish with this scheme, that cannot be done by a well-known and proven method already.

First off, you cannot depend on the client time. Many people don't sync their clock, and you'd have to take time zones into account.

Second, the attacker can just go through the auth scheme as many times as he pleases to brute-force as pointed out. You could add lock-out functionality, but you can add that to any scheme.

Third, your scheme prevents replaying of the authentication POST, but using the time, which is a bad idea due to the synchronization issues. A better idea would be challenge-response, a widely accepted mechanism for freshness guarantee.

If you would include a challenge token in the hash, an intercepted hash would not even provide access for a minute: it could only be used once.

I recommend you implement two-factor auth if you're that concerned about authentication and don't want to trust SSL. You can use challenge-response in combination with salted and stretched hashes to prevent replay and offline cracking.

2
  • What if the time was maintained exclusively by requests to the server? As in the client asked the server for the current universal time in a non-authenticated request? - Also, brute forcing this password scheme would be unfeasible. The maximum time for the minimum length password is 82832 years to crack (at 2,800,000,000 passwords a second GPU calculation) or the most is much larger than 5.075167570080647e+28 years. (Assuming a single computer on those calculations btw.)
    – Josh
    Aug 2, 2011 at 16:48
  • Oh, I forgot to add that because the hashes introduce a cpu-bound constraint to calculating valid passwords, those numbers should be even larger.
    – Josh
    Aug 2, 2011 at 16:58
5

I'll have to join those who say "stop trying to design your own crypto system". You aren't smart enough. I'm not smart enough. If you haven't spent a decade working on the problem, you can't do it.

Why have any maximum lengths at all? You are always going to hash it anyway. Let them have a million character password if they want, it's not going to matter, because you only store the 32bytes of the final hash, not the million bytes of the password.

Some people like pass phrases, which could be a long sentence of 100 characters. I can type a 100 character password using a phrase faster than a complicated password with special characters.

Don't base the salt on the username. Use completely random information, and generate a new salt every time the user changes their password. Otherwise, a hacker could precompute a large dictionary for a user, and repeatedly hack the account even when the user changes the password.

You seem to think in terms of choosing the most secure hash function possible. The reality is that SHA-512 is going to be no more secure than MD5 in such applications, especially if you use key strengthening. Repeating MD5 a thousand times is a lot MORE secure than SHA-512. Security is a tradeoff -- choose the hash algorithm which is most easily done on the client, which is likely SHA-1 or SHA-256, not the "most secure" possible.

SSL already has replay protection. Why complicate your authentication system by doing your own? Although, because of SSL, you are guaranteed that the clocks aren't too far off (otherwise, SSL would fail).

Even if you do everything wrong, such as using a simple MD5 hash, hackers won't be able to crack more than 50% of the passwords on your site. Conversely, if you do everything right, hackers will still be able to crack 20% of the passwords through a slightly mutated dictionary hack. No matter what you do, you cannot stop some passwords from being cracked if the database is compromised. Instead, your goal should be to do the standard things to minimize hacks, such as PBKDF2 with salts and key strengthening.

In addition, no matter how much time you spend on this, you are likely to make other common mistakes, like send session cookies in cleartext.

Ultimately, what I'm trying to say is: stop trying to design your own crypto system. You repeat the stupid meme "obscurity is not security" without really understanding it, yet you refuse to follow the common advice of stop trying to design your own crypto system.

3

I dont see how this would make brute forcing any harder from the client side. I could just automate passing your application a list of username/passwords until one works. If I gained access to your database, it would make brute forcing passwords with rainbow tables nearly impossible (if that is what you mean you are trying to protect against). But you will still have to store the salt with the username + hashed password (and presumably I could reverse engineer your hashing scheme), so I could generate a rainbow table for one entry in your database, if I was targeting a specific user, or only wanted one account.

As for preventing client side brute forcing, you could put a time lock on your login after a failed attempt. After each failed attempt the user has to wait 2^(failed attempts) seconds, before being able to attempt another login. This would have to be enforced client and server side. Also be sure to think about how a malicious user could use your scheme as a DoS for another user.

2
  • That is a good point, the client could be used as part of the brute force. However, wouldn't a server-side lockout be enough?
    – Josh
    Aug 2, 2011 at 13:41
  • lockout itself helps... but lockout based on what ? the IP ? the username ? depending on the way you implement it can discomfort legititmate users
    – Yahia
    Aug 2, 2011 at 14:10
2

I don't see it mentioned anywhere else, so I'll mention it here: Your salt isn't particularly secure. The (sole) point of a salt is to make precomputation attacks like rainbow tables impractical, and that's most effectively achieved if there's no way to guess the salt, and it has a wide range of possible values.

By using the username, you ensure that the same user/password combination will always have the same hash. Because there's a limited set of common usernames, an attacker can still precompute hashes for those usernames. You've multiplied the effort required by the number of common usernames, but that's not intractable. Using a random salt, as is standard practice, introduces a much larger multiplier.

Finally, I'll add one extra plug for the "don't invent your own cryptosystems" brigade. There already exist well tested systems that do what you're trying to do, as Thomas's excellent answer illustrates. Use one of them, don't invent your own.

1

It seems like you've missed the point of hashing a password. The point of hashing a password is as follows:

1) The server only stores the hashed password.

2) The user must provide the server with the unhashed password.

3) Thus someone who steals the password database from the server still doesn't know what to give the server unless he brute forces the password.

You've done this:

1) The server only stores the hashed password.

2) The user provides the server with the hashed password.

3) Thus someone who steals the password database from the server can impersonate any user no matter how good their password.

For purposes of evaluating the server-client algorithm, the "password" is the minimum information necessary to successfully authenticate to the server. In the case of your algorithm, the "password" is thus the hash of the hash created in step 4, and that is precisely what is stored on the server. So you are storing passwords unhashed/unencrypted. That's not good.

0

Brute forcing seems nearly impossible indeed, fastest way for a work around is a tcp sniffer to show the data send to the server (hashed username, password and datetime) and use this in a new request to the server.

If your server checks the datestamp from the client to check if it's not "older" then 1 minute, your client will need to authenticate every minute. A tcp sniffer can still be used to detect this.

To avoid this SSL might be a solution.

5
  • The datetime is hashed into the final password, so a sniffed access of the password would only grant a malicious user a password that works for whatever remains of the minute they stole it in. And this is over SSL, I just wanted to make sure that the data sent doesn't rely on the security of SSL alone to insure that sniffing isn't being performed. Now the point you bring up about re-authentication per minute is interesting. However, I plan to require an authentication hash for each server request, so the client only needs to authenticate per request, not per minute.
    – Josh
    Aug 2, 2011 at 12:17
  • In your original post, you never specified SSL was out of the question, besides, I can't think of another method to avoid tcp sniffing besides encrypting data, maybe if you include machine specific data like computer name / or ip so when the first authentication request comes, you store the ip, every next request you can match the senders ip with the stored one. Faking tcp packets is harder then just reading data from them and reusing that data.
    – Thomas
    Aug 2, 2011 at 12:35
  • "...are sent to the server via a TLS/SSL connection".
    – Josh
    Aug 2, 2011 at 12:38
  • You're right, I missed that line
    – Thomas
    Aug 2, 2011 at 12:45
  • Brute forcing is not impossible. One can simply exhaustively try possible passwords, consecutively attempting to log in to the server. (Or, if one records the password hash, one can mount offline dictionary search.)
    – D.W.
    Aug 3, 2011 at 7:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .