Store password securely but being able to check separate characters in that password

Question

I am writing a system where the user must log in with two passwords: a normal password (salted and hashed, stored in database), and a special password where the user needs to type only some letters, e.g. "please type the second, third and last letter of your password".

How can one design that system to support the second password?

Idea 1: store the password in plaintext. Of course not.

Idea 2: Store each character separately, salted and hashed. Bad because if the attacker knows the salt, it only takes a few dozen guesses to bruteforce the character.

Is there any other way?

---

Clarifications:

The two passwords have to be typed at the same time, like so:

The purposes of the second password are:

• Defeat the attacker who looks over your shoulder while you type the password, or a keylogger.
• Defeat the password manager in your browser, when someone like your family member can log in to your account if you chose to save your password in the browser.
• Provide a simple alternative to 2FA when the user is not accessing extremely sensitive information, so we don't bother them to retrieve their hardware one-time password generator (which they also have).

Answer 1

You can't - at least not in software, for reasons given by Matthew.

If you have a five character password with a-z, that's 26*26*26*26*26, or 11881376 possibilities. However, if you can probe one character at a time, it's 26+26+26+26+26, or 130 possibilities.

Even for long, complex, passwords this reduces the amount of work that has to be done to trivial levels.

In addition it's bad security. People should use password managers, to have unique passwords everywhere. Password managers do not support this kind of queries. And even if it's a typed password, it's difficult, as many people rely on muscle memory to enter passwords. I wouldn't be able to give you the third character of my password without typing it out and checking.

Answer 2

Use a Hardware Security Module (HSM) which is effectively write-only for the full password, and which generates the parts required. The flow in this case is that your app asks the HSM for a verification step, it returns a set of expected letters and some form of identified for the request, the user provides those letters, the app sends them to the HSM, and the HSM returns either "yes" or "no", depending on whether they are correct. The HSM should require the same set of letters to be provided for that account until the user provides them, or the account is locked out, to avoid an attacker with partial knowledge of the password being able to log in by refreshing until they get characters they do know. This method should be safe, given a reliable HSM, but is likely to also be expensive.

Storing the plain text password or hashed individual characters both allow an attacker able to access the database table to find the full password with a predictable (low) amount of effort. Similarly, hashing each possible group of characters results in a small potential search space, even if every group is hashed with a unique salt (brute forcing three characters is not hard, even with a long salt, since the salt is fixed for each one). Encrypting the secret password increases the effort required, but only slightly: if you use the initial password (appropriately stretched) as the key, you defeat the concept of needing two pieces of information to log in. If you use anything which is stored on the server, the attacker potentially has access to the key, so can obtain the passwords.