From: Andy Lutomirski <luto@amacapital.net>
To: George Spelvin <linux@sciencehorizons.net>
Cc: Andrew Lutomirski <luto@kernel.org>,
Andi Kleen <ak@linux.intel.com>,
"David S. Miller" <davem@davemloft.net>,
David Laight <David.Laight@aculab.com>,
"D. J. Bernstein" <djb@cr.yp.to>,
Eric Biggers <ebiggers3@gmail.com>,
Eric Dumazet <eric.dumazet@gmail.com>,
Hannes Frederic Sowa <hannes@stressinduktion.org>,
"Jason A. Donenfeld" <Jason@zx2c4.com>,
Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>,
"kernel-hardening@lists.openwall.com"
<kernel-hardening@lists.openwall.com>,
Linux Crypto Mailing List <linux-crypto@vger.kernel.org>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
Network Development <netdev@vger.kernel.org>,
Tom Herbert <tom@herbertland.com>,
Linus Torvalds <torvalds@linux-foundation.org>,
"Ted Ts'o" <tytso@mit.edu>,
Vegard Nossum <vegard.nossum@gmail.com>
Subject: Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)
Date: Wed, 21 Dec 2016 21:42:45 -0800 [thread overview]
Message-ID: <CALCETrU84-EeU91AkoAZLWrhK=FSrBgV139oSSM-Vw5Mc0mdAg@mail.gmail.com> (raw)
In-Reply-To: <20161222050138.12011.qmail@ns.sciencehorizons.net>
On Wed, Dec 21, 2016 at 9:01 PM, George Spelvin
<linux@sciencehorizons.net> wrote:
> Andy Lutomirski wrote:
>> I don't even think it needs that. This is just adding a
>> non-destructive final operation, right?
>
> It is, but the problem is that SipHash is intended for *small* inputs,
> so the standard implementations aren't broken into init/update/final
> functions.
>
> There's just one big function that keeps the state variables in
> registers and never stores them anywhere.
>
> If we *had* init/update/final functions, then it would be trivial.
>
>> Just to clarify, if we replace SipHash with a black box, I think this
>> effectively means, where "entropy" is random_get_entropy() || jiffies
>> || current->pid:
>
>> The first call returns H(random seed || entropy_0 || secret). The
>> second call returns H(random seed || entropy_0 || secret || entropy_1
>> || secret). Etc.
>
> Basically, yes. I was skipping the padding byte and keying the
> finalization rounds on the grounds of "can't hurt and might help",
> but we could do it a more standard way.
>
>> If not, then I have a fairly strong preference to keep whatever
>> construction we come up with consistent with something that could
>> actually happen with invocations of unmodified SipHash -- then all the
>> security analysis on SipHash goes through.
>
> Okay. I don't think it makes a difference, but it's not a *big* waste
> of time. If we have finalization rounds, we can reduce the secret
> to 128 bits.
>
> If we include the padding byte, we can do one of two things:
> 1) Make the secret 184 bits, to fill up the final partial word as
> much as possible, or
> 2) Make the entropy 1 byte smaller and conceptually misalign the
> secret. What we'd actually do is remove the last byte of
> the secret and include it in the entropy words, but that's
> just a rotation of the secret between storage and hashing.
>
> Also, I assume you'd like SipHash-2-4, since you want to rely
> on a security analysis.
I haven't looked, but I assume that the analysis at least thought
about reduced rounds, so maybe other variants are okay.
>> The one thing I don't like is
>> that I don't see how to prove that you can't run it backwards if you
>> manage to acquire a memory dump. In fact, I that that there exist, at
>> least in theory, hash functions that are secure in the random oracle
>> model but that *can* be run backwards given the full state. From
>> memory, SHA-3 has exactly that property, and it would be a bit sad for
>> a CSPRNG to be reversible.
>
> Er... get_random_int() is specifically *not* designed to be resistant
> to state capture, and I didn't try. Remember, what it's used for
> is ASLR, what we're worried about is somene learning the layouts
> of still-running processes, and and if you get a memory dump, you have
> the memory layout!
True, but it's called get_random_int(), and it seems like making it
stronger, especially if the performance cost is low to zero, is a good
thing.
>
> If you want anti-backtracking, though, it's easy to add. What we
> hash is:
>
> entropy_0 || secret || output_0 || entropy_1 || secret || output_1 || ...
>
> You mix the output word right back in to the (unfinalized) state after
> generating it. This is still equivalent to unmodified back-box SipHash,
> you're just using a (conceptually independent) SipHash invocation to
> produce some of its input.
Ah, cute. This could probably be sped up by doing something like:
entropy_0 || secret || output_0 ^ entropy_1 || secret || ...
It's a little weak because the output is only 64 bits, so you could
plausibly backtrack it on a GPU or FPGA cluster or on an ASIC if the
old entropy is guessable. I suspect there are sneaky ways around it
like using output_n-1 ^ output_n-2 or similar. I'll sleep on it.
>
> The only remaining issues are:
> 1) How many rounds, and
> 2) May we use HalfSipHash?
I haven't looked closely enough to have a real opinion here. I don't
know what the security margin is believed to be.
>
> I'd *like* to persuade you that skipping the padding byte wouldn't
> invalidate any security proofs, because it's true and would simplify
> the code. But if you want 100% stock, I'm willing to cater to that.
I lean toward stock in the absence of a particularly good reason. At
the very least I'd want to read that paper carefully.
>
> Ted, what do you think?
--
Andy Lutomirski
AMA Capital Management, LLC
next prev parent reply other threads:[~2016-12-22 5:43 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-22 2:07 George's crazy full state idea (Re: HalfSipHash Acceptable Usage) Andy Lutomirski
2016-12-22 5:01 ` George Spelvin
2016-12-22 5:42 ` Andy Lutomirski [this message]
2016-12-22 8:02 ` George Spelvin
2016-12-22 16:09 ` Andy Lutomirski
2016-12-22 19:24 ` George Spelvin
2016-12-22 19:32 ` Andy Lutomirski
2016-12-22 21:11 ` George Spelvin
2016-12-22 21:38 ` Hannes Frederic Sowa
2016-12-23 0:07 ` George Spelvin
2016-12-23 12:05 ` Hannes Frederic Sowa
2016-12-23 18:26 ` George Spelvin
2016-12-23 20:48 ` Hannes Frederic Sowa
2016-12-23 23:39 ` George Spelvin
2016-12-24 0:12 ` Hannes Frederic Sowa
2016-12-24 1:17 ` George Spelvin
2016-12-28 5:23 ` Hannes Frederic Sowa
2016-12-28 10:04 ` George Spelvin
2016-12-22 2:40 Jason A. Donenfeld
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='CALCETrU84-EeU91AkoAZLWrhK=FSrBgV139oSSM-Vw5Mc0mdAg@mail.gmail.com' \
--to=luto@amacapital.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=linux@sciencehorizons.net \
--cc=luto@kernel.org \
--cc=netdev@vger.kernel.org \
--cc=tom@herbertland.com \
--cc=torvalds@linux-foundation.org \
--cc=tytso@mit.edu \
--cc=vegard.nossum@gmail.com \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).