All of lore.kernel.org
 help / color / mirror / Atom feed
From: Nathan Chancellor <nathan@kernel.org>
To: "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc: linux-kernel@vger.kernel.org, linux-crypto@vger.kernel.org,
	llvm@lists.linux.dev
Subject: Re: [PATCH v3] random: use first 128 bits of input as fast init
Date: Wed, 4 May 2022 15:13:54 -0700	[thread overview]
Message-ID: <YnL6ouh5xxZIJqeN@dev-arch.thelio-3990X> (raw)
In-Reply-To: <20220504111644.284927-1-Jason@zx2c4.com>

Hi Jason,

On Wed, May 04, 2022 at 01:16:44PM +0200, Jason A. Donenfeld wrote:
> Before, the first 64 bytes of input, regardless of how entropic it was,
> would be used to mutate the crng base key directly, and none of those
> bytes would be credited as having entropy. Then 256 bits of credited
> input would be accumulated, and only then would the rng transition from
> the earlier "fast init" phase into being actually initialized.
> 
> The thinking was that by mixing and matching fast init and real init, an
> attacker who compromised the fast init state, considered easy to do
> given how little entropy might be in those first 64 bytes, would then be
> able to bruteforce bits from the actual initialization. By keeping these
> separate, bruteforcing became impossible.
> 
> However, by not crediting potentially creditable bits from those first 64
> bytes of input, we delay initialization, and actually make the problem
> worse, because it means the user is drawing worse random numbers for a
> longer period of time.
> 
> Instead, we can take the first 128 bits as fast init, and allow them to
> be credited, and then hold off on the next 128 bits until they've
> accumulated. This is still a wide enough margin to prevent bruteforcing
> the rng state, while still initializing much faster.
> 
> Then, rather than trying to piecemeal inject into the base crng key at
> various points, instead just extract from the pool when we need it, for
> the crng_init==0 phase. Performance may even be better for the various
> inputs here, since there are likely more calls to mix_pool_bytes() then
> there are to get_random_bytes() during this phase of system execution.
> 
> Since the preinit injection code is gone, bootloader randomness can then
> do something significantly more straight forward, removing the weird
> system_wq hack in hwgenerator randomness.
> 
> Cc: Theodore Ts'o <tytso@mit.edu>
> Cc: Dominik Brodowski <linux@dominikbrodowski.net>
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

Apologies if this has already been reported or noticed, I did not see
anything on lore.kernel.org.

I bisected a QEMU boot failure with ARCH=arm aspeed_g5_defconfig to this
change in -next, initially noticed by our continuous integration:

https://github.com/ClangBuiltLinux/continuous-integration2/runs/6292038704?check_suite_focus=true

# bad: [bb6ee10133faa3c4742ab8343b5e488cdb29445e] Add linux-next specific files for 20220504
# good: [ef8e4d3c2ab1f47f63b6c7e578266b7e5cc9cd1b] Merge tag 'hwmon-for-v5.18-rc6' of git://git.kernel.org/pub/scm/linux/kernel/git/groeck/linux-staging
git bisect start 'bb6ee10133faa3c4742ab8343b5e488cdb29445e' 'ef8e4d3c2ab1f47f63b6c7e578266b7e5cc9cd1b'
# good: [fc346f9c7d4404797b1e22e70b10367cfcb65973] Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git
git bisect good fc346f9c7d4404797b1e22e70b10367cfcb65973
# good: [31ae19714d8019a433c632c8bbc55a8ed51b4dc0] Merge branch 'timers/drivers/next' of git://git.linaro.org/people/daniel.lezcano/linux.git
git bisect good 31ae19714d8019a433c632c8bbc55a8ed51b4dc0
# good: [0a1f00e86626c074bd8b0b4fc4e425ed2cdf182e] Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/vkoul/dmaengine.git
git bisect good 0a1f00e86626c074bd8b0b4fc4e425ed2cdf182e
# bad: [64208983cb783cf86d310b713dca86cc48a92e21] Merge branch 'rust-next' of https://github.com/Rust-for-Linux/linux.git
git bisect bad 64208983cb783cf86d310b713dca86cc48a92e21
# good: [c5fab14b25743e24900bbc46c1d674ae085556a3] Merge branch 'renesas-pinctrl' of git://git.kernel.org/pub/scm/linux/kernel/git/geert/renesas-drivers.git
git bisect good c5fab14b25743e24900bbc46c1d674ae085556a3
# good: [6657c54d345821bec0ababf5566117074e9365e8] Merge branch 'hyperv-next' of git://git.kernel.org/pub/scm/linux/kernel/git/hyperv/linux.git
git bisect good 6657c54d345821bec0ababf5566117074e9365e8
# good: [49ff8dd832746466d8ee736fd2ac17468d96c2c8] Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/cxl/cxl.git
git bisect good 49ff8dd832746466d8ee736fd2ac17468d96c2c8
# good: [0c0f471ec568bb005ea8ca2660df03841f63b30d] Merge branch 'for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/vbabka/slab.git
git bisect good 0c0f471ec568bb005ea8ca2660df03841f63b30d
# bad: [fee7def4f22dadc01fbb89fc5bf69986b4f7d7a7] Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git
git bisect bad fee7def4f22dadc01fbb89fc5bf69986b4f7d7a7
# good: [675ba39e73c5cd58fca0a7efc39c22efc557aadd] nios2: use fallback for random_get_entropy() instead of zero
git bisect good 675ba39e73c5cd58fca0a7efc39c22efc557aadd
# good: [2334ae282252f27ccd44a65be6e36d251936175f] random: vary jitter iterations based on cycle counter speed
git bisect good 2334ae282252f27ccd44a65be6e36d251936175f
# bad: [fbc14042a7fa7820dd7ffdd27d97064edd09d2ea] random: use first 128 bits of input as fast init
git bisect bad fbc14042a7fa7820dd7ffdd27d97064edd09d2ea
# good: [99e2ecc9855eab30603275aeaa34ac7a7ff919b2] random: do not use batches when !crng_ready()
git bisect good 99e2ecc9855eab30603275aeaa34ac7a7ff919b2
# first bad commit: [fbc14042a7fa7820dd7ffdd27d97064edd09d2ea] random: use first 128 bits of input as fast init

