From patchwork Mon Sep 21 07:58:17 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788655 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id DEF7A1668 for ; Mon, 21 Sep 2020 07:59:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C720D21789 for ; Mon, 21 Sep 2020 07:59:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726318AbgIUH7S (ORCPT ); Mon, 21 Sep 2020 03:59:18 -0400 Received: from mx2.suse.de ([195.135.220.15]:56496 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726358AbgIUH7R (ORCPT ); Mon, 21 Sep 2020 03:59:17 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 2C92AB4FB; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 01/41] random: remove dead code in credit_entropy_bits() Date: Mon, 21 Sep 2020 09:58:17 +0200 Message-Id: <20200921075857.4424-2-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Since commit 90ea1c6436d2 ("random: remove the blocking pool") the local has_initialized in credit_entropy_bits() won't get set anymore and the corresponding if-clause became dead code. Remove it as well as the has_initialized variable itself from credit_entropy_bits(). Signed-off-by: Nicolai Stange --- drivers/char/random.c | 7 +------ 1 file changed, 1 insertion(+), 6 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d20ba1b104ca..0580968fd28c 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -660,7 +660,7 @@ static void process_random_ready_list(void) */ static void credit_entropy_bits(struct entropy_store *r, int nbits) { - int entropy_count, orig, has_initialized = 0; + int entropy_count, orig; const int pool_size = r->poolinfo->poolfracbits; int nfrac = nbits << ENTROPY_SHIFT; @@ -717,11 +717,6 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) goto retry; - if (has_initialized) { - r->initialized = 1; - kill_fasync(&fasync, SIGIO, POLL_IN); - } - trace_credit_entropy_bits(r->name, nbits, entropy_count >> ENTROPY_SHIFT, _RET_IP_); From patchwork Mon Sep 21 07:58:18 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788739 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 0D90C618 for ; Mon, 21 Sep 2020 08:02:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F21EB20BED for ; Mon, 21 Sep 2020 08:01:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726442AbgIUH7R (ORCPT ); Mon, 21 Sep 2020 03:59:17 -0400 Received: from mx2.suse.de ([195.135.220.15]:56334 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726211AbgIUH7R (ORCPT ); Mon, 21 Sep 2020 03:59:17 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 29F86B340; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 02/41] random: remove dead code for nbits < 0 in credit_entropy_bits() Date: Mon, 21 Sep 2020 09:58:18 +0200 Message-Id: <20200921075857.4424-3-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The nbits argument to credit_entropy_bits() is never negative and the branch handling it is dead code. Remove it. The code for handling the regular nbits > 0 case used to live in the corresponding else branch, but has now been lifted up to function scope. Move the declaration of 'pnfrac' to the function prologue in order to adhere to C99 rules. Likewise, move the declaration of 's' into the body loop, the only scope it's referenced from. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 69 ++++++++++++++++++++----------------------- 1 file changed, 32 insertions(+), 37 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 0580968fd28c..c4b7bdbd460e 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -654,7 +654,7 @@ static void process_random_ready_list(void) } /* - * Credit (or debit) the entropy store with n bits of entropy. + * Credit the entropy store with n bits of entropy. * Use credit_entropy_bits_safe() if the value comes from userspace * or otherwise should be checked for extreme values. */ @@ -663,50 +663,45 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) int entropy_count, orig; const int pool_size = r->poolinfo->poolfracbits; int nfrac = nbits << ENTROPY_SHIFT; + int pnfrac; if (!nbits) return; retry: entropy_count = orig = READ_ONCE(r->entropy_count); - if (nfrac < 0) { - /* Debit */ - entropy_count += nfrac; - } else { - /* - * Credit: we have to account for the possibility of - * overwriting already present entropy. Even in the - * ideal case of pure Shannon entropy, new contributions - * approach the full value asymptotically: - * - * entropy <- entropy + (pool_size - entropy) * - * (1 - exp(-add_entropy/pool_size)) - * - * For add_entropy <= pool_size/2 then - * (1 - exp(-add_entropy/pool_size)) >= - * (add_entropy/pool_size)*0.7869... - * so we can approximate the exponential with - * 3/4*add_entropy/pool_size and still be on the - * safe side by adding at most pool_size/2 at a time. - * - * The use of pool_size-2 in the while statement is to - * prevent rounding artifacts from making the loop - * arbitrarily long; this limits the loop to log2(pool_size)*2 - * turns no matter how large nbits is. - */ - int pnfrac = nfrac; - const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2; + /* + * Credit: we have to account for the possibility of + * overwriting already present entropy. Even in the + * ideal case of pure Shannon entropy, new contributions + * approach the full value asymptotically: + * + * entropy <- entropy + (pool_size - entropy) * + * (1 - exp(-add_entropy/pool_size)) + * + * For add_entropy <= pool_size/2 then + * (1 - exp(-add_entropy/pool_size)) >= + * (add_entropy/pool_size)*0.7869... + * so we can approximate the exponential with + * 3/4*add_entropy/pool_size and still be on the + * safe side by adding at most pool_size/2 at a time. + * + * The use of pool_size-2 in the while statement is to + * prevent rounding artifacts from making the loop + * arbitrarily long; this limits the loop to log2(pool_size)*2 + * turns no matter how large nbits is. + */ + pnfrac = nfrac; + do { /* The +2 corresponds to the /4 in the denominator */ + const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2; + unsigned int anfrac = min(pnfrac, pool_size/2); + unsigned int add = + ((pool_size - entropy_count)*anfrac*3) >> s; - do { - unsigned int anfrac = min(pnfrac, pool_size/2); - unsigned int add = - ((pool_size - entropy_count)*anfrac*3) >> s; - - entropy_count += add; - pnfrac -= anfrac; - } while (unlikely(entropy_count < pool_size-2 && pnfrac)); - } + entropy_count += add; + pnfrac -= anfrac; + } while (unlikely(entropy_count < pool_size-2 && pnfrac)); if (WARN_ON(entropy_count < 0)) { pr_warn("negative entropy/overflow: pool %s count %d\n", From patchwork Mon Sep 21 07:58:19 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788653 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 87BF6618 for ; Mon, 21 Sep 2020 07:59:18 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 779DD20874 for ; Mon, 21 Sep 2020 07:59:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726405AbgIUH7R (ORCPT ); Mon, 21 Sep 2020 03:59:17 -0400 Received: from mx2.suse.de ([195.135.220.15]:56444 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726318AbgIUH7R (ORCPT ); Mon, 21 Sep 2020 03:59:17 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 2E41AB4FC; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 03/41] random: prune dead assignment to entropy_bits in credit_entropy_bits() Date: Mon, 21 Sep 2020 09:58:19 +0200 Message-Id: <20200921075857.4424-4-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Since commit 90ea1c6436d2 ("random: remove the blocking pool"), the last assignment to 'entropy_bits' is dead. Remove it. While at it, move the declaration of 'entropy_bits' one scope down and make it const: it's not used anywhere outside and never updated after initialization. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index c4b7bdbd460e..14c39608cc17 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -716,13 +716,12 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) entropy_count >> ENTROPY_SHIFT, _RET_IP_); if (r == &input_pool) { - int entropy_bits = entropy_count >> ENTROPY_SHIFT; - if (crng_init < 2) { + const int entropy_bits = entropy_count >> ENTROPY_SHIFT; + if (entropy_bits < 128) return; crng_reseed(&primary_crng, r); - entropy_bits = ENTROPY_BITS(r); } } } From patchwork Mon Sep 21 07:58:20 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788737 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id F17A4618 for ; Mon, 21 Sep 2020 08:01:56 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E1AAC20874 for ; Mon, 21 Sep 2020 08:01:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726497AbgIUIBw (ORCPT ); Mon, 21 Sep 2020 04:01:52 -0400 Received: from mx2.suse.de ([195.135.220.15]:56606 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726402AbgIUH7S (ORCPT ); Mon, 21 Sep 2020 03:59:18 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 6CE26B500; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 04/41] random: drop 'reserved' parameter from extract_entropy() Date: Mon, 21 Sep 2020 09:58:20 +0200 Message-Id: <20200921075857.4424-5-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Since commit 43d8a72cd985 ("random: remove variable limit") all call sites of extract_entropy() pass in zero for the 'reserved' argument and the corresponding code in account() is effectively dead. Remove it and the drop the now unused 'reserved' argument from extract_entropy() as well as from account() called therefrom. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 17 ++++++----------- 1 file changed, 6 insertions(+), 11 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 14c39608cc17..35e381be20fe 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -506,7 +506,7 @@ struct entropy_store { }; static ssize_t extract_entropy(struct entropy_store *r, void *buf, - size_t nbytes, int min, int rsvd); + size_t nbytes, int min); static ssize_t _extract_entropy(struct entropy_store *r, void *buf, size_t nbytes, int fips); @@ -944,7 +944,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) } buf; if (r) { - num = extract_entropy(r, &buf, 32, 16, 0); + num = extract_entropy(r, &buf, 32, 16); if (num == 0) return; } else { @@ -1330,8 +1330,7 @@ EXPORT_SYMBOL_GPL(add_disk_randomness); * This function decides how many bytes to actually take from the * given pool, and also debits the entropy count accordingly. */ -static size_t account(struct entropy_store *r, size_t nbytes, int min, - int reserved) +static size_t account(struct entropy_store *r, size_t nbytes, int min) { int entropy_count, orig, have_bytes; size_t ibytes, nfrac; @@ -1345,8 +1344,6 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min, /* never pull more than available */ have_bytes = entropy_count >> (ENTROPY_SHIFT + 3); - if ((have_bytes -= reserved) < 0) - have_bytes = 0; ibytes = min_t(size_t, ibytes, have_bytes); if (ibytes < min) ibytes = 0; @@ -1469,12 +1466,10 @@ static ssize_t _extract_entropy(struct entropy_store *r, void *buf, * returns it in a buffer. * * The min parameter specifies the minimum amount we can pull before - * failing to avoid races that defeat catastrophic reseeding while the - * reserved parameter indicates how much entropy we must leave in the - * pool after each pull to avoid starving other readers. + * failing to avoid races that defeat catastrophic reseeding. */ static ssize_t extract_entropy(struct entropy_store *r, void *buf, - size_t nbytes, int min, int reserved) + size_t nbytes, int min) { __u8 tmp[EXTRACT_SIZE]; unsigned long flags; @@ -1495,7 +1490,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, } trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); - nbytes = account(r, nbytes, min, reserved); + nbytes = account(r, nbytes, min); return _extract_entropy(r, buf, nbytes, fips_enabled); } From patchwork Mon Sep 21 07:58:21 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788663 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 510256CA for ; Mon, 21 Sep 2020 07:59:25 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 36E1A214F1 for ; Mon, 21 Sep 2020 07:59:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726508AbgIUH7X (ORCPT ); Mon, 21 Sep 2020 03:59:23 -0400 Received: from mx2.suse.de ([195.135.220.15]:56800 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726454AbgIUH7T (ORCPT ); Mon, 21 Sep 2020 03:59:19 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id E94C1B4FD; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 05/41] random: don't reset entropy to zero on overflow Date: Mon, 21 Sep 2020 09:58:21 +0200 Message-Id: <20200921075857.4424-6-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org credit_entropy_bits() adds one or more positive values to the signed entropy_count and checks if the result is negative afterwards. Note that because the initial value of entropy_count is positive, a negative result can happen only on overflow. However, if the final entropy_count is found to have overflown, a WARN() is emitted and the entropy_store's entropy count reset to zero. Even though this case should never happen, it is better to retain previously available entropy as this will facilitate a future change factoring out that approximation of the exponential. Make credit_entropy_bits() tp reset entropy_count to the original value rather than zero on overflow. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 35e381be20fe..6adac462aa0d 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -706,7 +706,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) if (WARN_ON(entropy_count < 0)) { pr_warn("negative entropy/overflow: pool %s count %d\n", r->name, entropy_count); - entropy_count = 0; + entropy_count = orig; } else if (entropy_count > pool_size) entropy_count = pool_size; if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) From patchwork Mon Sep 21 07:58:22 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788661 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7E1461731 for ; Mon, 21 Sep 2020 07:59:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6D8402085B for ; Mon, 21 Sep 2020 07:59:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726507AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 Received: from mx2.suse.de ([195.135.220.15]:56798 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726455AbgIUH7T (ORCPT ); Mon, 21 Sep 2020 03:59:19 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 8BDECB502; Mon, 21 Sep 2020 07:59:52 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 06/41] random: factor the exponential approximation in credit_entropy_bits() out Date: Mon, 21 Sep 2020 09:58:22 +0200 Message-Id: <20200921075857.4424-7-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org In the course of calculating the actual amount of new entropy to credit, credit_entropy_bits() applies a linear approximation to exp(-nbits/pool_size)) (neglecting scaling factors in the exponent for the sake of simplicity). In order to limit approximation errors for large nbits, nbits is divided into chunks of maximum value pool_size/2 each and said approximation is applied to these individually in a loop. That loop has a theoretic upper bound of 2*log2(pool_size), which, with the given pool_size of 128 * 32 bits, equals 24. However, in practice nbits hardly ever exceeds values as a large as pool_size/2 == 2048, especially not when called from interrupt context, i.e. from add_interrupt_randomness() and alike. Thus, imposing a limit of one single iteration in these contexts would yield a good guarantee with respect to runtime while not losing any entropy. In preparation to enabling that, move the approximation code in credit_entropy_bits() into a separate function, pool_entropy_delta(). Based on the initial pool entropy count and the number of new entropy bits to credit, it calculates and returns a (positive) delta to add to the former. In case the 'fast' parameter is set to true, the calculation will be terminated after the first iteration, effectively capping the input nbits to one half of the pool size. There is no functional change; callers with 'fast' set to true will be introduced in a future patch. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 53 ++++++++++++++++++++++++++++++------------- 1 file changed, 37 insertions(+), 16 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 6adac462aa0d..15dd22d74029 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -366,7 +366,7 @@ * denominated in units of 1/8th bits. * * 2*(ENTROPY_SHIFT + poolbitshift) must <= 31, or the multiply in - * credit_entropy_bits() needs to be 64 bits wide. + * pool_entropy_delta() needs to be 64 bits wide. */ #define ENTROPY_SHIFT 3 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT) @@ -654,22 +654,24 @@ static void process_random_ready_list(void) } /* - * Credit the entropy store with n bits of entropy. - * Use credit_entropy_bits_safe() if the value comes from userspace - * or otherwise should be checked for extreme values. + * Based on the pool's current entropy fill level, specified as + * base_entropy_count, and the number of new entropy bits to add, + * return the amount of new entropy to credit. If the 'fast' + * parameter is set to true, the calculation will be guaranteed to + * terminate quickly, but this comes at the expense of capping + * nbits to one half of the pool size. */ -static void credit_entropy_bits(struct entropy_store *r, int nbits) +static unsigned int pool_entropy_delta(struct entropy_store *r, + int base_entropy_count, + int nbits, bool fast) { - int entropy_count, orig; const int pool_size = r->poolinfo->poolfracbits; + int entropy_count = base_entropy_count; int nfrac = nbits << ENTROPY_SHIFT; - int pnfrac; if (!nbits) - return; + return 0; -retry: - entropy_count = orig = READ_ONCE(r->entropy_count); /* * Credit: we have to account for the possibility of * overwriting already present entropy. Even in the @@ -691,24 +693,43 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) * arbitrarily long; this limits the loop to log2(pool_size)*2 * turns no matter how large nbits is. */ - pnfrac = nfrac; do { /* The +2 corresponds to the /4 in the denominator */ const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2; - unsigned int anfrac = min(pnfrac, pool_size/2); + unsigned int anfrac = min(nfrac, pool_size/2); unsigned int add = ((pool_size - entropy_count)*anfrac*3) >> s; entropy_count += add; - pnfrac -= anfrac; - } while (unlikely(entropy_count < pool_size-2 && pnfrac)); + nfrac -= anfrac; + } while (unlikely(!fast && entropy_count < pool_size-2 && nfrac)); if (WARN_ON(entropy_count < 0)) { pr_warn("negative entropy/overflow: pool %s count %d\n", r->name, entropy_count); - entropy_count = orig; - } else if (entropy_count > pool_size) + entropy_count = base_entropy_count; + } else if (entropy_count > pool_size) { entropy_count = pool_size; + } + + return entropy_count - base_entropy_count; +} + +/* + * Credit the entropy store with n bits of entropy. + * Use credit_entropy_bits_safe() if the value comes from userspace + * or otherwise should be checked for extreme values. + */ +static void credit_entropy_bits(struct entropy_store *r, int nbits) +{ + int entropy_count, orig; + + if (!nbits) + return; + +retry: + orig = READ_ONCE(r->entropy_count); + entropy_count = orig + pool_entropy_delta(r, orig, nbits, false); if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) goto retry; From patchwork Mon Sep 21 07:58:23 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788659 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4909C1668 for ; Mon, 21 Sep 2020 07:59:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3C34E20EDD for ; Mon, 21 Sep 2020 07:59:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726501AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 Received: from mx2.suse.de ([195.135.220.15]:56802 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726456AbgIUH7T (ORCPT ); Mon, 21 Sep 2020 03:59:19 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 1DDF8B503; Mon, 21 Sep 2020 07:59:53 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 07/41] random: let pool_entropy_delta() take nbits in units of 2^-ENTROPY_SHIFT Date: Mon, 21 Sep 2020 09:58:23 +0200 Message-Id: <20200921075857.4424-8-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Currently pool_entropy_delta() expects its nbits argument to be given in units of integral bits. Using fractional bits for processing intermediate entropy counts consistently throughout the code will facilitate upcoming changes to the entropy accounting logic in add_interrupt_randomness(). Replace pool_entropy_delta()'s nbits argument with nfrac, which used to be a local variable and is expected to be given in units of 2^-ENTROPY_SHIFT. Adapt the single caller, credit_entropy_bits(), accordingly. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 15dd22d74029..08caa7a691a5 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -655,21 +655,20 @@ static void process_random_ready_list(void) /* * Based on the pool's current entropy fill level, specified as - * base_entropy_count, and the number of new entropy bits to add, - * return the amount of new entropy to credit. If the 'fast' - * parameter is set to true, the calculation will be guaranteed to - * terminate quickly, but this comes at the expense of capping - * nbits to one half of the pool size. + * base_entropy_count, and the number of new entropy bits in units of + * 2^-ENTROPY_SHIFT to add, return the amount of new entropy to + * credit. If the 'fast' parameter is set to true, the calculation + * will be guaranteed to terminate quickly, but this comes at the + * expense of capping nbits to one half of the pool size. */ static unsigned int pool_entropy_delta(struct entropy_store *r, int base_entropy_count, - int nbits, bool fast) + int nfrac, bool fast) { const int pool_size = r->poolinfo->poolfracbits; int entropy_count = base_entropy_count; - int nfrac = nbits << ENTROPY_SHIFT; - if (!nbits) + if (!nfrac) return 0; /* @@ -729,7 +728,9 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) retry: orig = READ_ONCE(r->entropy_count); - entropy_count = orig + pool_entropy_delta(r, orig, nbits, false); + entropy_count = orig + pool_entropy_delta(r, orig, + nbits << ENTROPY_SHIFT, + false); if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) goto retry; From patchwork Mon Sep 21 07:58:24 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788657 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id DF007618 for ; Mon, 21 Sep 2020 07:59:22 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C9AEF20EDD for ; Mon, 21 Sep 2020 07:59:22 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726488AbgIUH7V (ORCPT ); Mon, 21 Sep 2020 03:59:21 -0400 Received: from mx2.suse.de ([195.135.220.15]:56832 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726471AbgIUH7U (ORCPT ); Mon, 21 Sep 2020 03:59:20 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id A8BF3B504; Mon, 21 Sep 2020 07:59:53 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 08/41] random: introduce __credit_entropy_bits_fast() for hot paths Date: Mon, 21 Sep 2020 09:58:24 +0200 Message-Id: <20200921075857.4424-9-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org When transferring entropy from the fast_pool into the global input_pool from add_interrupt_randomness(), there are at least two atomic operations involved: one when taking the input_pool's spinlock for the actual mixing and another one in the cmpxchg loop in credit_entropy_bits() for updating the pool's ->entropy_count. Because cmpxchg is potentially costly, it would be nice if it could be avoided. As said, the input_pool's spinlock is taken anyway, and I see no reason why its scope should not be extended to protect ->entropy_count as well. Performance considerations set aside, this will also facilitate future changes introducing additional fields to input_pool which will also have to get updated atomically from the consumer/producer sides. The actual move to extend the spinlock's scope to cover ->entropy_count will be the subject of a future patch. Prepare for that by putting a limit on the work to be done with the lock being held. In order to avoid releasing and regrabbing from hot producer paths, they'll keep the lock when executing those calculations in pool_entropy_delta(). The loop found in the latter has a theoretical upper bound of 2 * log2(pool_size) == 24 iterations. However, as all entropy increments awarded from the interrupt path are less than pool_size/2 in magnitude, it is safe to enforce a guaranteed limit of one on the iteration count by setting pool_entropy_delta()'s 'fast' parameter. Introduce __credit_entropy_bits_fast() doing exactly that. Currently it resembles the behaviour from credit_entropy_bits() except that - pool_entropy_delta() gets called with 'fast' set to true and - that __credit_entropy_bits_fast() returns a bool indicating whether the caller should reseed the primary_crng. Note that unlike it's the case with credit_entropy_bits(), the reseeding won't be possible from within __credit_entropy_bits_fast() anymore once it actually gets invoked with the pool lock being held in the future. There is no functional change. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 49 ++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 46 insertions(+), 3 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 08caa7a691a5..d9e4dd27d45d 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -714,6 +714,39 @@ static unsigned int pool_entropy_delta(struct entropy_store *r, return entropy_count - base_entropy_count; } +/* + * Credit the entropy store with n bits of entropy. + * To be used from hot paths when it is either known that nbits is + * smaller than one half of the pool size or losing anything beyond that + * doesn't matter. + */ +static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) +{ + int entropy_count, orig; + + if (!nbits) + return false; + +retry: + orig = READ_ONCE(r->entropy_count); + entropy_count = orig + pool_entropy_delta(r, orig, + nbits << ENTROPY_SHIFT, + true); + if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) + goto retry; + + trace_credit_entropy_bits(r->name, nbits, + entropy_count >> ENTROPY_SHIFT, _RET_IP_); + + if (unlikely(r == &input_pool && crng_init < 2)) { + const int entropy_bits = entropy_count >> ENTROPY_SHIFT; + + return (entropy_bits >= 128); + } + + return false; +} + /* * Credit the entropy store with n bits of entropy. * Use credit_entropy_bits_safe() if the value comes from userspace @@ -1169,6 +1202,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) unsigned num; } sample; long delta, delta2, delta3; + bool reseed; sample.jiffies = jiffies; sample.cycles = random_get_entropy(); @@ -1206,7 +1240,9 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) * Round down by 1 bit on general principles, * and limit entropy estimate to 12 bits. */ - credit_entropy_bits(r, min_t(int, fls(delta>>1), 11)); + reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11)); + if (reseed) + crng_reseed(&primary_crng, r); } void add_input_randomness(unsigned int type, unsigned int code, @@ -1274,6 +1310,7 @@ void add_interrupt_randomness(int irq, int irq_flags) __u64 ip; unsigned long seed; int credit = 0; + bool reseed; if (cycles == 0) cycles = get_reg(fast_pool, regs); @@ -1326,7 +1363,9 @@ void add_interrupt_randomness(int irq, int irq_flags) fast_pool->count = 0; /* award one bit for the contents of the fast pool */ - credit_entropy_bits(r, credit + 1); + reseed = __credit_entropy_bits_fast(r, credit + 1); + if (reseed) + crng_reseed(&primary_crng, r); } EXPORT_SYMBOL_GPL(add_interrupt_randomness); @@ -1599,7 +1638,11 @@ EXPORT_SYMBOL(get_random_bytes); */ static void entropy_timer(struct timer_list *t) { - credit_entropy_bits(&input_pool, 1); + bool reseed; + + reseed = __credit_entropy_bits_fast(&input_pool, 1); + if (reseed) + crng_reseed(&primary_crng, &input_pool); } /* From patchwork Mon Sep 21 07:58:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788735 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 11F97618 for ; Mon, 21 Sep 2020 08:01:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F168020EDD for ; Mon, 21 Sep 2020 08:01:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726590AbgIUIBq (ORCPT ); Mon, 21 Sep 2020 04:01:46 -0400 Received: from mx2.suse.de ([195.135.220.15]:56892 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726211AbgIUH7V (ORCPT ); Mon, 21 Sep 2020 03:59:21 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 4774AB506; Mon, 21 Sep 2020 07:59:54 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 09/41] random: protect ->entropy_count with the pool spinlock Date: Mon, 21 Sep 2020 09:58:25 +0200 Message-Id: <20200921075857.4424-10-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Currently, all updates to ->entropy_count are synchronized by means of cmpxchg-retry loops found in credit_entropy_bits(), __credit_entropy_bits_fast() and account() respectively. However, all but one __credit_entropy_bits_fast() call sites grap the pool ->lock already and it would be nice if the potentially costly cmpxchg could be avoided in these performance critical paths. In addition to that, future patches will introduce new fields to struct entropy_store which will required some kinf of synchronization with ->entropy_count updates from said producer paths as well. Protect ->entropy_count with the pool ->lock. - Make callers of __credit_entropy_bits_fast() invoke it with the pool ->lock held. Extend existing critical sections where possible. Drop the cmpxchg-reply loop in __credit_entropy_bits_fast() in favor of a plain assignment. - Retain the retry loop in credit_entropy_bits(): the potentially expensive pool_entropy_delta() should not be called under the lock in order to not unnecessarily block contenders. In order to continue to synchronize with __credit_entropy_bits_fast() and account(), the cmpxchg gets replaced by a plain comparison + store with the ->lock being held. - Make account() grab the ->lock and drop the cmpxchg-retry loop in favor of a plain assignent. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 44 +++++++++++++++++++++++++++++-------------- 1 file changed, 30 insertions(+), 14 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d9e4dd27d45d..9f87332b158f 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -718,7 +718,7 @@ static unsigned int pool_entropy_delta(struct entropy_store *r, * Credit the entropy store with n bits of entropy. * To be used from hot paths when it is either known that nbits is * smaller than one half of the pool size or losing anything beyond that - * doesn't matter. + * doesn't matter. Must be called with r->lock being held. */ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) { @@ -727,13 +727,11 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) if (!nbits) return false; -retry: - orig = READ_ONCE(r->entropy_count); + orig = r->entropy_count; entropy_count = orig + pool_entropy_delta(r, orig, nbits << ENTROPY_SHIFT, true); - if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) - goto retry; + WRITE_ONCE(r->entropy_count, entropy_count); trace_credit_entropy_bits(r->name, nbits, entropy_count >> ENTROPY_SHIFT, _RET_IP_); @@ -755,17 +753,28 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) static void credit_entropy_bits(struct entropy_store *r, int nbits) { int entropy_count, orig; + unsigned long flags; if (!nbits) return; retry: + /* + * Don't run the potentially expensive pool_entropy_delta() + * calculations under the spinlock. Instead retry until + * ->entropy_count becomes stable. + */ orig = READ_ONCE(r->entropy_count); entropy_count = orig + pool_entropy_delta(r, orig, nbits << ENTROPY_SHIFT, false); - if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) + spin_lock_irqsave(&r->lock, flags); + if (r->entropy_count != orig) { + spin_unlock_irqrestore(&r->lock, flags); goto retry; + } + WRITE_ONCE(r->entropy_count, entropy_count); + spin_unlock_irqrestore(&r->lock, flags); trace_credit_entropy_bits(r->name, nbits, entropy_count >> ENTROPY_SHIFT, _RET_IP_); @@ -1203,12 +1212,11 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) } sample; long delta, delta2, delta3; bool reseed; + unsigned long flags; sample.jiffies = jiffies; sample.cycles = random_get_entropy(); sample.num = num; - r = &input_pool; - mix_pool_bytes(r, &sample, sizeof(sample)); /* * Calculate number of bits of randomness we probably added. @@ -1235,12 +1243,16 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) if (delta > delta3) delta = delta3; + r = &input_pool; + spin_lock_irqsave(&r->lock, flags); + __mix_pool_bytes(r, &sample, sizeof(sample)); /* * delta is now minimum absolute delta. * Round down by 1 bit on general principles, * and limit entropy estimate to 12 bits. */ reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11)); + spin_unlock_irqrestore(&r->lock, flags); if (reseed) crng_reseed(&primary_crng, r); } @@ -1358,12 +1370,12 @@ void add_interrupt_randomness(int irq, int irq_flags) __mix_pool_bytes(r, &seed, sizeof(seed)); credit = 1; } - spin_unlock(&r->lock); fast_pool->count = 0; /* award one bit for the contents of the fast pool */ reseed = __credit_entropy_bits_fast(r, credit + 1); + spin_unlock(&r->lock); if (reseed) crng_reseed(&primary_crng, r); } @@ -1393,14 +1405,15 @@ EXPORT_SYMBOL_GPL(add_disk_randomness); */ static size_t account(struct entropy_store *r, size_t nbytes, int min) { - int entropy_count, orig, have_bytes; + int entropy_count, have_bytes; size_t ibytes, nfrac; + unsigned long flags; BUG_ON(r->entropy_count > r->poolinfo->poolfracbits); + spin_lock_irqsave(&r->lock, flags); /* Can we pull enough? */ -retry: - entropy_count = orig = READ_ONCE(r->entropy_count); + entropy_count = r->entropy_count; ibytes = nbytes; /* never pull more than available */ have_bytes = entropy_count >> (ENTROPY_SHIFT + 3); @@ -1420,8 +1433,8 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min) else entropy_count = 0; - if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) - goto retry; + WRITE_ONCE(r->entropy_count, entropy_count); + spin_unlock_irqrestore(&r->lock, flags); trace_debit_entropy(r->name, 8 * ibytes); if (ibytes && ENTROPY_BITS(r) < random_write_wakeup_bits) { @@ -1639,8 +1652,11 @@ EXPORT_SYMBOL(get_random_bytes); static void entropy_timer(struct timer_list *t) { bool reseed; + unsigned long flags; + spin_lock_irqsave(&input_pool.lock, flags); reseed = __credit_entropy_bits_fast(&input_pool, 1); + spin_unlock_irqrestore(&input_pool.lock, flags); if (reseed) crng_reseed(&primary_crng, &input_pool); } From patchwork Mon Sep 21 07:58:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788689 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id DC579618 for ; Mon, 21 Sep 2020 08:00:28 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BC88D214F1 for ; Mon, 21 Sep 2020 08:00:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726700AbgIUIA1 (ORCPT ); Mon, 21 Sep 2020 04:00:27 -0400 Received: from mx2.suse.de ([195.135.220.15]:56980 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726478AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id DFDBDB507; Mon, 21 Sep 2020 07:59:54 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 10/41] random: implement support for delayed entropy dispatching Date: Mon, 21 Sep 2020 09:58:26 +0200 Message-Id: <20200921075857.4424-11-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Consider the following scenario: Producer Consumer -------- -------- mix_pool_bytes() account() ->entropy_count -= n extract_buf() credit_entropy_bits() ->entropy_count += pool_entropy_delta() The amount of entropy to credit as calculated by pool_entropy_delta() depends on the current pool fill level: the higher the current ->entropy_count, the less the amount of new entropy credited. In the situation above, a too small value of ->entropy_count would have been observed and thus, too much entropy attributed to the new batch. I do recognize the fact that this is currently more of a theoretical concern. However, future patches will implement some statistical "health tests" to be run on raw samples like e.g. cycle counts obtained and mixed into the fast_pools in add_interrupt_randomness(). These tests must have processed more events than can fit into the fast_pools (~64) before the outcome is known. Thus, add_interrupt_randomness() will have to dump its fast_pool into the global input_pool a couple of times before the tests have completed and hence before the (accumulated) entropy credit may be released to input_pool's ->entropy_count. It follows that the final entropy credit attribution can be delayed for arbitrarily long to after the corresponding mix_pool_bytes() operation. The simplest solution would be to maintain a sequence counter which gets incremented from account(). The producer side would take a snapshot before mix_pool_bytes() and only eventually credit any entropy if it hasn't changed in the meanwhile. However, that would mean that a lot of precious entropy would be discarded, especially at boot time: as soon as the first CPU seeds the primary_crng(), a large part of the entropy accumulated through add_interrupt_randomness() on all other CPUs would be lost. So follow a watermark based approach instead. That is, provide the producer side with an ->entropy_count watermark which is guaranteed to not be less than the value of ->entropy_count at any point in time from before to after the mix_pool_bytes() operation(s). Note that the order in which concurrent producers credit entropy doesn't matter, because e1 = e0 + pool_entropy_delta(e0, n1) e2 = e1 + pool_entropy_delta(e1, n2) is equivalent (modulo approximation artifacts) to e2 = e0 + pool_entropy_delta(e0, n1 + n2). Thus, taking the larger of said watermark and the latest ->entropy_count value for the pool fill level when calculating pool_entropy_delta() will guarantee that the result won't exceed the true value. Introduce the new __queue_entropy() and __dequeue_entropy() functions intended to be used for delimiting one or more successive mix_pool_bytes() invocations for which the pool watermark tracking is needed. Both take a pointer to the target pool as well as to an instance of the new struct queued_entropy. For reasons explained below, __queue_entropy() also receives the amount of entropy transferred in the subsequent mix_pool_bytes() operation as an argument and accumulates that at the given struct queued_entropy instance. __queue_entropy() may be called any number of times on the same struct queued_entropy instance until a matching __dequeue_entropy() gets eventually invoked. The latter will return the total number of (fractional) entropy bits accumulated at queued_entropy as well as an appropriate pool watermark. Both are intended to be used for that pool_entropy_delta() calculation when subsequently dispatching the accumulated entropy to the pool. Producers are not actually expected to call __dequeue_entropy() directly. Instead, provide the new dispatch_queued_entropy() and __dispatch_queued_entropy_fast() helpers. These will eventually supersede credit_entropy_bits() respectively __credit_entropy_bits_fast(). Both take a queued_entropy instance, run __dequeue_entropy() on it, carry out the required pool_entropy_delta() calculations and add the result to the target pool's ->entropy_count. Conversion of the individual entropy producers to the new API will be the subject of future patches for the sake of better reviewability. For now, merely reimplement credit_entropy_bits() and __credit_entropy_bits_fast() on top of it in order to avoid excessive code duplication. Obviously, it's the consumer side's job to maintain the pool watermark: whenever ->entropy_count decreases, the watermark needs updating. Maintain the pool entropy watermark in the form of a delta to be added to the current ->entropy_count to obtain the actual value. To this end, introduce a new field ->entropy_watermark_delta to struct entropy_store. Rename the existing account(), which gets called right before the corresponding extract_buf()s in extract_entropy(), to account_begin(). Make it add the allocated entropy count, i.e. the amount by which the pool's ->entropy_count has been reduced, to ->entropy_watermark_delta. If possible, this watermark increment should be undone after the subsequent extract_buf()s have completed, because otherwise the watermark would grow unboundedly beyond the pool size over time. Note that this would render producers unable to dispatch any new non-zero entropy to ->entropy_count. Introduce the new account_complete() for handling the ->entropy_watermark_delta decrements and call it from extract_entropy() right after the extract_buf()s following the preceding account_begin() have finished. Obviously it's safe to decrement the watermark again in case nobody cares at all -- that is, if there currently isn't any entropy queued at the producer side. Introduce a new field ->queued_entropy_batches to struct entropy_store for keeping track of that. Make __queue_entropy() increment it upon the first request to queue a non-zero amount of entropy at a given struct queued_entropy instance. Likewise, make __dequeue_entropy() decrement it again iff a non-zero amount of entropy has been queued. Finally, make account_complete() undo the ->entropy_watermark_delta increment from the preceding account_begin() in case ->queued_entropy_batches is zero. Note that if ->queued_entropy_batches is found to be non-zero in account_complete(), ->entropy_watermark_delta is left untouched, i.e. the increment from the preceding account_begin() is "leaked". It follows that the watermark can still grow beyond any bound over time. However, if at the time account_complete() runs there is no entropy queued at the producer side *and* there is no other, concurrent extraction pending an upcoming __queue_entropy() could possibly interfere with, the watermark may even get reset to zero and thus, any leakages left from former invocations cleaned up. Introduce a new field ->pending_extractions to struct entropy_store for keeping track of the number of pending entropy extractions. Make account_begin() increment it and make account_complete() decrement it again. Make account_complete() reset ->entropy_watermark_delta in case ->queued_entropy_batches and ->entropy_watermark_delta are both zero. Once the initially mentioned health tests have been implemented and enabled, it will not be unlikely that there's always at least one CPU having some entropy queued at any point in time and thus, that ->queued_entropy_batches will never be found to equal zero in account_complete(). As a last resort, enforce upper bounds on the magnitude as well as on the lifetime of the pool watermark and reset it if any has been exceeded. All entropy currently queued up on the producer side needs to be invalidated in this case. Introduce a new field ->entropy_watermark_seq to struct entropy_store for maintaing a sequence count needed to implement entropy invalidations. Make __queue_entropy() take a snapshot at the first invocation and make it revalidate the snapshot when accumulating additional entropy in subsequent invocations. Make the final __dequeue_entropy() validate the snapshot and return zero for the amount of dequeued entropy on failure. Make account_complete() increment the sequence count when resetting the pool watermark even though ->queued_entropy_batches is non-zero. Note that this sequence count based invalidation scheme does not allow for watermark resets when there are multiple concurrent extractions pending: a future __queue_entropy() could potentially interfere with any of the other extractions and there is no way to invalidate it "in advance". However, this doesn't matter because there are hardly any concurrent entropy extractions after boot and even if there were: some account_complete() would always come last. What remains to be clarified is under which exact circumstances account_complete() would resort to resetting the pool watermark and invalidating all currently queued entropy. The limit on the watermark magnitude, ->entropy_watermark_delta to be more specific, has been set to one eighth of the pool size == 1/8 * 4096 bits == 512 bits. This has been chosen as a compromise between allowing for up to two 256 bit extractions/reseeds without invalidating queued entropy and not reducing the efficiency of new entropy contributions too much. Assuming a watermark value of 512 bits over the current ->entropy_count, the entropy credits as calculated by pool_entropy_delta() for new contributions are 87.5%, 75% and 50% respectively for pool fill levels of 0%, 50% and 75% of what they would have been with a ->entropy_watermark_delta of zero. In order to avoid a situation where a smallish ->entropy_watermark_delta which accumulated during boot time, but never manages to increase beyond the reset threshold, is kept forever, also impose a lifetime limit. The choice of 2 * CRNG_RESEED_INTERVAL for the maximum watermark lifetime follows the same line of reasoning as for the chosen magnitude limit. In order to enable this watermark lifetime management, add yet another new field ->entropy_watermark_leak_time to struct entropy_store. Make account_begin() set it to the current jiffies upon the first increment of ->entropy_watermark_delta from zero. Make account_complete() reset ->entropy_watermark_delta and invalidate all queued entropy as described above whenever ->pending_extractions is zero and either ->entropy_watermark_leak_time is older than two times CRNG_RESEED_INTERVAL or if ->entropy_watermark_delta exceeds one fourth of the pool size. As entropy producers haven't been converted to the new __queue_entropy() + dispatch_queued_entropy()/__dispatch_queued_entropy_fast() API yet, the net effect of this patch is to "fix" a scenario similar to the one initially described for those producers that call __mix_pool_bytes() and __credit_entropy_bits_fast() without dropping the pool's ->lock inbetween, i.e. for add_interrupt_randomness() and add_timer_randomness(). Namely, if said sequence happens to get serialized inbetween the account_begin() (formerly account()) and the last extract_buf() from a concurrent extraction, the pool's entropy watermark will now be taken into account when calculating the amount of new entropy to credit in __credit_entropy_bits_fast(), because the latter has been reimplemented on top of the new API. Other than that, it's noteworthy that the pool entropy watermark might exceed unexpectedly high levels at boot time, namely if multiple producers happen to trigger the initial seeding of the primary_crng and the subsequent entropy extractions complete when entropy has been queued up somewhere else, e.g. in try_to_generate_entropy(). As detailed above, high values of the pool watermark will reduce the efficiency when dispatching new entropy attributions, but note that - There are mechanisms in place to limit the effect in magnitude and time. - The watermark can never exceed the total amount of entropy collected so far. So entropy collection at boot time would have to be terribly efficient in order for this to matter. - As seeding the primary_crng is a prerequisite for the described scenario, a temporarily reduced entropy collection efficiency isn't really concerning: getting towards a seeded primary_crng is all that matters at this point. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 315 +++++++++++++++++++++++++++++++++++++++--- 1 file changed, 292 insertions(+), 23 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 9f87332b158f..b91d1fc08ac5 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -499,7 +499,13 @@ struct entropy_store { spinlock_t lock; unsigned short add_ptr; unsigned short input_rotate; + int entropy_count; + unsigned int entropy_watermark_delta; + unsigned int entropy_watermark_seq; + unsigned int queued_entropy_batches; + unsigned int pending_extractions; + unsigned long entropy_watermark_leak_time; unsigned int initialized:1; unsigned int last_data_init:1; __u8 last_data[EXTRACT_SIZE]; @@ -671,6 +677,9 @@ static unsigned int pool_entropy_delta(struct entropy_store *r, if (!nfrac) return 0; + if (pool_size <= base_entropy_count) + return 0; + /* * Credit: we have to account for the possibility of * overwriting already present entropy. Even in the @@ -714,26 +723,172 @@ static unsigned int pool_entropy_delta(struct entropy_store *r, return entropy_count - base_entropy_count; } +struct queued_entropy { + unsigned int pool_watermark_seq; + unsigned int queued_entropy_fracbits; +}; + /* - * Credit the entropy store with n bits of entropy. - * To be used from hot paths when it is either known that nbits is - * smaller than one half of the pool size or losing anything beyond that - * doesn't matter. Must be called with r->lock being held. + * Queue a given amount of new entropy which is about to mixed into + * the entropy pool for later dispatch. + * + * __queue_entropy() may be called one or more time on the same struct + * queued_entropy instance in order to accumulate entropy for later + * dispatch. However, any such sequence of invocations must eventually + * be followed by exactly one call to either of __dequeue_entropy(), + * __dispatch_queued_entropy_fast() or dispatch_queued_entropy() + * when the actual pool mixing has completed. + * __queue_entropy() must be called with r->lock held. + * + * Entropy extraction is a two-step process: + * 1.) The allocated amount of entropy gets subtracted from ->entropy_count. + * 2.) The entropy is actually extracted from the pool by means of one or more + * extract_buf() invocations. + * Likewise for the mixing side: + * 1.) The new entropy data gets mixed into the pool via __mix_pool_bytes() and + * 2.) the pool's ->entropy_count incremented by a certain amount afterwards. + * However, that amount of new entropy credited in the last step depends + * on the current pool fill level: the higher the current ->entropy_count, + * the less the amount of new entropy credited, c.f. pool_entropy_delta(). + * + * This must be accounted for in a scenario involving concurrent producers + * and consumers like the following: + * Producer Consumer + * -------- -------- + * ->entropy_count -= n + * __mix_pool_bytes() + * ->entropy_count += pool_entropy_delta() + * extract_buf() + * Note how the pool_entropy_delta() would observe a too small pool + * fill level and thus, credits too much entropy to the new batch. + * + * The solution to work around this is to maintain a watermark, which + * is guaranteed to be >= than the pool's ->entropy_count value + * at any point in time from before __mix_pool_bytes() to after it. + * + * A call to __queue_entropy() enables watermark tracking from the + * producers side, the final __dequeue_entropy() disables it and + * returns the watermark. See also account_begin() and + * account_complete(). + * + * Note there's no problem wuth multiple concurrent producers, because + * e1 = e0 + pool_entropy_delta(e0, n1); + * e2 = e1 + pool_entropy_delta(e1, n2); + * is equivalent (modulo approximation artifacts) to + * e2 = e0 + pool_entropy_delta(e0, n1 + n2); */ -static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) +static void __queue_entropy(struct entropy_store *r, struct queued_entropy *q, + unsigned int nfrac) +{ + if (!nfrac) + return; + + if (!q->queued_entropy_fracbits) { + /* + * First call with non-zero nbits, enable watermark + * tracking. + */ + q->pool_watermark_seq = r->entropy_watermark_seq; + r->queued_entropy_batches++; + } else if (q->pool_watermark_seq != r->entropy_watermark_seq) { + /* + * Previously queued entropy is doomed because + * the ->pool_watermark_delta had been reset. + * Don't add any more entropy on top of that. + */ + q->pool_watermark_seq = r->entropy_watermark_seq; + q->queued_entropy_fracbits = 0; + } + + q->queued_entropy_fracbits += nfrac; +} + +static void queue_entropy(struct entropy_store *r, struct queued_entropy *q, + unsigned int nfrac) { - int entropy_count, orig; + unsigned long flags; - if (!nbits) + spin_lock_irqsave(&r->lock, flags); + __queue_entropy(r, q, nfrac); + spin_unlock_irqrestore(&r->lock, flags); +} + +/* + * Dequeue previously queued entropy and return the pool entropy + * watermark to be used in pool_entropy_delta(). + * + * Must only be called after a sequence of one or more matching + * __queue_entropy() invocations. Must be called with r->lock + * held. + * + * __dequeue_entropy() returns the number of queued bits and resets + * q. *pool_watermark receives the pool entropy watermark as tracked + * from the beginning of the first preceding __queue_entropy() call + * up to the __dequeue_entropy() invocation. + * + * The number of returned fractional bits is intended to get + * subsequently passed together with the larger of *pool_watermark and + * r->entropy_count to pool_entropy_delta(). + * If r->lock is not dropped inbetween *pool_watermark and the load + * of r->entropy_count, the former is guaranteed to equal the maximum. + */ +static unsigned int __dequeue_entropy(struct entropy_store *r, + struct queued_entropy *q, + int *pool_watermark) +{ + unsigned int nfrac; + + nfrac = q->queued_entropy_fracbits; + if (!nfrac) + return 0; + + /* Disable watermark tracking. */ + q->queued_entropy_fracbits = 0; + r->queued_entropy_batches--; + + /* + * The watermark has been invalidated in the meanwhile and + * the queued entropy is lost. + */ + if (q->pool_watermark_seq != r->entropy_watermark_seq) + return 0; + + *pool_watermark = r->entropy_count + r->entropy_watermark_delta; + if (*pool_watermark < 0) + return 0; + + return nfrac; +} + +/* + * Credit the pool with previously queued entropy. + * + * Must only be called after a sequence of one or more matching + * __queue_entropy() invocations. Must be called with r->lock + * held. + * + * To be used from hot paths when it is either known that the amount + * of queued entropy is smaller than one half of the pool size or + * losing anything beyond that doesn't matter. + * + * Returns true if the caller is supposed to seed the primary_crng. + */ +static bool __dispatch_queued_entropy_fast(struct entropy_store *r, + struct queued_entropy *q) +{ + unsigned int nfrac; + int entropy_count, orig, pool_watermark; + + nfrac = __dequeue_entropy(r, q, &pool_watermark); + if (!nfrac) return false; orig = r->entropy_count; - entropy_count = orig + pool_entropy_delta(r, orig, - nbits << ENTROPY_SHIFT, + entropy_count = orig + pool_entropy_delta(r, pool_watermark, nfrac, true); WRITE_ONCE(r->entropy_count, entropy_count); - trace_credit_entropy_bits(r->name, nbits, + trace_credit_entropy_bits(r->name, nfrac >> ENTROPY_SHIFT, entropy_count >> ENTROPY_SHIFT, _RET_IP_); if (unlikely(r == &input_pool && crng_init < 2)) { @@ -747,15 +902,35 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) /* * Credit the entropy store with n bits of entropy. - * Use credit_entropy_bits_safe() if the value comes from userspace - * or otherwise should be checked for extreme values. + * To be used from hot paths when it is either known that nbits is + * smaller than one half of the pool size or losing anything beyond that + * doesn't matter. Must be called with r->lock being held. */ -static void credit_entropy_bits(struct entropy_store *r, int nbits) +static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) +{ + struct queued_entropy q = { 0 }; + + __queue_entropy(r, &q, nbits << ENTROPY_SHIFT); + return __dispatch_queued_entropy_fast(r, &q); +} + +/* + * Credit the pool with previously queued entropy. + * + * Must only be called after a sequence of one or more matching + * __queue_entropy() invocations. + */ +static void dispatch_queued_entropy(struct entropy_store *r, + struct queued_entropy *q) { - int entropy_count, orig; + unsigned int nfrac; + int entropy_count, orig, pool_watermark, base; unsigned long flags; - if (!nbits) + spin_lock_irqsave(&r->lock, flags); + nfrac = __dequeue_entropy(r, q, &pool_watermark); + spin_unlock_irqrestore(&r->lock, flags); + if (!nfrac) return; retry: @@ -765,9 +940,8 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) * ->entropy_count becomes stable. */ orig = READ_ONCE(r->entropy_count); - entropy_count = orig + pool_entropy_delta(r, orig, - nbits << ENTROPY_SHIFT, - false); + base = max_t(int, pool_watermark, orig); + entropy_count = orig + pool_entropy_delta(r, base, nfrac, false); spin_lock_irqsave(&r->lock, flags); if (r->entropy_count != orig) { spin_unlock_irqrestore(&r->lock, flags); @@ -776,7 +950,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) WRITE_ONCE(r->entropy_count, entropy_count); spin_unlock_irqrestore(&r->lock, flags); - trace_credit_entropy_bits(r->name, nbits, + trace_credit_entropy_bits(r->name, nfrac >> ENTROPY_SHIFT, entropy_count >> ENTROPY_SHIFT, _RET_IP_); if (r == &input_pool) { @@ -790,6 +964,19 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) } } +/* + * Credit the entropy store with n bits of entropy. + * Use credit_entropy_bits_safe() if the value comes from userspace + * or otherwise should be checked for extreme values. + */ +static void credit_entropy_bits(struct entropy_store *r, int nbits) +{ + struct queued_entropy q = { 0 }; + + queue_entropy(r, &q, nbits << ENTROPY_SHIFT); + dispatch_queued_entropy(r, &q); +} + static int credit_entropy_bits_safe(struct entropy_store *r, int nbits) { const int nbits_max = r->poolinfo->poolwords * 32; @@ -1402,8 +1589,12 @@ EXPORT_SYMBOL_GPL(add_disk_randomness); /* * This function decides how many bytes to actually take from the * given pool, and also debits the entropy count accordingly. + * + * Increases the pool entropy watermark (c.f. __queue_entropy() and + * __dequeue_entropy()) and must be followed with a matching + * account_complete() in order to decrease it again, if possible. */ -static size_t account(struct entropy_store *r, size_t nbytes, int min) +static size_t account_begin(struct entropy_store *r, size_t nbytes, int min) { int entropy_count, have_bytes; size_t ibytes, nfrac; @@ -1419,6 +1610,7 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min) have_bytes = entropy_count >> (ENTROPY_SHIFT + 3); ibytes = min_t(size_t, ibytes, have_bytes); + if (ibytes < min) ibytes = 0; @@ -1434,6 +1626,18 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min) entropy_count = 0; WRITE_ONCE(r->entropy_count, entropy_count); + + if (!r->entropy_watermark_delta) { + /* + * This is not exact. In fact it is not known yet if + * the watermark entropy added below will be actually + * be leaked in account_complete(). But there can be + * concurrent consumers and someone has to set this. + */ + r->entropy_watermark_leak_time = jiffies; + } + r->entropy_watermark_delta += nfrac; + r->pending_extractions++; spin_unlock_irqrestore(&r->lock, flags); trace_debit_entropy(r->name, 8 * ibytes); @@ -1445,6 +1649,69 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min) return ibytes; } +/* + * Undo the pool watermark increment from a preceding + * account_begin(), if possible. + */ +static void account_complete(struct entropy_store *r, size_t ibytes) +{ + unsigned long flags; + + spin_lock_irqsave(&r->lock, flags); + r->pending_extractions--; + if (!r->queued_entropy_batches) { + /* + * There's currently no entropy queued at the producer + * side and at the very least it is safe to undo the + * watermark increment from the matching + * account_begin(). + */ + if (!r->pending_extractions) { + /* + * No other extractions pending. It is even + * safe to dismiss all watermark increments + * which had to be leaked from previous, + * unrelated account_complete() invocations + * because there had been some entropy queued + * at their time. + */ + r->entropy_watermark_delta = 0; + } else { + unsigned int nfrac; + + nfrac = ibytes << (ENTROPY_SHIFT + 3); + r->entropy_watermark_delta -= nfrac; + } + } else if (!r->pending_extractions) { + /* + * There is currently some entropy queued at the + * producer side and there's no choice but to leave + * the pool watermark untouched and thus, to "leak" + * the increment from the matching account_begin(). + * + * However, if it gets too wild, the watermark is + * reset and all currently queued entropy invalidated. + * We don't want to keep leaked watermark increments + * forever and also keep them bounded by 1/8 of the + * pool size in total in order to limit its damping + * effect on new entropy in pool_entropy_delta(). + */ + int leak_limit; + unsigned long leak_cleanup_time; + + leak_limit = r->poolinfo->poolfracbits >> 3; + leak_cleanup_time = (r->entropy_watermark_leak_time + + 2 * CRNG_RESEED_INTERVAL); + if (r->entropy_watermark_delta > leak_limit || + time_after(jiffies, leak_cleanup_time)) { + r->entropy_watermark_delta = 0; + /* Invalidate all queued entropy. */ + r->entropy_watermark_seq++; + } + } + spin_unlock_irqrestore(&r->lock, flags); +} + /* * This function does the actual extraction for extract_entropy and * extract_entropy_user. @@ -1547,6 +1814,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, { __u8 tmp[EXTRACT_SIZE]; unsigned long flags; + ssize_t ret; /* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */ if (fips_enabled) { @@ -1564,9 +1832,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, } trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); - nbytes = account(r, nbytes, min); - - return _extract_entropy(r, buf, nbytes, fips_enabled); + nbytes = account_begin(r, nbytes, min); + ret = _extract_entropy(r, buf, nbytes, fips_enabled); + account_complete(r, nbytes); + return ret; } #define warn_unseeded_randomness(previous) \ From patchwork Mon Sep 21 07:58:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788695 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BCF35618 for ; Mon, 21 Sep 2020 08:00:45 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id AA92020EDD for ; Mon, 21 Sep 2020 08:00:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726694AbgIUIA1 (ORCPT ); Mon, 21 Sep 2020 04:00:27 -0400 Received: from mx2.suse.de ([195.135.220.15]:57142 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726492AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 82889B505; Mon, 21 Sep 2020 07:59:55 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 11/41] random: convert add_timer_randomness() to queued_entropy API Date: Mon, 21 Sep 2020 09:58:27 +0200 Message-Id: <20200921075857.4424-12-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org In an effort to drop __credit_entropy_bits_fast() in favor of the new __queue_entropy()/__dispatch_queued_entropy_fast() API, convert add_timer_randomness() from the former to the latter. There is no change in functionality at this point, because __credit_entropy_bits_fast() has already been reimplemented on top of the new API before. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index b91d1fc08ac5..e8c86abde901 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1400,6 +1400,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) long delta, delta2, delta3; bool reseed; unsigned long flags; + struct queued_entropy q = { 0 }; sample.jiffies = jiffies; sample.cycles = random_get_entropy(); @@ -1432,13 +1433,14 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) r = &input_pool; spin_lock_irqsave(&r->lock, flags); - __mix_pool_bytes(r, &sample, sizeof(sample)); /* * delta is now minimum absolute delta. * Round down by 1 bit on general principles, * and limit entropy estimate to 12 bits. */ - reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11)); + __queue_entropy(r, &q, min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT); + __mix_pool_bytes(r, &sample, sizeof(sample)); + reseed = __dispatch_queued_entropy_fast(r, &q); spin_unlock_irqrestore(&r->lock, flags); if (reseed) crng_reseed(&primary_crng, r); From patchwork Mon Sep 21 07:58:28 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788693 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7A8B11668 for ; Mon, 21 Sep 2020 08:00:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6BDC920EDD for ; Mon, 21 Sep 2020 08:00:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726702AbgIUIA2 (ORCPT ); Mon, 21 Sep 2020 04:00:28 -0400 Received: from mx2.suse.de ([195.135.220.15]:57144 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726489AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 1B007B50A; Mon, 21 Sep 2020 07:59:56 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 12/41] random: convert add_interrupt_randomness() to queued_entropy API Date: Mon, 21 Sep 2020 09:58:28 +0200 Message-Id: <20200921075857.4424-13-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org In an effort to drop __credit_entropy_bits_fast() in favor of the new __queue_entropy()/__dispatch_queued_entropy_fast() API, convert add_interrupt_randomness() from the former to the latter. There is no change in functionality at this point, because __credit_entropy_bits_fast() has already been reimplemented on top of the new API before. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index e8c86abde901..bd3774c6be4b 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1512,6 +1512,7 @@ void add_interrupt_randomness(int irq, int irq_flags) unsigned long seed; int credit = 0; bool reseed; + struct queued_entropy q = { 0 }; if (cycles == 0) cycles = get_reg(fast_pool, regs); @@ -1546,24 +1547,27 @@ void add_interrupt_randomness(int irq, int irq_flags) if (!spin_trylock(&r->lock)) return; - fast_pool->last = now; - __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); - /* * If we have architectural seed generator, produce a seed and - * add it to the pool. For the sake of paranoia don't let the - * architectural seed generator dominate the input from the - * interrupt noise. + * add it to the pool further below. For the sake of paranoia + * don't let the architectural seed generator dominate the + * input from the interrupt noise. */ - if (arch_get_random_seed_long(&seed)) { - __mix_pool_bytes(r, &seed, sizeof(seed)); - credit = 1; - } + credit = !!arch_get_random_long(&seed); + fast_pool->last = now; fast_pool->count = 0; - /* award one bit for the contents of the fast pool */ - reseed = __credit_entropy_bits_fast(r, credit + 1); + __queue_entropy(r, &q, (credit + 1) << ENTROPY_SHIFT); + __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); + if (credit) { + /* + * A seed has been obtained from + * arch_get_random_seed_long() above, mix it in. + */ + __mix_pool_bytes(r, &seed, sizeof(seed)); + } + reseed = __dispatch_queued_entropy_fast(r, &q); spin_unlock(&r->lock); if (reseed) crng_reseed(&primary_crng, r); From patchwork Mon Sep 21 07:58:29 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788691 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1B5EE139A for ; Mon, 21 Sep 2020 08:00:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0AE4220BED for ; Mon, 21 Sep 2020 08:00:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726706AbgIUIA2 (ORCPT ); Mon, 21 Sep 2020 04:00:28 -0400 Received: from mx2.suse.de ([195.135.220.15]:56802 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726487AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id B03C1B50E; Mon, 21 Sep 2020 07:59:56 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 13/41] random: convert try_to_generate_entropy() to queued_entropy API Date: Mon, 21 Sep 2020 09:58:29 +0200 Message-Id: <20200921075857.4424-14-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org In an effort to drop __credit_entropy_bits_fast() in favor of the new __queue_entropy()/__dispatch_queued_entropy_fast() API, convert try_to_generate_entropy() from the former to the latter. Replace the call to __credit_entropy_bits_fast() from the timer callback, entropy_timer(), by a queue_entropy() operation. Dispatch it from the loop in try_to_generate_entropy() by invoking __dispatch_queued_entropy_fast() after the timestamp has been mixed into the input_pool. In order to provide the timer callback and try_to_generate_entropy() with access to a common struct queued_entropy instance, move the currently anonymous struct definition from the local 'stack' variable declaration in try_to_generate_entropy() to file scope and assign it a name, "struct try_to_generate_entropy_stack". Make entropy_timer() obtain a pointer to the corresponding instance by means of container_of() on the ->timer member contained therein. Amend struct try_to_generate_entropy_stack by a new member ->q of type struct queued_entropy. Note that the described scheme alters behaviour a bit: first of all, new entropy credit now gets only dispatched to the pool after the actual mixing has completed rather than in an unsynchronized manner directly from the timer callback. As the mixing loop try_to_generate_entropy() is expected to run at higher frequency than the timer, this is unlikely to make any difference in practice. Furthermore, the pool entropy watermark as tracked over the period from queuing the entropy in the timer callback and to its subsequent dispatch from try_to_generate_entropy() is now taken into account when calculating the actual credit at dispatch. In consequence, the amount of new entropy dispatched to the pool will potentially be lowered if said period happens to overlap with the pool extraction from an initial crng_reseed() on the primary_crng. However, as getting the primary_crng seeded is the whole point of the try_to_generate_entropy() exercise, this won't matter. Note that instead of calling queue_entropy() from the timer callback, an alternative would have been to maintain an invocation counter and queue that up from try_to_generate_entropy() right before the mix operation. This would have reduced the described effect of the pool's entropy watermark and in fact matched the intended queue_entropy() API usage better. However, in this particular case of try_to_generate_entropy(), jitter is desired and invoking queue_entropy() with its buffer locking etc. from the timer callback could potentially contribute to that. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 42 +++++++++++++++++++++++++++++------------- 1 file changed, 29 insertions(+), 13 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index bd3774c6be4b..dfbe49fdbcf1 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1911,6 +1911,12 @@ void get_random_bytes(void *buf, int nbytes) EXPORT_SYMBOL(get_random_bytes); +struct try_to_generate_entropy_stack { + unsigned long now; + struct timer_list timer; + struct queued_entropy q; +} stack; + /* * Each time the timer fires, we expect that we got an unpredictable * jump in the cycle counter. Even if the timer is running on another @@ -1926,14 +1932,10 @@ EXPORT_SYMBOL(get_random_bytes); */ static void entropy_timer(struct timer_list *t) { - bool reseed; - unsigned long flags; + struct try_to_generate_entropy_stack *stack; - spin_lock_irqsave(&input_pool.lock, flags); - reseed = __credit_entropy_bits_fast(&input_pool, 1); - spin_unlock_irqrestore(&input_pool.lock, flags); - if (reseed) - crng_reseed(&primary_crng, &input_pool); + stack = container_of(t, struct try_to_generate_entropy_stack, timer); + queue_entropy(&input_pool, &stack->q, 1 << ENTROPY_SHIFT); } /* @@ -1942,10 +1944,9 @@ static void entropy_timer(struct timer_list *t) */ static void try_to_generate_entropy(void) { - struct { - unsigned long now; - struct timer_list timer; - } stack; + struct try_to_generate_entropy_stack stack = { 0 }; + unsigned long flags; + bool reseed; stack.now = random_get_entropy(); @@ -1957,14 +1958,29 @@ static void try_to_generate_entropy(void) while (!crng_ready()) { if (!timer_pending(&stack.timer)) mod_timer(&stack.timer, jiffies+1); - mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now)); + spin_lock_irqsave(&input_pool.lock, flags); + __mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now)); + reseed = __dispatch_queued_entropy_fast(&input_pool, &stack.q); + spin_unlock_irqrestore(&input_pool.lock, flags); + + if (reseed) + crng_reseed(&primary_crng, &input_pool); + schedule(); stack.now = random_get_entropy(); } del_timer_sync(&stack.timer); destroy_timer_on_stack(&stack.timer); - mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now)); + spin_lock_irqsave(&input_pool.lock, flags); + __mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now)); + /* + * Must be called here once more in order to complete a + * previously unmatched queue_entropy() from entropy_timer(), + * if any. + */ + __dispatch_queued_entropy_fast(&input_pool, &stack.q); + spin_unlock_irqrestore(&input_pool.lock, flags); } /* From patchwork Mon Sep 21 07:58:30 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788697 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id A9354139A for ; Mon, 21 Sep 2020 08:00:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 91618214F1 for ; Mon, 21 Sep 2020 08:00:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726506AbgIUIA1 (ORCPT ); Mon, 21 Sep 2020 04:00:27 -0400 Received: from mx2.suse.de ([195.135.220.15]:56798 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726496AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 3C97DB50F; Mon, 21 Sep 2020 07:59:57 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 14/41] random: drop __credit_entropy_bits_fast() Date: Mon, 21 Sep 2020 09:58:30 +0200 Message-Id: <20200921075857.4424-15-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org All former call sites of __credit_entropy_bits_fast() have been converted to the new __dispatch_queued_entropy_fast() API. Drop the now unused __credit_entropy_bits_fast(). Signed-off-by: Nicolai Stange --- drivers/char/random.c | 14 -------------- 1 file changed, 14 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index dfbe49fdbcf1..60ce185d7b2d 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -900,20 +900,6 @@ static bool __dispatch_queued_entropy_fast(struct entropy_store *r, return false; } -/* - * Credit the entropy store with n bits of entropy. - * To be used from hot paths when it is either known that nbits is - * smaller than one half of the pool size or losing anything beyond that - * doesn't matter. Must be called with r->lock being held. - */ -static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits) -{ - struct queued_entropy q = { 0 }; - - __queue_entropy(r, &q, nbits << ENTROPY_SHIFT); - return __dispatch_queued_entropy_fast(r, &q); -} - /* * Credit the pool with previously queued entropy. * From patchwork Mon Sep 21 07:58:31 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788687 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2003B139A for ; Mon, 21 Sep 2020 08:00:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0FFAF214F1 for ; Mon, 21 Sep 2020 08:00:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726674AbgIUIAO (ORCPT ); Mon, 21 Sep 2020 04:00:14 -0400 Received: from mx2.suse.de ([195.135.220.15]:57298 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726506AbgIUH7X (ORCPT ); Mon, 21 Sep 2020 03:59:23 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id C919BB512; Mon, 21 Sep 2020 07:59:57 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 15/41] random: convert add_hwgenerator_randomness() to queued_entropy API Date: Mon, 21 Sep 2020 09:58:31 +0200 Message-Id: <20200921075857.4424-16-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org In an effort to drop credit_entropy_bits() in favor of the new queue_entropy()/dispatch_queued_entropy() API, convert add_hwgenerator_randomness() from the former to the latter. As a side effect, the pool entropy watermark as tracked over the duration of the mix_pool_bytes() operation is now taken correctly taken into account when calulating the amount of new entropy to dispatch to the pool based on the latter's fill level. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 60ce185d7b2d..78e65367ea86 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -2640,6 +2640,7 @@ void add_hwgenerator_randomness(const char *buffer, size_t count, size_t entropy) { struct entropy_store *poolp = &input_pool; + struct queued_entropy q = { 0 }; if (unlikely(crng_init == 0)) { crng_fast_load(buffer, count); @@ -2652,8 +2653,9 @@ void add_hwgenerator_randomness(const char *buffer, size_t count, */ wait_event_interruptible(random_write_wait, kthread_should_stop() || ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits); + queue_entropy(poolp, &q, entropy << ENTROPY_SHIFT); mix_pool_bytes(poolp, buffer, count); - credit_entropy_bits(poolp, entropy); + dispatch_queued_entropy(poolp, &q); } EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); From patchwork Mon Sep 21 07:58:32 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788683 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 59CEC618 for ; Mon, 21 Sep 2020 08:00:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 49F5420EDD for ; Mon, 21 Sep 2020 08:00:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726518AbgIUIAO (ORCPT ); Mon, 21 Sep 2020 04:00:14 -0400 Received: from mx2.suse.de ([195.135.220.15]:57374 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726510AbgIUH7Y (ORCPT ); Mon, 21 Sep 2020 03:59:24 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 66493B511; Mon, 21 Sep 2020 07:59:58 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 16/41] random: convert random_ioctl() to queued_entropy API Date: Mon, 21 Sep 2020 09:58:32 +0200 Message-Id: <20200921075857.4424-17-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org In an effort to drop credit_entropy_bits_safe() in favor of the new queue_entropy()/dispatch_queued_entropy() API, convert random_ioctl() from the former to the latter. Implement two helpers: - queue_entropy_bits_safe(), which checks the entropy passed from userspace for extreme values in analogy to what credit_entropy_bits_safe() did - discard_queue_entropy(), which is invoked from random_ioctly() to discard the entropy queued prior to the write_pool() call in case the latter fails. Use them to convert the two call sites of credit_entropy_bits_safe() in random_ioctl() to the new API. As a side effect, the pool entropy watermark as tracked over the duration of the write_pool() operation is now taken correctly taken into account when calulating the amount of new entropy to dispatch to the pool based on the latter's fill level. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 57 ++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 53 insertions(+), 4 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 78e65367ea86..03eadefabbca 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -737,7 +737,9 @@ struct queued_entropy { * dispatch. However, any such sequence of invocations must eventually * be followed by exactly one call to either of __dequeue_entropy(), * __dispatch_queued_entropy_fast() or dispatch_queued_entropy() - * when the actual pool mixing has completed. + * when the actual pool mixing has completed. Alternatively, + * discard_queued_entropy() may be called in case the mixing has + * failed. * __queue_entropy() must be called with r->lock held. * * Entropy extraction is a two-step process: @@ -813,6 +815,26 @@ static void queue_entropy(struct entropy_store *r, struct queued_entropy *q, spin_unlock_irqrestore(&r->lock, flags); } +/* + * Queue entropy which comes from userspace and might take extreme + * values. + */ +static int queue_entropy_bits_safe(struct entropy_store *r, + struct queued_entropy *q, + int nbits) +{ + const int nbits_max = r->poolinfo->poolwords * 32; + + if (nbits < 0) + return -EINVAL; + + /* Cap the value to avoid overflows */ + nbits = min(nbits, nbits_max); + + queue_entropy(r, q, nbits << ENTROPY_SHIFT); + return 0; +} + /* * Dequeue previously queued entropy and return the pool entropy * watermark to be used in pool_entropy_delta(). @@ -950,6 +972,22 @@ static void dispatch_queued_entropy(struct entropy_store *r, } } +/* + * Discard queued entropy. May be called when e.g. a write_pool() + * operation failed and the corresponding previously queued entropy + * should not get dispatched to the pool. + */ +static void discard_queued_entropy(struct entropy_store *r, + struct queued_entropy *q) +{ + unsigned long flags; + int pool_watermark; + + spin_lock_irqsave(&r->lock, flags); + __dequeue_entropy(r, q, &pool_watermark); + spin_unlock_irqrestore(&r->lock, flags); +} + /* * Credit the entropy store with n bits of entropy. * Use credit_entropy_bits_safe() if the value comes from userspace @@ -2272,6 +2310,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) int size, ent_count; int __user *p = (int __user *)arg; int retval; + struct queued_entropy q = { 0 }; switch (cmd) { case RNDGETENTCNT: @@ -2285,7 +2324,11 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) return -EPERM; if (get_user(ent_count, p)) return -EFAULT; - return credit_entropy_bits_safe(&input_pool, ent_count); + retval = queue_entropy_bits_safe(&input_pool, &q, ent_count); + if (retval < 0) + return retval; + dispatch_queued_entropy(&input_pool, &q); + return 0; case RNDADDENTROPY: if (!capable(CAP_SYS_ADMIN)) return -EPERM; @@ -2295,11 +2338,17 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) return -EINVAL; if (get_user(size, p++)) return -EFAULT; + retval = queue_entropy_bits_safe(&input_pool, &q, ent_count); + if (retval < 0) + return retval; retval = write_pool(&input_pool, (const char __user *)p, size); - if (retval < 0) + if (retval < 0) { + discard_queued_entropy(&input_pool, &q); return retval; - return credit_entropy_bits_safe(&input_pool, ent_count); + } + discard_queued_entropy(&input_pool, &q); + return 0; case RNDZAPENTCNT: case RNDCLEARPOOL: /* From patchwork Mon Sep 21 07:58:33 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788685 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 85FFF1668 for ; Mon, 21 Sep 2020 08:00:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 768DF2151B for ; Mon, 21 Sep 2020 08:00:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726671AbgIUIAO (ORCPT ); Mon, 21 Sep 2020 04:00:14 -0400 Received: from mx2.suse.de ([195.135.220.15]:57440 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726514AbgIUH7Y (ORCPT ); Mon, 21 Sep 2020 03:59:24 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id ECF35B515; Mon, 21 Sep 2020 07:59:58 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 17/41] random: drop credit_entropy_bits() and credit_entropy_bits_safe() Date: Mon, 21 Sep 2020 09:58:33 +0200 Message-Id: <20200921075857.4424-18-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org All former call sites of credit_entropy_bits() and credit_entropy_bits_safe() respectively have been converted to the new dispatch_queued_entropy() API. Drop the now unused functions. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 29 +---------------------------- 1 file changed, 1 insertion(+), 28 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 03eadefabbca..a49805d0d23c 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -533,7 +533,7 @@ static __u32 const twist_table[8] = { /* * This function adds bytes into the entropy "pool". It does not * update the entropy estimate. The caller should call - * credit_entropy_bits if this is appropriate. + * queue_entropy()+dispatch_queued_entropy() if this is appropriate. * * The pool is stirred with a primitive polynomial of the appropriate * degree, and then twisted. We twist by three bits at a time because @@ -988,33 +988,6 @@ static void discard_queued_entropy(struct entropy_store *r, spin_unlock_irqrestore(&r->lock, flags); } -/* - * Credit the entropy store with n bits of entropy. - * Use credit_entropy_bits_safe() if the value comes from userspace - * or otherwise should be checked for extreme values. - */ -static void credit_entropy_bits(struct entropy_store *r, int nbits) -{ - struct queued_entropy q = { 0 }; - - queue_entropy(r, &q, nbits << ENTROPY_SHIFT); - dispatch_queued_entropy(r, &q); -} - -static int credit_entropy_bits_safe(struct entropy_store *r, int nbits) -{ - const int nbits_max = r->poolinfo->poolwords * 32; - - if (nbits < 0) - return -EINVAL; - - /* Cap the value to avoid overflows */ - nbits = min(nbits, nbits_max); - - credit_entropy_bits(r, nbits); - return 0; -} - /********************************************************************* * * CRNG using CHACHA20 From patchwork Mon Sep 21 07:58:34 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788681 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 780CD618 for ; Mon, 21 Sep 2020 08:00:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5D07720874 for ; Mon, 21 Sep 2020 08:00:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726461AbgIUIAI (ORCPT ); Mon, 21 Sep 2020 04:00:08 -0400 Received: from mx2.suse.de ([195.135.220.15]:57542 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726518AbgIUH70 (ORCPT ); Mon, 21 Sep 2020 03:59:26 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 8BDA5B514; Mon, 21 Sep 2020 07:59:59 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 18/41] random: move arch_get_random_seed() calls in crng_reseed() into own loop Date: Mon, 21 Sep 2020 09:58:34 +0200 Message-Id: <20200921075857.4424-19-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org x86's RDSEED/RDRAND insns have reportedly been slowed down significantly due to the ucode update required to mitigate against the "Special Register Buffer Data Sampling" vulnerability (CVE-2020-0543) and should not get invoked from the interrupt path anymore. In preparation of getting rid of that arch_get_random_long() call currently found in add_interrupt_randomness(), move those arch_get_random_long() calls in crng_reseed() into a separate loop and outside of the crng->lock. There is no functional change. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index a49805d0d23c..1945249597e0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1200,14 +1200,18 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) _crng_backtrack_protect(&primary_crng, buf.block, CHACHA_KEY_SIZE); } - spin_lock_irqsave(&crng->lock, flags); + for (i = 0; i < 8; i++) { unsigned long rv; if (!arch_get_random_seed_long(&rv) && !arch_get_random_long(&rv)) rv = random_get_entropy(); - crng->state[i+4] ^= buf.key[i] ^ rv; + buf.key[i] ^= rv; } + + spin_lock_irqsave(&crng->lock, flags); + for (i = 0; i < 8; i++) + crng->state[i+4] ^= buf.key[i]; memzero_explicit(&buf, sizeof(buf)); crng->init_time = jiffies; spin_unlock_irqrestore(&crng->lock, flags); From patchwork Mon Sep 21 07:58:35 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788679 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 678B6618 for ; Mon, 21 Sep 2020 08:00:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5248F20EDD for ; Mon, 21 Sep 2020 08:00:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726620AbgIUH7u (ORCPT ); Mon, 21 Sep 2020 03:59:50 -0400 Received: from mx2.suse.de ([195.135.220.15]:57622 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726524AbgIUH71 (ORCPT ); Mon, 21 Sep 2020 03:59:27 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 2A891B510; Mon, 21 Sep 2020 08:00:00 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 19/41] random: reintroduce arch_has_random() + arch_has_random_seed() Date: Mon, 21 Sep 2020 09:58:35 +0200 Message-Id: <20200921075857.4424-20-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org A future patch will introduce support for making up for a certain amount of lacking entropy in crng_reseed() by means of arch_get_random_long() or arch_get_random_seed_long() respectively. However, before even the tiniest bit of precious entropy is withdrawn from the input_pool, it should be checked if whether the current arch even has support for these. Reintroduce arch_has_random() + arch_has_random_seed() and implement them for arm64, powerpc, s390 and x86 as appropriate (yeah, I know this should go in separate commits, but this is part of a RFC series). Note that this more or less reverts commits 647f50d5d9d9 ("linux/random.h: Remove arch_has_random, arch_has_random_seed") cbac004995a0 ("powerpc: Remove arch_has_random, arch_has_random_seed") 5e054c820f59 ("s390: Remove arch_has_random, arch_has_random_seed") 5f2ed7f5b99b ("x86: Remove arch_has_random, arch_has_random_seed") Signed-off-by: Nicolai Stange --- arch/arm64/include/asm/archrandom.h | 25 ++++++++++++++++++------- arch/powerpc/include/asm/archrandom.h | 12 +++++++++++- arch/s390/include/asm/archrandom.h | 14 ++++++++++++-- arch/x86/include/asm/archrandom.h | 18 ++++++++++++++---- include/linux/random.h | 8 ++++++++ 5 files changed, 63 insertions(+), 14 deletions(-) diff --git a/arch/arm64/include/asm/archrandom.h b/arch/arm64/include/asm/archrandom.h index 44209f6146aa..055d18713db7 100644 --- a/arch/arm64/include/asm/archrandom.h +++ b/arch/arm64/include/asm/archrandom.h @@ -26,17 +26,13 @@ static inline bool __arm64_rndr(unsigned long *v) return ok; } -static inline bool __must_check arch_get_random_long(unsigned long *v) -{ - return false; -} -static inline bool __must_check arch_get_random_int(unsigned int *v) +static inline bool arch_has_random(void) { return false; } -static inline bool __must_check arch_get_random_seed_long(unsigned long *v) +static inline bool arch_has_random_seed(void) { /* * Only support the generic interface after we have detected @@ -44,7 +40,22 @@ static inline bool __must_check arch_get_random_seed_long(unsigned long *v) * cpufeature code and with potential scheduling between CPUs * with and without the feature. */ - if (!cpus_have_const_cap(ARM64_HAS_RNG)) + return cpus_have_const_cap(ARM64_HAS_RNG); +} + +static inline bool __must_check arch_get_random_long(unsigned long *v) +{ + return false; +} + +static inline bool __must_check arch_get_random_int(unsigned int *v) +{ + return false; +} + +static inline bool __must_check arch_get_random_seed_long(unsigned long *v) +{ + if (!arch_has_random_seed()) return false; return __arm64_rndr(v); diff --git a/arch/powerpc/include/asm/archrandom.h b/arch/powerpc/include/asm/archrandom.h index 9a53e29680f4..47c2d74e7244 100644 --- a/arch/powerpc/include/asm/archrandom.h +++ b/arch/powerpc/include/asm/archrandom.h @@ -6,6 +6,16 @@ #include +static inline bool arch_has_random(void) +{ + return false; +} + +static inline bool arch_has_random_seed(void) +{ + return ppc_md.get_random_seed; +} + static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; @@ -18,7 +28,7 @@ static inline bool __must_check arch_get_random_int(unsigned int *v) static inline bool __must_check arch_get_random_seed_long(unsigned long *v) { - if (ppc_md.get_random_seed) + if (arch_has_random_seed()) return ppc_md.get_random_seed(v); return false; diff --git a/arch/s390/include/asm/archrandom.h b/arch/s390/include/asm/archrandom.h index de61ce562052..18973845634c 100644 --- a/arch/s390/include/asm/archrandom.h +++ b/arch/s390/include/asm/archrandom.h @@ -21,6 +21,16 @@ extern atomic64_t s390_arch_random_counter; bool s390_arch_random_generate(u8 *buf, unsigned int nbytes); +static inline bool arch_has_random(void) +{ + return false; +} + +static inline bool arch_has_random_seed(void) +{ + return static_branch_likely(&s390_arch_random_available); +} + static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; @@ -33,7 +43,7 @@ static inline bool __must_check arch_get_random_int(unsigned int *v) static inline bool __must_check arch_get_random_seed_long(unsigned long *v) { - if (static_branch_likely(&s390_arch_random_available)) { + if (arch_has_random_seed()) { return s390_arch_random_generate((u8 *)v, sizeof(*v)); } return false; @@ -41,7 +51,7 @@ static inline bool __must_check arch_get_random_seed_long(unsigned long *v) static inline bool __must_check arch_get_random_seed_int(unsigned int *v) { - if (static_branch_likely(&s390_arch_random_available)) { + if (arch_has_random_seed()) { return s390_arch_random_generate((u8 *)v, sizeof(*v)); } return false; diff --git a/arch/x86/include/asm/archrandom.h b/arch/x86/include/asm/archrandom.h index ebc248e49549..030f46c9e310 100644 --- a/arch/x86/include/asm/archrandom.h +++ b/arch/x86/include/asm/archrandom.h @@ -70,24 +70,34 @@ static inline bool __must_check rdseed_int(unsigned int *v) */ #ifdef CONFIG_ARCH_RANDOM +static inline bool arch_has_random(void) +{ + return static_cpu_has(X86_FEATURE_RDRAND); +} + +static inline bool arch_has_random_seed(void) +{ + return static_cpu_has(X86_FEATURE_RDSEED); +} + static inline bool __must_check arch_get_random_long(unsigned long *v) { - return static_cpu_has(X86_FEATURE_RDRAND) ? rdrand_long(v) : false; + return arch_has_random() ? rdrand_long(v) : false; } static inline bool __must_check arch_get_random_int(unsigned int *v) { - return static_cpu_has(X86_FEATURE_RDRAND) ? rdrand_int(v) : false; + return arch_has_random() ? rdrand_int(v) : false; } static inline bool __must_check arch_get_random_seed_long(unsigned long *v) { - return static_cpu_has(X86_FEATURE_RDSEED) ? rdseed_long(v) : false; + return arch_has_random_seed() ? rdseed_long(v) : false; } static inline bool __must_check arch_get_random_seed_int(unsigned int *v) { - return static_cpu_has(X86_FEATURE_RDSEED) ? rdseed_int(v) : false; + return arch_has_random_seed() ? rdseed_int(v) : false; } extern void x86_init_rdrand(struct cpuinfo_x86 *c); diff --git a/include/linux/random.h b/include/linux/random.h index f45b8be3e3c4..d4653422a0c7 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -120,6 +120,14 @@ unsigned long randomize_page(unsigned long start, unsigned long range); #ifdef CONFIG_ARCH_RANDOM # include #else +static inline bool arch_has_random(void) +{ + return false; +} +static inline bool arch_has_random_seed(void) +{ + return false; +} static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; From patchwork Mon Sep 21 07:58:36 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788673 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E6F2B618 for ; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D714A20EDD for ; Mon, 21 Sep 2020 07:59:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726630AbgIUH7v (ORCPT ); Mon, 21 Sep 2020 03:59:51 -0400 Received: from mx2.suse.de ([195.135.220.15]:57702 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726532AbgIUH71 (ORCPT ); Mon, 21 Sep 2020 03:59:27 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id BB3A9B51A; Mon, 21 Sep 2020 08:00:00 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 20/41] random: provide min_crng_reseed_pool_entropy() Date: Mon, 21 Sep 2020 09:58:36 +0200 Message-Id: <20200921075857.4424-21-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Currently, the current minimum entropy required from the input_pool for reseeding the primary_crng() is 16 bytes == 128 bits. A future patch will introduce support for obtaining up to a certain fraction thereof from the architecture's RNG, if available. This will effectively lower the minimum input_pool ->entropy_count required for a successful reseed of the primary_crng. As this value is used at a couple of places, namely crng_reseed() itself as well as dispatch_queued_entropy() and __dispatch_queued_entropy_fast(), introduce min_crng_reseed_pool_entropy() to ensure consistency among these. min_crng_reseed_pool_entropy() returns the minimum amount of entropy in bytes required from the input_pool for a successful reseed of the primary_crng. Currently it's hardcoded to 16. Use it in place of the hardcoded constants in crng_reseed(), dispatch_queued_entropy() and __dispatch_queued_entropy_fast(). Signed-off-by: Nicolai Stange --- drivers/char/random.c | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 1945249597e0..424de1565927 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -516,6 +516,8 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, static ssize_t _extract_entropy(struct entropy_store *r, void *buf, size_t nbytes, int fips); +static int min_crng_reseed_pool_entropy(void); + static void crng_reseed(struct crng_state *crng, struct entropy_store *r); static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy; @@ -916,7 +918,7 @@ static bool __dispatch_queued_entropy_fast(struct entropy_store *r, if (unlikely(r == &input_pool && crng_init < 2)) { const int entropy_bits = entropy_count >> ENTROPY_SHIFT; - return (entropy_bits >= 128); + return (entropy_bits >= min_crng_reseed_pool_entropy() * 8); } return false; @@ -965,7 +967,7 @@ static void dispatch_queued_entropy(struct entropy_store *r, if (crng_init < 2) { const int entropy_bits = entropy_count >> ENTROPY_SHIFT; - if (entropy_bits < 128) + if (entropy_bits < min_crng_reseed_pool_entropy() * 8) return; crng_reseed(&primary_crng, r); } @@ -1182,6 +1184,15 @@ static int crng_slow_load(const char *cp, size_t len) return 1; } +/* + * Minimum amount of entropy in bytes required from the input_pool for + * a successful reseed of the primary_crng. + */ +static int min_crng_reseed_pool_entropy(void) +{ + return 16; +} + static void crng_reseed(struct crng_state *crng, struct entropy_store *r) { unsigned long flags; @@ -1192,7 +1203,8 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) } buf; if (r) { - num = extract_entropy(r, &buf, 32, 16); + num = extract_entropy(r, &buf, 32, + min_crng_reseed_pool_entropy()); if (num == 0) return; } else { From patchwork Mon Sep 21 07:58:37 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788671 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BF499618 for ; Mon, 21 Sep 2020 07:59:50 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A73AD20EDD for ; Mon, 21 Sep 2020 07:59:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726417AbgIUH7u (ORCPT ); Mon, 21 Sep 2020 03:59:50 -0400 Received: from mx2.suse.de ([195.135.220.15]:56892 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726537AbgIUH71 (ORCPT ); Mon, 21 Sep 2020 03:59:27 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 59C6DB51C; Mon, 21 Sep 2020 08:00:01 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 21/41] random: don't invoke arch_get_random_long() from add_interrupt_randomness() Date: Mon, 21 Sep 2020 09:58:37 +0200 Message-Id: <20200921075857.4424-22-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org x86's RDSEED/RDRAND insns have reportedly been slowed down significantly on certain CPU families due to the ucode update required to mitigate against the "Special Register Buffer Data Sampling" vulnerability (CVE-2020-0543) and should not get invoked from the interrupt path anymore. Currently, add_interrupt_randomness() obtains an arch_get_random_long() sample for each bit of entropy awarded to the "interrupt source", mixes it into the input_pool and awards that sample another bit of entropy. This lock step between the interrupt source and arch_get_random_long() ensures that the latter cannot dominate the former. There are some more entropy sources all mixing into input_pool with a non-zero entropy attribution: - try_to_generate_entropy() at boot time - add_input_randomness() and add_disk_randomness() - add_hwgenerator_randomness(). I don't see what's so special about the interrupt randomness source that entropy awarded to the architectural RNG should be limited to its output rate only rather than to the joint rate from all these entropy sources as a whole. Follow this approach. Don't mix arch_get_random_long() entropy from add_interrupt_randomness() into the input_pool. Instead, make crng_reseed() invoke the architectural RNG to make up for any lack of entropy up to one half of the minimum seed size. That is, if the input_pool contains less than 128 bits of entropy, the architectural RNG will be invoked and attributed an entropy value equal to the difference, but never more than 64 bits. Note that - the architectural RNG won't be able to dominate the other randomness sources taken together in this scheme and - in case the input_pool contains more entropy than required for the minimum seed level, it won't be attributed any entropy at all. That is, the architectural RNG is effectively turned into an emergency reserve in a sense. A potentially adverse effect of this change is that entropy might get depleted at a higher rate than before from the interrupt source, namely if the input_pool contains more than half of the minimum seed size of entropy at reseed. However, the entropy sources feeding into input_pool are assumed to provide entropy at a steady rate when averaged over the time scale of a reseed interval, which is several minutes in length. Thus, as the primary_crng reseeds are the only consumers of input_pool entropy nowadays, the input_pool's fill level can be assumed to be relatively constant at the time of reseeds and an equilibrium between the rates at which the input_pool receives and releases entropy will be reached. OTOH, remember that the rate at which the pool entropy increases is exponentially damped as the pool fills up. In case the interrupt source is a major contributor to the pool, not having to account anymore for the architectural RNG's noise formerly mixed in in lockstep will leave considerably more pool capacity to the interrupt noise, which is a welcomed side effect. So, make min_crng_reseed_pool_entropy() return only half of the minimum seed size required in case an architectural RNG will likely be able to provide the other half, as indicated by arch_has_random() || arch_has_random_seed(). This will effectively - make dispatch_queued_entropy() to attempt an intitial seed of the primary_crng as soon as the amount of entropy available from the input_pool has first exceeded that threshold and also - makes crng_reseed() to lower the minimum amount of entropy to be extracted from the input_pool by means of extract_entropy() to one half of the minimum seed size. Introduce a new boolean variable "arch_randomness_required" to crng_reseed() for tracking whether or not the seed must be amended by additional output from the architectural RNG. Initialize it to false, make crng_reseed() set it in case its extract_entropy() invocation could obtain only less than the minimum seed size from input_pool. crng_reseed() already attempts to xor output from the architectural RNG over the full length of the crng state, i.e. over the full length of the latter's 256 bit ChaCha20 key. Currently, failure in doing so is not considered fatal. Make it so if arch_randomness_required has been set. Note that assuming one bit of entropy per bit obtained from the architectural RNG, it would actually suffice to successfully obtain (16 - num + sizeof(u32) - 1) / sizeof(u32) u32's from arch_get_random_long()/arch_get_random_seed_long(), where 16 is the minimum seed size in bytes and num is the number of bytes which have been previuously obtained from the input_pool. However, this assumption might be overly optimistic and the total number of arch_get_random_long() invocations per 64 bits of entropy attributed to it has already been lowered from >= 64 to eight by this patch. Moreover, the arch_get_random_long() loop in crng_reseed() would need to get reorganized in order to make sure that there will actually be a sufficient number of successful invocations when writing to the target buffer area following the bytes obtained from the input_pool. Thus, in case failing arch_get_random_long()s in combination with arch_randomness_required set became a problem in the future, it would be better to improve the error path and simply return the unused entropy extracted from the input_pool back. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 49 +++++++++++++++++++++++++------------------ 1 file changed, 29 insertions(+), 20 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 424de1565927..7712b4464ef5 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1190,6 +1190,14 @@ static int crng_slow_load(const char *cp, size_t len) */ static int min_crng_reseed_pool_entropy(void) { + /* + * If there's an architecture provided RNG, use it for + * up to one half of the minimum entropy needed for + * reseeding. That way it won't dominate the entropy + * collected by other means at input_pool. + */ + if (arch_has_random() || arch_has_random_seed()) + return 8; return 16; } @@ -1197,6 +1205,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) { unsigned long flags; int i, num; + bool arch_randomness_required = false; union { __u8 block[CHACHA_BLOCK_SIZE]; __u32 key[8]; @@ -1205,8 +1214,16 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) if (r) { num = extract_entropy(r, &buf, 32, min_crng_reseed_pool_entropy()); - if (num == 0) + if (num == 0) { return; + } else if (num < 16) { + /* + * The input_pool did not provide sufficient + * entropy for reseeding and the architecture + * provided RNG will have to make up for it. + */ + arch_randomness_required = true; + } } else { _extract_crng(&primary_crng, buf.block); _crng_backtrack_protect(&primary_crng, buf.block, @@ -1216,8 +1233,17 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) for (i = 0; i < 8; i++) { unsigned long rv; if (!arch_get_random_seed_long(&rv) && - !arch_get_random_long(&rv)) + !arch_get_random_long(&rv)) { + if (arch_randomness_required) { + /* + * The input_pool failed to provide + * sufficient entropy and the arch RNG + * could not make up for that either. + */ + return; + } rv = random_get_entropy(); + } buf.key[i] ^= rv; } @@ -1522,8 +1548,6 @@ void add_interrupt_randomness(int irq, int irq_flags) cycles_t cycles = random_get_entropy(); __u32 c_high, j_high; __u64 ip; - unsigned long seed; - int credit = 0; bool reseed; struct queued_entropy q = { 0 }; @@ -1560,26 +1584,11 @@ void add_interrupt_randomness(int irq, int irq_flags) if (!spin_trylock(&r->lock)) return; - /* - * If we have architectural seed generator, produce a seed and - * add it to the pool further below. For the sake of paranoia - * don't let the architectural seed generator dominate the - * input from the interrupt noise. - */ - credit = !!arch_get_random_long(&seed); - fast_pool->last = now; fast_pool->count = 0; /* award one bit for the contents of the fast pool */ - __queue_entropy(r, &q, (credit + 1) << ENTROPY_SHIFT); + __queue_entropy(r, &q, 1 << ENTROPY_SHIFT); __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); - if (credit) { - /* - * A seed has been obtained from - * arch_get_random_seed_long() above, mix it in. - */ - __mix_pool_bytes(r, &seed, sizeof(seed)); - } reseed = __dispatch_queued_entropy_fast(r, &q); spin_unlock(&r->lock); if (reseed) From patchwork Mon Sep 21 07:58:38 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788677 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id B0A921668 for ; Mon, 21 Sep 2020 08:00:06 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9E47F20EDD for ; Mon, 21 Sep 2020 08:00:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726623AbgIUH7u (ORCPT ); Mon, 21 Sep 2020 03:59:50 -0400 Received: from mx2.suse.de ([195.135.220.15]:57144 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726540AbgIUH71 (ORCPT ); Mon, 21 Sep 2020 03:59:27 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id E0FA9B516; Mon, 21 Sep 2020 08:00:01 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 22/41] random: introduce arch_has_sp800_90b_random_seed() Date: Mon, 21 Sep 2020 09:58:38 +0200 Message-Id: <20200921075857.4424-23-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org NIST SP800-90C allows for the combination of multiple SP800-90B entropy sources by concatenating their individual outputs together, c.f. sec. 5.3.4 and also the constructions in 10.3.1 from the second draft. We're already doing exactly that when reseeding the primary CRNG from the input pool and possibly from arch_get_random_seed_long() + arch_get_random_long(). The input pool will be moved gradually towards SP800-90B compliance with future patches. Provide a means for the random driver to check whether arch_get_random_seed_long() is also a full entropy source conforming to NIST SP800-90B. Note that I couldn't find any explicit statement in the specs that would allow for using NRBGs as defined by SP800-90C as a drop-in replacement for "entropy sources" in the sense of SP800-90B. In particular there is no statement that NRBGs may be combined with other SP800-90B entropy sources. However, NRBGs always provide stronger guarantees in that they provide certain protection against silent failure of backing entropy sources. Thus, I think it would be perfectly acceptable to combine SP800-90C NRBGs, i.e. ARMv8's RNDRRS or x86's RDSEED with other entropy sources. Introduce arch_has_sp800_90b_random_seed(). - Make the generic stub return false. - Make the arm64 variant return false as well: the current arch_get_random_seed_long() is based on RNDR, not RNDRRS. - Make it return false on powerpc and s390, too. - Let arch_has_sp800_90b_random_seed() return true on x86 if the CPU has RDSEED support. Yes, I know, one change per patch, but this is part of a RFC series. Signed-off-by: Nicolai Stange --- arch/arm64/include/asm/archrandom.h | 10 +++++++++- arch/powerpc/include/asm/archrandom.h | 5 +++++ arch/s390/include/asm/archrandom.h | 5 +++++ arch/x86/include/asm/archrandom.h | 8 ++++++++ include/linux/random.h | 9 +++++++++ 5 files changed, 36 insertions(+), 1 deletion(-) diff --git a/arch/arm64/include/asm/archrandom.h b/arch/arm64/include/asm/archrandom.h index 055d18713db7..db7813c79b3e 100644 --- a/arch/arm64/include/asm/archrandom.h +++ b/arch/arm64/include/asm/archrandom.h @@ -42,7 +42,15 @@ static inline bool arch_has_random_seed(void) */ return cpus_have_const_cap(ARM64_HAS_RNG); } - +static inine bool arch_has_sp800_90b_random_seed(void) +{ + /* + * Section K.12.1 from the Arm Architecture Reference Manual + * Armv8" (DDI0487F) sounds like RNDRRS could qualify as a + * NIST SP800-90C NRBG, but we're currently using RNDR only. + */ + return false; +} static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; diff --git a/arch/powerpc/include/asm/archrandom.h b/arch/powerpc/include/asm/archrandom.h index 47c2d74e7244..ba0f816d9750 100644 --- a/arch/powerpc/include/asm/archrandom.h +++ b/arch/powerpc/include/asm/archrandom.h @@ -16,6 +16,11 @@ static inline bool arch_has_random_seed(void) return ppc_md.get_random_seed; } +static inline bool arch_has_sp800_90b_random_seed(void) +{ + return false; +} + static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; diff --git a/arch/s390/include/asm/archrandom.h b/arch/s390/include/asm/archrandom.h index 18973845634c..1ee7f9e4b255 100644 --- a/arch/s390/include/asm/archrandom.h +++ b/arch/s390/include/asm/archrandom.h @@ -31,6 +31,11 @@ static inline bool arch_has_random_seed(void) return static_branch_likely(&s390_arch_random_available); } +static inline bool arch_has_sp800_90b_random_seed(void) +{ + return false; +} + static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; diff --git a/arch/x86/include/asm/archrandom.h b/arch/x86/include/asm/archrandom.h index 030f46c9e310..94d4ee8c9e45 100644 --- a/arch/x86/include/asm/archrandom.h +++ b/arch/x86/include/asm/archrandom.h @@ -80,6 +80,14 @@ static inline bool arch_has_random_seed(void) return static_cpu_has(X86_FEATURE_RDSEED); } +static inline bool arch_has_sp800_90b_random_seed(void) +{ + /* + * According to the Intel SDM, rdseed is NIST SP800-90B + * compliant. + */ + return arch_has_random_seed(); +} static inline bool __must_check arch_get_random_long(unsigned long *v) { return arch_has_random() ? rdrand_long(v) : false; diff --git a/include/linux/random.h b/include/linux/random.h index d4653422a0c7..933f5daa4a1c 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -128,6 +128,15 @@ static inline bool arch_has_random_seed(void) { return false; } +/* + * Whether or not arch_get_random_seed_long() qualifies as a NIST + * SP800-90B compliant entropy source providing full entropy output. + * NIST SP800-90C NRBG's are probably fine, too. + */ +static inline bool arch_has_sp800_90b_random_seed(void) +{ + return false; +} static inline bool __must_check arch_get_random_long(unsigned long *v) { return false; From patchwork Mon Sep 21 07:58:39 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788675 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7A186139A for ; Mon, 21 Sep 2020 08:00:06 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6AB8C2085B for ; Mon, 21 Sep 2020 08:00:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726628AbgIUH7u (ORCPT ); Mon, 21 Sep 2020 03:59:50 -0400 Received: from mx2.suse.de ([195.135.220.15]:56802 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726420AbgIUH71 (ORCPT ); Mon, 21 Sep 2020 03:59:27 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 80FADB51D; Mon, 21 Sep 2020 08:00:02 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 23/41] random: don't award entropy to non-SP800-90B arch RNGs in FIPS mode Date: Mon, 21 Sep 2020 09:58:39 +0200 Message-Id: <20200921075857.4424-24-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org It is required by SP800-90C that only SP800-90B compliant entropy sources may be used for seeding DRBGs. Don't award any entropy to arch_get_random_long() if fips_enabled is true. Don't award any entropy to arch_get_random_seed_long() if fips_enabled && !arch_has_sp800_90b_random_seed(). This is achieved by making min_crng_reseed_pool_entropy() return the full minimum seed size if fips_enabled && !arch_has_sp800_90b_random_seed() is true. This prevents crng_reseed() from attempting to make up for any lack of entropy in the input_pool by reading from the architectural RNG. Make crng_reseed() bail out in FIPS mode if the input_pool provides insufficient entropy and any of the arch_get_random_seed_long() invocations fails: there's no statement regarding SP900-90B compliance of arch_get_random_long() and so it can't be used as a backup. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 7712b4464ef5..aaddee4e4ab1 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1195,9 +1195,13 @@ static int min_crng_reseed_pool_entropy(void) * up to one half of the minimum entropy needed for * reseeding. That way it won't dominate the entropy * collected by other means at input_pool. + * If in FIPS mode, restrict this to SP900-90B compliant + * architectural RNGs. */ - if (arch_has_random() || arch_has_random_seed()) + if (arch_has_sp800_90b_random_seed() || + (!fips_enabled && (arch_has_random() || arch_has_random_seed()))) { return 8; + } return 16; } @@ -1233,7 +1237,8 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r) for (i = 0; i < 8; i++) { unsigned long rv; if (!arch_get_random_seed_long(&rv) && - !arch_get_random_long(&rv)) { + ((arch_randomness_required && fips_enabled) || + !arch_get_random_long(&rv))) { if (arch_randomness_required) { /* * The input_pool failed to provide From patchwork Mon Sep 21 07:58:40 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788665 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id ED1F7618 for ; Mon, 21 Sep 2020 07:59:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DC2D420EDD for ; Mon, 21 Sep 2020 07:59:39 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726597AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 Received: from mx2.suse.de ([195.135.220.15]:57940 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726545AbgIUH73 (ORCPT ); Mon, 21 Sep 2020 03:59:29 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 14EEEB51E; Mon, 21 Sep 2020 08:00:03 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 24/41] init: call time_init() before rand_initialize() Date: Mon, 21 Sep 2020 09:58:40 +0200 Message-Id: <20200921075857.4424-25-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Commit d55535232c3d ("random: move rand_initialize() earlier") moved the rand_initialize() invocation from the early initcalls to right after timekeeping_init(), but before time_init(). However, rand_initialize() would indirectly invoke random_get_entropy(), which is an alias to get_cycles() on most archs, in case an architectural RNG is not available. Problem is that on some archs, e.g. ARM, get_cycles() can only be relied upon when time_init() has completed. Move the invocation of time_init() a couple of lines up in start_kernel() so that it gets called before rand_initialize(). Note that random_get_entropy() data doesn't get any entropy credit and thus, this issue is not to be considered a bug, but more of an inconsistency. Fixes: d55535232c3d ("random: move rand_initialize() earlier") Signed-off-by: Nicolai Stange --- init/main.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/init/main.c b/init/main.c index ae78fb68d231..30892675f48e 100644 --- a/init/main.c +++ b/init/main.c @@ -942,6 +942,7 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void) hrtimers_init(); softirq_init(); timekeeping_init(); + time_init(); /* * For best initial stack canary entropy, prepare it after: @@ -956,7 +957,6 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void) add_device_randomness(command_line, strlen(command_line)); boot_init_stack_canary(); - time_init(); perf_event_init(); profile_init(); call_function_init(); From patchwork Mon Sep 21 07:58:41 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788669 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 43C3A618 for ; Mon, 21 Sep 2020 07:59:49 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 352A120874 for ; Mon, 21 Sep 2020 07:59:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726574AbgIUH7i (ORCPT ); Mon, 21 Sep 2020 03:59:38 -0400 Received: from mx2.suse.de ([195.135.220.15]:58044 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726546AbgIUH7a (ORCPT ); Mon, 21 Sep 2020 03:59:30 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id A4C55B524; Mon, 21 Sep 2020 08:00:03 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 25/41] random: probe cycle counter resolution at initialization Date: Mon, 21 Sep 2020 09:58:41 +0200 Message-Id: <20200921075857.4424-26-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org An upcoming patch will change the entropy estimate per add_interrupt_randomness() event for fips_enabled based on whether random_get_entropy() resp. get_cycles() is able to capture individual instructions. For example, x86's TSC would qualify, whereas I've seen cycle counters on e.g. a Raspberry PI 2B with an advertised resolution of only 52ns even though the CPU had been clocked at 1GHz. And then there's possibly hardware which doesn't have a cycle counter at all and where get_cycles() would always return the same constant. Make rand_initialize() probe the cycle counter resolution. Introduce a new static_key have_highres_cycle_ctr, indicicating whether or not the system's cycle counter is able to capture individual instructions. Initially it's set to true. Introduce probe_cycle_ctr_resolution() and call it from rand_initialize(). Make probe_cycle_ctr_resolution() compare 16 successive random_get_entropy() values and disable have_highres_cycle_ctr in case the same value has been read two times in a row. As have_highres_cycle_ctr will be only accessed if fips_enabled is true, make it return early in case it's not set. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) diff --git a/drivers/char/random.c b/drivers/char/random.c index aaddee4e4ab1..a985ceb22c7c 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -335,6 +335,7 @@ #include #include #include +#include #include #include @@ -478,6 +479,8 @@ static struct ratelimit_state urandom_warning = static int ratelimit_disable __read_mostly; +static DEFINE_STATIC_KEY_TRUE(have_highres_cycle_ctr); + module_param_named(ratelimit_disable, ratelimit_disable, int, 0644); MODULE_PARM_DESC(ratelimit_disable, "Disable random ratelimit suppression"); @@ -2170,6 +2173,31 @@ static void __init init_std_data(struct entropy_store *r) mix_pool_bytes(r, utsname(), sizeof(*(utsname()))); } +static void probe_cycle_ctr_resolution(void) +{ + cycles_t prev; + int i; + + if (!fips_enabled) + return; + + /* + * Check if the cycle counter has insn granularity (or at + * least close to). + */ + prev = random_get_entropy(); + for (i = 0; i < 16; ++i) { + cycles_t next; + + next = random_get_entropy(); + if (next == prev) { + static_branch_disable(&have_highres_cycle_ctr); + return; + } + prev = next; + } +} + /* * Note that setup_arch() may call add_device_randomness() * long before we get here. This allows seeding of the pools @@ -2182,6 +2210,7 @@ static void __init init_std_data(struct entropy_store *r) */ int __init rand_initialize(void) { + probe_cycle_ctr_resolution(); init_std_data(&input_pool); crng_initialize_primary(&primary_crng); crng_global_init_time = jiffies; From patchwork Mon Sep 21 07:58:42 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788667 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 29FF96CA for ; Mon, 21 Sep 2020 07:59:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1413420EDD for ; Mon, 21 Sep 2020 07:59:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726594AbgIUH7i (ORCPT ); Mon, 21 Sep 2020 03:59:38 -0400 Received: from mx2.suse.de ([195.135.220.15]:58098 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726550AbgIUH7b (ORCPT ); Mon, 21 Sep 2020 03:59:31 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 32E87B520; Mon, 21 Sep 2020 08:00:04 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 26/41] random: implement support for evaluating larger fast_pool entropies Date: Mon, 21 Sep 2020 09:58:42 +0200 Message-Id: <20200921075857.4424-27-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The fast_pools, mixed into from add_interrupt_randomness(), are 128 bits wide and get awarded at most an entropy value as low as one bit in total. An upcoming patch will significantly increase the estimated entropy per event and this will make the fast_pools to receive much larger values of successively mixed in event entropy. In analogy to the reasoning in commit 30e37ec516ae ("random: account for entropy loss due to overwrites"), probabilistic collisions will have to get accounted for when calculating the total fast_pool entropy. From said commit, the final fast_pool entropy equals e = pool_size * (1 - exp(-num_events * entropy_per_event / pool_size)) Where pool_size is 128 bits in this case and num_events * entropy_per_event equals the sum of all estimated entropy from the IRQ events previously mixed in. Disclaimer: I'm cargo-culting here. That probabilisic overwrites are in fact an issue sounds plausible after having read e.g. "Balls into Bins" by M.Raab and A. Steger. But I haven't managed to derive this equation by myself, nor have I found it in any literature. Anyway, implement the new fast_pool_entropy() for evaluating the equation given above by means of a suitable approximation. add_interrupt_randomness() empties its fast_pool into the global input_pool whenever the number of accumulated events has reached a threshold of 64 and the input_pool's ->lock is uncontended. Thus, the number of IRQ events accumulated at the fast_pool can be assumed to be unlikely to exceed larger factors of 64. The maximum estimate supported for per-IRQ entropy will be 1 bit and thus, this sets an upper bound on the range where the approximation is supposed to work well. At the same time, estimates for the per-IRQ entropy as low as 1/64 bits should be supported and the approximation should not be too coarse in these lower regions in order to avoid excessive loss when entropy is likely a scarce resource anyway. Apply a piecewise linear approximation to the fast_pool entropy, with the lengths of the resp. intervals getting doubled with increasing input values. That is, let the first interval cover 32 bits worth of input entropy, the next one 64 bits and stop after a final one of length 128 bits. Any input entropy beyond 32 + 64 + 128 bits gets discarded in order to limit the computations done from interrupt context, but as outlined above, this is unlikely to matter in practice. The shorter intervals for the regions of smaller values will improve the accuracy of the approximation in these areas, i.e. for small estimates for the per-IRQ entropy. Note that the new fast_pool_entropy() is not being used anywhere yet, it will be wired up in an upcoming commit. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 52 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) diff --git a/drivers/char/random.c b/drivers/char/random.c index a985ceb22c7c..ac36c56dd135 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1547,6 +1547,58 @@ static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs) return *ptr; } +/* + * Calculate the entropy of a fast_pool after num_events IRQ events of + * assessed entropy 2^-event_entropy_shift each have been mixed in. + */ +static unsigned int fast_pool_entropy(unsigned int num_events, + int event_entropy_shift) +{ + unsigned int result, cur, interval_len; + + /* + * Assume that each event fed into the fast_pool + * carries h = 2^-event_entropy_shift bits of entropy. + * In analogy to how entropy deltas are calculated + * in pool_entropy_delta() for the struct entropy_store + * input_pool, a fast_pool which received num_events + * of total entropy num_events * h will contain + * p * (1 - exp(-num_events * h / p) + * bits of entropy, where p equals the poolsize of 128 bits. + * + * Note that most of the time num_events will be ~64, c.f. + * add_interrupt_randomness. Approximate the resulting + * fast_pool entropy in a piecewise linear manner from below: + * from 0 to 32, from 32 to 96 and from 96 to 224. + * Event entropy above 224 gets simply discarded. For p = 128, + * the calculated fast_pool entropy is ~226 at + * num_events * h == 32, ~540 at 96 and ~846 at 224, all given + * in units of 2^-ENTROPY_SHIFT. + */ + BUILD_BUG_ON(sizeof(((struct fast_pool *)NULL)->pool) != 16); + BUILD_BUG_ON(ENTROPY_SHIFT != 3); + + /* Interval from 0 to 32. */ + interval_len = 32 << event_entropy_shift; + cur = min_t(unsigned int, num_events, interval_len); + result = (226 * cur) >> 5; /* shift is for /32 */ + num_events -= cur; + + /* Interval of length 64 from 32 to 96. */ + interval_len <<= 1; + cur = min_t(unsigned int, num_events, interval_len); + result += ((540 - 226) * cur) >> 6; /* shift is for /64 */ + num_events -= cur; + + /* Interval of length 128 from 96 to 224. */ + interval_len <<= 1; + cur = min_t(unsigned int, num_events, interval_len); + result += ((846 - 540) * cur) >> 7; /* shift is for /128 */ + + /* Return value is in units of 2^-ENTROPY_SHIFT. */ + return result >> event_entropy_shift; +} + void add_interrupt_randomness(int irq, int irq_flags) { struct entropy_store *r; From patchwork Mon Sep 21 07:58:43 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788703 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id EABFB1668 for ; Mon, 21 Sep 2020 08:00:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D631B214F1 for ; Mon, 21 Sep 2020 08:00:54 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726467AbgIUIAx (ORCPT ); Mon, 21 Sep 2020 04:00:53 -0400 Received: from mx2.suse.de ([195.135.220.15]:57440 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726579AbgIUH7k (ORCPT ); Mon, 21 Sep 2020 03:59:40 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id C5D09B523; Mon, 21 Sep 2020 08:00:04 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 27/41] random: increase per-IRQ event entropy estimate if in FIPS mode Date: Mon, 21 Sep 2020 09:58:43 +0200 Message-Id: <20200921075857.4424-28-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org NIST SP800-90C prohibits the use of multiple correlated entropy sources. However, add_interrupt_randomness(), add_disk_randomness() and add_input_randomness() are clearly not independent and an upcoming patch will make the latter two to stop contributing any entropy to the global balance if fips_enabled is on. With the current parameter settings, it can be assumed that add_disk_randomness() resp. add_input_randomness() are the dominating contributors to the overall entropy reserve for some common workloads: both more or less estimate the entropy per event to equal the width of the minimum out of the first, second and third jiffes deltas to the previous occurrence. add_interrupt_randomness() on the other hand only attributes one single bit entropy to a full batch of 64 IRQ events (or once a second if that completes earlier). Thus, the upcoming exclusion of two potent entropy sources should somehow be compensated for. Stephan Müller worked around this very problem in his "LRNG" proposal ([1]) by increasing the entropy estimate per IRQ event. Namely, in case a get_cycles() with instruction granularity is available, he estimated one bit of entropy per IRQ event and (IIRC) 1/10 bits otherwise. I haven't tested this claim myself, in particular not on smaller devices. But for the sake of moving the development of this RFC series forward, I'll assume it as granted and hereby postulate that The lower eight bits of the differences between get_cycles() from two successive IRQ events on the same CPU carry - one bit of min-entropy in case a get_cycles() with instruction granularity is available and - 1/8 bit of min-entropy in case get_cycles() is still non-trivial, but has a lower resolution. In particular this is assumed to be true for highly periodic interrupts like those issued for e.g. USB microframes and on all supported architectures. In the former case, the underlying source of randomness is believed to follow the same principles as for the Jitter RNGs resp. try_to_generate_entropy(): diffences in RAM vs. CPU clockings and unpredictability of cache states to a certain extent. Notes: - NIST SP800-90B requires a means to access raw samples for validation purposes. Implementation of such an interface is deliberately not part of this RFC series here, but would necessarily be subject of future work. So there would be a means to at least validate these assumptions. - The choice of 1/8 over the 1/10 from the LRNG patchset has been made because it's a power of two and I suppose that the estimate of 1/10 had been quite arbitrary anyway. Replacement of the 1/8 by smaller powers of two down to 1/64 will be supported throughout this patch series. Some health tests as required by NIST SP800-90B will be implemented later in this series. In order to allow for dynamically decreasing the assessed entropy on a per-CPU basis upon health test failures, make it an attibute of the per-CPU struct fast_pool. That is, introduce a new integer field ->event_entropy_shift to struct fast_pool. The estimated entropy per IRQ sample will be calculated as 2^-event_entropy_shift. Initialize it statically with -1 to indicate that runtime initialization hasn't happened yet. Introduce fast_pool_init_accounting() which gets called unconditionally from add_interrupt_randomness() for doing the necessary runtime initializations once, i.e. if ->event_entropy_shift is still found to be negative. Implement it with the help of the also new min_irq_event_entropy_shift(), which will return the initial ->event_entropy_shift value as determined according to the rules from above. That is, depending on the have_highres_cycle_ctr, the result is eiher zero or three. Note that have_highres_cycle_ctr will only get properly initialized from rand_initialize() if fips_enabled is set, but ->event_entropy_shift will also only ever get accessed in this case. Finally, for the case tha fips_enabled is set, make add_interrupt_randomness() to estimate the amount of entropy transferred from the fast_pool into the global input_pool as fast_pool_entropy(->count, ->event_entropy_shift), rather than only one single bit. Remember that fast_pool_entropy() calculates the amount of entropy contained in a fast_pool, based on the total number of events mixed into it and the estimated entropy per event. [1] https://lkml.kernel.org/r/5695397.lOV4Wx5bFT@positron.chronox.de Suggested-by: Stephan Müller Signed-off-by: Nicolai Stange --- drivers/char/random.c | 50 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 45 insertions(+), 5 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index ac36c56dd135..8f79e90f2429 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -615,6 +615,7 @@ struct fast_pool { unsigned long last; unsigned short reg_idx; unsigned char count; + int event_entropy_shift; }; /* @@ -1509,7 +1510,9 @@ void add_input_randomness(unsigned int type, unsigned int code, } EXPORT_SYMBOL_GPL(add_input_randomness); -static DEFINE_PER_CPU(struct fast_pool, irq_randomness); +static DEFINE_PER_CPU(struct fast_pool, irq_randomness) = { + .event_entropy_shift = -1, +}; #ifdef ADD_INTERRUPT_BENCH static unsigned long avg_cycles, avg_deviation; @@ -1599,6 +1602,32 @@ static unsigned int fast_pool_entropy(unsigned int num_events, return result >> event_entropy_shift; } +static inline int min_irq_event_entropy_shift(void) +{ + if (static_branch_likely(&have_highres_cycle_ctr)) { + /* + * If a cycle counter with a good enough resolution is + * available, estimate the entropy per IRQ event to + * be no more than 2^-0 == 1 bit. + */ + return 0; + } + + /* + * Otherwise return an estimate upper bound of + * 2^-3 == 1/8 bit per event. + */ + return 3; +} + +static inline void fast_pool_init_accounting(struct fast_pool *f) +{ + if (likely(f->event_entropy_shift >= 0)) + return; + + f->event_entropy_shift = min_irq_event_entropy_shift(); +} + void add_interrupt_randomness(int irq, int irq_flags) { struct entropy_store *r; @@ -1610,6 +1639,7 @@ void add_interrupt_randomness(int irq, int irq_flags) __u64 ip; bool reseed; struct queued_entropy q = { 0 }; + unsigned int nfrac; if (cycles == 0) cycles = get_reg(fast_pool, regs); @@ -1644,13 +1674,23 @@ void add_interrupt_randomness(int irq, int irq_flags) if (!spin_trylock(&r->lock)) return; - fast_pool->last = now; - fast_pool->count = 0; - /* award one bit for the contents of the fast pool */ - __queue_entropy(r, &q, 1 << ENTROPY_SHIFT); + fast_pool_init_accounting(fast_pool); + + if (!fips_enabled) { + /* award one bit for the contents of the fast pool */ + nfrac = 1 << ENTROPY_SHIFT; + } else { + nfrac = fast_pool_entropy(fast_pool->count, + fast_pool->event_entropy_shift); + } + __queue_entropy(r, &q, nfrac); __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); reseed = __dispatch_queued_entropy_fast(r, &q); spin_unlock(&r->lock); + + fast_pool->last = now; + fast_pool->count = 0; + if (reseed) crng_reseed(&primary_crng, r); } From patchwork Mon Sep 21 07:58:44 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788705 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 9DDC9139A for ; Mon, 21 Sep 2020 08:01:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8BEB720EDD for ; Mon, 21 Sep 2020 08:01:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726766AbgIUIAy (ORCPT ); Mon, 21 Sep 2020 04:00:54 -0400 Received: from mx2.suse.de ([195.135.220.15]:57702 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726586AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 591BBB529; Mon, 21 Sep 2020 08:00:05 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 28/41] random: don't award entropy to disk + input events if in FIPS mode Date: Mon, 21 Sep 2020 09:58:44 +0200 Message-Id: <20200921075857.4424-29-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org NIST SP800-90C prohibits the use of multiple correlated entropy sources. Obviously, add_disk_randomness(), add_input_randomness() and add_interrupt_randomness() are not independent. Follow the approach taken by Stephan Müller's LRNG patchset ([1]) and don't award any entropy to the former two if fips_enabled is true. Note that the entropy loss has already been compensated for by a previous patch increasing the IRQ event estimate. The actual entropy accounting from add_disk_randomness() and add_input_randomness() is implemented in the common add_timer_randomness() called therefrom. Make the latter to not dispatch any entropy to the global entropy balance if fips_enabled is on. [1] https://lkml.kernel.org/r/5695397.lOV4Wx5bFT@positron.chronox.de Suggested-by: Stephan Müller Signed-off-by: Nicolai Stange --- drivers/char/random.c | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 8f79e90f2429..680ccc82a436 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1481,12 +1481,24 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) r = &input_pool; spin_lock_irqsave(&r->lock, flags); - /* - * delta is now minimum absolute delta. - * Round down by 1 bit on general principles, - * and limit entropy estimate to 12 bits. - */ - __queue_entropy(r, &q, min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT); + if (!fips_enabled) { + unsigned int nfrac; + + /* + * delta is now minimum absolute delta. + * Round down by 1 bit on general principles, + * and limit entropy estimate to 12 bits. + */ + nfrac = min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT; + __queue_entropy(r, &q, nfrac); + } else { + /* + * Multiple correlated entropy sources are prohibited + * by NIST SP800-90C. Leave it up to + * add_interrupt_randomness() to contribute any + * entropy. + */ + } __mix_pool_bytes(r, &sample, sizeof(sample)); reseed = __dispatch_queued_entropy_fast(r, &q); spin_unlock_irqrestore(&r->lock, flags); From patchwork Mon Sep 21 07:58:45 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788723 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 369C2618 for ; Mon, 21 Sep 2020 08:01:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 21BC920BED for ; Mon, 21 Sep 2020 08:01:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726365AbgIUIBa (ORCPT ); Mon, 21 Sep 2020 04:01:30 -0400 Received: from mx2.suse.de ([195.135.220.15]:56802 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726588AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id ED703B521; Mon, 21 Sep 2020 08:00:05 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 29/41] random: move definition of struct queued_entropy and related API upwards Date: Mon, 21 Sep 2020 09:58:45 +0200 Message-Id: <20200921075857.4424-30-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The next patch will add a member of type struct queued_entropy to struct fast_pool and thus, the former's definition needs to be visible at the latter's. Move the definition of struct queued_entropy upwards in the file so that it comes before the definition struct fast_pool. Move the associated function definitions as well in order to keep everything together. Note that said function definitions had originally been inserted at the old location with the intent to minimize their introducing patch's diff by placing them near the now removed credit_entropy_delta() they superseded. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 243 +++++++++++++++++++++--------------------- 1 file changed, 124 insertions(+), 119 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 680ccc82a436..55e784a5a2ec 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -519,6 +519,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, static ssize_t _extract_entropy(struct entropy_store *r, void *buf, size_t nbytes, int fips); +static unsigned int pool_entropy_delta(struct entropy_store *r, + int base_entropy_count, + int nfrac, bool fast); + static int min_crng_reseed_pool_entropy(void); static void crng_reseed(struct crng_state *crng, struct entropy_store *r); @@ -610,125 +614,6 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in, spin_unlock_irqrestore(&r->lock, flags); } -struct fast_pool { - __u32 pool[4]; - unsigned long last; - unsigned short reg_idx; - unsigned char count; - int event_entropy_shift; -}; - -/* - * This is a fast mixing routine used by the interrupt randomness - * collector. It's hardcoded for an 128 bit pool and assumes that any - * locks that might be needed are taken by the caller. - */ -static void fast_mix(struct fast_pool *f) -{ - __u32 a = f->pool[0], b = f->pool[1]; - __u32 c = f->pool[2], d = f->pool[3]; - - a += b; c += d; - b = rol32(b, 6); d = rol32(d, 27); - d ^= a; b ^= c; - - a += b; c += d; - b = rol32(b, 16); d = rol32(d, 14); - d ^= a; b ^= c; - - a += b; c += d; - b = rol32(b, 6); d = rol32(d, 27); - d ^= a; b ^= c; - - a += b; c += d; - b = rol32(b, 16); d = rol32(d, 14); - d ^= a; b ^= c; - - f->pool[0] = a; f->pool[1] = b; - f->pool[2] = c; f->pool[3] = d; - f->count++; -} - -static void process_random_ready_list(void) -{ - unsigned long flags; - struct random_ready_callback *rdy, *tmp; - - spin_lock_irqsave(&random_ready_list_lock, flags); - list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) { - struct module *owner = rdy->owner; - - list_del_init(&rdy->list); - rdy->func(rdy); - module_put(owner); - } - spin_unlock_irqrestore(&random_ready_list_lock, flags); -} - -/* - * Based on the pool's current entropy fill level, specified as - * base_entropy_count, and the number of new entropy bits in units of - * 2^-ENTROPY_SHIFT to add, return the amount of new entropy to - * credit. If the 'fast' parameter is set to true, the calculation - * will be guaranteed to terminate quickly, but this comes at the - * expense of capping nbits to one half of the pool size. - */ -static unsigned int pool_entropy_delta(struct entropy_store *r, - int base_entropy_count, - int nfrac, bool fast) -{ - const int pool_size = r->poolinfo->poolfracbits; - int entropy_count = base_entropy_count; - - if (!nfrac) - return 0; - - if (pool_size <= base_entropy_count) - return 0; - - /* - * Credit: we have to account for the possibility of - * overwriting already present entropy. Even in the - * ideal case of pure Shannon entropy, new contributions - * approach the full value asymptotically: - * - * entropy <- entropy + (pool_size - entropy) * - * (1 - exp(-add_entropy/pool_size)) - * - * For add_entropy <= pool_size/2 then - * (1 - exp(-add_entropy/pool_size)) >= - * (add_entropy/pool_size)*0.7869... - * so we can approximate the exponential with - * 3/4*add_entropy/pool_size and still be on the - * safe side by adding at most pool_size/2 at a time. - * - * The use of pool_size-2 in the while statement is to - * prevent rounding artifacts from making the loop - * arbitrarily long; this limits the loop to log2(pool_size)*2 - * turns no matter how large nbits is. - */ - do { - /* The +2 corresponds to the /4 in the denominator */ - const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2; - unsigned int anfrac = min(nfrac, pool_size/2); - unsigned int add = - ((pool_size - entropy_count)*anfrac*3) >> s; - - entropy_count += add; - nfrac -= anfrac; - } while (unlikely(!fast && entropy_count < pool_size-2 && nfrac)); - - if (WARN_ON(entropy_count < 0)) { - pr_warn("negative entropy/overflow: pool %s count %d\n", - r->name, entropy_count); - entropy_count = base_entropy_count; - } else if (entropy_count > pool_size) { - entropy_count = pool_size; - } - - return entropy_count - base_entropy_count; -} - struct queued_entropy { unsigned int pool_watermark_seq; unsigned int queued_entropy_fracbits; @@ -994,6 +879,126 @@ static void discard_queued_entropy(struct entropy_store *r, spin_unlock_irqrestore(&r->lock, flags); } +struct fast_pool { + __u32 pool[4]; + unsigned long last; + unsigned short reg_idx; + unsigned char count; + int event_entropy_shift; +}; + +/* + * This is a fast mixing routine used by the interrupt randomness + * collector. It's hardcoded for an 128 bit pool and assumes that any + * locks that might be needed are taken by the caller. + */ +static void fast_mix(struct fast_pool *f) +{ + __u32 a = f->pool[0], b = f->pool[1]; + __u32 c = f->pool[2], d = f->pool[3]; + + a += b; c += d; + b = rol32(b, 6); d = rol32(d, 27); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(b, 16); d = rol32(d, 14); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(b, 6); d = rol32(d, 27); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(b, 16); d = rol32(d, 14); + d ^= a; b ^= c; + + f->pool[0] = a; f->pool[1] = b; + f->pool[2] = c; f->pool[3] = d; + f->count++; +} + +static void process_random_ready_list(void) +{ + unsigned long flags; + struct random_ready_callback *rdy, *tmp; + + spin_lock_irqsave(&random_ready_list_lock, flags); + list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) { + struct module *owner = rdy->owner; + + list_del_init(&rdy->list); + rdy->func(rdy); + module_put(owner); + } + spin_unlock_irqrestore(&random_ready_list_lock, flags); +} + +/* + * Based on the pool's current entropy fill level, specified as + * base_entropy_count, and the number of new entropy bits in units of + * 2^-ENTROPY_SHIFT to add, return the amount of new entropy to + * credit. If the 'fast' parameter is set to true, the calculation + * will be guaranteed to terminate quickly, but this comes at the + * expense of capping nbits to one half of the pool size. + */ +static unsigned int pool_entropy_delta(struct entropy_store *r, + int base_entropy_count, + int nfrac, bool fast) +{ + const int pool_size = r->poolinfo->poolfracbits; + int entropy_count = base_entropy_count; + + if (!nfrac) + return 0; + + if (pool_size <= base_entropy_count) + return 0; + + /* + * Credit: we have to account for the possibility of + * overwriting already present entropy. Even in the + * ideal case of pure Shannon entropy, new contributions + * approach the full value asymptotically: + * + * entropy <- entropy + (pool_size - entropy) * + * (1 - exp(-add_entropy/pool_size)) + * + * For add_entropy <= pool_size/2 then + * (1 - exp(-add_entropy/pool_size)) >= + * (add_entropy/pool_size)*0.7869... + * so we can approximate the exponential with + * 3/4*add_entropy/pool_size and still be on the + * safe side by adding at most pool_size/2 at a time. + * + * The use of pool_size-2 in the while statement is to + * prevent rounding artifacts from making the loop + * arbitrarily long; this limits the loop to log2(pool_size)*2 + * turns no matter how large nbits is. + */ + do { + /* The +2 corresponds to the /4 in the denominator */ + const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2; + unsigned int anfrac = min(nfrac, pool_size/2); + unsigned int add = + ((pool_size - entropy_count)*anfrac*3) >> s; + + entropy_count += add; + nfrac -= anfrac; + } while (unlikely(!fast && entropy_count < pool_size-2 && nfrac)); + + if (WARN_ON(entropy_count < 0)) { + pr_warn("negative entropy/overflow: pool %s count %d\n", + r->name, entropy_count); + entropy_count = base_entropy_count; + } else if (entropy_count > pool_size) { + entropy_count = pool_size; + } + + return entropy_count - base_entropy_count; +} + + /********************************************************************* * * CRNG using CHACHA20 From patchwork Mon Sep 21 07:58:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788729 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7EF36618 for ; Mon, 21 Sep 2020 08:01:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6A7FA20874 for ; Mon, 21 Sep 2020 08:01:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726357AbgIUIBc (ORCPT ); Mon, 21 Sep 2020 04:01:32 -0400 Received: from mx2.suse.de ([195.135.220.15]:57142 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726590AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 874A5B52A; Mon, 21 Sep 2020 08:00:06 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 30/41] random: add a queued_entropy instance to struct fast_pool Date: Mon, 21 Sep 2020 09:58:46 +0200 Message-Id: <20200921075857.4424-31-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org When health tests are introduced with upcoming patches, it will become necessary to keep entropy queued across add_interrupt_randomness() invocations for later dispatch to the global balance. Prepare for this by adding a struct queued_entropy member to the per-CPU fast_pool. Use it in place of that queue with automatic storage duration in add_interrupt_randomness(). Signed-off-by: Nicolai Stange --- drivers/char/random.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 55e784a5a2ec..37746df53acf 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -885,6 +885,7 @@ struct fast_pool { unsigned short reg_idx; unsigned char count; int event_entropy_shift; + struct queued_entropy q; }; /* @@ -1655,7 +1656,7 @@ void add_interrupt_randomness(int irq, int irq_flags) __u32 c_high, j_high; __u64 ip; bool reseed; - struct queued_entropy q = { 0 }; + struct queued_entropy *q = &fast_pool->q; unsigned int nfrac; if (cycles == 0) @@ -1700,9 +1701,9 @@ void add_interrupt_randomness(int irq, int irq_flags) nfrac = fast_pool_entropy(fast_pool->count, fast_pool->event_entropy_shift); } - __queue_entropy(r, &q, nfrac); + __queue_entropy(r, q, nfrac); __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); - reseed = __dispatch_queued_entropy_fast(r, &q); + reseed = __dispatch_queued_entropy_fast(r, q); spin_unlock(&r->lock); fast_pool->last = now; From patchwork Mon Sep 21 07:58:47 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788719 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id D7950139A for ; Mon, 21 Sep 2020 08:01:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C876820BED for ; Mon, 21 Sep 2020 08:01:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726788AbgIUIBH (ORCPT ); Mon, 21 Sep 2020 04:01:07 -0400 Received: from mx2.suse.de ([195.135.220.15]:58044 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726587AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 1D565B52C; Mon, 21 Sep 2020 08:00:07 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 31/41] random: introduce struct health_test + health_test_reset() placeholders Date: Mon, 21 Sep 2020 09:58:47 +0200 Message-Id: <20200921075857.4424-32-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The to be implemented health tests will maintain some per-CPU state as they successively process the IRQ samples fed into the resp. fast_pool from add_interrupt_randomness(). In order to not to clutter future patches with trivialities, introduce an empty struct health_test supposed to keep said state in the future. Add a member of this new type to struct fast_pool. Introduce a health_test_reset() stub, which is supposed to (re)initialize instances of struct health_test. Invoke it from the fast_pool_init_accounting() to make sure that a fast_pool's contained health_test instance gets initialized once before its first usage. Make add_interrupt_randomness call fast_pool_init_accounting() earlier: health test functionality will get invoked before the latter's old location and it must have been initialized by that time. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 37746df53acf..0f56c873a501 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -879,6 +879,11 @@ static void discard_queued_entropy(struct entropy_store *r, spin_unlock_irqrestore(&r->lock, flags); } +struct health_test {}; + +static void health_test_reset(struct health_test *h) +{} + struct fast_pool { __u32 pool[4]; unsigned long last; @@ -886,6 +891,7 @@ struct fast_pool { unsigned char count; int event_entropy_shift; struct queued_entropy q; + struct health_test health; }; /* @@ -1644,6 +1650,7 @@ static inline void fast_pool_init_accounting(struct fast_pool *f) return; f->event_entropy_shift = min_irq_event_entropy_shift(); + health_test_reset(&f->health); } void add_interrupt_randomness(int irq, int irq_flags) @@ -1674,6 +1681,8 @@ void add_interrupt_randomness(int irq, int irq_flags) add_interrupt_bench(cycles); this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]); + fast_pool_init_accounting(fast_pool); + if (unlikely(crng_init == 0)) { if ((fast_pool->count >= 64) && crng_fast_load((char *) fast_pool->pool, @@ -1692,8 +1701,6 @@ void add_interrupt_randomness(int irq, int irq_flags) if (!spin_trylock(&r->lock)) return; - fast_pool_init_accounting(fast_pool); - if (!fips_enabled) { /* award one bit for the contents of the fast pool */ nfrac = 1 << ENTROPY_SHIFT; From patchwork Mon Sep 21 07:58:48 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788701 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7CCF5139A for ; Mon, 21 Sep 2020 08:00:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6516A20BED for ; Mon, 21 Sep 2020 08:00:54 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726610AbgIUIAq (ORCPT ); Mon, 21 Sep 2020 04:00:46 -0400 Received: from mx2.suse.de ([195.135.220.15]:57298 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726591AbgIUH7k (ORCPT ); Mon, 21 Sep 2020 03:59:40 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id A947EB52B; Mon, 21 Sep 2020 08:00:07 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 32/41] random: introduce health test stub and wire it up Date: Mon, 21 Sep 2020 09:58:48 +0200 Message-Id: <20200921075857.4424-33-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org NIST SP800-90B requires certain statistical tests to be run continuously on a noise source's output. In preparation to implementing those, introduce an empty stub, health_test_process() and wire it up to add_interrupt_randomness(). This patch does not implement any actual testing functionality yet, it's mereley meant to define the interactions between add_interrupt_randomness() and the health tests. health_test_process() is to be invoked on individual noise samples, i.e. cycle counter values and returns, either of three possible status codes indicating to the calling add_interrupt_randomness() that - either some more samples are needed in order to complete the statistical tests, - that the tests have finished with positive result on the latest run of noise samples or - that the tests have failed. Introduce an enum health_result defining constants corresponding to these resp. cases: health_queue, health_dispatch and health_discard. Provide another value, health_none, to indicate the case that the health tests are disabled, because e.g. fips_enabled is unset. Make the stub health_test_process() return this value for now. As long as the statistical tests need more input noise samples before reaching a conclusion, health_queue will get returned from health_test_process(). FWIW, the number of successive input samples needed by the tests will be at the order of 128 to 8192, depending on the per-IRQ entropy estimate. add_interrupt_randomness() currently attempts to transfer the noise kept within in the per-CPU fast_pool, which is of limited capacity, to the global input_pool as soon as a threshold of 64 events is reached and it will continue to do so. However, as long as some tests are pending, i.e. keep returning health_queue, the associated amount of estimated entropy must not get added to the global input_pool balance, but queued up at the fast_pool's queued_entropy instance. Once the health test have eventually succeeded, as indiciated by health_test_process(), the entropy previously queued up may get dispatched to the global reserve. OTOH, on test failure health_discard will get returned and all entropy queued up from add_interrupt_randomness() since the last dispatch (or discard resp.) must get discarded. Note that add_interrupt_randomness() will continue to unconditionally mix the samples into the fast_pools and eventually into the global input_pool -- the health test results really only affect the entropy accounting. So, make add_interrupt_randomness() invoke health_test_process() on the current cycle counter value in case fips_enabled is set. In case a fast_pool's fill level threshold of 64 events is reached at a time when health tests are still pending and keep returning health_queue, let add_interrupt_randomness() continue to mix the fast_pool's contents into the input_pool as before, but enqueue the associated amount of entropy at the fast_pool's associated queued_entropy instance for later dispatch. Both, entropy dispatch as well as discard operations, require a call to __dequeue_entropy(), which in turn must only get invoked with the input_pool's ->lock being held. It follows that in case the spin_trylock() in add_interrupt_randomness() failed, the latter would not be able to perform entropy dispatch or discard operations immediately at the time those have been requested by the health tests. Add two new boolean flags, ->dispatch_needed and ->discard_needed, to struct fast_pool. Set them from add_interrupt_randomness() in case health_test_process() returned health_dispatch or health_discard resp.. Make the current and subsequent add_interrupt_randomness() invocations to check for ->dispatch_needed and ->discard_needed and to attempt to execute any pending dispatch/discard request. Clear ->dispatch_needed and ->discard_needed again when the prerequisite ->lock could eventually be obtained. As actual health tests returning anything but health_none haven't been implemented yet, there is no behavioural change at this point. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 78 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 75 insertions(+), 3 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 0f56c873a501..cb6441b96b8e 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -881,14 +881,30 @@ static void discard_queued_entropy(struct entropy_store *r, struct health_test {}; +enum health_result { + health_none, + health_queue, + health_dispatch, + health_discard, +}; + static void health_test_reset(struct health_test *h) {} +static enum health_result +health_test_process(struct health_test *h, unsigned int event_entropy_shift, + u8 sample) +{ + return health_none; +} + struct fast_pool { __u32 pool[4]; unsigned long last; unsigned short reg_idx; unsigned char count; + bool dispatch_needed : 1; + bool discard_needed : 1; int event_entropy_shift; struct queued_entropy q; struct health_test health; @@ -1662,9 +1678,10 @@ void add_interrupt_randomness(int irq, int irq_flags) cycles_t cycles = random_get_entropy(); __u32 c_high, j_high; __u64 ip; - bool reseed; + bool reseed = false; struct queued_entropy *q = &fast_pool->q; unsigned int nfrac; + enum health_result health_result = health_none; if (cycles == 0) cycles = get_reg(fast_pool, regs); @@ -1682,6 +1699,12 @@ void add_interrupt_randomness(int irq, int irq_flags) this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]); fast_pool_init_accounting(fast_pool); + if (fips_enabled) { + health_result = + health_test_process(&fast_pool->health, + fast_pool->event_entropy_shift, + cycles); + } if (unlikely(crng_init == 0)) { if ((fast_pool->count >= 64) && @@ -1693,8 +1716,48 @@ void add_interrupt_randomness(int irq, int irq_flags) return; } + switch (health_result) { + case health_dispatch: + /* + * Still haven't made it around processing a previous + * entropy discard request? + */ + fast_pool->dispatch_needed = !fast_pool->discard_needed; + break; + + case health_discard: + /* + * Still haven't made it around processing a previous + * entropy dispatch request? + */ + fast_pool->discard_needed = !fast_pool->dispatch_needed; + break; + + case health_queue: + /* + * If a previous sample triggered a dispatch which is + * still pending, it's impossible to add new events on + * top as far as entropy accounting is + * concerned. Don't count any events until we get a + * hold of the input_pool ->lock and complete the + * dispatch below. Undo the increment from fast_mix() + * above. + */ + if (fast_pool->dispatch_needed) + fast_pool->count--; + break; + + case health_none: + /* + * fips_enabled is unset, suppress compiler warnings. + */ + break; + }; + if ((fast_pool->count < 64) && - !time_after(now, fast_pool->last + HZ)) + !(health_result == health_none && + time_after(now, fast_pool->last + HZ)) && + !fast_pool->dispatch_needed && !fast_pool->discard_needed) return; r = &input_pool; @@ -1710,7 +1773,16 @@ void add_interrupt_randomness(int irq, int irq_flags) } __queue_entropy(r, q, nfrac); __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); - reseed = __dispatch_queued_entropy_fast(r, q); + + if (fast_pool->dispatch_needed || health_result == health_none) { + reseed = __dispatch_queued_entropy_fast(r, q); + fast_pool->dispatch_needed = false; + } else if (fast_pool->discard_needed) { + int dummy; + + __dequeue_entropy(r, q, &dummy); + fast_pool->discard_needed = false; + } spin_unlock(&r->lock); fast_pool->last = now; From patchwork Mon Sep 21 07:58:49 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788721 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id C8F65618 for ; Mon, 21 Sep 2020 08:01:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BB01720EDD for ; Mon, 21 Sep 2020 08:01:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726336AbgIUIBH (ORCPT ); Mon, 21 Sep 2020 04:01:07 -0400 Received: from mx2.suse.de ([195.135.220.15]:58098 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726577AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 43BD2B52E; Mon, 21 Sep 2020 08:00:08 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 33/41] random: make health_test_process() maintain the get_cycles() delta Date: Mon, 21 Sep 2020 09:58:49 +0200 Message-Id: <20200921075857.4424-34-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The min-entropy estimate has been made for the lower eight bits of the deltas between cycle counter values from successive IRQ events and thus, the upcoming health tests should actually be run on these deltas. Introduce a new field ->previous_sample to struct health_test for storing the previous get_cycles() value. Make health_test_process() maintain it and also calculate the delta between the current and the previous value at this point already in preparation to passing it to the upcoming health tests. Note that ->previous_sample is deliberately not touched from health_test_reset() in order to maintain a steady flow of correctly calculated deltas across health test resets. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index cb6441b96b8e..33f9b7b59f92 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -879,7 +879,9 @@ static void discard_queued_entropy(struct entropy_store *r, spin_unlock_irqrestore(&r->lock, flags); } -struct health_test {}; +struct health_test { + u8 previous_sample; +}; enum health_result { health_none, @@ -895,6 +897,16 @@ static enum health_result health_test_process(struct health_test *h, unsigned int event_entropy_shift, u8 sample) { + u8 sample_delta; + + /* + * The min-entropy estimate has been made for the lower eight + * bits of the deltas between cycle counter values from + * successive IRQ events. + */ + sample_delta = sample - h->previous_sample; + h->previous_sample = sample; + return health_none; } From patchwork Mon Sep 21 07:58:50 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788717 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 63965618 for ; Mon, 21 Sep 2020 08:01:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4E07B20BED for ; Mon, 21 Sep 2020 08:01:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726793AbgIUIBI (ORCPT ); Mon, 21 Sep 2020 04:01:08 -0400 Received: from mx2.suse.de ([195.135.220.15]:57542 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726583AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id D4E8DB52D; Mon, 21 Sep 2020 08:00:08 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 34/41] random: implement the "Adaptive Proportion" NIST SP800-90B health test Date: Mon, 21 Sep 2020 09:58:50 +0200 Message-Id: <20200921075857.4424-35-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org NIST SP800-90B requires an implementation of the "Adaptive Proportion" health test (APT) or similar for detecting noise source entropy degradations. This tests works by counting how many times the first sample value in a sequence of n events occurs among the remaining n-1 samples. The test will reject if this number exceeds a certain threshold. With a min-entropy estimate of H=2^-event_entropy_shift per IRQ event, the probability of observing any particular sample value is bounded by p <= 2^-H. Assuming i.i.d., the number of occurences of such a sample value among n - 1 events follows the binomial distribution with parameters n - 1 and p. The probability to observe up to k occurences of a given sample value is not less than that distribution's CDF F(n - 1, p, k) at point k, per the definition of CDFs and the fact that F(n - 1, p1, k) >= F(n - 1, p2, k) for p1 <= p2 in the particular case of Binomial distributions. It follows that an upper bound on the probability of observing the same value c or more times among n - 1 consecutive samples is given by 1 - F(n - 1, p, c - 1). In conclusion, the probability of false positives is <= p * (1 - F(n - 1, p, c - 1)) for the Adaptive Proportion test. NIST SP800-90B recommends to set n to either 512 or 1024 and to choose a cut-off value c such that the probability of false positives is <= 2^-20. However, assuming an estimated per-IRQ entropy of 1 bit, it would take 1024/128 == 8 minimum crng seed sizes worth of entropy before the APT eventually completes and the accumulated entropy may get released to the global reserve. Thus, it is desirable to set n such that the APT will complete within 128 bits worth of entropy, i.e. to n = 128 / H. However, for such relatively small values of n, an upper bound as small as 2^-20 for the false positives probability would make the test's statistical power, i.e. the capability to detect degraded noise sources, plummet to uselessness. Note that add_interrupt_randomness() will continue to unconditionally mix all events into the fast_pools, independent of the APT's outcome. Thus, allowing for a higher probability of false positives cannot change the output distribution, but only potentially affect the entropy accounting. Choose an upper bound of 2^-16 for the probability of false positives. The resulting cut-off values for the different supported values of per-IRQ entropy estimates are tabulated below. The "power" column lists the probabilities (again for i.i.d.) that the APT would report a failure in case the actual entropy has degraded to one half of the assumed estimate. H n c power -------------------- 1 128 87 52.5% 1/2 256 210 67.5% 1/4 512 463 76.7% 1/8 1024 973 82.8% 1/16 2048 1997 82.6% 1/32 4096 4044 85.8% 1/64 8192 8140 85.8% Add a couple of new fields to struct health_test for storing the required APT state to struct health_test: - ->apt_event_count: total number of samples processed by the currently pending APT, - ->apt_candidate: the sample value whose number of occurences the currently pending APT is counting, - ->apt_candidate_count: the number of occurences of ->apt_candidate the currently pending APT has encountered so far. Implement the APT logic and wrap it in a new function, health_test_apt(). Invoke it from health_test_process(). Signed-off-by: Nicolai Stange --- drivers/char/random.c | 56 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 54 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 33f9b7b59f92..131302cbc495 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -880,6 +880,10 @@ static void discard_queued_entropy(struct entropy_store *r, } struct health_test { + unsigned short apt_event_count; + unsigned short apt_candidate_count; + u8 apt_candidate; + u8 previous_sample; }; @@ -890,8 +894,56 @@ enum health_result { health_discard, }; +/* Adaptive Proportion Test */ +static void health_apt_reset(struct health_test *h) +{ + h->apt_event_count = 0; +} + +static enum health_result +health_test_apt(struct health_test *h, unsigned int event_entropy_shift, + u8 sample_delta) +{ + unsigned int n = 128 << event_entropy_shift; + /* + * Observing some particular sample value more often than + * these thresholds, specified for the different possible + * values of event_entropy_shift each, should have probability + * <= 2^-16. + */ + static const unsigned int c[] = {87, 210, 463, 973, 1997, 4044, 8140}; + + if (!h->apt_event_count) { + h->apt_event_count = 1; + h->apt_candidate = sample_delta; + h->apt_candidate_count = 0; + return health_queue; + } + + ++h->apt_event_count; + if (unlikely(h->apt_candidate == sample_delta && + ++h->apt_candidate_count == c[event_entropy_shift])) { + health_apt_reset(h); + return health_discard; + } else if (c[event_entropy_shift] - h->apt_candidate_count > + n - h->apt_event_count) { + /* + * The currently pending APT might not have seen all n + * events yet, but it's already known by now that it + * can't fail anymore. Note that the above condition + * also coverts the case h->apt_event_count == n. + */ + health_apt_reset(h); + return health_dispatch; + } + + return health_queue; +} + static void health_test_reset(struct health_test *h) -{} +{ + health_apt_reset(h); +} static enum health_result health_test_process(struct health_test *h, unsigned int event_entropy_shift, @@ -907,7 +959,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, sample_delta = sample - h->previous_sample; h->previous_sample = sample; - return health_none; + return health_test_apt(h, event_entropy_shift, sample_delta); } struct fast_pool { From patchwork Mon Sep 21 07:58:51 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788699 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id D75B2139A for ; Mon, 21 Sep 2020 08:00:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C894120EDD for ; Mon, 21 Sep 2020 08:00:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726741AbgIUIAr (ORCPT ); Mon, 21 Sep 2020 04:00:47 -0400 Received: from mx2.suse.de ([195.135.220.15]:57374 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726578AbgIUH7k (ORCPT ); Mon, 21 Sep 2020 03:59:40 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 6E74BB525; Mon, 21 Sep 2020 08:00:09 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 35/41] random: improve the APT's statistical power Date: Mon, 21 Sep 2020 09:58:51 +0200 Message-Id: <20200921075857.4424-36-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The Adapative Proportion Test as specified by NIST SP800-90B counts how often the first sample value in a sequence of n samples occurs among the remaining n - 1 ones and will report failure if the result is unexpectedly large. The intention is to capture cases where a noise source's actual min-entropy falls below the one estimated during the validation process. Note that, assuming i.i.d., a decrease in per-IRQ min-entropy corresponds to an increase in the maximum probability among all possible sample values, per the definition of min-entropy. For example, consider the maximum supported per-IRQ min-entropy estimate of H=1, which corresponds to a maximum probability of p = 2^-H = 50% among all possible sample values. Now, if the actual entropy degraded to H/2, it would mean that some sample value's likelihood had increased to ~70%. The ability of the APT to detect this degradation is limited by the way it's currently implemented: a prerequisite for successfully reporting a sequence of n samples as bad is to find the offending sample value at the leading position. Thus, the power of the APT is always limited by the probability of the offending sample value, i.e. 70% in this example, no matter how large the total number n of examined of samples is. This can be improved upon by taking advantage of the fact that only values of H <= 1 are currently supported for the per-IRQ entropy estimate. It follows that the maximum probability among all sample values would increase to > 1/2 in case the actual min-entropy happened to fall below the assumed value. If we were to examine a sequence of n1 samples, the expected number of occurrences of the offending sample value would be > 1/2 * n1 (again assuming i.i.d). For example, for an actual entropy of H/2, with H=1 as above, the probability to find 4 or more samples of the same value among a sequence of n1 = 7 events would be ~88%, which is an improvement over the 70% from above. So partition the total number of samples n = 128/H to examine from the APT into two parts, n1 and n2, such that n = n1 + n2 with n1 odd. Rather than simply picking the first sample value to subsequently search for in the remaining n-1 events, make the APT to run a "presearch" on the first n1 samples in order to find the value occurring more than n1 / 2 times, if there is such one. Make the APT then continue as usual: let it search the remaining n2 samples for the found candidate value, count the number of occurrences and report failure if a certain threshold is reached. Of course, new thresholds should be installed in order to gain optimal statistical power from the second phase while still maintaining a false positive rate of 2^-16 as before. An exhaustive search among all possibilities for the different choices of n1 and supported per-IRQ min-entropies revealed that n1 = 7 is optimal for n = 128 (H = 1) and close to the resp. optimum for larger n, i.e. smaller H. With this choice, the new presearch scheme yields new thresholds ("c") and probabilities to detect a entropy degradations to H/2 ("power") as tabulated below: H n c power -------------------- 1 128 83 64.7% 1/2 256 205 79.1% 1/4 512 458 81.6% 1/8 1024 968 84.0% 1/16 2048 1991 84.9% 1/32 4096 4038 86.9% 1/64 8192 8134 86.4% Compare this to the former numbers for the original implementation: H n c power -------------------- 1 128 87 52.5% 1/2 256 210 67.5% 1/4 512 463 76.7% 1/8 1024 973 82.8% 1/16 2048 1997 82.6% 1/32 4096 4044 85.8% 1/64 8192 8140 85.8% So for smaller values of H, i.e. for H <= 1/8, the improvement isn't really impressive, but that was to be expected. OTOH, for the larger Hs, that is for the per-IRQ entropies estimated for systems with a high resolution get_cycles(), there is a clear advantage over the old scheme. Implement the described presearch for finding the sample value occurring more than half of the times among the first n1=7 events in a sequence of n=128/H samples to examine, if there is such one. Rather than maintaining individual per-CPU counters for the 2^8 possible sample values each, count the numbers of ones at the eight resp. bit positions. Note that if some sample value has indeed been observed more than half of the time, it will dominate all these bit counters and its value can be unambiguously restored from them, which is all that is needed. For better reviewability, represent the eight bit counters as an array of eight u8's at struct health_test and implement the bit counting as well as the final candidate extraction in the most naive way. A follow-up patch will sequeeze the counters into a single u32 and also optimize the bit counting and candidate extraction performance-wise. Implement the new health_apt_presearch_update() for updating the presearch bit counters. Call it from health_test_apt() on the first n1=7 samples. Implement the new health_apt_presearch_finalize() for restoring the candidate from the presearch bit counters. Call it from health_test_apt() once the n1'th event in a sequence has been processed and the presearch phase is to be concluded. Make health_test_apt() search for the candidate value as determined by the presearch phase among the sequence's remaining n2 = n - n1 samples. Adapt the failure thresholds to the now slightly smaller n2 values. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 58 +++++++++++++++++++++++++++++++++++++------ 1 file changed, 50 insertions(+), 8 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 131302cbc495..75a103f24fea 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -881,8 +881,13 @@ static void discard_queued_entropy(struct entropy_store *r, struct health_test { unsigned short apt_event_count; - unsigned short apt_candidate_count; - u8 apt_candidate; + union { + u8 apt_presearch_bit_counters[8]; + struct { + unsigned short apt_candidate_count; + u8 apt_candidate; + }; + }; u8 previous_sample; }; @@ -895,9 +900,44 @@ enum health_result { }; /* Adaptive Proportion Test */ +#define HEALTH_APT_PRESEARCH_EVENT_COUNT 7 + +static void health_apt_presearch_update(struct health_test *h, u8 sample_delta) +{ + int i; + + for (i = 0; i < 8; ++i) { + h->apt_presearch_bit_counters[i] = sample_delta & 0x1; + sample_delta >>= 1; + } +} + +static void health_apt_presearch_finalize(struct health_test *h) +{ + int i; + + /* + * If some event octet occurred more than half of the time, + * i.e. more than HEALTH_APT_PRESEARCH_EVENT_COUNT / 2 times, + * then its value can be restored unambigiously from the eight + * ->apt_presearch_bit_counters each holding the count of 1s + * encountered at the corresponding bit positions. + */ + h->apt_candidate = 0; + for (i = 0; i < 8; ++i) { + if (h->apt_presearch_bit_counters[i] >= + (HEALTH_APT_PRESEARCH_EVENT_COUNT + 1) / 2) { + h->apt_candidate |= 1 << i; + } + } + h->apt_candidate_count = 0; +}; + static void health_apt_reset(struct health_test *h) { h->apt_event_count = 0; + memset(h->apt_presearch_bit_counters, 0, + sizeof(h->apt_presearch_bit_counters)); } static enum health_result @@ -911,16 +951,18 @@ health_test_apt(struct health_test *h, unsigned int event_entropy_shift, * values of event_entropy_shift each, should have probability * <= 2^-16. */ - static const unsigned int c[] = {87, 210, 463, 973, 1997, 4044, 8140}; + static const unsigned int c[] = {83, 205, 458, 968, 1991, 4038, 8134}; + + BUILD_BUG_ON(HEALTH_APT_PRESEARCH_EVENT_COUNT != 7); - if (!h->apt_event_count) { - h->apt_event_count = 1; - h->apt_candidate = sample_delta; - h->apt_candidate_count = 0; + ++h->apt_event_count; + if (unlikely(h->apt_event_count <= HEALTH_APT_PRESEARCH_EVENT_COUNT)) { + health_apt_presearch_update(h, sample_delta); + if (h->apt_event_count == HEALTH_APT_PRESEARCH_EVENT_COUNT) + health_apt_presearch_finalize(h); return health_queue; } - ++h->apt_event_count; if (unlikely(h->apt_candidate == sample_delta && ++h->apt_candidate_count == c[event_entropy_shift])) { health_apt_reset(h); From patchwork Mon Sep 21 07:58:52 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788709 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id B928C618 for ; Mon, 21 Sep 2020 08:01:08 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A51DB20BED for ; Mon, 21 Sep 2020 08:01:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726790AbgIUIBH (ORCPT ); Mon, 21 Sep 2020 04:01:07 -0400 Received: from mx2.suse.de ([195.135.220.15]:57622 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726584AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 0A838B530; Mon, 21 Sep 2020 08:00:10 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 36/41] random: optimize the APT's presearch Date: Mon, 21 Sep 2020 09:58:52 +0200 Message-Id: <20200921075857.4424-37-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The Adaptive Proportion Test's presearch phase is supposed to determine the sample value occurring more than half of the times among the first n1=7 events in a sequence, if there is any such one. To this end, it maintains eight counters at struct health_test for counting the numbers of ones observed at each of the eight resp. bit positions within the sample values' octets. The idea is that if any sample value had been encountered more than half of the time, it would dominate all these counters and its value could be restored unambiguously from them. For better reviewability, this had been implemented in the most straightforward way: - the counters had been represented as an array of eight u8s at struct health_test and - both, the counter updating as well as the candidate extracion code had been implemented by means of a loop over the eight bit positions. As this is all accessed from add_interrupt_randomness(), optimizations won't harm. In particular, using a total of eight bytes for the bit counters is wasteful and can be reduced to half of that, optimizing the size of struct health_test, which in turn is stored as part of the per-CPU struct fast_pool. For counts up to n1=7, 3 bits would suffice. Rather than using an array of eight u8s, store the bit counter within an u32's eight four-bit nibbles. Even though it probably won't matter on average in practice, because the APT presearch is run only for a small fraction of all IRQ events, reduce the number of instructions issued from the bit counter maintenance and candidate extraction code as well. If nothing else, this can potentially reduce the maximum IRQ latency by a few cycles. Namely, make the bit counter updating code in health_apt_presearch_update() spread the eight bits from the input sample evenly across an u32. That is, the bit at position i will end up at position 4*i. This can be achieved within five binops and four shifts. This intermediate value can then get subsequently added in a single operation to the "packed" bit counters kept in struct health_test in order to conclude the operation. As for the final candidate extraction in health_apt_presearch_finalize(), remember that the i'th counter needs to get compared against n1 / 2 = 7 / 2 in order to restore the i'th bit from the resulting candidate value. The condition that one such bit counter is >= 4 is equivalent to testing its bit at the 2nd position, counted from zero. Thus, (->apt_presearch_bit_counters & 0x44444444) >> 2 will yield a value where the LSB from the i'th nibble, equals the i'th bit from the result and everything else is unset. The final result can then be obtained by "shrinking" this intermediate representation back into an u8. In total, the candidate extraction can be achieved within a sequence of seven binops and six shifts. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 71 ++++++++++++++++++++++++++++++++----------- 1 file changed, 53 insertions(+), 18 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 75a103f24fea..2c744d2a9b26 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -882,7 +882,7 @@ static void discard_queued_entropy(struct entropy_store *r, struct health_test { unsigned short apt_event_count; union { - u8 apt_presearch_bit_counters[8]; + u32 apt_presearch_bit_counters; struct { unsigned short apt_candidate_count; u8 apt_candidate; @@ -904,40 +904,75 @@ enum health_result { static void health_apt_presearch_update(struct health_test *h, u8 sample_delta) { - int i; + u32 encoded; - for (i = 0; i < 8; ++i) { - h->apt_presearch_bit_counters[i] = sample_delta & 0x1; - sample_delta >>= 1; - } + /* + * Encode the sample octet by "widening" it into 8 + * nibbles. That is, bit i from the source will be assigned to + * bit 4*i in the result. All other bits are set to zero. + */ + encoded = sample_delta; + encoded = (encoded & 0xf) | ((encoded >> 4) << 16); + encoded |= (encoded << 6); + encoded |= (encoded << 3); + encoded &= 0x11111111; + + /* + * The nibbles from ->apt_presearch_bit_counters, each + * counting the number of occurences of 1s at the + * corresponding bit position, don't overflow into each other. + */ + BUILD_BUG_ON(ilog2(HEALTH_APT_PRESEARCH_EVENT_COUNT) >= 4); + h->apt_presearch_bit_counters += encoded; } static void health_apt_presearch_finalize(struct health_test *h) { - int i; + u32 majority, decoded; /* * If some event octet occurred more than half of the time, * i.e. more than HEALTH_APT_PRESEARCH_EVENT_COUNT / 2 times, * then its value can be restored unambigiously from the eight - * ->apt_presearch_bit_counters each holding the count of 1s - * encountered at the corresponding bit positions. + * ->apt_presearch_bit_counters nibbles each holding the count + * of 1s encountered at the corresponding bit positions. + * + * Because HEALTH_APT_PRESEARCH_EVENT_COUNT is a power of two + * minus one, the condition + * nibble >= HEALTH_APT_PRESEARCH_EVENT_COUNT / 2 + * is true iff the nibble's bit at postion + * ilog2(HEALTH_APT_PRESEARCH_EVENT_COUNT) is set. */ - h->apt_candidate = 0; - for (i = 0; i < 8; ++i) { - if (h->apt_presearch_bit_counters[i] >= - (HEALTH_APT_PRESEARCH_EVENT_COUNT + 1) / 2) { - h->apt_candidate |= 1 << i; - } - } + BUILD_BUG_ON(!is_power_of_2(HEALTH_APT_PRESEARCH_EVENT_COUNT + 1)); +#define MAJORITY_BIT ilog2(HEALTH_APT_PRESEARCH_EVENT_COUNT) +#define SHL_AND_OR(a, shl) ((a) | ((a) << shl)) +#define SET_ALL_NIBBLES_TO(to) SHL_AND_OR(SHL_AND_OR(SHL_AND_OR(to, 16), 8), 4) +#define MAJORITY_MASK SET_ALL_NIBBLES_TO(1 << MAJORITY_BIT) + majority = (h->apt_presearch_bit_counters & MAJORITY_MASK); + majority >>= MAJORITY_BIT; +#undef MAJORITY_MASK +#undef SET_ALL_NIBBLES_TO +#undef MAJORITY_BIT + + /* + * Reverse the encoding from health_apt_update_presearch(). + * That is, "shrink" the eight nibbles back into an octet such + * that the result's i'th bit is set to the i'th nibble's LSB. + */ + decoded = majority; + decoded |= (decoded >> 3); + decoded |= (decoded >> 3); + decoded |= (decoded >> 3); + decoded = (((decoded >> 16) << 4) | (decoded & 0xf)) & 0xff; + + h->apt_candidate = decoded; h->apt_candidate_count = 0; }; static void health_apt_reset(struct health_test *h) { h->apt_event_count = 0; - memset(h->apt_presearch_bit_counters, 0, - sizeof(h->apt_presearch_bit_counters)); + h->apt_presearch_bit_counters = 0; } static enum health_result From patchwork Mon Sep 21 07:58:53 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788707 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 0D2C41668 for ; Mon, 21 Sep 2020 08:01:06 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0050520EDD for ; Mon, 21 Sep 2020 08:01:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726761AbgIUIAy (ORCPT ); Mon, 21 Sep 2020 04:00:54 -0400 Received: from mx2.suse.de ([195.135.220.15]:57144 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726589AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 9E7B9B288; Mon, 21 Sep 2020 08:00:10 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 37/41] random: implement the "Repetition Count" NIST SP800-90B health test Date: Mon, 21 Sep 2020 09:58:53 +0200 Message-Id: <20200921075857.4424-38-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The "Repetition Count Test" (RCT) as specified by NIST SP800-90B simply counts the number of times the same sample value has been observed and reports failure if an highly unlikely threshold is exceeded. The exact values of the latter depend on the estimated per-IRQ min-entropy H as well as on the upper bounds set on the probability of false positives. For the latter, a maximum value of 2^-20 is recommended and with this value the threshold can be calculated as 1 + ceil(20 / H). It should be noted that the RCT has very poor statistical power and is only intended to detect catastrophic noise source failures, like the get_cycles() in add_interrupt_randomness() always returning the same constant. Add the fields needed for maintaining the RCT state to struct health_test: ->rct_previous_delta for storing the previous sample value and ->rct_count for keeping track of how many times this value has been observed in a row so far. Implement the RCT and wrap it in a new function, health_test_rct(). Make the health test entry point, health_test_process(), call it early before invoking the APT and forward failure reports to the caller. All other return codes from the RCT are ignored, because - as said, the statistical power is weak and a positive outcome wouldn't tell anything and - it's not desirable to make the caller, i.e. add_interrupt_randomness(), to further queue any entropy once the concurrently running APT has signaled a successful completion. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 55 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+) diff --git a/drivers/char/random.c b/drivers/char/random.c index 2c744d2a9b26..54ee082ca4a8 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -890,6 +890,9 @@ struct health_test { }; u8 previous_sample; + + u8 rct_previous_delta; + unsigned short rct_count; }; enum health_result { @@ -899,6 +902,43 @@ enum health_result { health_discard, }; +/* Repetition count test. */ +static enum health_result +health_test_rct(struct health_test *h, unsigned int event_entropy_shift, + u8 sample_delta) +{ + unsigned int c; + + if (likely(sample_delta != h->rct_previous_delta)) { + h->rct_previous_delta = sample_delta; + h->rct_count = 0; + return health_dispatch; + } + + h->rct_count++; + if (!h->rct_count) { + /* Overflow. */ + h->rct_count = -1; + } + + /* + * With a min-entropy of H = 2^-event_entropy_shift bits per + * event, the maximum probability of seing any particular + * sample value (i.e. delta) is bounded by 2^-H. Thus, the + * probability to observe the same events C times in a row is + * less than 2^-((C - 1) * H). Limit the false positive rate + * of the repetition count test to 2^-20, which yields a + * cut-off value of C = 1 + 20/H. Note that the actual number + * of repetitions equals ->rct_count + 1, so this offset by + * one must be accounted for in the comparison below. + */ + c = 20 << event_entropy_shift; + if (h->rct_count >= c) + return health_discard; + + return health_queue; +} + /* Adaptive Proportion Test */ #define HEALTH_APT_PRESEARCH_EVENT_COUNT 7 @@ -1027,6 +1067,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, u8 sample) { u8 sample_delta; + enum health_result rct; /* * The min-entropy estimate has been made for the lower eight @@ -1036,6 +1077,20 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, sample_delta = sample - h->previous_sample; h->previous_sample = sample; + rct = health_test_rct(h, event_entropy_shift, sample_delta); + if (rct == health_discard) { + /* + * Something is really off, get_cycles() has become + * (or always been) a constant. + */ + return health_discard; + } + + /* + * Otherwise return whatever the APT returns. In particular, + * don't care about whether the RCT needs to consume more + * samples to complete. + */ return health_test_apt(h, event_entropy_shift, sample_delta); } From patchwork Mon Sep 21 07:58:54 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788715 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 220C8618 for ; Mon, 21 Sep 2020 08:01:28 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0B31D20874 for ; Mon, 21 Sep 2020 08:01:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726577AbgIUIBI (ORCPT ); Mon, 21 Sep 2020 04:01:08 -0400 Received: from mx2.suse.de ([195.135.220.15]:56892 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726576AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 3CEE4B532; Mon, 21 Sep 2020 08:00:11 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 38/41] random: enable NIST SP800-90B startup tests Date: Mon, 21 Sep 2020 09:58:54 +0200 Message-Id: <20200921075857.4424-39-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org NIST SP800-90B, section 4.3 requires an entropy source to inhibit output until the so-called "startup" tests have completed. These "startup" test shall process at least 1024 consecutive samples by means of the continuous health tests, i.e. the already implemented Repetition Count Test (RCT) and Adaptive Proportion Test (APT). Introduce a new field ->warmup to struct health_test. Initialize it to 1024 from health_test_reset(). Make health_test_process() decrement ->warmup once per event processed without test failure, but reset ->warmup to the intitial value upon failure. Prevent health_test_process() from returning health_dispatch as long as ->warmup hasn't dropped to zero. This will cause the caller, i.e. add_interrupt_randomness(), to not dispatch any entropy to the global balance until the startup tests have finished. Note that this change will delay the initial seeding of the primary_crng, especially for those values of the estimated per-IRQ min-entropy H where the mimimum of 1024 events from above is by several factors larger than 128/H, the number of events to be processed by a single APT run. That would only affect systems running with fips_enabled though and there's simply no way to avoid it without violating the specs. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 25 +++++++++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 54ee082ca4a8..bd8c24e433d0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -880,6 +880,7 @@ static void discard_queued_entropy(struct entropy_store *r, } struct health_test { + unsigned short warmup; unsigned short apt_event_count; union { u32 apt_presearch_bit_counters; @@ -1059,6 +1060,13 @@ health_test_apt(struct health_test *h, unsigned int event_entropy_shift, static void health_test_reset(struct health_test *h) { + /* + * Don't dispatch until at least 1024 events have been + * processed by the continuous health tests as required by + * NIST SP800-90B for the startup tests. + */ + h->warmup = 1024; + health_apt_reset(h); } @@ -1067,7 +1075,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, u8 sample) { u8 sample_delta; - enum health_result rct; + enum health_result rct, apt; /* * The min-entropy estimate has been made for the lower eight @@ -1083,6 +1091,8 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, * Something is really off, get_cycles() has become * (or always been) a constant. */ + if (h->warmup) + health_test_reset(h); return health_discard; } @@ -1091,7 +1101,18 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, * don't care about whether the RCT needs to consume more * samples to complete. */ - return health_test_apt(h, event_entropy_shift, sample_delta); + apt = health_test_apt(h, event_entropy_shift, sample_delta); + if (unlikely(h->warmup) && --h->warmup) { + if (apt == health_discard) + health_test_reset(h); + /* + * Don't allow the caller to dispatch until warmup + * has completed. + */ + return apt == health_dispatch ? health_queue : apt; + } + + return apt; } struct fast_pool { From patchwork Mon Sep 21 07:58:55 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788731 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 89750139A for ; Mon, 21 Sep 2020 08:01:45 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7AE9820EDD for ; Mon, 21 Sep 2020 08:01:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726723AbgIUIBb (ORCPT ); Mon, 21 Sep 2020 04:01:31 -0400 Received: from mx2.suse.de ([195.135.220.15]:56980 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726582AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id C5247B531; Mon, 21 Sep 2020 08:00:11 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 39/41] random: make the startup tests include muliple APT invocations Date: Mon, 21 Sep 2020 09:58:55 +0200 Message-Id: <20200921075857.4424-40-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Given a per-IRQ min-entropy estimate of H, the Adaptive Proportion Tests (APT) will need to consume at most n = 128/H samples before reaching a conclusion. The supported values for H are 1, 1/2, 1/4, 1/8, ..., 1/64, but only 1 and 1/8 are currently being actively used on systems with and without a high resolution get_cycles() respectively. The corresponding number of samples consumed by one APT execution are 128, 256, 512, 1024, 2048, 4096 and 8192. Currently, the ->warmup parameter used for controlling the startup is hardcoded to be initialized to 1024 and the health test logic won't permit the caller, i.e. add_interrupt_randomness() to dispatch any entropy to the global balance until that many events have been processed *and* the first APT has completed, whichever comes later. It would take roughly eight successful APT invocations for H=1 until the startup sequence has completed, but for all H <= 1/8, the ->warmup logic is effectively useless because the first APT would always need to process >= 1024 samples anyway. The probabilites of one single APT invocation successfully detecting a degradation of the per-IRQ min-entopy to H/2 ("power") are as follows for the different supported H estimates: H n power --------------- 1 128 64.7% 1/2 256 79.1% 1/4 512 81.6% 1/8 1024 84.0% 1/16 2048 84.9% 1/32 4096 86.9% 1/64 8192 86.4% Thus, for H=1, the probability that at least one out of those eight APT invocations will detect a degradation to H/2 is 1 - (1 - 64.7%)^8 = 99.98%, which is quite good. OTOH, the 84.0% achievable with the single APT invocation for H = 1/8 is only semi-satisfactory. Note that as it currently stands, the only point in time where the health tests can still intervene and keep back low quality noise from the primary_crng is before the initial seed has happened. Afterwards, failing continuous health tests would only potentially delay those best effort reseeds (which is questionable behaviour in itself, as the crng state's entropy is never reduced in the course of reseeding). A future patch will enable dynamically switching from the initial H=1 or 1/8 resp. to lower per-IRQ entropy values upon health test failures in order to keep those systems going where these more or less arbitrary per-IRQ entropy estimates turn out to be simply wrong. From a paranoia POV, it is certainly a good idea to run the APT several times in a row during startup in order to achieve a good statistical power. Extending the warmup to cover the larger of the 1024 events required by NIST SP800-90B and four full APT lengths will result in a combined probability of detecting an entropy degradation to H/2 of >= 99.98% across all supported values of H. The obvious downside is that the number of IRQ events required for the initial seed will be qadrupled, at least for H <= 1/8. Follow this approach. Amend health_test_reset()'s signature by an additional parameter, event_entropy_shift, and make it set ->warmup to the larger of 1024 and 4 * 128 / (2^-event_entropy_shift). Adjust all call sites accordingly. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index bd8c24e433d0..86dd87588b1b 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1058,14 +1058,21 @@ health_test_apt(struct health_test *h, unsigned int event_entropy_shift, return health_queue; } -static void health_test_reset(struct health_test *h) +static void health_test_reset(struct health_test *h, + unsigned int event_entropy_shift) { /* - * Don't dispatch until at least 1024 events have been - * processed by the continuous health tests as required by - * NIST SP800-90B for the startup tests. + * Let H = 2^-event_entropy_shift equal the estimated per-IRQ + * min-entropy. One APT will consume at most 128 / H samples + * until completion. Run the startup tests for the larger of + * 1024 events as required by NIST or four times the APT + * length. In either case, the combined probability of the + * resulting number of successive APTs to detect a degradation + * of H to H/2 will be >= 99.8%, for any supported value of + * event_entropy_shift. */ - h->warmup = 1024; + h->warmup = 4 * (128 << event_entropy_shift); + h->warmup = max_t(unsigned int, h->warmup, 1024); health_apt_reset(h); } @@ -1092,7 +1099,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, * (or always been) a constant. */ if (h->warmup) - health_test_reset(h); + health_test_reset(h, event_entropy_shift); return health_discard; } @@ -1104,7 +1111,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, apt = health_test_apt(h, event_entropy_shift, sample_delta); if (unlikely(h->warmup) && --h->warmup) { if (apt == health_discard) - health_test_reset(h); + health_test_reset(h, event_entropy_shift); /* * Don't allow the caller to dispatch until warmup * has completed. @@ -1883,7 +1890,7 @@ static inline void fast_pool_init_accounting(struct fast_pool *f) return; f->event_entropy_shift = min_irq_event_entropy_shift(); - health_test_reset(&f->health); + health_test_reset(&f->health, f->event_entropy_shift); } void add_interrupt_randomness(int irq, int irq_flags) From patchwork Mon Sep 21 07:58:56 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788725 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 686C8618 for ; Mon, 21 Sep 2020 08:01:33 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 523FD20EDD for ; Mon, 21 Sep 2020 08:01:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726845AbgIUIBb (ORCPT ); Mon, 21 Sep 2020 04:01:31 -0400 Received: from mx2.suse.de ([195.135.220.15]:56798 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726581AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 60A82B535; Mon, 21 Sep 2020 08:00:12 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 40/41] random: trigger startup health test on any failure of the health tests Date: Mon, 21 Sep 2020 09:58:56 +0200 Message-Id: <20200921075857.4424-41-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The startup health tests to be executed at boot as required by NIST 800-90B consist of running the contiuous health tests, i.e. the Adaptive Proportion Test (APT) and the Repetition Count Test (RCT), until a certain amount of noise samples have been examined. In case of test failure during this period, the startup tests would get restarted by means of reinitializing the fast_pool's ->warmup member with the original number of total samples to examine during startup. A future patch will enable dynamically switching from the initial H=1 or 1/8 per-IRQ min-entropy estimates to lower values upon health test failures in order to keep those systems going where these more or less arbitrary per-IRQ entropy estimates turn out to simply be wrong. It is certainly desirable to restart the startup health tests upon such a switch. In order to keep the upcoming code comprehensible, move the startup test restart logic from health_test_process() into add_interrupt_randomness(). For simplicity, make add_interrupt_randomness() trigger a startup test on each health test failure. Note that there's a change in behaviour: up to now, only the bootime startup tests would have restarted themselves upon failure, whereas now even a failure of the continuous health tests can potentially trigger a startup test long after boot. Note that as it currently stands, rerunning the full startup tests after the crng has received its initial seed has the only effect to inhibit entropy dispatch for a while and thus, to potentially delay those best effort crng reseeds during runtime. As reseeds never reduce a crng state's entropy, this behaviour is admittedly questionable. However, further patches introducing forced reseeds might perhaps become necessary in the future, c.f. the specification of "reseed_interval" in NIST SP800-90A. Thus, it's better to keep the startup health test restart logic consistent for now. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 86dd87588b1b..bb79dcb96882 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1098,8 +1098,6 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, * Something is really off, get_cycles() has become * (or always been) a constant. */ - if (h->warmup) - health_test_reset(h, event_entropy_shift); return health_discard; } @@ -1110,8 +1108,6 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, */ apt = health_test_apt(h, event_entropy_shift, sample_delta); if (unlikely(h->warmup) && --h->warmup) { - if (apt == health_discard) - health_test_reset(h, event_entropy_shift); /* * Don't allow the caller to dispatch until warmup * has completed. @@ -1928,6 +1924,14 @@ void add_interrupt_randomness(int irq, int irq_flags) health_test_process(&fast_pool->health, fast_pool->event_entropy_shift, cycles); + if (unlikely(health_result == health_discard)) { + /* + * Oops, something's odd. Restart the startup + * tests. + */ + health_test_reset(&fast_pool->health, + fast_pool->event_entropy_shift); + } } if (unlikely(crng_init == 0)) { From patchwork Mon Sep 21 07:58:57 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788711 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 73C751668 for ; Mon, 21 Sep 2020 08:01:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 64CE4214F1 for ; Mon, 21 Sep 2020 08:01:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726796AbgIUIBI (ORCPT ); Mon, 21 Sep 2020 04:01:08 -0400 Received: from mx2.suse.de ([195.135.220.15]:57940 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726592AbgIUH7j (ORCPT ); Mon, 21 Sep 2020 03:59:39 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id E0F6EB533; Mon, 21 Sep 2020 08:00:12 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 41/41] random: lower per-IRQ entropy estimate upon health test failure Date: Mon, 21 Sep 2020 09:58:57 +0200 Message-Id: <20200921075857.4424-42-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Currently, if fips_enabled is set, a per-IRQ min-entropy estimate of either 1 bit or 1/8 bit is assumed, depending on whether a high resolution get_cycles() is available or not. The statistical NIST SP800-90B startup health tests are run on a certain amount of noise samples and are intended to reject in case this hypothesis turns out to be wrong, i.e. if the actual min-entropy is smaller. As long as the startup tests haven't finished, entropy dispatch and thus, the initial crng seeding, is inhibited. On test failure, the startup tests would restart themselves from the beginning. It follows that in case a system's actual per-IRQ min-entropy is smaller than the more or less arbitrarily assessed 1 bit or 1/8 bit resp., there will be a good chance that the initial crng seed will never complete. AFAICT, such a situation could potentially prevent certain userspace daemons like OpenSSH from loading. In order to still be able to make any progress, make add_interrupt_randomness() lower the per-IRQ min-entropy by one half upon each health test failure, but only until the minimum supported value of 1/64 bits has been reached. Note that health test failures will cause a restart of the startup health tests already and thus, a certain number of additional noise samples resp. IRQ events will have to get examined by the health tests before the initial crng seeding can take place. This number of fresh events required is reciprocal to the estimated per-IRQ min-entropy H: for the Adaptive Proportion Test (APT) it equals ~128 / H. It follows that this patch won't be of much help for embedded systems or VMs with poor IRQ rates at boot time, at least not without manual intervention. But there aren't many options left when fips_enabled is set. With respect to NIST SP800-90B conformance, this patch enters kind of a gray area: NIST SP800-90B has no notion of such a dynamically adjusted min-entropy estimate. Instead, it is assumed that some fixed value has been estimated based on general principles and subsequently validated in the course of the certification process. However, I would argue that if a system had successfully passed certification for 1 bit or 1/8 bit resp. of estimated min-entropy per sample, it would automatically be approved for all smaller values as well. Had we started out with such a lower value passing the health tests from the beginning, the latter would never have complained in the first place and the system would have come up just fine. Finally, note that all statistical tests have a non-zero probability of false positives and so do the NIST SP800-90B health tests. In order to not keep the estimated per-IRQ entropy at a smaller level than necessary for forever after spurious health test failures, make add_interrupt_randomness() attempt to double it again after a certain number of successful health test passes at the degraded entropy level have been completed. This threshold should not be too small in order to avoid excessive entropy accounting loss due to continuously alternating between a too large per-IRQ entropy estimate and the next smaller value. For now, choose a value of five as a compromise between quick recovery and limiting said accounting loss. So, introduce a new member ->good_tests to struct fast_pool for keeping track of the number of successfult health test passes. Make add_interrupt_randomness() increment it upon successful healh test completion and reset it to zero on failures. Make add_interrupt_randomness() double the current min-entropy estimate and restart the startup health in case ->good_tests is > 4 and the entropy had previously been lowered. Signed-off-by: Nicolai Stange --- drivers/char/random.c | 25 +++++++++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index bb79dcb96882..24c09ba9d7d0 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1126,6 +1126,7 @@ struct fast_pool { bool dispatch_needed : 1; bool discard_needed : 1; int event_entropy_shift; + unsigned int good_tests; struct queued_entropy q; struct health_test health; }; @@ -1926,9 +1927,13 @@ void add_interrupt_randomness(int irq, int irq_flags) cycles); if (unlikely(health_result == health_discard)) { /* - * Oops, something's odd. Restart the startup - * tests. + * Oops, something's odd. Lower the entropy + * estimate and restart the startup tests. */ + fast_pool->event_entropy_shift = + min_t(unsigned int, + fast_pool->event_entropy_shift + 1, 6); + fast_pool->good_tests = 0; health_test_reset(&fast_pool->health, fast_pool->event_entropy_shift); } @@ -1951,6 +1956,7 @@ void add_interrupt_randomness(int irq, int irq_flags) * entropy discard request? */ fast_pool->dispatch_needed = !fast_pool->discard_needed; + fast_pool->good_tests++; break; case health_discard: @@ -2005,6 +2011,21 @@ void add_interrupt_randomness(int irq, int irq_flags) if (fast_pool->dispatch_needed || health_result == health_none) { reseed = __dispatch_queued_entropy_fast(r, q); fast_pool->dispatch_needed = false; + + /* + * In case the estimated per-IRQ min-entropy had to be + * lowered due to health test failure, but the lower + * value has proven to withstand the tests for some + * time now, try to give the next better value another + * shot. + */ + if (unlikely((fast_pool->event_entropy_shift > + min_irq_event_entropy_shift())) && + fast_pool->good_tests > 4) { + fast_pool->event_entropy_shift--; + health_test_reset(&fast_pool->health, + fast_pool->event_entropy_shift); + } } else if (fast_pool->discard_needed) { int dummy;