As you correctly note, standard password hashing schemes won't work if authentication is done using only a substring of the password. There are a number of ways that such a system could be implemented:
Store the password in plain:
- Simple and easy to implement.
- Insecure if the database is compromised.
- May not comply with regulations requiring hashed or encrypted password storage (but using low-level database encryption might get around that).
Store the password encrypted, decrypt to check:
- No more secure than storing it in plain if the encryption key is also compromised.
- May satisfy regulations forbidding password storage in plain.
- Could be made more secure by using a dedicated hardware security module or a separate authentication server, which would store the key and provide a black-box interface for encryption and substring verification.
Store hashes of all (or sufficiently many) possible substrings:
- Needs much more storage space than other solutions.
- Password can still be recovered fairly easily by brute force if the database is compromised, since each substring can be attacked separately.
Use k-out-of-n threshold secret sharing:
- Needs less space than storing multiple hashes, but more than storing the password in plain or using reversible encryption.
- No need to decrypt the password for substring verification.
- Still susceptible to brute force attack if database is compromised: anyone who can guess k letters of the password can recover the rest. (In fact, with some implementations, k-1 letters might be enough.)
Ultimately, all of these schemes suffer from weakness against brute force attacks if the database is compromised. The fundamental reason for this is that there just isn't very much entropy in a three-letter substring of a typical password (or, indeed, of even a particularly strong one), so it won't take many guesses to crack.
Which of these is best? That's hard to say. If I had to choose one of these schemes, I'd probably go for encrypted storage using strong symmetric encryption (such as AES), with a separate server or HSM to handle encryption and verification. That way, at least, an attacker compromising a front-end server wouldn't be able to just copy the database and attack it offline (although they could still mount a brute force attack on the HSM if it didn't implement effective rate limiting).
However, I'd say that the whole idea of using only part of the password for authentication is deeply flawed: it doesn't really deliver the security benefits it's supposed to, except in a few particularly constrained attack scenarios (such as an eavesdropper that can only observe one authentication event, and cannot just keep trying until they get the same challenge), yet it fundamentally weakens security by reducing the amount of information needed for successful authentication. There are much better solutions, such as TANs, to the security concerns that partial password authentication is supposed to address.