It can be reproduced with:

$ make -skj"$(nproc)" ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- mrproper aspeed_g5_defconfig all

$ qemu-system-arm \
-initrd ... \
-machine romulus-bmc \
-no-reboot \
-dtb arch/arm/boot/dts/aspeed-bmc-opp-romulus.dtb \
-display none \
-kernel arch/arm/boot/zImage \
-m 512m \
-nodefaults \
-serial mon:stdio
...
[    0.000000] random: get_random_u32 called from __kmem_cache_create+0x24/0x46c with crng_init=0
[    0.000000] 8<--- cut here ---
[    0.000000] Unable to handle kernel NULL pointer dereference at virtual address 00000000
[    0.000000] [00000000] *pgd=00000000
[    0.000000] Internal error: Oops: 5 [#1] SMP ARM
[    0.000000] CPU: 0 PID: 0 Comm: swapper Not tainted 5.18.0-rc5-00021-gfbc14042a7fa #1
[    0.000000] Hardware name: Generic DT based system
[    0.000000] PC is at random_get_entropy_fallback+0x14/0x24
[    0.000000] LR is at extract_entropy.constprop.0+0x4c/0x1bc
[    0.000000] pc : [<8019ea0c>]    lr : [<8055f620>]    psr: a00001d3
[    0.000000] sp : 80e01db8  ip : 00000000  fp : 00000000
[    0.000000] r10: 80e0bb80  r9 : 80eeec94  r8 : 80e01f20
[    0.000000] r7 : 80e01e84  r6 : 80e01dd0  r5 : 80e01df0  r4 : 80e01dd0
[    0.000000] r3 : 80ede0c0  r2 : 80eeec94  r1 : 00000000  r0 : 00000000
[    0.000000] Flags: NzCv  IRQs off  FIQs off  Mode SVC_32  ISA ARM  Segment none
[    0.000000] Control: 00c5387d  Table: 80004008  DAC: 00000051
[    0.000000] Register r0 information: NULL pointer
[    0.000000] Register r1 information: NULL pointer
[    0.000000] Register r2 information: non-slab/vmalloc memory
[    0.000000] Register r3 information: non-slab/vmalloc memory
[    0.000000] Register r4 information: non-slab/vmalloc memory
[    0.000000] Register r5 information: non-slab/vmalloc memory
[    0.000000] Register r6 information: non-slab/vmalloc memory
[    0.000000] Register r7 information: non-slab/vmalloc memory
[    0.000000] Register r8 information: non-slab/vmalloc memory
[    0.000000] Register r9 information: non-slab/vmalloc memory
[    0.000000] Register r10 information: non-slab/vmalloc memory
[    0.000000] Register r11 information: NULL pointer
[    0.000000] Register r12 information: NULL pointer
[    0.000000] Process swapper (pid: 0, stack limit = 0x(ptrval))
[    0.000000] Stack: (0x80e01db8 to 0x80e02000)
[    0.000000] 1da0:                                                       80e01dd0 8055f620
[    0.000000] 1dc0: 80a98ac8 80eeec6c ffffff10 ffff0a01 80e01e68 80ece060 00000056 80e0bb80
[    0.000000] 1de0: 3ffff822 ffffff00 ffff0a01 00000000 80e0bb80 00000056 00000000 00000000
[    0.000000] 1e00: 80ece060 80e0bb80 00000000 80e138d8 80ece060 00000052 80172a4c 80173748
[    0.000000] 1e20: 80e01e74 80173748 00000052 9e9cd435 00000000 00000000 80b711d4 00000004
[    0.000000] 1e40: 800001d3 80eeec64 80e01e84 80e01f20 80eeec94 80b1d474 00000000 8055fc3c
[    0.000000] 1e60: 00000004 80e01f24 80e01e84 00000004 80e0bb80 80d3e0b4 80b1d474 8055fca0
[    0.000000] 1e80: 0000005c 61723501 006f646e 00000000 00000000 00000000 80e05d60 fffffffe
[    0.000000] 1ea0: 00000000 80b711d4 00000000 80b1d474 00000000 8017141c 80e01f14 00000000
[    0.000000] 1ec0: 00000000 00000000 00000000 80e0bb80 801ac33c 801fec4c 00000052 801fecbc
[    0.000000] 1ee0: 00000052 8016e834 00000052 80171c78 80e01f14 808e4360 80e0bb80 808f4438
[    0.000000] 1f00: 80e01f14 00000000 80d3e024 80eeec64 80e0bb80 80ee2914 80e57bf8 80560e44
[    0.000000] 1f20: 80d3e024 00000000 80ee2914 80d3e024 80d3e024 80b3e538 80ee2914 802bfa98
[    0.000000] 1f40: 00000010 00000020 80d3e024 80b3e538 80ee2914 80e57bf8 80d3e0b4 80b1d474
[    0.000000] 1f60: 00000000 80d13370 00000000 80ee7e38 80d3e024 80d16578 00000000 00000000
[    0.000000] 1f80: 00000000 80ec9000 80ec9000 80ec9000 9edffa00 00c0387d 80e05cc0 ffffffff
[    0.000000] 1fa0: 00000000 80d0115c ffffffff ffffffff 00000000 80d00768 00000000 80e0bb80
[    0.000000] 1fc0: 00000000 80d39a5c 00000000 00000000 00000000 80d004bc 00000051 00c0387d
[    0.000000] 1fe0: ffffffff 88392000 410fb767 00c5387d 00000000 00000000 00000000 00000000
[    0.000000]  random_get_entropy_fallback from extract_entropy.constprop.0+0x4c/0x1bc
[    0.000000]  extract_entropy.constprop.0 from crng_make_state+0x184/0x1a4
[    0.000000]  crng_make_state from _get_random_bytes.part.0+0x44/0xe8
[    0.000000]  _get_random_bytes.part.0 from get_random_u32+0xc8/0xe0
[    0.000000]  get_random_u32 from __kmem_cache_create+0x24/0x46c
[    0.000000]  __kmem_cache_create from create_boot_cache+0x94/0xbc
[    0.000000]  create_boot_cache from kmem_cache_init+0x68/0x178
[    0.000000]  kmem_cache_init from start_kernel+0x3b0/0x69c
[    0.000000]  start_kernel from 0x0
[    0.000000] Code: e52de004 ebfdbebb e59f300c e5930148 (e5903000)
[    0.000000] ---[ end trace 0000000000000000 ]---
...

Cheers,
Nathan

  reply	other threads:[~2022-05-04 22:13 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-04-30 13:24 [PATCH] random: use first 128 bits of input as fast init Jason A. Donenfeld
2022-05-03 13:12 ` [PATCH v2] " Jason A. Donenfeld
2022-05-04 11:16   ` [PATCH v3] " Jason A. Donenfeld
2022-05-04 22:13     ` Nathan Chancellor [this message]
2022-05-05  0:34       ` Jason A. Donenfeld
2022-05-13  6:22     ` Dominik Brodowski
2022-05-13 10:17       ` Jason A. Donenfeld

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=YnL6ouh5xxZIJqeN@dev-arch.thelio-3990X \
    --to=nathan@kernel.org \
    --cc=Jason@zx2c4.com \
    --cc=linux-crypto@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=llvm@lists.linux.dev \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.