10

Technology Review's Why Autocorrect for Passwords is a Great Idea says:

New research shows those frustrations could be avoided using the same approach used to fix typos in text messages and documents: autocorrect.

“This is, in our view, a pretty big deal,” says Ari Juels, a professor at the Jacobs Technion-Cornell Institute at Cornell Tech, in New York City. “Websites should be changing their password policies to make users’ lives easier. The security degradation is pretty small.”

The article also cites the paper pASSWORD tYPOS and How to Correct Them Securely, which starts with:

We provide the first treatment of typo-tolerant password authentication for arbitrary user-selected passwords.

While they say that it is safe, this sounds like a bad idea to me.

How secure actually is this idea?

4
  • 3
    Very little typo correction could be done on good passwords which are not dictionary based and mix lower and upper case characters. This approach is only possible when the password strength is already quite limited. In some cases that can be acceptable, but end user's judgment on this is not reliable. If you're dealing with any sensitive information, password strength should be enforced. Jun 2 '16 at 5:12
  • 5
    Have you read the cited paper? It is a complete analysis of the approach. Well documented and published in a high level conference. I think we have to trust the approach. Security of the passwords is strongly related with their usability... So very fascinating approach.
    – robob
    Jun 2 '16 at 5:18
  • @robob I read it, as well as I could. As I'm not a security expert, phrases like "Levenshtein distance" and "acceptance utility of an exact checker" don't really convey a lot of meaning to me.
    – user74730
    Jun 2 '16 at 5:26
  • 3
    Admittedly, I have long forgotten about Levenshtein distance, but it is an interesting approach. Still, the degree of error would be too high for me to be comfortable. I randomly generate my passphrases, so I have no clue what it is. If they get autocorrected because a partial word got generated, I wouldn't know until it was too late. Then I'd be unhappy.
    – h4ckNinja
    Jun 2 '16 at 5:34
13

Full disclosure: I am one of the authors of the paper.

An exact password checking system stores a standard salted, slow-to-compute hash of the password. When a password, such as password123, is registered with the authentication service, a random salt "sa" is selected (this should be 16 or more random bytes) and a slow-to-compute hash function H is applied: H(sa,password123). The result, call it h, is stored in a database along with the salt sa. As mentioned, one should pick H to be slow (10s or 100s of milliseconds to compute). Good choices are argon2, scrypt, or PBKDF2, properly configured.

When a user later attempts login, if they type in their password the hash is recomputed and checked against the stored value. In the example above, if the user sends password123 then one recomputes (again slowly) H(sa,password123) and checks the result --- it matches the previously computed h and login can be allowed. Any deviation in the submitted password from the previously registered one results in a totally different hash value, and login fails.

Our idea is simple: if the first check fails, the system can additionally apply a small number of "corrector" functions to the submitted password, and then apply the hashing algorithm to the result. For example we might fix a caps lock corrector function F_caps that takes as input a password and outputs the password with the capitalization of all letters changed: F_caps(PASSWORD123) = password123 and F_caps(pAsSwOrD123) = PaSsWoRd123. We might also fix a first-letter capitalization corrector: F_first(Password123) = password123 and F_first(pASSWORD123) = PASSWORD123. Note that these are simple to implement.

Then to do typo-tolerant checking one would apply the following logic for a previously registered salt, hash pair (sa,h) and submitted password pw

If H(sa,pw) = h or H(sa,F_caps(pw)) = h or H(sa,F_first(pw)) = h then allow login

As an example, if one submitted PASSWORD123, the checks would be on PASSWORD123, password123, and pASSWORD123, with the second check succeeding.

A few points:

1) The efficacy of offline brute force attacks are exactly the same as before. Why? Because we only store sa,h. The attacker, given sa,h, will only learn the password via a brute-force attack that tries the correct password, in our example password123. There is no loss in security here as we haven't changed how H is computed.

