69

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?

Screenshot

Note: I'm not asking if it is a good or bad practice, I ask about possibility / feasibility / method of hashing.

marked as duplicate by Xander, RoraΖ, Iszi, user45139, Neil Smithline Sep 28 '15 at 18:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

11 Answers 11

62

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.

  • Comments are not for extended discussion; this conversation has been moved to chat. – Rory Alsop Sep 27 '15 at 15:33
  • You do realize that to prove the answer is no you must prove it mathematically? – BAR Sep 27 '15 at 16:52
  • 1
    Keep in mind that weighing the risk of server vs. client compromise doesn't just mean comparing the chances, it also means comparing the consequences. Server means all user data is at risk, client means only the affected users' data is. (Which may or may not still lead you to the same conclusion.) – hvd Sep 27 '15 at 20:21
  • @hvd, also compare the numbers. Numbers of clients vs numbers of servers. – Paul Draper Sep 28 '15 at 1:59
53

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.

  • 1
    Interesting point! Always good to remind people that there's more than one way to skin a cat. – Jesse K Sep 25 '15 at 14:58
  • 5
    It may be encrypted with a random key, and the key encrypted with a public key. Then when it needs to be checked, the five characters, plus the encrypted password and the encrypted key are passed to the HSM which decrypts the password and performs the check. That way the storage doesn't have to be inside the HSM – Ben Sep 25 '15 at 15:14
  • 2
    Do you have a link to an HSM that performs this technology? I've never heard about an HSM doing this. – Neil Smithline Sep 28 '15 at 18:52
13

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.

  • 1
    I would think a keylogger wouldn't be enough, since it won't know the absolute positions of the characters. A simplified example: if the system asks for 3 characters, and your keylogger records the following entries: 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. – Dan Henderson Sep 25 '15 at 17:41
9

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:

  1. Encrypt the plaintext password and place in a sort of cold-storage.
  2. Periodically decrypt the password to create new combos and hash these.

This way storage space is kept reasonable. And your unhashed password should be in a more secure layer of the system.

5

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/

4

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.

2

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.

2

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.

1

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.

  • 10
    This would be a disaster. You'd have to store loads of hashes, each one of which would be readily brute force-able. The answer to the question is no. – paj28 Sep 23 '15 at 10:33
  • @paj28 Why do you say the answer is no? It seems to me that it should be possible to construct an irreversible function whose value is zero at a chosen set of values, each of which corresponds to getting five characters in the password. – David Schwartz Sep 23 '15 at 10:39
  • 7
    @DavidSchwartz Even if that were proved to be possible, it would only solve one of the two problems paj28 alluded too. You no longer have to store loads of hashes, but it's still readily brute-force-able: Suppose an attacker wants to crack the password, and has access to the stored data. First she tries to brute force the first 5 characters - this is possible, since the stored data is sufficient to validate her guesses, and easy, since there's at most 40 bits of entropy, probably less. Then she tries to brute force the next 5 characters. She continues in this fashion until she's cracked it. – James_pic Sep 23 '15 at 12:09
  • 3
    @DavidScholefield salts are normally stored right next to the password hashes to allow verification. So you should not assume the salt is secret if someone is trying to crack the hash. – otus Sep 23 '15 at 15:05
  • 1
    @DavidSchwartz I'd hardly call ruling out 99.9999% of passwords "little help". And it's still possible that more sophisticated schemes will succeed. Suppose the attacker has a candidate for the first 5 characters of the password. She can now take a guess at character 6, and check her guess using combinations of the first 5. If she finds a match, she now has 6 characters, and can guess at 7. If not, she backtracks. Perhaps a clever hashing algorithm could prevent this somehow, but no concrete algorithm has been proposed yet. – James_pic Sep 23 '15 at 19:53
1

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.

-1

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.

  • OK, so how to test a password if all you have is a hash and some letters from password? Are you saying yes because you know of a way to do it, or merely because it wasn't disproved yet? – Mołot Sep 23 '15 at 21:29
  • 1
    “You cannot learn the password from the protocol.” You absolutely can, no matter which part of the protocol you’re referring to. – Ry- Sep 24 '15 at 4:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.