# Validating subset of a password

Is anyone aware of an algorithm/method that allows me to validate just a few letters (or other characters) from a password. For example, the application asks for the 2nd, 3rd, 6th and 9th letters from the password. Which letters are requested is determined randomly.

I really, really don't want to store passwords in plain text. This technique is used by at least one UK bank.

I this a good idea? Can anyone offer any help? I'm a fairly competent programmer.

# 1st Edit

When a password is required, the user is prompted to provide a random selection of the characters in their correct positions. This selection might be, say, the 2nd, 3rd, 6th and 9th characters, or might be some other selection, chosen at random. The only feedback that the user gets is "pass" or "fail". He cannot use this to probe each character in the password at his leisure.

Being able to validate the characters of a password independently is almost equivalent to storing the password in cleartext.

If the password consists of $n$ characters in an alphabet of size $a$, then verifying hashed passwords requires $a^n$ queries. (A query is an online lookup until your password database is leaked, and a hash calculation after that.) Verifying individual characters reveals the password in $n\,a$ queries. I'm ignoring the correllation between the different characters of a typical low-randomness, human-chosen password, but the point remains: being able to verify characters individually reduces the guessing work from exponential in the amount of entropy, to linear.

When banks do single-character validation, they are storing the password in plaintext, or close enough that it doesn't make any difference. What can be done to mitigate the risks are:

• Store the password database in a hardware security module; the passwords never get out of the HSM, the HSM itself does the indivdual comparisons.
• Only do individual-character checks for a secondary password, and store it encrypted with the primary password (which is stored only in hashed form).
• Vadim and Gilles, thank you both very much for your careful analysis and for your answers. I'm going to study them. – Nicole May 8 '16 at 10:43

Validating individual letters of a password reduces complexity of guessing that password by trying all possible variants, so I would suggest avoiding such a design.

PCP (probabilistic checkable proofs) is a well-known case of validating just a small portion of the "witness" (defined in that context), with focus on algorithm complexity.

Regarding "1st Edit": pass/fail response to "simplified" query is exactly how complexity is reduced. Random selection of letters requested might be considered a challenge/response scheme, on condition it can not be affected. Worst case would be repeated or single-letter queries.