2) There is negligible change in the security against remote guessing attacks. We show this via extensive analyses in the paper, but it boils down to the fact that in the real world the best strategy is to submit the most likely passwords up to some threshold (e.g., many sites lock an account after 10 failed attempts). The extra checks performed due to typo correction may help the attacker get a little bit more lucky, but we show that it is essentially negligible. If one is worried about it we give techniques that reduce it even further.

3) Typo-tolerance will increase CPU utilization for the login server (and possibly memory load, when H is a memory-hard hash such as scrypt or argon2). This is because of the extra slow-to-compute invocations of H. In practice this doesn't seem to be as much overhead as you might expect (3x in our example above) because anyway users would have ended up resubmitting after rejection and you pay the price for each attempt.

4) We do not suggest allowing arbitrary typos. This isn't even possible currently, as it would require recomputing H a prohibitive number of times (remember it is slow!), and anyway this would be insecure. One needs to carefully choose which typos to allow based on a principled analysis. We believe the two correctors mentioned above, caps lock and first letter capitalization, are a no-brainer for secure deployment, beyond that it starts getting more nuanced.

We added an FAQ that provides additional information: https://www.cs.cornell.edu/~rahul/projects/pwtypos.html

5
  • 1
    It sounds reasonable, but users should not be encouraged to use passwords that can be autocorrected. As soon as that's the case, it means that users are following some pattern. Otherwise you would not be able to alter the pattern. It's most likely a nice-to-have thing, but hopefully it will be useless in the future if you know what I mean :)
    – Potaito
    Jun 6 '16 at 17:37
  • 1
    @potAito It can still make sense to use a small subset of these autocorrections even for good passwords. I may type my random password without noticing that the caps lock key is on, or I may forget that my smartphone automatically capitalizes the first letter in a string I enter.
    – PwdRsch
    Jun 6 '16 at 18:40
  • @PwdRsch Okay you are right, those are about the only exceptions :)
    – Potaito
    Jun 6 '16 at 19:15
  • "Typo-tolerance will increase CPU utilization for the login server" have you analysed the risks of easier DDOS from this additional CPU usage? Jun 9 '16 at 14:06
  • 2
    What about password theft from someone looking over the shoulder or recording video of a user typing? Wouldn't it make it easier to mimic a password and get it just close enough for the autocorrection to let them get in? It would be like my bank asking for my name, address, phone number, and birthdate, someone knowing 3/4 and still gaining authorization. Usability and security are often at odds. Passwords are usually the problem. Some other means of authentication is probably preferable if you want to make it "easy" for users, but still secure.
    – nbering
    Jun 9 '16 at 22:50
1

Edit: This answer is not correct, see the top voted answer. In the appendix they referred to "secure sketches" but upon reading the paper closer I see that they do not recommend that method:

In theory a secure sketch [17] could be used to correct some typos in the server side. However, the proven bounds for existing constructions are too weak to provide meaningful protection for our setting (in which entropy is quite low).

They already acknowledged my points I wrote here and rejected that idea. I completely missed that reading the paper the first time.

--

Despite the fact that the research paper seems highly credible, I myself disagree with their findings. Although their calculations are sound, their assumptions don't take into account real-world attack scenarios nor do they take into account how people select passwords.

Essentially what they are saying is that there are a few common mistakes, such as having capslock enabled, not capitalizing the first letter, adding or removing a character, or hitting an adjacent key on the keyboard. Their proposed solution allows for all of these seemingly minor errors to be ignored so the system will accept the password as close enough.

While this is a huge improvement in usability (we all make typos when entering passwords), the tradeoff in security is much greater than they acknowledge. Part of the problem is that they don't address online (logging in to a live web site) vs offline (obtaining the hash database and cracking them on your on computer). With an offline attack where the attacker can potentially brute force billions of passwords per second, fuzzy passwords would fail greatly.

Say, for example, that a hacker obtains a database of a million passwords and attempts a hybrid dictionary attack on the them. Normally, the password cracking software will take a word like "password" and try all the permutations of that, including Password, pAssword, PAssword, password1, password!, etc. Having to try hundreds of permutations of every single dictionary word is what makes password cracking so time-consuming.

