If you controlled the passwords your users chose, you might be in a position to talk about "strong passwords" combining with "salted hashes" to make a reasonable solution.

Here's a bcrypt hash. Crack it, and I'll donate $200 to the charity of your choice. It's not random, and the cost factor on the hash is not high.

  $2a$14$Dk9dLUH6khBEU3tIHGkNX.6rm6kccRwDUq.bopQ68INbDumal3BiG