In all generality, no, you cannot use such a scheme with a storage based on hashing and still expect the same kind of security as with full-password hashing as it is normally practised.
Here is the demonstration: the point of storing the hashed password, and not the plaintext password, is that you just assume that attackers may obtain a (possibly read-only) glimpse of the server's contents (e.g. with a stolen backup tape). With that copy, the attacker can emulate the server behaviour on his own machines.
In particular, the attacker can:
- Start his emulation of the server.
- Begin an authentication procedure with that emulated server. The server asks for, say, the 1st, 5th and 8th letters of the user's password.
- The attacker snapshots the whole emulated server state at that point.
- For every possible combination of three letters, the attacker restart the emulated server at the snapshot point, enter the three letters, and see if the emulated server is happy or not.
- Once the attacker has found the right combination of three letters (there are only 26×26×26 = 17576 combinations of three letters, which is really few for an automated attacker who can do things by the million -- remember that all of this happens on the emulated server, on the attacker's own machines), he can start over at step 1, to guess other letters. After a few iterations, the attacker has the complete user's password, and can confidently log onto the real server.
In practice, the attacker does not need to really set up a complete virtual machine with snapshots; he can just concentrate on the few kilobytes of code that handle the authentication process. But basing the description on snapshots and server emulation shows that this kind of attack is generic, and there is nothing that can be done to protect against it as long as the attack model applies.
To again achieve security, then, the model must be made not to apply. In the discussion above, I assume that the attacker can get a copy of the server state. Thus, to prevent that attack, we must make it so that there is at least part of the server state that the attacker cannot plunder. In that case, just store a symmetric key K in that attacker-free part of the server, and use symmetric encryption for storing the passwords.
I expect most sites that asks for letter combinations within the user's password to use such reversible encryption. This can be considered as "safe" if the key K is indeed kept out of reach of attackers, which is hard unless you do it seriously (and expensively).
Still in all generality, asking for three letters means that you grant entry to random attackers with probability 1/17576, which is, in my opinion, a bit too high for comfort, considering that we are talking about a publicly reachable server. The whole concept of asking only for some letters is meant to be "more secure" but in fact it is more about sprinkling some obnoxious ritual elements so that you may feel more secure, possibly at the expense of actual security.