In the case of fuzzy passwords, nearly all those permutations would work as valid passwords. Say it simply tries "password" against the entire set of a million passwords. The hacker would get correct matches for every account that word and every single permutation. The big problem here is that many people make their passwords stronger by changing one letter, using random capitalization, adding a number or punctuation at the end, etc. Fuzzy passwords make all of those techniques ineffective.

It is important that we force an attacker to try every single permutation to gain even a millisecond of time for each attempt. That is precisely the reason we use hundreds or thousands of rounds of hashing with algorithms like PBKDF2. Every bit of work the password cracking software has to do with each password works to our advantage.

In the paper they are considering the entire password space and they correctly calculate that fuzzy checking does not significantly decrease the number of possible passwords an attacker must brute force. The problem is that passwords are not distributed evenly in this potential space, but rather clustered around the relatively tiny space that consists of dictionary words. If you take that into consideration the loss of security is significant.

To put this in perspective, if you take the surface area of the entire US (3.8 million sq miles) to represent all the possible passwords one could choose, the actual passwords everyone uses would fit in an area of about 5 sq feet. Fuzzy passwords in such a tiny space would be a disaster.

The idea would work well on systems with casual security and where usability is important. It might also be acceptable when used in combination with multiple authentication factors such as a hardware token or biometric sensor. But, for everything else, the technique simply is not secure enough.

8
  • "In the case of fuzzy passwords, nearly all those permutations would work as valid passwords. Say it simply tries "password" against the entire set of a million passwords. The hacker would get correct matches for every account that word and every single permutation" __________________ I don't believe this is what the paper is saying. If the password is passWord, and the attacker tries "'password", that's not one of the common errors described in the paper. Having Caps lock on would mean "PASSwORD" would be accepted for "passWord". Just one more possibility. Jun 2 '16 at 21:23
  • 3
    You're making a mistake about the offline cracking. Offline cracking involves trying to replicate a one-way hash. A one-way hash can't be fuzzy. They would be implementing the spellcheck at the application input, and would likely try hashing slight variations of the attempted password (caps on, capitalization, etc) and see if any of those match the hash that is stored.
    – nyxgeek
    Jun 3 '16 at 0:39
  • 1
    @nyxgeek Or they compute the hash after converting the input to fixed case...
    – user
    Jun 3 '16 at 12:32
  • @SteveSether I don't think they specify exactly which permutations would be allowed, I got the impression this would be a configurable parameter. Jun 3 '16 at 23:35
  • 2
    This answer is 100% wrong. The papers mentioned in the OP do not propose fuzzy hashing. They propose using standard hashing which means this autocorrect functionality isn't relevant to offline attacks Jun 4 '16 at 4:09
0

There are two plausible attack scenarios here:

  1. Offline cracking
  2. Online Cracking

In the offline cracking situation the paper still describes that strong cryptographic principles should be applied. This means there is no fuzzy logic. There is only the work required to compute the final hash knowing the salt and guessing at inputs. There is no real advantage or disadvantage of the paper's methods in this scenario.

In the online cracking situation, when the attacker is guessing passwords at random against some online source there is a usability and security trade off. Essentially, each attempt is worth several (depending on the correction algorithm used and the amount of correction possible). The trade off here seems theoretically minimal in a single account scenario.

However, within a realistic online threat model attacks occur on a much larger scale. Botnets attempt attacks of common passwords in the hope that some are correct purely by chance. What this paper describes is something that would, at a large scale, increase the overall risk of account compromise.

Ultimately it comes down to the security usability trade off. In this situation I would be disinclined to set such a policy at any scale as it would effectively multiple the effectiveness of malicious attempts.

-1

According to the paper, there is zero security impact in the case of offline brute-force attacks. This is because there is no change to the database containing hashed passwords. Online checking of typos uses "exact checking," i.e., matching against a stored hash, as a subroutine.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy