netdev - Re: ipv4: Simplify ARP hash function.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20110708.125118.886216418938741383.davem@davemloft.net>
Date:	Fri, 08 Jul 2011 12:51:18 -0700 (PDT)
From:	David Miller <davem@...emloft.net>
To:	mirqus@...il.com
Cc:	roland@...estorage.com, johnwheffner@...il.com, mj@....cz,
	netdev@...r.kernel.org
Subject: Re: ipv4: Simplify ARP hash function.

From: Micha┅ Miros┅aw <mirqus@...il.com>
Date: Fri, 8 Jul 2011 21:39:18 +0200

> With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.

Ok, I'm convinced, thanks :-)

--------------------
#include <stdlib.h>
#include <stdio.h>

int hashfn(unsigned int key, unsigned int rnd)
{
	unsigned int x = key ^ rnd;

	x ^= (x >> 8) ^ (x >> 16) ^ (x >> 24);

	return x & 0xff;
}

int count[256];

unsigned int collide(unsigned int key)
{
	unsigned int b0 = key >> 24;
	unsigned int b1 = (key >> 16) & 0xff;
	unsigned int b2 = (key >> 8) & 0xff;

	key &= ~0xff;
	key |= (b0 ^ b1 ^ b2);

	return key;
}

int main(int argc, char **argp)
{
	unsigned int rnd = atoi(argp[1]);
	unsigned int i;

	for (i = 0; i < (64 * 1024); i++) {
		unsigned int key = i << 8;
		unsigned int hash;

		key = collide(key);
		hash = hashfn(key, rnd);
		printf("%u: %u\n", key, hash);
		count[hash]++;
	}
	for (i = 0; i < 256; i++)
		printf("COUNT[%3u]=%3u\n", i, count[i]);
	return 0;
}
--
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/majordomo-info.html