Kernel-hardening archive on lore.kernel.org
 help / color / Atom feed
From: Kristen Carlson Accardi <kristen@linux.intel.com>
To: tglx@linutronix.de, mingo@redhat.com, bp@alien8.de,
	hpa@zytor.com, arjan@linux.intel.com, keescook@chromium.org
Cc: rick.p.edgecombe@intel.com, x86@kernel.org,
	linux-kernel@vger.kernel.org,
	kernel-hardening@lists.openwall.com,
	Kristen Carlson Accardi <kristen@linux.intel.com>
Subject: [RFC PATCH 04/11] x86/boot/KASLR: Introduce PRNG for faster shuffling
Date: Wed,  5 Feb 2020 14:39:43 -0800
Message-ID: <20200205223950.1212394-5-kristen@linux.intel.com> (raw)
In-Reply-To: <20200205223950.1212394-1-kristen@linux.intel.com>

From: Kees Cook <keescook@chromium.org>

This *might* improve shuffling speed at boot. Possibly only marginally.
This has not yet been tested, and would need to have some performance
tests run to determine if it helps before merging.

(notes from Kristen) - initial performance tests suggest that any
improvement is indeed marginal. However, this code is useful
for using a known seed.

Signed-off-by: Kees Cook <keescook@chromium.org>
Signed-off-by: Kristen Carlson Accardi <kristen@linux.intel.com>
---
 arch/x86/boot/compressed/kaslr.c |  4 +--
 arch/x86/include/asm/kaslr.h     |  3 +-
 arch/x86/lib/kaslr.c             | 50 +++++++++++++++++++++++++++++++-
 arch/x86/mm/init.c               |  2 +-
 arch/x86/mm/kaslr.c              |  2 +-
 5 files changed, 55 insertions(+), 6 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index d7408af55738..ae4dce76a9bd 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -598,7 +598,7 @@ static unsigned long slots_fetch_random(void)
 	if (slot_max == 0)
 		return 0;
 
-	slot = kaslr_get_random_long("Physical") % slot_max;
+	slot = kaslr_get_random_seed("Physical") % slot_max;
 
 	for (i = 0; i < slot_area_index; i++) {
 		if (slot >= slot_areas[i].num) {
@@ -880,7 +880,7 @@ static unsigned long find_random_virt_addr(unsigned long minimum,
 	slots = (KERNEL_IMAGE_SIZE - minimum - image_size) /
 		 CONFIG_PHYSICAL_ALIGN + 1;
 
-	random_addr = kaslr_get_random_long("Virtual") % slots;
+	random_addr = kaslr_get_random_seed("Virtual") % slots;
 
 	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
 }
diff --git a/arch/x86/include/asm/kaslr.h b/arch/x86/include/asm/kaslr.h
index db7ba2feb947..47d5b25e5b11 100644
--- a/arch/x86/include/asm/kaslr.h
+++ b/arch/x86/include/asm/kaslr.h
@@ -2,7 +2,8 @@
 #ifndef _ASM_KASLR_H_
 #define _ASM_KASLR_H_
 
-unsigned long kaslr_get_random_long(const char *purpose);
+unsigned long kaslr_get_random_seed(const char *purpose);
+unsigned long kaslr_get_prandom_long(void);
 
 #ifdef CONFIG_RANDOMIZE_MEMORY
 void kernel_randomize_memory(void);
diff --git a/arch/x86/lib/kaslr.c b/arch/x86/lib/kaslr.c
index 2b3eb8c948a3..41b5610855a3 100644
--- a/arch/x86/lib/kaslr.c
+++ b/arch/x86/lib/kaslr.c
@@ -46,7 +46,7 @@ static inline u16 i8254(void)
 	return timer;
 }
 
-unsigned long kaslr_get_random_long(const char *purpose)
+unsigned long kaslr_get_random_seed(const char *purpose)
 {
 #ifdef CONFIG_X86_64
 	const unsigned long mix_const = 0x5d6008cbf3848dd3UL;
@@ -96,3 +96,51 @@ unsigned long kaslr_get_random_long(const char *purpose)
 
 	return random;
 }
+
+/*
+ * 64bit variant of Bob Jenkins' public domain PRNG
+ * 256 bits of internal state
+ */
+struct prng_state {
+	u64 a, b, c, d;
+};
+
+static struct prng_state state;
+static bool initialized;
+
+#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;
+}
+
+static void prng_init(struct prng_state *state)
+{
+	int i;
+
+	state->a = kaslr_get_random_seed(NULL);
+	state->b = kaslr_get_random_seed(NULL);
+	state->c = kaslr_get_random_seed(NULL);
+	state->d = kaslr_get_random_seed(NULL);
+
+	for (i = 0; i < 30; ++i)
+		(void)prng_u64(state);
+
+	initialized = true;
+}
+
+unsigned long kaslr_get_prandom_long(void)
+{
+	if (!initialized)
+		prng_init(&state);
+
+	return prng_u64(&state);
+}
diff --git a/arch/x86/mm/init.c b/arch/x86/mm/init.c
index e7bb483557c9..c974dbab2293 100644
--- a/arch/x86/mm/init.c
+++ b/arch/x86/mm/init.c
@@ -722,7 +722,7 @@ void __init poking_init(void)
 	 */
 	poking_addr = TASK_UNMAPPED_BASE;
 	if (IS_ENABLED(CONFIG_RANDOMIZE_BASE))
-		poking_addr += (kaslr_get_random_long("Poking") & PAGE_MASK) %
+		poking_addr += (kaslr_get_random_seed("Poking") & PAGE_MASK) %
 			(TASK_SIZE - TASK_UNMAPPED_BASE - 3 * PAGE_SIZE);
 
 	if (((poking_addr + PAGE_SIZE) & ~PMD_MASK) == 0)
diff --git a/arch/x86/mm/kaslr.c b/arch/x86/mm/kaslr.c
index dc6182eecefa..b30bd1db7543 100644
--- a/arch/x86/mm/kaslr.c
+++ b/arch/x86/mm/kaslr.c
@@ -123,7 +123,7 @@ void __init kernel_randomize_memory(void)
 	for (i = 0; i < ARRAY_SIZE(kaslr_regions); i++)
 		remain_entropy -= get_padding(&kaslr_regions[i]);
 
-	prandom_seed_state(&rand_state, kaslr_get_random_long("Memory"));
+	prandom_seed_state(&rand_state, kaslr_get_random_seed("Memory"));
 
 	for (i = 0; i < ARRAY_SIZE(kaslr_regions); i++) {
 		unsigned long entropy;
-- 
2.24.1


  parent 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 ` Kristen Carlson Accardi [this message]
2020-02-06  1:11   ` [RFC PATCH 04/11] x86/boot/KASLR: Introduce PRNG for faster shuffling Andy Lutomirski
2020-02-06 15:10   ` Jason A. Donenfeld
2020-02-07  7:23     ` Jean-Philippe Aumasson
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=20200205223950.1212394-5-kristen@linux.intel.com \
    --to=kristen@linux.intel.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=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