random character checking at logon

Hi,

Any advice on this puzzle would really be appreciated.

We have a policy for internet based login that passwords shouldn't be entered 
in full. Random characters from the password are prompted for- e.g. 2nd, 3rd, 
last. 

Separately we have a policy that passwords shouldn't be stored in the clear on 
the backend - one-way hashes are preferred.

Nothing unusual in either of those policies, but satisfying both requirements 
is proving difficult. 

I have a solution which works but is ugly and consumes a lot of database 
resources, namely to hash all possible combinations of a userid, the prompted 
for positions and their correct values. Authentication consists of looking for 
a match on the table of hashes. Password changes require large numbers of 
deletions and insertions from the table.

I would be interested if anyone has a more elegant solution.

Tim