This is what you really want if you care a lot about avoiding the small domain problem (brute forcing H(myguess) so that I finally find H(myguess) == password_hash):<p>Just use an algorithm that is acceptably slow when used to authenticate users, but unacceptably slow when using for brute forcing.<p>For instance<p>HMAC(1,HMAC(2,HMAC(3,MAC(4,HMAC(..N,HMAC("yourPublicZZaaalt","yourpassword"))))))<p>Use N big enough so that you need a few milliseconds to run this code as optimized C.<p>If you are smart, design it so that CUDA wont help.<p>Now you are done. Brute forcing will take just too much if the password is not <i>too</i> obvious. It will be still possible to test 10000 hashes in a reasonable time maybe, but forget to run John The Ripper against it.