https://bugzilla.wikimedia.org/show_bug.cgi?id=28419
--- Comment #13 from Aryeh Gregor <[email protected]> 2011-05-12 14:25:41 UTC --- (In reply to comment #12) > But given that the whole point is to include a physical barrier to someone > being able to brute-force a stolen database on a GPU cluster or somesuch, > storing a hash of the non-db key in the db turns the problem back into resting > on the preimage security of whatever hash function is used on the key. We aren't worried about the preimage security of the hash function. No widely-used cryptographic hash function that I know of has ever had a practical preimage attack. Even MD4, which is so badly broken that you can generate collisions *by hand*, has no preimage attack better than 2^102 or so. What we're worried about is brute-forcing, and you can't brute-force a (for instance) 40-byte hexadecimal string. That's 2^160 possibilities, which reduces to 2^80 given birthday attacks, which is wildly impractical. Make it 60 bytes if you like, or 100. Even if you had a preimage attack, that only gives you *some* preimage. If you choose a salt that's at least a few bytes longer than the hash, then with overwhelming probability, the preimage generated by your attack will not be the same as the actual salt. That makes it useless to an attacker. > Generate the (potentially many) preimages that match the hash (by brute force > if necessary), You cannot generate preimages for a cryptographic hash function using brute force, unless the input is guessable. Many passwords are guessable, or at least short (which amounts to the same thing), which is why brute-forcing works at all. A long random string cannot be brute-forced, and can't even be obtained from vulnerabilities in the hash function (as long as it's a few bytes longer than the hash itself). Put another way: if the hash is 256 bits and the salt is 320 bits, then there will be at least 2^64 possible salts on average that have a given hash. Even if you had a magic oracle that enumerated all the possible preimages of the hash of the right length, you'd never be able to try them all. For perspective, storing that many salts would take up millions of terabytes; and if you had a 10 GHz CPU that could somehow do one hash execution per clock cycle, it would take several decades to check all the hashes. If that seems a little too easy to get, make the salt 1024 bits -- it's not going to affect execution speed noticeably. > Having a non-db secret > key only provides a fundamentally *new* layer of protection (as opposed to > just > an incrementally stronger implementation of the existing security) if no > information at all about it is stored in the database. Correct. For all intents and purposes, the cryptographic hash of a long random string provides no information about the string at all. Thus it's fine to store. (In crypto terms, the information it provides is "negligible". Almost nothing in crypto gives you better assurances than "except with negligible probability". You could successfully invert an RSA public key in constant time, too, but only with negligible probability.) > This is all rather off-topic for this particular bug, anyway... This bug is about replacing MediaWiki's hash function, so it seems quite germane. Maybe we should make a mediawiki.org page to write up the conclusions, so people don't have to wade through the discussion to get at them. -- Configure bugmail: https://bugzilla.wikimedia.org/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are on the CC list for the bug. _______________________________________________ Wikibugs-l mailing list [email protected] https://lists.wikimedia.org/mailman/listinfo/wikibugs-l
