lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 PHC  
Open Source and information security mailing list archives
 

Date: 22 Feb 2007 18:49:00 0500 From: linux@...izon.com To: johnpol@....mipt.ru, medwards.linux@...il.com Cc: akepner@....com, bcrl@...ck.org, dada1@...mosbay.com, davem@...emloft.net, linux@...izon.com, netdev@...r.kernel.org Subject: Re: Extensible hashing and RCU > I think you misunderstood me. If you are trying to DoS me from > outside with a hash collision attack, you are trying to feed me > packets that fall into the same hash bucket. The Jenkins hash does > not have to be artifactfree, and does not have to be > cryptographically strong. It just has to do a passable job of mixing > a random salt into the tuple, so you don't know which string of > packets to feed me in order to fill one (or a few) of my buckets. > XORing salt into a folded tuple doesn't help; it just permutes the > buckets. If you want to understand this more formally, read up on "universal families of hash functions," which is the name cryptologists give to this concept. When used according to directions, they are actually *more* secure than standard cryptographic hashes such as MD5 and SHA. The key difference is that *the attacker doesn't get to see the hash output*. The basic pattern is:  Here's a family of hash functions, e.g. a salted hash function.  I pick one at random. (E.g. choose a salt.)  Now your challenge is to generate a pair of inputs which will collide.  Note that you never get to see sample input/output pairs of the hash function. All you know is that it's a member of the family.  It is surprisingly easy to find families of size N such that an attacker has on the order of a 1/N chance to construct a collision.  This remains true even if you assume that the attacker has infinite computational power. This pattern corresponds exactly to an attacker trying to force collisions in a hash table they can't see. As far as I know, nobody has proved salted jash a truly universal family, but so many amazingly simple algorithms have been proved universal that it wouldn't surprise me if it was. For example, the family of all CRCs computed modulo nbit primitive polynomials is a universal family. If you do know the polynomial, it's ridiculously easy to build a collision. If you don't, it's provably impossible. (Footnote: the chance isn't exactly 1/N, but also depends on the size of the input relative to the size of the hash. With bigger inputs, it's easier to make them match according to more of the hashes. Ultimately, if you have N kbit CRC polynomials, you can make them all collide with an N*kbit input. But since N is proportional to 2^k, it's easy to make k big enough that this is impractical.) The rehashevery10minutes detail is theoretically unnecessary, but does cover the case where a wouldbe attacker *does* get a chance to look at a machine, such as by using routing delays to measure the effectiveness of a collision attempt. Now, as for flaming about how xor generates more uniform distributions than jhash  that's to be expected from a weak hash. By relying on nonuniform properties of the input (particularly that hosts tend to walk linearly through the source port space), you can make hash values walk linearly through your hash table, and get a completely even distribution rather than a *random* one. This is great for efficiency, but depends on letting patterns in the hash input through to the output, which is exactly the property that makes it vulnerable to a deliberate DoS attempt. If you want to test your distribution for randomness, go have a look at Knuth volume 2 (seminumerical algorithms) and see the discussion of the KolmogorovSmirnov test. Some lumpiness is *expected* in a truly random distribution.  To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomoinfo.html
Powered by blists  more mailing lists