From patchwork Wed Dec 21 23:02:13 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Jason A. Donenfeld" X-Patchwork-Id: 9483877 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 2356C600C1 for ; Wed, 21 Dec 2016 23:03:09 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1523428285 for ; Wed, 21 Dec 2016 23:03:09 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 09DDC2849D; Wed, 21 Dec 2016 23:03:09 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from mother.openwall.net (mother.openwall.net [195.42.179.200]) by mail.wl.linuxfoundation.org (Postfix) with SMTP id DCBF628285 for ; Wed, 21 Dec 2016 23:03:07 +0000 (UTC) Received: (qmail 21776 invoked by uid 550); 21 Dec 2016 23:02:57 -0000 Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: kernel-hardening@lists.openwall.com Delivered-To: mailing list kernel-hardening@lists.openwall.com Received: (qmail 19836 invoked from network); 21 Dec 2016 23:02:48 -0000 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=zx2c4.com; h=from:to:cc :subject:date:message-id:in-reply-to:references; s=mail; bh=AZt6 gAJ49vwVpjuS5z+W086v85c=; b=EUyyasAPPiUTpvke2PXgdRN6zGd1+90P8BMx pSehEx+sccu8/dFSzR8fnIm77OPyTaXKsFHy1fZojnuSI02qlvOCAVni0x/2FYvT agN7vfeoTyv7dM6g8VkbpbIpOz11nCa+ohIvvFie3pp6Ki9+a0SllynLzRjDQyBY oI+qiPu1lU12hHloNuZ8BL3ukCczCJmSVjmsLugkbaTVGbuCeYsx5nNjqiDYKsrW RHNQGKL3rTn268dGD9TV8X/bCrPy+T6RANRCU84MA9ZDa9r8dvpe4hjesJW2naKY qGo8YYEDmwVcCvY1Kbg/XPySNRVrwm3fRqfP3dcz1G2epOtNJw== From: "Jason A. Donenfeld" To: Netdev , kernel-hardening@lists.openwall.com, LKML , linux-crypto@vger.kernel.org, David Laight , Ted Tso , Hannes Frederic Sowa , edumazet@google.com, Linus Torvalds , Eric Biggers , Tom Herbert , ak@linux.intel.com, davem@davemloft.net, luto@amacapital.net, Jean-Philippe Aumasson Cc: "Jason A. Donenfeld" Date: Thu, 22 Dec 2016 00:02:13 +0100 Message-Id: <20161221230216.25341-4-Jason@zx2c4.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20161221230216.25341-1-Jason@zx2c4.com> References: <20161216030328.11602-1-Jason@zx2c4.com> <20161221230216.25341-1-Jason@zx2c4.com> Subject: [kernel-hardening] [PATCH v7 3/6] random: use SipHash in place of MD5 X-Virus-Scanned: ClamAV using ClamSMTP This duplicates the current algorithm for get_random_int/long, but uses siphash instead. This comes with several benefits. It's certainly faster and more cryptographically secure than MD5. This patch also separates hashed fields into three values instead of one, in order to increase diffusion. The previous MD5 algorithm used a per-cpu MD5 state, which caused successive calls to the function to chain upon each other. While it's not entirely clear that this kind of chaining is absolutely necessary when using a secure PRF like siphash, it can't hurt, and the timing of the call chain does add a degree of natural entropy. So, in keeping with this design, instead of the massive per-cpu 64-byte MD5 state, there is instead a per-cpu previously returned value for chaining. The speed benefits are substantial: | siphash | md5 | speedup | ------------------------------ get_random_long | 137130 | 415983 | 3.03x | get_random_int | 86384 | 343323 | 3.97x | Signed-off-by: Jason A. Donenfeld Cc: Jean-Philippe Aumasson Cc: Ted Tso --- drivers/char/random.c | 84 +++++++++++++++++++++++++++++--------------------- include/linux/random.h | 1 - init/main.c | 1 - 3 files changed, 49 insertions(+), 37 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d6876d506220..ea9858d9d8b4 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -262,6 +262,7 @@ #include #include #include +#include #include #include @@ -2042,17 +2043,31 @@ struct ctl_table random_table[] = { }; #endif /* CONFIG_SYSCTL */ -static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned; -int random_int_secret_init(void) +struct random_int_secret { + siphash_key_t secret; + u64 chaining; + unsigned long birthdate; + bool initialized; +}; +static DEFINE_PER_CPU(struct random_int_secret, random_int_secret); + +enum { + SECRET_ROTATION_TIME = HZ * 60 * 5 +}; + +static struct random_int_secret *get_random_int_secret(void) { - get_random_bytes(random_int_secret, sizeof(random_int_secret)); - return 0; + struct random_int_secret *secret = &get_cpu_var(random_int_secret); + if (unlikely(!secret->initialized || + !time_is_after_jiffies(secret->birthdate + SECRET_ROTATION_TIME))) { + secret->initialized = true; + secret->birthdate = jiffies; + get_random_bytes(secret->secret, sizeof(secret->secret)); + } + return secret; } -static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) - __aligned(sizeof(unsigned long)); - /* * Get a random word for internal kernel use only. Similar to urandom but * with the goal of minimal entropy pool depletion. As a result, the random @@ -2061,20 +2076,20 @@ static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) */ unsigned int get_random_int(void) { - __u32 *hash; - unsigned int ret; - - if (arch_get_random_int(&ret)) - return ret; - - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = hash[0]; - put_cpu_var(get_random_int_hash); - - return ret; + unsigned int arch_result; + u64 result; + struct random_int_secret *secret; + + if (arch_get_random_int(&arch_result)) + return arch_result; + + secret = get_random_int_secret(); + result = siphash_3u64(secret->chaining, jiffies, + (u64)random_get_entropy() + current->pid, + secret->secret); + secret->chaining += result; + put_cpu_var(secret); + return result; } EXPORT_SYMBOL(get_random_int); @@ -2083,20 +2098,19 @@ EXPORT_SYMBOL(get_random_int); */ unsigned long get_random_long(void) { - __u32 *hash; - unsigned long ret; - - if (arch_get_random_long(&ret)) - return ret; - - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = *(unsigned long *)hash; - put_cpu_var(get_random_int_hash); - - return ret; + unsigned long arch_result; + u64 result; + struct random_int_secret *secret; + + if (arch_get_random_long(&arch_result)) + return arch_result; + + secret = get_random_int_secret(); + result = siphash_3u64(secret->chaining, jiffies, random_get_entropy() + + current->pid, secret->secret); + secret->chaining += result; + put_cpu_var(secret); + return result; } EXPORT_SYMBOL(get_random_long); diff --git a/include/linux/random.h b/include/linux/random.h index 7bd2403e4fef..16ab429735a7 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -37,7 +37,6 @@ extern void get_random_bytes(void *buf, int nbytes); extern int add_random_ready_callback(struct random_ready_callback *rdy); extern void del_random_ready_callback(struct random_ready_callback *rdy); extern void get_random_bytes_arch(void *buf, int nbytes); -extern int random_int_secret_init(void); #ifndef MODULE extern const struct file_operations random_fops, urandom_fops; diff --git a/init/main.c b/init/main.c index 23c275cca73a..a3af9296cafd 100644 --- a/init/main.c +++ b/init/main.c @@ -879,7 +879,6 @@ static void __init do_basic_setup(void) do_ctors(); usermodehelper_enable(); do_initcalls(); - random_int_secret_init(); } static void __init do_pre_smp_initcalls(void)