19 ms·

Linux RNG flaws

182 points by tbodt 8y ago

dmateos 8y ago
4795 b2242bd 30230fc 9fb6ae d7 7d 69 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 5140 f a a a 5 a a a a 5 a Nice.
snissn 8y ago
Tldr?
- cryptonector 8y ago
  From TFA: > == Discarded early randomness, including device randomness == > == RNG is treated as cryptographically safe too early == > == Interaction between kernel and entropy-persisting userspace is broken == > == No entropy is fed into NUMA CRNGs between rand_initialize() initcall and crng_init==2 == > == initcall can propagate entropy into primary and NUMA CRNGs while crng_init==1 == and > == Impact == > I have spent a few days attempting to figure out how bad these issues are. > I believe that on an Intel Grass Canyon system, with RDRAND disabled, > ASLR disabled, fast boot enabled, no connected devices, with boot on power, > some frequency scaling options disabled, and the fan set to maximum, > it should be possible to express the entropy in the used RDTSC samples in around > 105 bits or less. (I'm not sure which parts of this configuration actually > influence the amount of entropy; but ASLR certainly does influence it, since the > one interrupt sample that is fed into the RNG before the RNG initialization > contains an instruction pointer.)
  - ploxiln 8y ago
    Due to some unfortunate complications of somewhat recent changes: > The worst part of this (one device entropy sample being enough to move to crng_init==1) was AFAICS introduced in commit ee7998c50c26 ("random: do not ignore early device randomness"), first in v4.14. confirmed by the fix for that bit: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/drivers/char/random.c?id=dc12baacb95f205948f64dc936a47d89ee110117 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
  - londons_explore 8y ago
    "105 bits" isn't too shabby. I'd only start to worry when it gets to say 70 bits or less. That's the kind of size a state actor could precompute ssh host keys for each of the initial random number states in a common distro for example. If a state actor could compute ssh keys in 50 milliseconds on custom hardware, and they had 100,000 machines generating those keys, they could generate enough keys to have a 1 in 1 million chance for 70 bits of entropy after 20 years.
    - loeg 8y ago
      Emphasis on "or less." Anyway, far far below expected entropy.
- lucb1e 8y ago
  Read each of the headings and see the bottom part for impact. The final update (added today) mentions the resolution.
- ethbro 8y ago
  Early system, post-boot randomness is hard. Linux wasn't handling it ideally. Consequently, things which relied on a cryptographically safe RNG were likely executing before that could be guaranteed. Sequencing was modified to better align expectations with actual system operation.
loeg 8y ago
It's worth noting that FreeBSD also had some RNG troubles quite recently (2017)[0] (talk: [1]). Personally, I don't think they were as severe as this. (But I am biased, I do FreeBSD development.) What I'm trying to say is, getting random right is hard. It's easy to produce something random-looking that isn't good enough. JMG's FreeBSD 2017 RNG talk Tl;dr: 1. Boot-time entropy might leak on either UFS or ZFS; might be re-used in a byzantine ZFS environment. (Not addressed, as far as I know.) 2. Input entropy data (pre-whitening) had only about 0.18 bits of entropy per byte of input. NIST likes to see 4-6 bits per byte. (Not really an issue due to sufficient input volume.) Partially due to: 3. All the fast, high-quality sources of random entropy were accidentally disabled(!). (All the PURE_* ones, including x86 RDRAND.) Fixed in r324394. 4. Other low entropy structures were getting mixed in. Probably harmless, but reduces entropy-per-byte measure that NIST cares about. Fixed in r324372. The earlier 2015 FreeBSD RNG issues were probably as severe as this Linux issue[2]: > URGENT: RNG broken for last 4 months > If you are running a current kernel r273872 or later, please upgrade your kernel to r278907 or later immediately and regenerate keys. > I discovered an issue where the new framework code was not calling randomdev_init_reader, which means that read_random(9) was not returning good random data. read_random(9) is used by arc4random(9) which is the primary method that arc4random(3) is seeded from. > This means most/all keys generated may be predictable and must be regenerated. This includes, but not limited to, ssh keys and keys generated by openssl. This is purely a kernel issue, and a simple kernel upgrade w/ the patch is sufficient to fix the issue. [0]: https://www.funkthat.com/~jmg/vbsdcon_2017_ddfreebsdrng_slides.pdf https://www.funkthat.com/~jmg/vbsdcon_2017_ddfreebsdrng_slid... [1]: https://www.youtube.com/watch?v=A41cDCE6pTc https://www.youtube.com/watch?v=A41cDCE6pTc [2]: https://lists.freebsd.org/pipermail/freebsd-current/2015-February/054580.html https://lists.freebsd.org/pipermail/freebsd-current/2015-Feb...
tytso 8y ago
The flaws only applied for keys generated during early boot. Jann and I looked, but we didn't find a way that this could be turned into a practical exploit, which is why we considered, but decided against, doing any kind of coordinated disclosure. The potential weakness applies before you see crng_init=2 message, and in practice on many machines this happens well before a minute --- on my laptop, in under 10 seconds. The main problem with the fix is that there are some userspace applications which assumed they could get cryptographic randomness super-early during system startup, and with a patched kernel, those userspace applications would block --- and in some cases, block the boot altogether. With no activity, there is no entropy to harness, and the boot scripts essentially deadlock waiting for the random pool to be initialized. So for some hardware, and some distributions, we're getting some boot hangs that we now need to try to workaround or fix somehow. In general, the best thing to do is not to rely on cryptographic strength random number generation during early boot. Key generation should be done lazily, and deferred for as long as possible.
- edflsafoiewq 8y ago
  What kind of applications need cryptographic randomness during early boot?
  - tinus_hn 8y ago
    The classic application is generating the ssh server keys. I don’t know if that solely uses the system RNG though.
    - AstralStorm 8y ago
      Pretty silly. If you can network, you have access to at least 3 decent sources of entropy. (Network traffic, hardware clock randomness and network device clock. Potentially power supply monitoring and bus clocks. And finally thermal sources.) And then you can always bake in the key into flash. The problem here is that you would have to probe RNG stats manually as it returned readiness too early.
champtar 8y ago
Just to be sure I understand fully, if I take a small embedded router running OpenWRT, that maybe take ~1min for the urandom pool to be ready. https://git.openwrt.org/?p=openwrt/openwrt.git;a=commitdiff;h=3946a5529132c80793a9e5ee665a3cd6b0835310;hp=e408abd7fb8e2a8842726345f393236c53496933 https://git.openwrt.org/?p=openwrt/openwrt.git;a=commitdiff;... On the first boot we save 512 bytes from getrandom(). On the second boot we restore the seed (cat seed > /dev/urandom) before almost all the user space starts. Many daemons (dropbear/openvpn) will read from /dev/urandom before urandom pool is considered ready, but after the seed is restored. With the new patches, are the daemons benefiting from the seed ?
- mkj 8y ago
  Note that Dropbear will read urandom upon each incoming connection so that should be mitigated in many circumstances. (Hopefully some systems are using the delayed hostkey generation option too)
lihes 8y ago
man urandom > When read during early boot time, /dev/urandom may return data prior to the entropy pool being initialized. I see no bugs here. Just repeating what is written in the man page.
- anon1385 8y ago
  Keep in mind that a lot of high profile security people on HN and elsewhere have spent many years now telling everybody that the linux urandom man page is wrong, so don't be surprised when people ignore it. https://hn.algolia.com/?query=urandom%20manpage&sort=byPopularity&prefix&page=0&dateRange=all&type=comment https://hn.algolia.com/?query=urandom%20manpage&sort=byPopul...
- jwilk 8y ago
  Please don't post shallow dismissals. None of the reported bugs are about /dev/urandom returning data too early.
- oconnor663 8y ago
  If you continue to the next sentence in that man page: > If this is of concern in your application, use getrandom(2) or /dev/random instead. These bugs affect getrandom too.
  - lihes 8y ago
    Where is it written? Could you pin point it? I see urandom everywhere.
    - oconnor663 8y ago
      I got it from this part, unless I'm misreading: > Multiple callers, including sys_getrandom(..., flags=0), attempt to wait for the > RNG to become cryptographically safe before reading from it by checking for > crng_ready() and waiting if necessary. However, crng_ready() only checks for > `crng_init > 0`, and `crng_init==1` does not imply that the RNG is > cryptographically safe.
jlgaddis 8y ago
On RHEL 7 (and derivatives), by default, SSH keys are generated on first boot and with entropy acquired from /dev/urandom. It is possible, however, to force it sshd-keygen, sshd, et al., to use /dev/random instead (by setting "SSH_USE_STRONG_RNG" in /etc/sysconfig/sshd to a value >= 14). In this case, would keys still potentially be at risk? --- For a while now, I've been generating my SSH host keys at the end of the kickstart installation process (for physical hosts) with SSH_USE_STRONG_RNG=32 (in a "%post" script). Virtual guests (KVM) still generate theirs on first boot, but they have the benefit of access to the host's /dev/random and also get a random seed "injected" into their disk image just before first boot -- although I'm not sure if that helps with this issue.
nikic 8y ago
Seeing that `i % len` in https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/drivers/char/random.c?id=dc12baacb95f205948f64dc936a47d89ee110117 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... makes me uncomfortable. This is performing a non-constant modulus on every loop iteration, which seems quite excessive even for a slow path. Performing wraparounds using a separate branch would be more efficient.
- loeg 8y ago
  The amount of data this is used for is vanishingly small. Of course it could be eliminated entirely by copying shorter inputs to a local CHACHA20_KEY_SIZE stack buffer first, but why bother? Typical input size is on the order of 5. Additionally, CHACHA20_KEY_SIZE is a power of 2 and optimizing compilers like GCC will convert the modulus into a binary-AND.
- jlgaddis 8y ago
  You should submit a patch.
John_KZ 8y ago
Wasn't there a popular article with the author vehemently supporting the use of /dev/urandom because of it's nonblocking characteristics? I vividly remember it. Also I think it's common knowledge that there's little entropy available during startup but developers have no control over it regardless. I didn't know it was that bad though. That's really bad.

182 points by tbodt 8y ago

4795 b2242bd 30230fc 9fb6ae d7 7d 69 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 5140 f a a a 5 a a a a 5 a Nice.

snissn 8y ago

Tldr?

cryptonector 8y ago
From TFA: > == Discarded early randomness, including device randomness == > == RNG is treated as cryptographically safe too early == > == Interaction between kernel and entropy-persisting userspace is broken == > == No entropy is fed into NUMA CRNGs between rand_initialize() initcall and crng_init==2 == > == initcall can propagate entropy into primary and NUMA CRNGs while crng_init==1 == and > == Impact == > I have spent a few days attempting to figure out how bad these issues are. > I believe that on an Intel Grass Canyon system, with RDRAND disabled, > ASLR disabled, fast boot enabled, no connected devices, with boot on power, > some frequency scaling options disabled, and the fan set to maximum, > it should be possible to express the entropy in the used RDTSC samples in around > 105 bits or less. (I'm not sure which parts of this configuration actually > influence the amount of entropy; but ASLR certainly does influence it, since the > one interrupt sample that is fed into the RNG before the RNG initialization > contains an instruction pointer.)
- ploxiln 8y ago
  Due to some unfortunate complications of somewhat recent changes: > The worst part of this (one device entropy sample being enough to move to crng_init==1) was AFAICS introduced in commit ee7998c50c26 ("random: do not ignore early device randomness"), first in v4.14. confirmed by the fix for that bit: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/drivers/char/random.c?id=dc12baacb95f205948f64dc936a47d89ee110117 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
- londons_explore 8y ago
  "105 bits" isn't too shabby. I'd only start to worry when it gets to say 70 bits or less. That's the kind of size a state actor could precompute ssh host keys for each of the initial random number states in a common distro for example. If a state actor could compute ssh keys in 50 milliseconds on custom hardware, and they had 100,000 machines generating those keys, they could generate enough keys to have a 1 in 1 million chance for 70 bits of entropy after 20 years.
  - loeg 8y ago
    Emphasis on "or less." Anyway, far far below expected entropy.
lucb1e 8y ago
Read each of the headings and see the bottom part for impact. The final update (added today) mentions the resolution.
ethbro 8y ago
Early system, post-boot randomness is hard. Linux wasn't handling it ideally. Consequently, things which relied on a cryptographically safe RNG were likely executing before that could be guaranteed. Sequencing was modified to better align expectations with actual system operation.

loeg 8y ago

It's worth noting that FreeBSD also had some RNG troubles quite recently (2017)[0] (talk: [1]). Personally, I don't think they were as severe as this. (But I am biased, I do FreeBSD development.) What I'm trying to say is, getting random right is hard. It's easy to produce something random-looking that isn't good enough. JMG's FreeBSD 2017 RNG talk Tl;dr: 1. Boot-time entropy might leak on either UFS or ZFS; might be re-used in a byzantine ZFS environment. (Not addressed, as far as I know.) 2. Input entropy data (pre-whitening) had only about 0.18 bits of entropy per byte of input. NIST likes to see 4-6 bits per byte. (Not really an issue due to sufficient input volume.) Partially due to: 3. All the fast, high-quality sources of random entropy were accidentally disabled(!). (All the PURE_* ones, including x86 RDRAND.) Fixed in r324394. 4. Other low entropy structures were getting mixed in. Probably harmless, but reduces entropy-per-byte measure that NIST cares about. Fixed in r324372. The earlier 2015 FreeBSD RNG issues were probably as severe as this Linux issue[2]: > URGENT: RNG broken for last 4 months > If you are running a current kernel r273872 or later, please upgrade your kernel to r278907 or later immediately and regenerate keys. > I discovered an issue where the new framework code was not calling randomdev_init_reader, which means that read_random(9) was not returning good random data. read_random(9) is used by arc4random(9) which is the primary method that arc4random(3) is seeded from. > This means most/all keys generated may be predictable and must be regenerated. This includes, but not limited to, ssh keys and keys generated by openssl. This is purely a kernel issue, and a simple kernel upgrade w/ the patch is sufficient to fix the issue. [0]: https://www.funkthat.com/~jmg/vbsdcon_2017_ddfreebsdrng_slides.pdf https://www.funkthat.com/~jmg/vbsdcon_2017_ddfreebsdrng_slid... [1]: https://www.youtube.com/watch?v=A41cDCE6pTc https://www.youtube.com/watch?v=A41cDCE6pTc [2]: https://lists.freebsd.org/pipermail/freebsd-current/2015-February/054580.html https://lists.freebsd.org/pipermail/freebsd-current/2015-Feb...

tytso 8y ago

The flaws only applied for keys generated during early boot. Jann and I looked, but we didn't find a way that this could be turned into a practical exploit, which is why we considered, but decided against, doing any kind of coordinated disclosure. The potential weakness applies before you see crng_init=2 message, and in practice on many machines this happens well before a minute --- on my laptop, in under 10 seconds. The main problem with the fix is that there are some userspace applications which assumed they could get cryptographic randomness super-early during system startup, and with a patched kernel, those userspace applications would block --- and in some cases, block the boot altogether. With no activity, there is no entropy to harness, and the boot scripts essentially deadlock waiting for the random pool to be initialized. So for some hardware, and some distributions, we're getting some boot hangs that we now need to try to workaround or fix somehow. In general, the best thing to do is not to rely on cryptographic strength random number generation during early boot. Key generation should be done lazily, and deferred for as long as possible.

edflsafoiewq 8y ago
What kind of applications need cryptographic randomness during early boot?
- tinus_hn 8y ago
  The classic application is generating the ssh server keys. I don’t know if that solely uses the system RNG though.
  - AstralStorm 8y ago
    Pretty silly. If you can network, you have access to at least 3 decent sources of entropy. (Network traffic, hardware clock randomness and network device clock. Potentially power supply monitoring and bus clocks. And finally thermal sources.) And then you can always bake in the key into flash. The problem here is that you would have to probe RNG stats manually as it returned readiness too early.

champtar 8y ago

Just to be sure I understand fully, if I take a small embedded router running OpenWRT, that maybe take ~1min for the urandom pool to be ready. https://git.openwrt.org/?p=openwrt/openwrt.git;a=commitdiff;h=3946a5529132c80793a9e5ee665a3cd6b0835310;hp=e408abd7fb8e2a8842726345f393236c53496933 https://git.openwrt.org/?p=openwrt/openwrt.git;a=commitdiff;... On the first boot we save 512 bytes from getrandom(). On the second boot we restore the seed (cat seed > /dev/urandom) before almost all the user space starts. Many daemons (dropbear/openvpn) will read from /dev/urandom before urandom pool is considered ready, but after the seed is restored. With the new patches, are the daemons benefiting from the seed ?

mkj 8y ago
Note that Dropbear will read urandom upon each incoming connection so that should be mitigated in many circumstances. (Hopefully some systems are using the delayed hostkey generation option too)

lihes 8y ago

man urandom > When read during early boot time, /dev/urandom may return data prior to the entropy pool being initialized. I see no bugs here. Just repeating what is written in the man page.

anon1385 8y ago
Keep in mind that a lot of high profile security people on HN and elsewhere have spent many years now telling everybody that the linux urandom man page is wrong, so don't be surprised when people ignore it. https://hn.algolia.com/?query=urandom%20manpage&sort=byPopularity&prefix&page=0&dateRange=all&type=comment https://hn.algolia.com/?query=urandom%20manpage&sort=byPopul...
jwilk 8y ago
Please don't post shallow dismissals. None of the reported bugs are about /dev/urandom returning data too early.
oconnor663 8y ago
If you continue to the next sentence in that man page: > If this is of concern in your application, use getrandom(2) or /dev/random instead. These bugs affect getrandom too.
- lihes 8y ago
  Where is it written? Could you pin point it? I see urandom everywhere.
  - oconnor663 8y ago
    I got it from this part, unless I'm misreading: > Multiple callers, including sys_getrandom(..., flags=0), attempt to wait for the > RNG to become cryptographically safe before reading from it by checking for > crng_ready() and waiting if necessary. However, crng_ready() only checks for > `crng_init > 0`, and `crng_init==1` does not imply that the RNG is > cryptographically safe.

jlgaddis 8y ago

On RHEL 7 (and derivatives), by default, SSH keys are generated on first boot and with entropy acquired from /dev/urandom. It is possible, however, to force it sshd-keygen, sshd, et al., to use /dev/random instead (by setting "SSH_USE_STRONG_RNG" in /etc/sysconfig/sshd to a value >= 14). In this case, would keys still potentially be at risk? --- For a while now, I've been generating my SSH host keys at the end of the kickstart installation process (for physical hosts) with SSH_USE_STRONG_RNG=32 (in a "%post" script). Virtual guests (KVM) still generate theirs on first boot, but they have the benefit of access to the host's /dev/random and also get a random seed "injected" into their disk image just before first boot -- although I'm not sure if that helps with this issue.

nikic 8y ago

Seeing that `i % len` in https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/drivers/char/random.c?id=dc12baacb95f205948f64dc936a47d89ee110117 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... makes me uncomfortable. This is performing a non-constant modulus on every loop iteration, which seems quite excessive even for a slow path. Performing wraparounds using a separate branch would be more efficient.

loeg 8y ago
The amount of data this is used for is vanishingly small. Of course it could be eliminated entirely by copying shorter inputs to a local CHACHA20_KEY_SIZE stack buffer first, but why bother? Typical input size is on the order of 5. Additionally, CHACHA20_KEY_SIZE is a power of 2 and optimizing compilers like GCC will convert the modulus into a binary-AND.
jlgaddis 8y ago
You should submit a patch.

John_KZ 8y ago

Wasn't there a popular article with the author vehemently supporting the use of /dev/urandom because of it's nonblocking characteristics? I vividly remember it. Also I think it's common knowledge that there's little entropy available during startup but developers have no control over it regardless. I didn't know it was that bad though. That's really bad.