From: "George Spelvin" <firstname.lastname@example.org> To: email@example.com, firstname.lastname@example.org Cc: email@example.com, firstname.lastname@example.org, David.Laight@aculab.com, email@example.com, firstname.lastname@example.org, email@example.com, Jason@zx2c4.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com Subject: Re: HalfSipHash Acceptable Usage Date: 21 Dec 2016 01:34:12 -0500 [thread overview] Message-ID: <firstname.lastname@example.org> (raw) In-Reply-To: <email@example.com> Eric Dumazet wrote: > On Tue, 2016-12-20 at 22:28 -0500, George Spelvin wrote: >> Cycles per byte on 1024 bytes of data: >> Pentium Core 2 Ivy >> 4 Duo Bridge >> SipHash-2-4 38.9 8.3 5.8 >> HalfSipHash-2-4 12.7 4.5 3.2 >> MD5 8.3 5.7 4.7 > > So definitely not faster. > > 38 cycles per byte is a problem, considering IPV6 is ramping up. As I said earlier, SipHash performance on 32-bit x86 really sucks, because it wants an absolute minimum of 9 32-bit registers (8 for the state plus one temporary for the rotates), and x86 has 7. > What about SHA performance (syncookies) on P4 ? I recompiled with -mtune=pentium4 and re-ran. MD5 time went *up* by 0.3 cycles/byte, HalfSipHash went down by 1 cycle, and SipHash didn't change: Cycles per byte on 1024 bytes of data: Pentium Core 2 Ivy 4 Duo Bridge SipHash-2-4 38.9 8.3 5.8 HalfSipHash-2-4 11.5 4.5 3.2 MD5 8.6 5.7 4.7 SHA-1 19.0 8.0 6.8 (This is with a verbatim copy of the lib/sha1.c code; I might be able to optimize it with some asm hackery.) Anyway, you see why we were looking longingly at HalfSipHash. In fact, I have an idea. Allow me to make the following concrete suggestion for using HalfSipHash with 128 bits of key material: - 64 bits are used as the key. - The other 64 bits are used as an IV which is prepended to the message to be hashed. As a matter of practical implementation, we precompute the effect of hashing the IV and store the 128-bit HalfSipHash state, which is used just like a 128-bit key. Because of the way it is constructed, it is obviously no weaker than standard HalfSipHash's 64-bit security claim. I don't know the security of this, and it's almost certainly weaker than 128 bits, but I *hope* it's at least a few bits stronger than 64 bits. 80 would be enough to dissuade any attacker without a six-figure budget (that's per attack, not a one-time capital investment). 96 would be ample for our purposes. What I do know is that it makes a brute-force attack without significant cryptanalytic effort impossible. To match the spec exactly, we'd need to add the 8-byte IV length to the length byte which pads the final block, but from a security point of view, it does not matter. As long as we are consistent within any single key, any unique mapping between padding byte and message length (mod 256) is equally good. We may choose based on implementation convenience. (Also note my earlier comments about when it is okay to omit the padding length byte entirely: any time all the data to be hashed with a given key is fixed in format or self-delimiting (e.g. null-terminated). This applies to many of the networking uses.)
next prev parent reply other threads:[~2016-12-21 6:34 UTC|newest] Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-12-19 17:32 Jason A. Donenfeld [not found] ` <CAGiyFdduUNSGq24zfsk0ZU=hnOCmewAw8vw6XvDoS-3f+3UPKQ@mail.gmail.com> 2016-12-19 21:00 ` Jason A. Donenfeld 2016-12-20 21:36 ` Theodore Ts'o 2016-12-20 23:07 ` George Spelvin 2016-12-20 23:55 ` Eric Dumazet 2016-12-21 3:28 ` George Spelvin 2016-12-21 5:29 ` Eric Dumazet 2016-12-21 6:34 ` George Spelvin [this message] 2016-12-21 14:24 ` Jason A. Donenfeld 2016-12-21 15:55 ` George Spelvin 2016-12-21 16:37 ` Jason A. Donenfeld 2016-12-21 16:41 ` [kernel-hardening] " Rik van Riel 2016-12-21 17:25 ` Linus Torvalds 2016-12-21 18:07 ` George Spelvin 2016-12-22 1:54 ` Andy Lutomirski 2016-12-21 14:42 ` Jason A. Donenfeld 2016-12-21 15:56 ` Eric Dumazet 2016-12-21 16:33 ` Jason A. Donenfeld 2016-12-21 16:39 ` [kernel-hardening] " Rik van Riel 2016-12-21 17:08 ` Eric Dumazet 2016-12-21 18:37 ` George Spelvin 2016-12-21 18:40 ` Jason A. Donenfeld 2016-12-21 22:27 ` Theodore Ts'o 2016-12-22 0:18 ` George Spelvin 2016-12-22 1:13 ` George Spelvin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --firstname.lastname@example.org \ --email@example.com \ --cc=David.Laight@aculab.com \ --cc=Jason@zx2c4.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --subject='Re: HalfSipHash Acceptable Usage' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).