linux-kernel - Re: Where exactly will arch_fast

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-next>] [day] [month] [year] [list]

Date:	7 Dec 2014 00:20:41 -0500
From:	"George Spelvin" <linux@...izon.com>
To:	herbert@...dor.apana.org.au
Cc:	dborkman@...hat.com, hannes@...essinduktion.org, linux@...izon.com,
	linux-kernel@...r.kernel.org, netdev@...r.kernel.org, tgraf@...g.ch
Subject: Re: Where exactly will arch_fast_hash be used

If you want DoS-resistant hash tables, I'm working on adding SipHash
to the kernel.

This is a keyed pseudo-random function designed specifically for that
application.  I am starting with ext4 directory hashes, and then intended
to expand to secure sequence numbers (since it's far faster than MD5).

(I'm trying to figure out a good interface, since the crypto API
is a bit heavy for something to heavily optimized.)

But one comment caught my eye:
> Even if security wasn't an issue, straight CRC32 has really poor
> lower-order bit distribution, which makes it a terrible choice for
> a hash table that simply uses the lower-order bits.

Er... huh?  That's the first time I've heard that claim, and while I'm not
Philip Koopman or Guy Castagnoli, I thought I understood CRCs pretty well.

CRCs generally mix bits pretty well.  The sparse 16-bit CRCs chosen
for implementation simplicity had some limitations, but the Castagnoli
polynomial is quite dense.

And their mathematical symmetry means that the low bits really shouldn't
be any different from any other bits.  But if it is an issue, it's just
as easy work to shift down the correct number of high bits rather than
using the low.

Can you point me to a source for that statement?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/