linux-kernel - Re: [PATCH v2] siphash: add cryptographically secure hashtable 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]

Date:   Mon, 12 Dec 2016 13:37:03 -0800
From:   Linus Torvalds <torvalds@...ux-foundation.org>
To:     "Jason A. Donenfeld" <Jason@...c4.com>
Cc:     "kernel-hardening@...ts.openwall.com" 
        <kernel-hardening@...ts.openwall.com>,
        LKML <linux-kernel@...r.kernel.org>,
        Linux Crypto Mailing List <linux-crypto@...r.kernel.org>,
        George Spelvin <linux@...izon.com>,
        Scott Bauer <sbauer@....utah.edu>,
        Andi Kleen <ak@...ux.intel.com>,
        Andy Lutomirski <luto@...capital.net>,
        Greg KH <gregkh@...uxfoundation.org>,
        Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com>,
        "Daniel J . Bernstein" <djb@...yp.to>
Subject: Re: [PATCH v2] siphash: add cryptographically secure hashtable function

On Sun, Dec 11, 2016 at 9:48 PM, Jason A. Donenfeld <Jason@...c4.com> wrote:
> I modified the test to hash data of size 0 through 7 repeatedly
> 100000000 times, and benchmarked that a few times on a Skylake laptop.
> The `load_unaligned_zeropad & bytemask_from_count` version was
> consistently 7% slower.
>
> I then modified it again to simply hash a 4 byte constant repeatedly
> 1000000000 times. The `load_unaligned_zeropad & bytemask_from_count`
> version was around 6% faster. I tried again with a 7 byte constant and
> got more or less a similar result.
>
> Then I tried with a 1 byte constant, and found that the
> `load_unaligned_zeropad & bytemask_from_count` version was slower.
>
> So, it would seem that between the `if (left)` and the `switch
> (left)`, there's the same number of branches.

Interesting.

For the dcache code (which is where that trick comes from), we used to
have a loop (rather than the duff's device thing), and it performed
badly due to the consistently badly predicted branch of the loop. But
I never compared it against the duff's device version.

I guess you could try to just remove the "if (left)" test entirely, if
it is at least partly the mispredict. It should do the right thing
even with a zero count, and it might schedule the code better. Code
size _should_ be better with the byte mask model (which won't matter
in the hot loop example, since it will all be cached, possibly even in
the uop cache for really tight benchmark loops).

             Linus