There is a system that, on a login form, presents about 40 boxes for password letters (to hide password's actual length), and only random ones (the same amount each time) are editable. Explanation is - to secure me from keyloggers. Seems legit. But does it means my password is kept in plain text? Or is there any known hash algorithm that would permit this?
Note: I'm not asking if it is a good or bad practice, I ask about possibility / feasibility / method of hashing.
No - there's no practical way to hash your password in this case.
For the website to work this way, the hash would have to allow you to verify that a 5-character subset of the password matches a certain value. That means you could brute force those 5 characters on their own, which is readily practical, and once you know 5 characters, it's easy to brute force the rest. This is somewhat similar to the weakness of LANMAN passwords.
Partial passwords do have security benefits, especially against key loggers. Banking apps sometimes have a normal password that is hashed on the server, and an additional authentication code, which you only enter partially, and is NOT hashed on the server. This is considered completely acceptable, but becoming less common as multi-factor authentication is a better solution.
In this particular case, it is not clear-cut that this is a bad idea. You need to weigh the risk of server compromise against the risk of client-side key loggers. In fact, it is the client that is at greater risk. So despite going against normal best practice, this website is not so dumb after all.
As others have stated, any attempt to solve this problem with hashing algorithms is doomed to failure.
However, I think it's worth talking about how ING probably solve this. (Disclaimer: I've never worked for ING, but I have worked for other large banks).
It's likely that ING store your password in a Hardware Security Module. This is a tamper-resistant piece of hardware, which is designed so that not even the operator of the system can extract your password hashes. Internally, it probably stores your password in plaintext (or something near plaintext), but only communicates with the outside world via "please enter characters x, y and z" operations, and limits the number of attempts permitted.
In this scenario, the security of your password depends on the HSM being tamper resistant. There have been published attacks on HSMs, but the attack surface is reduced, compared to hashes stored in an RDBMS.
One way this could be implemented is to store a hundred or so of the hashes of partial passwords. Each time the user logs in with partial password, it will be marked as used. The list of hashes can be regenerated every time you need to enter a full password.
This scheme does weaken security against brute force or cryptanalysis, but it can protect from key logger if you often have to login from untrusted machines.
I'd seen this scheme used on a travel money card, as travelers may often need to use the account from public computers. For normal banking though, I think this just weakens security. If your regular, personal computer is infected a key logger, it'll just take a few logins to collect the full password from the partial passwords.
To strengthen this scheme from cryptanalysis and brute force attack, the partial passwords would need to be stored with a very slow hash, like PBKDF2 with lots of rounds. And to hamper the attacker's ability to brute force the hashes in parallel all at once, you need to force the partial password to be used in the specific order they were created. For example, using the n'th partial password to encrypt the number list and the salt for the n+1'th partial password would force the attacker to solve the n'th partial password before they can start work on the n+1'th.
F E D, B A C, F A C, and D A C, you won't know whether my password is FEEDBACK, BOLDFACED, or FRIEDBACON. The combinations F E B and E D A eliminate 1 of them, and using I, K, or N eliminate 2, but of course those are just 3 possible passwords. I think it would take many, many logins for a keylogger alone to assemble the full password.
Commented
Sep 25, 2015 at 17:41
Yes - It is possible they simply hash all the combinations they are going to show you.
Although I would think they have not implemented this and are storing your password, likely encrypted, but not hashed.
A better combo of security using this method while being mindful of storage space:
This way storage space is kept reasonable. And your unhashed password should be in a more secure layer of the system.
It might not be hashed but it might be stored encrypted. Theoretically they could have used Threshold Scheme with allowed ASCII characters as keys then check if the result fits the result. This way (theoreticaly) you should not need to store a password only a solution.
PS. For example see http://programmingpraxis.com/2011/06/17/adi-shamirs-threshold-scheme/
Suppose the password might be 40 characters long. Suppose the characters can be interpreted as numbers c_1,c_2, ... c_40 of some suitable finite field F (Galois Field). Also suppose F has at least 40 elements.
Suppose we compute the interpolation polynomial p for 40 predefined none zero elements of F such that p(a_j) == c_j. We now store 35 coefficients of this polynomial plus a (salted) hash of the other 5.
Whenever the user gives us 5 of the characters we can leverage the known 35 coefficients to recover the missing 5 coefficients and then compute the hash. If any the 5 characters is wrong we will end up with a different polynomial and thus a different hash. So you might want to store the hash in some dedicated hardware security module as James_plc already pointed out.
So yes, this is possible. However if your secure store gets compromised it is at least as simple to crack as brute forcing a 5 letter password.
For other algorithms in this direction you might want to learn more about secret sharing.
Does it means my password is kept in plain text?
It's very likely that it is either in plain text or encrypted, but it's not certain.
For example, when you initially submit your password they could hash and save different 5-character combinations of your password and the character-indexes they apply to.
However, anyone who gains access to that information and the hashing algorithm could easily crack the 5-character hashes and re-assemble them to get your original password, so even if it is hashed it is a weak model.
I suppose you could store a list of hashes of all combinations of any X characters, where X is the number of characters you need to provide.
This wouldn't be a very strong hash though if the rest of the hash was formed of known characters. It would be possible to derive the rest of the junk characters from a user salt or derived in some fashion from the X characters provided, but that's still not the strongest hash.
I can't see why the authentication algorithm couldn't store all combinations of your password substrings as hashes against the ordered list of the character positions, so if your password was:
password
then there would be a table of (key, hash) where the keys were e.g.
'1' for first letter only '1,2' for first and second letter only '4,5,6' for fourth, fifth and six letters only
and store against those keys the hash of a string of the letters indicated, so against
'4,5,6' would be the hash('swo') from the example password.
The problem with this of course is that reversing the hashes would be simple unless they were salted with a per user salt, and even then it would be relatively simple to brute force the hashes of short sequences for obvious reasons if the sale were compromised (keeping the salt secret would be a solution to this).
Not sure how else they'd do it though...
Interesting question.
The answer is that security-wise it is a bad idea, but that it is technically possible that it is hashed.
If it is a random subset of your full password you are entering(like first, second, fifth, sixth, and last characters one time, and a different random selection the next time) you could accomplish this by (on initial save)breaking the password into predetermined subsets and then hashing.
Essentially this is just a fancy way to have users enter in multiple passwords without knowing that is what they are doing. The user then knows which password to enter based on which boxes are available.
While there are things you could do to offset it(enforcing much longer initial passwords, strict 3 login attempts/day, increasing the number of multiple-passwords saved and switching to a new one after every login attempt and not allowing repetition until a successful login, etc), this would in general make your passwords shorter(in your case 5 characters) and therefore weaker.
As an aside, the protection you would get from keyloggers in any case would be minimal. It would just require the keylogger to actually look at several of your logins and figure out what your full password is. Better key logging security would be to use two factor authentication, which doesn't have to be complicated or expensive. When the user logs in just present them with a code that they can write down and enter in to login next time.
yes It reminds me of the zero knowledge proof protocol. The password cannot be intercepted because it is never transmitted or even fully entered by the user. (You cannot learn the password from the protocol.) But the secret should be strong enough. If you ask one character then of course after you have seen each position you know the password. The same holds for hashing. If the hash is weak it can be broken.
Edit: I think the hashing in this case is not a md5 hash or similar, in this case with the hash is meant the secret that contains the password. In zero knowledge documentation there is often a colored graph or a large polynomial. I don't recall the details.
Maybe think of it as prime factorization. Suppose you have a list of primes and store (Product : i : p[i]^i) (e.g. 504) in the database and I ask you the 3rd prime factor... in case you answer 2 you can easily check it's the third number...as 504 == 7*3*3*2*2*2 now move to large prime numbers like in strong encryption.
