On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
And here are another ones which produce the same hash value. Of course searching for pair for jhash('jhash is broken') will require more steps, but it is doable.That means that if attacker has a full control over one host, it can create a chain of maximum 4 entries in socket table (if jhash is used). If it is udp, that means that attacker control addresses too without syn cookies, which in turn means that below list can be increased to infinite.
Evgeniy, you're not gettin' it. Have you ever heard of a Poisson distribution? That's what you have to aim for in a (bog-standard) hash table -- a hash function that scrambles the key space until you have a Poisson distribution in the hash buckets no matter whan pile of keys the attacker throws at you. That's a "perfect" hash function in the statistician's sense (not a "perfect hash" function in the compiler designer's sense). Yes there will be collisions, and they will start happening much earlier than you will think, if you have never heard of Poisson distributions before; that's called the "birthday problem" and it is a chestnut of a mathematical puzzle generally encountered by bright twelve-year-olds in extra-curricular math classes. The only sensible way to deal with them is to use a better data structure -- like a 2-left hash (Google it) or something tree-ish. That is not, however, what you're not getting. What you're not getting is the use of a "salt" or "secret" or whatever you want to call it to turn a weak hash into an impenetrable defense against chosen-plaintext collision attacks. You can run your PRNG until you slag your poor botnet's little CPUs searching for a set of tuples that collide in the same bucket on your test system-under-attack. But they won't collide on mine, and they won't collide on Eric's, and they won't collide on yours the next time it's rebooted. Because even a weak hash (in the cryptographer's sense) is good enough to scramble the key space radically differently with two different salts. XOR doesn't cut it -- the salt will permute the buckets but not toss each one's contents up into the air to land in a bunch of different buckets. But Jenkins does cut it, as discussed in the source code Eric pointed out to you. Of course you don't change the salt except when resizing the hash (which is a dumb thing to do anyway, and a sure sign that a hash table is not the right data structure). That would kinda defeat the purpose of having a hash table in the first place. If you can't assimilate this and articulate it back to us in your own words instead of repeating "any hash that doesn't totally, utterly suck slows my meaningless artificial benchmark by 50%", you may not be the right person to design and implement a new RCU data structure in a kernel that thousands of us trust to withstand exposure to the open Internet to the best of a commodity processor's ability. Cheers, - Michael - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
