linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "George Spelvin" <linux@sciencehorizons.net>
To: linux@sciencehorizons.net, tytso@mit.edu
Cc: ak@linux.intel.com, davem@davemloft.net, David.Laight@aculab.com,
	djb@cr.yp.to, ebiggers3@gmail.com, eric.dumazet@gmail.com,
	hannes@stressinduktion.org, Jason@zx2c4.com,
	jeanphilippe.aumasson@gmail.com,
	kernel-hardening@lists.openwall.com,
	linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org,
	luto@amacapital.net, netdev@vger.kernel.org, tom@herbertland.com,
	torvalds@linux-foundation.org, vegard.nossum@gmail.com
Subject: Re: HalfSipHash Acceptable Usage
Date: 21 Dec 2016 20:13:35 -0500	[thread overview]
Message-ID: <20161222011335.8023.qmail@ns.sciencehorizons.net> (raw)
In-Reply-To: <20161221222702.h2vboms776zpgpi4@thunk.org>

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[4]".  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.

      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 \
    --in-reply-to=20161222011335.8023.qmail@ns.sciencehorizons.net \
    --to=linux@sciencehorizons.net \
    --cc=David.Laight@aculab.com \
    --cc=Jason@zx2c4.com \
    --cc=ak@linux.intel.com \
    --cc=davem@davemloft.net \
    --cc=djb@cr.yp.to \
    --cc=ebiggers3@gmail.com \
    --cc=eric.dumazet@gmail.com \
    --cc=hannes@stressinduktion.org \
    --cc=jeanphilippe.aumasson@gmail.com \
    --cc=kernel-hardening@lists.openwall.com \
    --cc=linux-crypto@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luto@amacapital.net \
    --cc=netdev@vger.kernel.org \
    --cc=tom@herbertland.com \
    --cc=torvalds@linux-foundation.org \
    --cc=tytso@mit.edu \
    --cc=vegard.nossum@gmail.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).