33

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?

gerrit
  • 1,829
  • 1
  • 17
  • 26
  • 9
    One other possible explanation is that when the password was entered several of the positions were stored individually and hashed (i.e. for a password of "password" the values ZZsZZZZZ and ZZZZZZrZ were also hashed which allows your example challenge question to be verified via hashing and not decrypting). But it does seem more likely that your postulate is correct (That they are stored with, at best, two way encryption) – Jeff Meden Jun 19 '15 at 16:01
  • 8
    @JeffMeden Yes but from the cryptographic perspective that's equivalent to "passwords are stored unhashed": the website operator has enough information to cheaply recover the original password, which means they are able to leak enough information for an attacker to do the same. So not much different to storing the password encrypted and hoping that only the database leaks and not the key(s). – RomanSt Jun 20 '15 at 00:40
  • 1
    So there's an existing question on this http://security.stackexchange.com/questions/4830/how-do-some-sites-e-g-online-banks-only-ask-for-specific-characters-from-a-pa/4835#4835 . One thing that the answers below haven't (AFAICS) covered is that it is possible to store passwords in a reversibly encrypted format securely, via the use of a Hardware Security Module (HSM), and this is relatively common practice in the banking industry (in the UK at least). – Rory McCune Jun 21 '15 at 11:34

6 Answers6

34

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.

Owen
  • 574
  • 5
  • 9
  • 4
    Even if we are talking the full Unicode space (which we almost certainly aren't), that's *still* only just over 1M possible code points per character. Even if the password is then, say, a known 30 characters long, that brings the number of hash operations needed to break the password down from, say, a modest 62^30 to a good 1M×30. That's a reduction by *46 orders of magnitude*. Even with an expensive hash, this turns an offline full recovery attack from completely infeasible to practically trivial for any determined attacker. A salt does not significantly raise the work factor in this case. – user Jun 20 '15 at 16:47
  • @MichaelKjörling: Most of Unicode is unmapped, and many (most?) of the mapped characters are private use. Those are not going to be in your password. Worse, the average password is entirely composed of ASCII, Latin-n for some n, or some other single Unicode block, and you have to assume dedicated attackers will be able to guess that information based on locale. At best, that gives you CJK to play with, which is still quite a lot, but what about the rest of the world? – Kevin Jun 21 '15 at 02:16
  • Whoa... I've just realized that most (if not all) banks in Poland use this login security. I always knew it was pretty bad to begin with (it makes logging in that much more annoying - I know my mother used to keep her password written down with numbers below it), but now I'm starting to get actually scared. :/ – Shaamaan Jun 21 '15 at 10:22
  • @Kevin I agree that most of Unicode would not be candidates for any given password, but my comment was meant to illustrate the *best* (for some definition of "best") case. The Unicode code space allows for a bit over 1M code points, hence that's the figure I used. The point was how much of a reduction of password security that is, not the exact number of possibilities to consider for each character position. It doesn't matter really even if the number of possible code points per character is 100x larger or smaller, because that *still* is only going to make a tiny dent in the conclusion. – user Jun 21 '15 at 10:54
  • I don't think this is necessarily bad news. This way of validating password is effective against phishing and key loggers. If the database is breached, however, you'll have bigger problems to worry about than unhashed passwords. Also, people shouldn't (and hopefully rarely) reuse their online banking password on other sites. – billc.cn Jun 22 '15 at 21:36
18

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.

Charlie Platt
  • 204
  • 1
  • 2
  • 17
    Time to switch banks then. – gerrit Jun 19 '15 at 15:59
  • 3
    @gerrit not always possible. Here in Italy, every single bank I've tried has **laughable** security practices _at best_. – o0'. Jun 19 '15 at 19:50
  • 2
    Doesn't that depend on their threat model? It means anyone who can steal their database has your password; on the other hand, it improves security against anyone who can intercept your login attempts. – user253751 Jun 21 '15 at 03:53
  • 2
    @Lohoris You think that's bad? Five years ago in Denmark one company was given a monopoly on authentication for all financial and governmental systems. All sites would load the same Java applet, which made it a ridiculously easy target for phishing. And if you were using it from a Linux system, it turns out that it would be impossible to log in if `/tmp` was mounted with the `noexec` option. – kasperd Jun 21 '15 at 09:32
  • `impossible to log in if /tmp was mounted with the noexec option.` I... that... what? How? Was it actually downloading a file to `/tmp` from the browser and executing it? – forest Dec 28 '17 at 11:31
8

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.

ztk
  • 2,247
  • 13
  • 22
4

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.

March Ho
  • 1,675
  • 1
  • 12
  • 15
  • (Removed the previous comment) Just one minor minor note: Of course they could have stored the passwords without any encryption as well. Still though, the more I consider this, the more reasonable it seems. Quite unorthodox for sure, but purely from a penetration point of view it seems quite interesting. Would require a better analysis to see whether it's worth it, but it definitely is a valid advantage. – David Mulder Jun 19 '15 at 21:26
3

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

  1. User chooses his/her password P. It consists of letters p1, p2, p3, ... pk.
  2. 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.
  3. The system will also generate N-1 32 bits' long random numbers R1, R2, ... R(N-1)
  4. 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).
  5. 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.

C. Authentication

The next part of the system is user authentication, which is very simple and fast.

  1. The system selects N positions in the password - i1, i2, ... iN.
  2. 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).
  3. 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.
  4. 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)] )
  5. 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)

Jordan Szubert
  • 131
  • 3
  • 2
    Welcome to Stack Exchange! Link-only answers are discouraged; they become useless when the link dies. For this reason, I've edited the relevant info from the link into your post. – S.L. Barth Jun 20 '15 at 07:09
  • I am not a cryptographer, but it seems that this is not significantly more difficult to crack than a system based solely on symmetric encryption, once the bank's server has been compromised. – March Ho Jun 20 '15 at 20:51
0

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 cg and 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 2000 and 2015).

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).

Hagen von Eitzen
  • 1,098
  • 8
  • 19