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.

This is a classical scenario: For our web based authentication platform we have a username and a password field. User enters these values and presses Log In. The browser gathers the user data, calculates a digest of the password and sends everything to the server side. We don't want to send the password over the network, it might not be safe.

On the server side we have the database which stores the hashes for passwords in a table (among other stuff).

Initially we were using MD5 for this purpose but after a while we threw out the idea as being the most over hacked message digest with large available rainbow tables, so once someone captures the packet they easily can guess the password (if it's a weak one).

Now we have switched to SHA1 for calculating the digest... There remains only one problem. The initial database layout was to use 32 characters for the message digest of the password (the length of the MD5 hex string) ... however the SHA1 is 40 characters long (when transformed to hex bytes). The bigger problem is that we don't want to increase the length of the message digest table's column (nor the length of the used message digest itself) since the digest value is used at some stages in a few algorithms and it relies on the fact that it has 32 characters.

So someone from the architecture team came up with the idea: Let's add an extra validation step to the login procedure and ask a 4 digit long pin from the user. And when we have this PIN we simply remove two times the characters found at the given PIN position from the SHA1 digest of the password (from the beginning and from the end), and this way we end up with a 32 character long digest, which cannot be traced back to the password since it hasn't got all the required information.

There is just only one thing which bothers us: what are the theoretical chances that two different passwords which give two different hashes after applying two different character removal algorithms (based on two different PINs) will give the same result.

And since we have no cryptanalyst nor cryptographer in our team we have to turn to the community :) Thank you for helping.

share|improve this question
7  
Just send the password in plaintext (over HTTPS/SSL/TLS) to the server and use a proper password hash on the server. It's the job of TLS to protect data in transit, don't try to invent your own crappy hashing scheme instead. –  CodesInChaos Aug 20 at 7:34
5  
Unsalted SHA-1 is just as crappy a password hash as MD5. –  CodesInChaos Aug 20 at 7:35
4  
"There is just only one thing which bothers us": hire a good security consultant and given your scheme, there will be a lot more bothering you. –  owlstead Aug 20 at 9:21
2  
"the digest value is used at some stages in a few algorithms", but why? if you need a 32 char psuedo random per user then create a unique ID per user, that way you will be safe from users changing their password screwing with those algorithms –  ratchet freak Aug 20 at 10:11
1  
Collision resistance is not what you should worry about for password hashes, preimage resistance is the point. –  Paŭlo Ebermann Aug 20 at 22:07

2 Answers 2

up vote 12 down vote accepted

Short answer: don't. Use a password hash like PBKDF2, scrypt or bcrypt.

Also, if at all possible, use a library that takes care of the low level stuff like password database for you. E.g. passlib might work if you use Python. I'm sorry if that sounds blunt, but that's how it is.

To answer your actual questions:

There is just only one thing which bothers us: what are the theoretical chances that two different passwords which give two different hashes after applying two different character removal algorithms (based on two different PINs) will give the same result.

The chances that two different password give the same final hashes are the same regardless of whether the PINs are different or not. The chance is $2^{-n}$ for an $n$-bit final hash. I.e. $2^{-128}$ for a 128-bit hash.

(To see why the PINs don't matter, consider the output hash as a random number. That's the best you can do. Different PINs would only matter if the password hashes are equal.)

You can instead just truncate the hash, including the PIN in the string to be hashed together with the password. Also, if you went this way, you might as well use SHA-256 which is believed secure, instead of SHA-1 which has theoretical attacks that truncation might make practical.


Again, you should not use just a normal hash to protect passwords. Further, your idea of hashing the password in the client is insecure:

The browser gathers the user data, calculates a digest of the password and sends everything to the server side. We don't want to send the password over the network, it might not be safe.

This is a good instinct, but it doesn't work as you described it. Anyone who steals your password database will be able to use a hash to log in if you don't hash on the server side. (Your site/app may ask for a password, but the attacker doesn't have to use it.)

You can hash both on the client and the server, although that only protects the plaintext password in case the encryption is broken. That's nice for users who reuse passwords, but will not protect their accounts on your system any more than just hashing on the server.

(Unless the connection where you send the plaintext password over is encrypted, an eavesdropper can always just get the password/hash and log in!)


One more additional suggestion: if you really are limited to 32 characters in the password database, consider using base 64 encoding for the hashes if at all possible. That allows you to store 192 bits of the password hash. Binary would be even better, allowing the full 256 bits of scrypt or PBKDF2 with SHA-256.

share|improve this answer
1  
or even basE91 $\;$ –  Ricky Demer Aug 20 at 8:27

Sending a hashed password adds no value. Consider this, what the client sends after the hash is what the server considers as a password. Additionally; you are leaking an implementation detail on the client. SSL/TLS already ensure channel security; and then using a slow password hashing algorithm has already been proven to work. Precomputing the hash does not prevent an attacker from carrying out a replay attack. The advantage of using BCrypt or SCrypt on the server side on the other hand allows you to increase the complexity for new passwords without breaking backward compatibility with existing passwords.

share|improve this answer
2  
It does have some value: you may be able to distribute the work of a slow password hash on the clients and use a fast hash on the server. –  otus Aug 20 at 12:54
    
@otus any hashing that happens on the client is useless. It makes the hashing susceptible to replay attacks. The point of a employing a slow hashing algorithm is to make a brute force attack unfeasible. You also need a constant time hashing algorithm so that clients can not determine the correct strings in a password based on the time it takes to validate on server. –  Bugsta Aug 20 at 15:41
1  
I meant hashing on both client and server. That is similar as hashing only on the server, except the hash becomes the password. With a strong client-side hash the "password" is closer to a random string, so the server can use e.g. HKDF. –  otus Aug 20 at 15:46
    
@otus but the hash is still susceptible to a replay attack. As an attacker I don't need to know your password as I can send the hash to the server to impersonate you. –  Bugsta Aug 20 at 15:47
    
Yes, if you see the hash, which you shouldn't because of the encryption. –  otus Aug 20 at 15:49

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.