Are partial hashes secure for this purpose? If so, you could store a partial hash and send some sort of random token to the client. The client could then create a hash from the password and token, and the server could check by finishing the hash with the token. If the tokens are not reusable, then I'd think that'd solve the problem.