4 ms·
This would increase the complexity of the hash verification by log2(N) times, where N is the number of user records. So even if you do have a billion hashes, yo
by rorrr 14y ago
This would increase the complexity of the hash verification by log2(N) times, where N is the number of user records. So even if you do have a billion hashes, you only slowed the attackers 30 times. You might as well increase the BCRYPT complexity and skip this scheme.
- zaroth 14y agoThis should be used with scrypt or bcrypt set to the highest difficulty your application can support. The point is to increase difficulty of targeting an individual user, and increase difficulty of stealing the data in the first place. This is separate and distinct protection from what scrypt/bcrypt gives you. [Edit] In a typical GPU accelerated brute force attack, the target hash and salt are both known as fixed 20 or 32-byte values, and you iterate through candidate passwords until you find a match. In the proposed technique, the target hash is NOT known! Instead, what you do know is a salt and a list of a few billion hashes, ONE of which can be obtained by combining the salt with some unknown password. This is a very different equation, and I believe, much harder to solve, since your target value can't just be kept in a register or L1 cache for comparison purposes.
- rorrr 14y agoActually, I was wrong about O(log(N)), the lookup time is O(1), you just have to put all known hashes in a map structure, or even better, a rainbow hash. So your technique only adds some constant lookup time. Instead of if (hash == target_hash) ... you will do if (map[hash]) .... Sorry, I think you are wrong.
- xaway12345 14y agoeh, this is amortized O(1) and you are almost guaranteed slow lookups for a large number of requests. don't confuse true O(1) with amortized ;)