Kernel-hardening archive on lore.kernel.org
 help / color / Atom feed
From: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
To: "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc: Kristen Carlson Accardi <kristen@linux.intel.com>,
	keescook@chromium.org, tglx@linutronix.de,  mingo@redhat.com,
	bp@alien8.de, hpa@zytor.com, arjan@linux.intel.com,
	 rick.p.edgecombe@intel.com, x86@kernel.org,
	 LKML <linux-kernel@vger.kernel.org>,
	kernel-hardening@lists.openwall.com
Subject: Re: [RFC PATCH 04/11] x86/boot/KASLR: Introduce PRNG for faster shuffling
Date: Fri, 7 Feb 2020 08:23:53 +0100
Message-ID: <CAGiyFdes26XnNeDfaz-vkm+bU7MBYQiK3xty2EigGjOXBGui2w@mail.gmail.com> (raw)
In-Reply-To: <20200206151001.GA280489@zx2c4.com>

[-- Attachment #1: Type: text/plain, Size: 2317 bytes --]

Let me share my 2 cents:

That permutation might be safe but afaict it hasn't been analyzed wrt
modern cryptographic techniques and there might well be differential
characteristics, statistical biases, etc.

What about just using SipHash's permutation, already in the kernel? It
works on 4*u64 words too, and 6 rounds would be enough.

Doing a basic ops count, we currently have 5 group operations and 3
rotations per round or 150 and 90 for the 30 init rounds. With SipHash it'd
be 48 and 36 with the proposed 6 rounds. Probably insignificant speed wise
as init is only done once but just to show that we'd get both better
security assurance and better performance.


On Thu, Feb 6, 2020 at 4:10 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote:

> Hey Kees,
>
> On Wed, Feb 05, 2020 at 02:39:43PM -0800, Kristen Carlson Accardi wrote:
> > +#define rot(x, k) (((x)<<(k))|((x)>>(64-(k))))
> > +static u64 prng_u64(struct prng_state *x)
> > +{
> > +     u64 e;
> > +
> > +     e = x->a - rot(x->b, 7);
> > +     x->a = x->b ^ rot(x->c, 13);
> > +     x->b = x->c + rot(x->d, 37);
> > +     x->c = x->d + e;
> > +     x->d = e + x->a;
> > +
> > +     return x->d;
> > +}
>
> I haven't looked closely at where the original entropy sources are
> coming from and how all this works, but on first glance, this prng
> doesn't look like an especially cryptographically secure one. I realize
> that isn't necessarily your intention (you're focused on speed), but
> actually might this be sort of important? If I understand correctly, the
> objective of this patch set is so that leaking the address of one
> function doesn't leak the address of all other functions, as is the case
> with fixed-offset kaslr. But if you leak the addresses of _some_ set of
> functions, and your prng is bogus, might it be possible to figure out
> the rest? For some prngs, if you give me the output stream of a few
> numbers, I can predict the rest. For others, it's not this straight
> forward, but there are some varieties of similar attacks. If any of that
> set of concerns turns out to apply to your prng_u64 here, would that
> undermine kaslr in similar ways as the current fixed-offset variety? Or
> does it not matter because it's some kind of blinded fixed-size shuffle
> with complex reasoning that makes this not a problem?
>
> Jason
>

