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.
for(int i = 0; i < int.MaxValue; i++)
var hash = Hash(hashstring);
hashstring = Convert.ToBase64String(hash);
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)