If authentication occurs by asking the user for the characters at certain positions in the password (such as: give the 3rd and 7th character in the password), does this imply that passwords are stored unhashed? Or are there safe hashing techniques where it is possible to verify the hash of a subset of the password against the hash of the entire password?
If you can verify the password by character, it significantly reduces the effective strength of the password. Rather than being exponentially stronger for each character it would only be incrementally stronger.
For example, say I have a password four characters long that is "ABCD". If I have to know the entire password to get it right, the possible permutations (say only upper, lower and numeric allowed for arguments sake) is 62^4, or 14.8M possible combinations. If on the other hand I can determine a success for each character by itself, I can find the password in 62 * 4 combinatons, or 248 operations using brute force.
So while it may or may not be possible to hash a password this way, doing so would effectively eliminate any security of doing so.
It is possible that the service not only computed the hash of the full password when it was created, but also hashed the 3rd and 7th character (or possibly every character) individually. That way, they technically wouldn't be storing the characters or the full password in plaintext. However this would be a terrible idea. A hash of a single character is essentially no better than plaintext since there are only perhaps 62 possible single character hashes per salt (if a salt is used).
Either way, if the service has the ability to recognize part of the password as opposed to only the full password it is bad news.
Any authentication which asks the user for details about the password indicates that the plaintext password is available to the system. This means they are unhashed, but may still be encrypted and protected by other means.
There are no techniques to verify the subset of a hashed password against the whole of the hashed password. This is actually one of the objectives of a hash function as it protects against guessing a password character by character.
As previous answers have already stated, there is no known technique to carry out a partial hash of a password and verify the string. The nature of unidirectional hash functions makes it impossible to verify if a password is similar to another, only that the passwords are identical. Therefore, it would imply that the bank has stored the passwords either using two-way encryption, by hashing the substrings, or (the horror!) as plaintext.
This technique actually has a number of benefits and drawbacks, contrary to the current opinions that this technique has no redeeming factors.
Compromise of bank passwords can take place in two ways, via hacking of the bank servers resulting in a hash leak, or via password compromise on the user's end (keyloggers, trojans, simple shoulder surfing, MITM attacks on SSH) etc.
Storing the passwords in a way that allows substrings to be retrieved allows a hacker who has gained access to the bank's database to easily obtain the plaintext passwords, even if they are extremely strong. If the bank used two-way encryption, a hacker who has gained access to the encrypted database would almost certainly be able to obtain the keys. If they hashed a selection of substrings instead, it would result in a case similar to the NTLM weak hashes which would make it easy to retrieve the plaintext passwords. The very small hash space of 3-5 characters (assuming a hash was used) would make reversal attempts trivial, even if a salt was used.
However, this must be balanced against alternative risks. A potential bank hacker who has gained access to only the victim's computer (and potentially also their 2-factor authentication token) would not be able to access the victim's bank account, since a different subset of characters from the password would be required.
Since the latter case of bank account security compromises are far more likely, it makes sense to a limited degree for banks to implement such hashing systems.
Seems that partial password need not be stored in plaintext-equivalent way. This scheme, based on Shamir secret sharing scheme might be useful: http://www.smartarchitects.co.uk/news/9/15/Partial-Passwords---How.html
A. Global Parameters
At the beginning, someone has to define global parameters of the system. Well, there is actually just one - how many letters will users have to select. Let us call the parameter N. The maximum length of password (L) is important only from the database point of view - you will need to store a 32b long number for each character.
B. adding New User
- User chooses his/her password P. It consists of letters p1, p2, p3, ... pk.
- The system will generate at least 32 bits' long secret key - K - unique for each user. 32 bits is enough if N is 3, for larger N (the number of letters users have to correctly select each time) you may want to increase the length of K.
- The system will also generate N-1 32 bits' long random numbers R1, R2, ... R(N-1)
- The next step is a computation of k points (k being the length of the password) on a polynomial: y=K+R1*x + R2*x^2 + ... + R(N-1)*x^(N-1), for x = 1, 2, ... k. Let us denote the results as y1, y2, ..., y(N-1).
- Values s1=(y1-p1), s2=(y2-p2), ... sk=(yk-pk) is stored in the database. Each number takes 32 bits. One will also need to store K, or the hash of K.
The next part of the system is user authentication, which is very simple and fast.
- The system selects N positions in the password - i1, i2, ... iN.
- A user selects N letters from her/his password at specified positions so that we have pairs (p'1, i1), (p'2, i2), ..., (p'N, iN).
- The system recovers yi values for indices i selected in step 1 - simply just adding stored values (see step 5 above) to values p'i entered by the users.
- Now we have to solve the polynomial equation to obtain K'. The equation for that looks horribly but it is quick to compute and can even be partially pre-computed as it uses indices (positions of letters): K' = \sum_i [ yi * [ (\PI_j (j) ) / (\PI_j (i-j)) ] ], where i and j run over i1, i2, ..., iN (step 1), and j skips the actual selected i. Example: let's say that user selected 2nd, 3rd, and 4th letter, the solution will be: K'=y2*( 3*4/[(2-3)(2-4)] )+y3( 2*4/[(3-2)(3-4)] ) + y4( 2*3/[(4-2)*(4-3)] )
- The last step is to compare K and K'. If they are equal, user entered correct values and is logged in.
One note here - the secret is not K, but values yi reconstructed when user enters his/her letters.
(I'm not a security expert and I don't know if this scheme makes sense)
If they always use the 3rd and 7th character for this, they might save only hases of the password and this excerpt. Essentially, this would split your full-length password
abcdefghijklm into two shorter passwords
abdefhijklm. Of these, the two character password offers practically no security. Additionally, the remaining password is not only shortened by two characters, it is also susceptible to "crib" attack: Unless the original password was completely random, the easily guessed characters give a nice hint towards what we are looking for (e.g., among all passwords in use with seventh character
2 I bet there is a significant proportion that has length exactly 10 and ends in something betwen
At any rate, if they had considered the security implications thoroughly enough to store the password "excerpts" securely they should have noticed that the excerpt is a great risk. This suggests that such considerations were not made, which again suggests that they store the password in cleartext (aka. Occam's razor).