[-- Attachment #2: Type: text/html, Size: 2943 bytes --]

  reply index

Thread overview: 73+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-02-05 22:39 [RFC PATCH 00/11] Finer grained kernel address space randomization Kristen Carlson Accardi
2020-02-05 22:39 ` [RFC PATCH 01/11] modpost: Support >64K sections Kristen Carlson Accardi
2020-02-06 12:38   ` Kees Cook
2020-02-05 22:39 ` [RFC PATCH 02/11] x86: tools/relocs: Support >64K section headers Kristen Carlson Accardi
2020-02-06 12:39   ` Kees Cook
2020-02-05 22:39 ` [RFC PATCH 03/11] x86/boot: Allow a "silent" kaslr random byte fetch Kristen Carlson Accardi
2020-02-06  1:08   ` Andy Lutomirski
2020-02-06 11:48     ` Kees Cook
2020-02-06 16:58     ` Kristen Carlson Accardi
2020-02-05 22:39 ` [RFC PATCH 04/11] x86/boot/KASLR: Introduce PRNG for faster shuffling Kristen Carlson Accardi
2020-02-06  1:11   ` Andy Lutomirski
2020-02-06 15:10   ` Jason A. Donenfeld
2020-02-07  7:23     ` Jean-Philippe Aumasson [this message]
2020-02-07  9:05       ` Kees Cook
2020-02-07 16:52         ` Kristen Carlson Accardi
2020-02-05 22:39 ` [RFC PATCH 05/11] x86: Makefile: Add build and config option for CONFIG_FG_KASLR Kristen Carlson Accardi
2020-02-06 10:30   ` Peter Zijlstra
2020-02-06 11:52     ` Kees Cook
2020-02-25 17:55   ` Arvind Sankar
2020-02-26 19:13     ` Kristen Carlson Accardi
2020-03-24 21:24     ` Kristen Carlson Accardi
2020-03-25 15:34       ` Kees Cook
2020-02-05 22:39 ` [RFC PATCH 06/11] x86: make sure _etext includes function sections Kristen Carlson Accardi
2020-02-06 12:26   ` Kees Cook
2020-02-06 13:15     ` Jann Horn
2020-02-06 16:27       ` David Laight
2020-02-06 14:39     ` Arvind Sankar
2020-02-06 15:29       ` Arvind Sankar
2020-02-06 16:11         ` Andy Lutomirski
2020-02-06 14:57     ` Arvind Sankar
2020-02-06 15:45       ` Arvind Sankar
2020-02-06 19:41     ` Kristen Carlson Accardi
2020-02-06 20:02       ` Andy Lutomirski
2020-02-07  9:24         ` Peter Zijlstra
2020-02-10  1:43           ` Kees Cook
2020-02-10 10:51             ` Peter Zijlstra
2020-02-10 15:54               ` Arjan van de Ven
2020-02-10 16:36                 ` Arvind Sankar
2020-02-21 19:50                   ` Josh Poimboeuf
2020-02-21 23:05                     ` Arvind Sankar
2020-02-05 22:39 ` [RFC PATCH 07/11] x86/tools: Adding relative relocs for randomized functions Kristen Carlson Accardi
2020-02-06 12:37   ` Kees Cook
2020-02-05 22:39 ` [RFC PATCH 08/11] x86: Add support for finer grained KASLR Kristen Carlson Accardi
2020-02-06  1:17   ` Andy Lutomirski
2020-02-06 11:56     ` Kees Cook
2020-02-06 17:36       ` Kristen Carlson Accardi
2020-02-06 10:38   ` Peter Zijlstra
2020-02-06 12:06     ` Kees Cook
2020-02-06 14:52       ` Peter Zijlstra
2020-02-06 17:25         ` Kristen Carlson Accardi
2020-02-06 17:35           ` Peter Zijlstra
2020-02-06 17:43             ` Kristen Carlson Accardi
2020-02-25 17:49   ` Arvind Sankar
2020-02-26 19:26     ` Kristen Carlson Accardi
2020-02-05 22:39 ` [RFC PATCH 09/11] kallsyms: hide layout and expose seed Kristen Carlson Accardi
2020-02-06 12:32   ` Kees Cook
2020-02-06 17:51     ` Kristen Carlson Accardi
2020-02-06 19:27       ` Jann Horn
2020-03-02 19:01         ` Kristen Carlson Accardi
2020-03-02 19:08           ` Kees Cook
2020-03-02 19:19             ` Kristen Carlson Accardi
2020-02-27  2:42       ` Baoquan He
2020-02-27 16:02         ` Kees Cook
2020-02-28  3:36           ` Baoquan He
2020-02-05 22:39 ` [RFC PATCH 10/11] module: Reorder functions Kristen Carlson Accardi
2020-02-06 12:41   ` Kees Cook
2020-02-11 12:39     ` Jessica Yu
2020-02-05 22:39 ` [RFC PATCH 11/11] x86/boot: Move "boot heap" out of .bss Kristen Carlson Accardi
2020-02-06  0:11   ` Arvind Sankar
2020-02-06  0:33     ` Kristen Carlson Accardi
2020-02-06 11:13     ` Kees Cook
2020-02-06 14:25       ` Arvind Sankar
2020-02-06 21:32         ` Kees Cook

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=CAGiyFdes26XnNeDfaz-vkm+bU7MBYQiK3xty2EigGjOXBGui2w@mail.gmail.com \
    --to=jeanphilippe.aumasson@gmail.com \
    --cc=Jason@zx2c4.com \
    --cc=arjan@linux.intel.com \
    --cc=bp@alien8.de \
    --cc=hpa@zytor.com \
    --cc=keescook@chromium.org \
    --cc=kernel-hardening@lists.openwall.com \
    --cc=kristen@linux.intel.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@redhat.com \
    --cc=rick.p.edgecombe@intel.com \
    --cc=tglx@linutronix.de \
    --cc=x86@kernel.org \
    /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

Kernel-hardening archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/kernel-hardening/0 kernel-hardening/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 kernel-hardening kernel-hardening/ https://lore.kernel.org/kernel-hardening \
		kernel-hardening@lists.openwall.com
	public-inbox-index kernel-hardening

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/com.openwall.lists.kernel-hardening


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git