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, firstname.lastname@example.org, Jason@zx2c4.com, 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 20:13:35 -0500 [thread overview] Message-ID: <firstname.lastname@example.org> (raw) In-Reply-To: <email@example.com> As a separate message, to disentangle the threads, I'd like to talk about get_random_long(). After some thinking, I still like the "state-preserving" construct that's equivalent to the current MD5 code. Yes, we could just do siphash(current_cpu || per_cpu_counter, global_key), but it's nice to preserve a bit more. It requires library support from the SipHash code to return the full SipHash state, but I hope that's a fair thing to ask for. Here's my current straw man design for comment. It's very similar to the current MD5-based design, but feeds all the seed material in the "correct" way, as opposed to Xring directly into the MD5 state. * Each CPU has a (Half)SipHash state vector, "unsigned long get_random_int_hash". Unlike the current MD5 code, we take care to initialize it to an asymmetric state. * There's a global 256-bit random_int_secret (which we could reseed periodically). To generate a random number: * If get_random_int_hash is all-zero, seed it with fresh a half-sized SipHash key and the appropriate XOR constants. * Generate three words of random_get_entropy(), jiffies, and current->pid. (This is arbitary seed material, copied from the current code.) * Crank through that with (Half)SipHash-1-0. * Crank through the random_int_secret with (Half)SipHash-1-0. * Return v1 ^ v3. Here are the reasons: * The first step is just paranoia, but SipHash's security promise depends on starting with an asymmetric state, we want unique per-CPU states, and it's a one-time cost. * When the input words are themselves secret, there's no security advantage, and almost no speed advantage, to doing two rounds for one input word versus two words with one round each. Thus, SipHash-1. * The above is not exactly true, due to the before+after XOR pattern that SipHash uses, but I think it's true anyway. * Likewise, there's no benefit to unkeyed finalization rounds over keyed ones. That's why I just enlarged the global secret. * The per-call seed material is hashed first on general principles, because that's the novel part that might have fresh entropy. * To the extent the initial state is secret, the rounds processing the global secret are 4 finalization rounds for the initial state and the per-call entropy. * The final word(s) of the global secret might be vulnerable to analysis, due to incomplete mixing, but since the global secret is always hashed in the same order, and larger that the desired security level, the initial words should be secure. * By carrying forward the full internal state, we ensure that repeated calls return different results, and to the extent that the per-call seed material has entropy, it's preserved. * The final return is all that's needed, since the last steps in the SipRound are "v1 ^= v2" and "v3 ^= v0". It's no security loss, and a very minor speedup. * Also, this avoids directly "exposing" the final XOR with the last word of the global secret (which is made to v0). If I'm allowed to use full SipHash, some shortcuts can be taken, but I believe the above would be secure with HalfSipHash. If additional performance is required, I'd consider shrinking the global secret to 192 bits on 32-bit machines but I want more than 128 bits of ey material, and enough rounds to be equivalent to 4 finalization rounds.
prev parent reply other threads:[~2016-12-22 1:13 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 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 [this message]
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).