"Please Enter Nth Character" without HSM

Question

This question has been asked a few times, but always in the format

"How does examplewebsite.com implement their 'please enter xth yth and 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?

Answer 1

Suppose that the question sent to the client can be about three characters: the server asks for (for instance) the 4th, 7th and 8th characters of the password.

Freeze time! At that exact point, the server has asked the question above, and will be able to verify an answer from the client. This means that in its complete state, there is enough information to tell whether a specific sequence of three character values is a correct answer or not. And it can tell that after investing a limited amount of CPU, say at most one second worth of computations on the server.

If that's software only, then the state can be recovered. We envision an attacker who hijacked the machine, so he can grab a full copy of the hard disk. At that point, the attacker has everything, so he can run an emulation of the server on his own machines. In particular, he can rewind the server to a known previous state.

Therefore, the attacker can now run an exhaustive search on the three character values, by trying and rewinding the emulated server.

This is unavoidable. Without dedicated uncloneable hardware (a HSM, namely), this kind of attack must work. This basically means that the password strength is that of a three-character password, i.e. nothing worth boasting about.