13

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?

Community
  • 1
lynks
  • 10,646
  • 5
  • 29
  • 54
  • Lagrange polynomials might be an interesting avenue to look into, but I'm not exactly clear on how they can be applied. I think in general you're going to run into the problem of cheap bruteforcing. – Polynomial Apr 22 '13 at 12:34
  • From what I've seen the only realistic implementation of choose x from y is symmetric encryption, and in most online scenarios the only way to achieve that without exposing the key somewhere on a server is to use an HSM. – Rory McCune Apr 22 '13 at 12:51
  • [Shamir's Secret Sharing](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing) could be used to [turn the problem into polynomial calculations](http://www.smartarchitects.co.uk/news/9/15/Partial-Passwords---How.html). – Adi Apr 22 '13 at 13:04

1 Answers1

11

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.

Tom Leek
  • 170,038
  • 29
  • 342
  • 480
  • 1
    Ok. Normally, I don't care about people not explaining downvotes - I've just given up on that cause. But c'mon! Nobody should be allowed to downvote Little Bear without providing *solid* justification! – Iszi Apr 22 '13 at 14:21
  • 1
    My answer mostly expresses that it can be mathematically proven that there cannot be a good solution -- negative results are rarely popular, which might explain a downvote, out of anger at the Universe in general. – Tom Leek Apr 22 '13 at 14:29
  • 3
    *shakes fist at the universe* – Steve Apr 22 '13 at 18:02
  • So, what does your instinct tell you is the implementation of these authentication mechanisms in practice? Do you suspect that they are in fact less secure than a standard salt+hash password login? From memory I have only seen these in financial institution logins - whom I would have expected to have gone the extra mile for security. But you never know... – El Ronnoco Nov 28 '22 at 12:28