Re: Question about tcp hash function tcp_hashfn()

Evgeniy,

On Wed, 31 May 2006, Evgeniy Polyakov wrote:
Worse: he folded the jenkins algorith result with

h ^= h >> 16;
h ^= h >> 8;

Destroying the coverage of the function.

It was done to simulate socket code which uses the same folding.
Leaving 32bit space is just wrong, consider hash table size with that
index.

Btw, that probably requires some clarification.
Since hash table size is definitely less than returned hash value, so
higher bits are removed, for that case above folding is done both in
XOR hash and my test case.
It is possible to just remove higher bits, but fairly ditributed parts
being xored produce still fairly distributed value.

h ^= h >> 16;
h ^= h >> 8;

This does not remove high order bits in either function.
Your comparison results are simply invalid with these two lines in place.

--brian
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: [RFC][PATCH] Make cryptoapi non-optional?
    ... > patterns in the returned hash by xoring the first half of the hash ... that's not why the folding was done. ... information that a Very Sophisticated Attacker (say, ... easier for them to attack the SHA algorithm. ...
    (Linux-Kernel)
  • Re: Question about tcp hash function tcp_hashfn()
    ... It was done to simulate socket code which uses the same folding. ... Since hash table size is definitely less than returned hash value, ... same distribution. ...
    (Linux-Kernel)
  • Re: [RFC][PATCH] Make cryptoapi non-optional?
    ... The idea with the folding was that we can cover up any systemic ... patterns in the returned hash by xoring the first half of the hash ... are going to translate into a correlation between otherwise ... anti-correlated) system xy is going to have only 1 bit of entropy. ...
    (Linux-Kernel)
  • Re: [RFC][PATCH] Make cryptoapi non-optional?
    ... >> patterns in the returned hash by xoring the first half of the hash ... >> once in the input pool, and once in the output pool, along with lots ... you are returning a strong digest of the pool state. ... > As far as I can tell, folding the hash result doesn't help, because ...
    (Linux-Kernel)
  • Re: [RFC][PATCH] Make cryptoapi non-optional?
    ... and folding is demonstrably worse if SHA-1's output is ... If there any kind of correlation between any two individual bits, ... Consider that a requirement of a secure cryptographic hash is one ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)