From nobody Tue Feb 15 02:09:27 2022 X-Original-To: dev-commits-src-branches@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 5BBB919C3825; Tue, 15 Feb 2022 02:09:28 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4JyPfc0Vkdz3vR6; Tue, 15 Feb 2022 02:09:28 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1644890968; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=qFnfLdCsoIJt9lz2xTuYntKTeVrAYnYjm9y6AaTwPDo=; b=FOo6sftSIOTCMPnLi21QynagCuw+4kEqG91LHZu/1XB8G69FB6K9Byya6K+F0Jw5rWSu1m 5cz/HVlfIhdnvBMckiYimiIvczRmTX3Eu/eEBLR+bv9AG8S5i1gw+sZfqf7Gdjoh7NcREI HWDZOhaj3GgUUgt5stlDeoteYhpaKezb2+dur6r6fF7d5LSe/fyXfbV/FIe6JUgV84vd/N YS7473+4ZkMZJU7r7IsV9HOaID7Ou9XfZQ92nyC2MlIougSrkXu4M+gDvFqHfLnE9Xa3lk SCDJJd9tQmSQv5MgU21geitqzmSVfa/IylohscTe5K6yiwMBXbWzrnJtAs0ETQ== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id CB36019F34; Tue, 15 Feb 2022 02:09:27 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 21F29R3u046637; Tue, 15 Feb 2022 02:09:27 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 21F29RJE046636; Tue, 15 Feb 2022 02:09:27 GMT (envelope-from git) Date: Tue, 15 Feb 2022 02:09:27 GMT Message-Id: <202202150209.21F29RJE046636@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: "David E. O'Brien" Subject: git: 35cf9aa65b56 - stable/12 - random(4): Remove "EXPERIMENTAL" verbiage from concurrent operation List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: obrien X-Git-Repository: src X-Git-Refname: refs/heads/stable/12 X-Git-Reftype: branch X-Git-Commit: 35cf9aa65b5605e9433d4bf8750a5c0ddec11864 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1644890968; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=qFnfLdCsoIJt9lz2xTuYntKTeVrAYnYjm9y6AaTwPDo=; b=X4Mw3mucPcpOn41V688BpE0qfMLVbX09zDtvBlqaq/00aSvKPv3MOFv9d+tReOoLC4fSq4 b0kpHDCKcooE9XjUk5WI8zItRRsoeoqio9Id5r4gbNED06qx4jCbKfQmVZLVIcIvF/9Dx7 bESv+LOyu7qFuZ0Wqlq2HPmpozwi73T8M6KISP2/lgOPPGCOVHl6y87lOk1B3Z4RBOsYQP SJq4gnlEGlQhESexQRm3RlMLTSJVdoL8yiE6u91zuIVS3kfMLxJ8M8JdD2tlG7xaiUOXaR 0j95OCzVMEXK0JuTtyRe5u1Md8f0o1og7XkQclRTdc5FGRfq2MLkcFWDuQg0/A== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1644890968; a=rsa-sha256; cv=none; b=rTn5Fl6Jr2LhCuYhVChaK0+TtBb8QhuztmuFsq2y0AkZhkM8tDLEOtJ8jev9af+RlbvqAS yqE1ioKquYlb3VceFVwPJ09gleBapQc1y/eUZNtceHjahb7ZEDaSEUqWfnhWk6Nc1PS67e zwaee/tUCktxVt4NVOI5Ju0fC0g5eWkR8a5Hl1rTayNf/A9j8IWuZhKsDPHYo5lP/NV8br TKWtKPrOLF94V+LiNacDyNHL9KkKeVopOPdOCtFwQMgbEld4dCkOWr7uO/qMlAgNqTmlzz 79GfRgnoD0LVhYRPfb+gAVLRHZ62rAv1GUHKpEWZ63heyTCgwKvRI0C0dlNl4g== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/12 has been updated by obrien: URL: https://cgit.FreeBSD.org/src/commit/?id=35cf9aa65b5605e9433d4bf8750a5c0ddec11864 commit 35cf9aa65b5605e9433d4bf8750a5c0ddec11864 Author: Conrad Meyer AuthorDate: 2019-08-15 00:39:53 +0000 Commit: David E. O'Brien CommitDate: 2022-02-15 02:09:08 +0000 random(4): Remove "EXPERIMENTAL" verbiage from concurrent operation No functional change. Add a verbose comment giving an example side-by-side comparison between the prior and Concurrent modes of Fortuna, and why one should believe they produce the same result. The intent is to flip this on by default prior to 13.0, so testing is encouraged. To enable, add the following to loader.conf: kern.random.fortuna.concurrent_read="1" The intent is also to flip the default blockcipher to the faster Chacha-20 prior to 13.0, so testing of that mode of operation is also appreciated. To enable, add the following to loader.conf: kern.random.use_chacha20_cipher="1" (cherry picked from commit 878a05a4e67a49bccb036b9d323254c0bf17538b) --- sys/dev/random/fortuna.c | 114 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 105 insertions(+), 9 deletions(-) diff --git a/sys/dev/random/fortuna.c b/sys/dev/random/fortuna.c index 0e66ba3e97f6..f93cf7145ca3 100644 --- a/sys/dev/random/fortuna.c +++ b/sys/dev/random/fortuna.c @@ -125,8 +125,8 @@ static struct fortuna_state { } fortuna_state; /* - * Experimental concurrent reads feature. For now, disabled by default. But - * we may enable it in the future. + * This knob enables or disables Concurrent Reads. The plan is to turn it on + * by default sometime before 13.0 branches. * * The benefit is improved concurrency in Fortuna. That is reflected in two * related aspects: @@ -141,6 +141,107 @@ static struct fortuna_state { * global state mutex, potentially blocking on a reader. Our adaptive * mutexes assume that a lock holder currently on CPU will release the lock * quickly, and spin if the owning thread is currently running. + * + * The concern is that the reduced lock scope might results in a less safe + * random(4) design. However, the reduced-lock scope design is still + * fundamentally Fortuna. This is discussed below. + * + * Fortuna Read() only needs mutual exclusion between readers to correctly + * update the shared read-side state: just C, the 128-bit counter, and K, the + * current cipher key. + * + * In the Fortuna design, the global counter C should provide an independent + * range of values per generator (CTR-mode cipher or similar) invocation. + * + * Under lock, we can save a copy of C on the stack, and increment the global C + * by the number of blocks a Read request will require. + * + * Still under lock, we can save a copy of the key K on the stack, and then + * perform the usual key erasure K' <- Keystream(C, K, ...). This does require + * generating 256 bits (32 bytes) of cryptographic keystream output with the + * global lock held, but that's all; none of the user keystream generation must + * be performed under lock. + * + * At this point, we may unlock. + * + * Some example timelines below (to oversimplify, all requests are in units of + * native blocks, and the keysize happens to be equal or less to the native + * blocksize of the underlying cipher, and the same sequence of two requests + * arrive in the same order). The possibly expensive consumer keystream + * generation portion is marked with '**'. + * + * Status Quo fortuna_read() Reduced-scope locking + * ------------------------- --------------------- + * C=C_0, K=K_0 C=C_0, K=K_0 + * + * 1:Lock() 1:Lock() + * + * 1:GenBytes() 1:stack_C := C_0 + * 1: Keystream(C_0, K_0, N) 1:stack_K := K_0 + * 1: ** 1:C' := C_0 + N + * 1: C' := C_0 + N 1:K' := Keystream(C', K_0, 1) + * 1: <- Keystream 1: <1 block generated> + * 1: K' := Keystream(C', K_0, 1) 1: C'' := C' + 1 + * 1: <1 block generated> 1: <- Keystream + * 1: C'' := C' + 1 1:Unlock() + * 1: <- Keystream + * 1: <- GenBytes() + * 1:Unlock() + * + * Just prior to unlock, shared state is identical: + * ------------------------------------------------ + * C'' == C_0 + N + 1 C'' == C_0 + N + 1 + * K' == keystream generated from K' == keystream generated from + * C_0 + N, K_0. C_0 + N, K_0. + * K_0 has been erased. K_0 has been erased. + * + * After both designs unlock, the 2nd reader is unblocked. + * + * 2:Lock() 2:Lock() + * 2:GenBytes() 2:stack_C' := C'' + * 2: Keystream(C'', K', M) 2:stack_K' := K' + * 2: ** 2:C''' := C'' + M + * 2: C''' := C'' + M 2:K'' := Keystream(C''', K', 1) + * 2: <- Keystream 2: <1 block generated> + * 2: K'' := Keystream(C''', K', 1) 2: C'''' := C''' + 1 + * 2: <1 block generated> 2: <- Keystream + * 2: C'''' := C''' + 1 2:Unlock() + * 2: <- Keystream + * 2: <- GenBytes() + * 2:Unlock() + * + * Just prior to unlock, shared state is still identical: + * ------------------------------------------------------ + * + * C'''' == (C_0 + N + 1) + M + 1 C'''' == (C_0 + N + 1) + M + 1 + * K'' == keystream generated from K'' == keystream generated from + * C_0 + N + 1 + M, K'. C_0 + N + 1 + M, K'. + * K' has been erased. K' has been erased. + * + * Finally, in the new design, the two consumer threads can finish the + * remainder of the generation at any time (including simultaneously): + * + * 1: GenBytes() + * 1: Keystream(stack_C, stack_K, N) + * 1: ** + * 1: <- Keystream + * 1: <- GenBytes + * 1:ExplicitBzero(stack_C, stack_K) + * + * 2: GenBytes() + * 2: Keystream(stack_C', stack_K', M) + * 2: ** + * 2: <- Keystream + * 2: <- GenBytes + * 2:ExplicitBzero(stack_C', stack_K') + * + * The generated user keystream for both threads is identical between the two + * implementations: + * + * 1: Keystream(C_0, K_0, N) 1: Keystream(stack_C, stack_K, N) + * 2: Keystream(C'', K', M) 2: Keystream(stack_C', stack_K', M) + * + * (stack_C == C_0; stack_K == K_0; stack_C' == C''; stack_K' == K'.) */ static bool fortuna_concurrent_read __read_frequently = false; @@ -203,7 +304,7 @@ random_fortuna_init_alg(void *unused __unused) SYSCTL_ADD_BOOL(&random_clist, SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO, "concurrent_read", CTLFLAG_RDTUN, - &fortuna_concurrent_read, 0, "If non-zero, enable EXPERIMENTAL " + &fortuna_concurrent_read, 0, "If non-zero, enable " "feature to improve concurrent Fortuna performance."); #endif @@ -606,13 +707,8 @@ random_fortuna_read_concurrent(uint8_t *buf, size_t bytecount, RANDOM_RESEED_LOCK(); KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0")); + /* - * Technically, we only need mutual exclusion to update shared state - * appropriately. Nothing about updating the shared internal state - * requires that we perform (most) expensive cryptographic keystream - * generation under lock. (We still need to generate 256 bits of - * keystream to re-key between consumers.) - * * Save the original counter and key values that will be used as the * PRF for this particular consumer. */