From patchwork Wed Apr 13 11:54:11 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Jason A. Donenfeld" X-Patchwork-Id: 12811973 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 6373AC433F5 for ; Wed, 13 Apr 2022 12:03:19 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-Id:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=fjzxg7/pYAbp6hfTivITtpUXvYJiHtXbCWSAlPB1K3I=; b=X9AB8LUX+6bix3 gsgV+DwYM1VfjNhiqe6gtONqulBa1ImFzdHR98b7Edoptn0et+MaDfNWDGn5DAsTp/9yFRFP1ujLp aBxm8yzaWNRRia0Cz0LdEUygA510kD6ryzelYcDjyqXTM8whAAcfn7Tl2nq1ICKS9y4RNv/Dz68aJ yNOMriZ7IjTXemn53T23r9lP9P3keudylPuxbZvcjlXbCWWrFhY/HizxkQLBRfymI8mFs8RvPMwPV wfO+bxjopdx9QVR4JJjwO2zhvyQJR33p2eIZvB2fg1QFtdMG55eb5lbylzH6UfguJW/BztwXdeamb q+sywEBy0xjbBb618xEQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1nebiF-000t6l-2L; Wed, 13 Apr 2022 12:03:07 +0000 Received: from ams.source.kernel.org ([145.40.68.75]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1nebbi-000plW-CF; Wed, 13 Apr 2022 11:56:24 +0000 Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ams.source.kernel.org (Postfix) with ESMTPS id F32C6B8236A; Wed, 13 Apr 2022 11:56:20 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 85A48C385A3; Wed, 13 Apr 2022 11:56:16 +0000 (UTC) Authentication-Results: smtp.kernel.org; dkim=pass (1024-bit key) header.d=zx2c4.com header.i=@zx2c4.com header.b="junDIiDc" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=zx2c4.com; s=20210105; t=1649850975; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=fiIIehyP4yge5lc1OcKOx/eUaAXcUxPxgblGteZoshs=; b=junDIiDctoUCRkUat7woDmumAUEZHL9whNtphl8wVibpXWs0m3BSt4ddgw0+aJBjBUZ459 OLfWPB5+0FAy3Ujc2zYe4Sbgi7slIhWo40XFhuFMEPgRW/a8GkxM2wdRTXxmuu5LKQKQRo 97Dw+1rONMYs7IGIIBpA7xQb0N6oJfI= Received: by mail.zx2c4.com (ZX2C4 Mail Server) with ESMTPSA id 2e2d18c2 (TLSv1.3:AEAD-AES256-GCM-SHA384:256:NO); Wed, 13 Apr 2022 11:56:14 +0000 (UTC) From: "Jason A. Donenfeld" To: linux-kernel@vger.kernel.org, linux-crypto@vger.kernel.org, tglx@linutronix.de, arnd@arndb.de Cc: "Jason A. Donenfeld" , Theodore Ts'o , Dominik Brodowski , Russell King , Catalin Marinas , Will Deacon , Geert Uytterhoeven , Thomas Bogendoerfer , Paul Walmsley , Palmer Dabbelt , Albert Ou , "David S . Miller" , Richard Weinberger , Anton Ivanov , Johannes Berg , Ingo Molnar , Borislav Petkov , Dave Hansen , "H . Peter Anvin" , Chris Zankel , Max Filippov , John Stultz , Stephen Boyd , Dinh Nguyen , linux-arm-kernel@lists.infradead.org, linux-m68k@lists.linux-m68k.org, linux-mips@vger.kernel.org, linux-riscv@lists.infradead.org, sparclinux@vger.kernel.org, linux-um@lists.infradead.org, x86@kernel.org, linux-xtensa@linux-xtensa.org Subject: [PATCH v4 11/11] random: insist on random_get_entropy() existing in order to simplify Date: Wed, 13 Apr 2022 13:54:11 +0200 Message-Id: <20220413115411.21489-12-Jason@zx2c4.com> In-Reply-To: <20220413115411.21489-1-Jason@zx2c4.com> References: <20220413115411.21489-1-Jason@zx2c4.com> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20220413_045622_760031_406A8BE5 X-CRM114-Status: GOOD ( 29.15 ) X-BeenThere: linux-riscv@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-riscv" Errors-To: linux-riscv-bounces+linux-riscv=archiver.kernel.org@lists.infradead.org All platforms are now guaranteed to provide some value for random_get_entropy(). In case some bug leads to this not being so, we print a warning, because that indicates that something is really very wrong (and likely other things are impacted too). This should never be hit, but it's a good and cheap way of finding out if something ever is problematic. Since we now have viable fallback code for random_get_entropy() on all platforms, which is, in the worst case, not worse than jiffies, we can count on getting the best possible value out of it. That means there's no longer a use for using jiffies as entropy input. It also means we no longer have a reason for doing the round-robin register flow in the IRQ handler, which was always of fairly dubious value. Instead we can greatly simplify the IRQ handler inputs and also unify the construction between 64-bits and 32-bits. We now collect the cycle counter and the return address, since those are the two things that matter. Because the return address and the irq number are likely related, to the extent we mix in the irq number, we can just xor it into the top unchanging bytes of the return address, rather than the bottom changing bytes of the cycle counter as before. Then, we can do a fixed 2 rounds of SipHash/HSipHash. Finally, we use the same construction of hashing only half of the [H]SipHash state on 32-bit and 64-bit. We're not actually discarding any entropy, since that entropy is carried through until the next time. And more importantly, it lets us do the same sponge-like construction everywhere. Cc: Theodore Ts'o Signed-off-by: Jason A. Donenfeld --- drivers/char/random.c | 87 ++++++++++++++----------------------------- 1 file changed, 28 insertions(+), 59 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index 6b01b2be9dd4..8931b3fac1d3 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1005,6 +1005,9 @@ int __init rand_initialize(void) urandom_warning.interval = 0; unseeded_warning.interval = 0; } + + WARN(!random_get_entropy(), "Missing cycle counter and fallback timer; RNG " + "entropy collection will consequently suffer."); return 0; } @@ -1018,15 +1021,14 @@ int __init rand_initialize(void) */ void add_device_randomness(const void *buf, size_t size) { - unsigned long cycles = random_get_entropy(); - unsigned long flags, now = jiffies; + unsigned long entropy = random_get_entropy(); + unsigned long flags; if (crng_init == 0 && size) crng_pre_init_inject(buf, size, false); spin_lock_irqsave(&input_pool.lock, flags); - _mix_pool_bytes(&cycles, sizeof(cycles)); - _mix_pool_bytes(&now, sizeof(now)); + _mix_pool_bytes(&entropy, sizeof(entropy)); _mix_pool_bytes(buf, size); spin_unlock_irqrestore(&input_pool.lock, flags); } @@ -1049,12 +1051,11 @@ struct timer_rand_state { */ static void add_timer_randomness(struct timer_rand_state *state, unsigned int num) { - unsigned long cycles = random_get_entropy(), now = jiffies, flags; + unsigned long entropy = random_get_entropy(), now = jiffies, flags; long delta, delta2, delta3; spin_lock_irqsave(&input_pool.lock, flags); - _mix_pool_bytes(&cycles, sizeof(cycles)); - _mix_pool_bytes(&now, sizeof(now)); + _mix_pool_bytes(&entropy, sizeof(entropy)); _mix_pool_bytes(&num, sizeof(num)); spin_unlock_irqrestore(&input_pool.lock, flags); @@ -1216,7 +1217,6 @@ struct fast_pool { unsigned long pool[4]; unsigned long last; unsigned int count; - u16 reg_idx; }; static DEFINE_PER_CPU(struct fast_pool, irq_randomness) = { @@ -1236,11 +1236,11 @@ static DEFINE_PER_CPU(struct fast_pool, irq_randomness) = { * and therefore this has no security on its own. s represents the * 128 or 256-bit SipHash state, while v represents a 128-bit input. */ -static void fast_mix(unsigned long s[4], const unsigned long *v) +static void fast_mix(unsigned long s[4], const unsigned long v[2]) { size_t i; - for (i = 0; i < 16 / sizeof(long); ++i) { + for (i = 0; i < 2; ++i) { s[3] ^= v[i]; #ifdef CONFIG_64BIT s[0] += s[1]; s[1] = rol64(s[1], 13); s[1] ^= s[0]; s[0] = rol64(s[0], 32); @@ -1280,33 +1280,17 @@ int random_online_cpu(unsigned int cpu) } #endif -static unsigned long get_reg(struct fast_pool *f, struct pt_regs *regs) -{ - unsigned long *ptr = (unsigned long *)regs; - unsigned int idx; - - if (regs == NULL) - return 0; - idx = READ_ONCE(f->reg_idx); - if (idx >= sizeof(struct pt_regs) / sizeof(unsigned long)) - idx = 0; - ptr += idx++; - WRITE_ONCE(f->reg_idx, idx); - return *ptr; -} - static void mix_interrupt_randomness(struct work_struct *work) { struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix); /* - * The size of the copied stack pool is explicitly 16 bytes so that we - * tax mix_pool_byte()'s compression function the same amount on all - * platforms. This means on 64-bit we copy half the pool into this, - * while on 32-bit we copy all of it. The entropy is supposed to be - * sufficiently dispersed between bits that in the sponge-like - * half case, on average we don't wind up "losing" some. + * The size of the copied stack pool is explicitly 2 longs so that we + * only ever ingest half of the siphash output each time, retaining + * the other half as the next "key" that carries over. The entropy is + * supposed to be sufficiently dispersed between bits so on average + * we don't wind up "losing" some. */ - u8 pool[16]; + unsigned long pool[2]; /* Check to see if we're running on the wrong CPU due to hotplug. */ local_irq_disable(); @@ -1338,36 +1322,21 @@ static void mix_interrupt_randomness(struct work_struct *work) void add_interrupt_randomness(int irq) { enum { MIX_INFLIGHT = 1U << 31 }; - unsigned long cycles = random_get_entropy(), now = jiffies; + unsigned long cycles = random_get_entropy(); struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness); struct pt_regs *regs = get_irq_regs(); unsigned int new_count; - union { - u32 u32[4]; - u64 u64[2]; - unsigned long longs[16 / sizeof(long)]; - } irq_data; - - if (cycles == 0) - cycles = get_reg(fast_pool, regs); - - if (sizeof(unsigned long) == 8) { - irq_data.u64[0] = cycles ^ rol64(now, 32) ^ irq; - irq_data.u64[1] = regs ? instruction_pointer(regs) : _RET_IP_; - } else { - irq_data.u32[0] = cycles ^ irq; - irq_data.u32[1] = now; - irq_data.u32[2] = regs ? instruction_pointer(regs) : _RET_IP_; - irq_data.u32[3] = get_reg(fast_pool, regs); - } - fast_mix(fast_pool->pool, irq_data.longs); + fast_mix(fast_pool->pool, (unsigned long[2]){ + (regs ? instruction_pointer(regs) : _RET_IP_) ^ swab(irq), + cycles + }); new_count = ++fast_pool->count; if (new_count & MIX_INFLIGHT) return; - if (new_count < 64 && (!time_after(now, fast_pool->last + HZ) || + if (new_count < 64 && (!time_is_before_jiffies(fast_pool->last + HZ) || unlikely(crng_init == 0))) return; @@ -1403,28 +1372,28 @@ static void entropy_timer(struct timer_list *t) static void try_to_generate_entropy(void) { struct { - unsigned long cycles; + unsigned long entropy; struct timer_list timer; } stack; - stack.cycles = random_get_entropy(); + stack.entropy = random_get_entropy(); /* Slow counter - or none. Don't even bother */ - if (stack.cycles == random_get_entropy()) + if (stack.entropy == random_get_entropy()) return; timer_setup_on_stack(&stack.timer, entropy_timer, 0); while (!crng_ready() && !signal_pending(current)) { if (!timer_pending(&stack.timer)) mod_timer(&stack.timer, jiffies + 1); - mix_pool_bytes(&stack.cycles, sizeof(stack.cycles)); + mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); schedule(); - stack.cycles = random_get_entropy(); + stack.entropy = random_get_entropy(); } del_timer_sync(&stack.timer); destroy_timer_on_stack(&stack.timer); - mix_pool_bytes(&stack.cycles, sizeof(stack.cycles)); + mix_pool_bytes(&stack.entropy, sizeof(stack.entropy)); }