This question has been asked a few times, but always in the format
examplewebsite.comimplement their 'please enter
zth characters of your password' function?"
And the answer is typically assumed to be that they use an HSM capable of answering such a query with a pass/fail against the stored password.
It seems to me that there must be a sensible way of achieving this without using secure hardware. This might be an unlikely scenario, given that anyone who cares enough about security to implement such keylogger-mitigation will probably have the budget and expertise to use an HSM. But from an academic point of view, is there a good implementation?
A naive approach might be to store all
3 choose n combinations, where
n is the password length, and
choose is the mathematical combination function.
But storing these triplets is problematic;
- No amount of salting is going to be able to defend the database given that the search space is so easily brute-forced.
- A long password has a very large number of possible combinations leading to lookup and storage issues. We could limit the number to a fixed cap, but that starts to harm the password strength (in quite a complex way that depends on which triples you choose to store).
- The indexes used to generate each triple also need to be stored, and both points above also apply.
This approach is poor, is there a better approach that would not require the use of an HSM?