Are there any uses of having a non-deterministic salt value for hashes?

Question

So I've been toying with the idea of having non-deterministic salt values for hashes.

Let me explain what I mean:

Basically, I applied some properties from Bitcoin including a "difficulty" (ie, hashed value must begin with a certain number of 0 bits) and came up with something that could be used for password hashes.

My algorithm:

string hashstring=password;
for(int i = 0; i < int.MaxValue; i++)
{
    var hash = Hash(hashstring);
    hashstring = Convert.ToBase64String(hash);
    if(MeetsDifficulty(hash, difficulty))
    {
        Console.WriteLine("i: "+i);
        return hashstring;
    }
}

password in this case, is something like password+salt where salt is a standard cyrptographic random salt stored with the hash. However, as you can see, there is also an i value for how many times it must be hashed, which is not stored along with the hash.

In this way, you must hash the password a number of times until you find something that meets the required difficulty level. This is easy to verify, but does require time because it's unknown exactly how many times the value must be hashed.

There are some interesting properties of this mechanism:

• An incorrect password is slightly undetectable. The only way to know it's incorrect is if you know the difficulty level and you find a hash which meets it, but doesn't match the hash
• It's probably quite hard to compute any of this in parallel?
• In theory, it's completely unknown how long it will take to verify or compute a hash (other than probabilities)
• Bruteforce would probably be hard because each password attempted may result in extremely large amounts of hashes needed to verify it to the difficulty

However, I can't really come up with a good use for these properties. Is there any good things to apply such a scheme to or is there anything that uses such a scheme?

Also, are there any potential weaknesses to this hashing scheme?

For my testing, I used SHA256 as the hashing algorithm, and it got quite slow after a difficulty of about 20 bits of zeros. However, this could easily be replaced with using scrypt, bcrypt, or SHA512

Also, one more idea is that you could possibly construct "quick" to verify hashes, but only when given the correct password. (by changing the salt if, say, you've already hashed the value X times and you want to target only hashing the value Y times to verify it when given a correct password)

Answer 1

Not really. This does protect you from client side brute forcing, but opens you up to DoS-like attacks.

The flaw here is that when someone is attempting to brute force a password, the CPU power they use is yours, not theirs. Which means that your system can be brought down on its knees much faster by a distributed brute force attack. Especially since there's no "escape" to the for loop till integer overflow: If I enter an incorrect password, your server will try getting the right hash for it for a while.

You won't be able to keep the difficulty too high, either. Thing is, this exact computation is carried out every time the person wants to log in. This is not hard-to-make-but-easy-to-verify like the Bitcoin system. Since i is unknown, this is just as hard to make at it is to verify.

The only thing this protects against (only slightly) is if your database got compromised -- then you would be protected against bruteforcing. But salts on SHA256 manage this job well anyway.