CRNG not ready and entropy used early at boot

[tlaurion]

EDIT for current state:

• This PR enables CPU HW crypto backend for both AMD and Intel and passes random.trust_cpu=1 from coreboot command line to Heads kernel boot option.
• Consequently, crng is ready prior of tpm calls and shredding operations which currently read from /dev/urandom which is not locking if not enough entropy available
• qemu depends on host's /dev/urandom through cirtio, and cannot depend on AMD cpu extension since emulated cpu is too old to offer RDRAND compatible extention.
• Next step could be to reenable TPM and JITTER as expected initially, and have rng-tools and licap-ng deployed under Heads.
• As of now the current approach of this PR is better than what was in master.
• Will try to find ways to compare both with available tools
• Still needed: see how libcrypt deals with entropy before generating key material (gnupg)

---

Older

Heads uses entropy early at boot through while CRNG initialization is not yet complete.
This is the result of explorations done, goal being to open a debate on the proper way forward.

The problem is that the CRNG is not ready when some system services need to use random numbers at boot time, such as shredding files, calling tpm binary, generating secrets, disk unlock key, and most importantly generating in-memory key material.

These operations are crucial for the security and privacy and they should not be compromised by a lack of entropy or a weak random number generator. The reason for this problem is that the kernel needs to collect at least 4096 bits of entropy before it can initialize the CRNG, and the default entropy sources are not sufficient or fast enough to provide that amount of entropy at boot time.

To solve this problem, I have explored some possible options to increase the entropy sources and reduce the crng readiness time. These options are:

• Use the kernel option random.trust_cpu=1 and pass it as a command line parameter to skip the PRNG part of the boot process and use the CPU's hardware random number generator (e.g. RDRAND for x86 CPUs) as a source of randomness, without mixing it with other entropy sources. This will reduce crng readiness time by avoiding the entropy starvation problem. However, this may not be secure or trustworthy, as there is a possibility of a backdoor in the RDRAND implementation or the XOR instruction that could compromise the quality of randomness. Some experts recommend using RDRAND only as an additional entropy source, not as the sole one.
• Use the TPM chip as another source of entropy, as it can provide high-quality randomness that is resistant to physical attacks and tampering. You can check if the TPM is recognized as a hardware random number generator (HRNG) by running cat /proc/sys/kernel/random/entropy_avail.
• Use other sources of entropy like jitter, hardware interrupts, mouse movements, keyboard presses. Linux uses a complex algorithm to combine multiple entropy sources into a single pool, and then hashes the pool to produce random output. Mixing entropy sources can improve the security and robustness of randomness, especially if some of the sources are compromised or biased.
• If we decide to trust CPU extention for crng early readiness, we could deactivate it early in Heads init script by changing the kernel parameter random.trust_cpu after the crng is ready. This way, we could use the CPU as the sole source of entropy for CRNG initialization, but switch to other sources afterwards.

To enable these options, we need to make some changes to the kernel configuration and command line parameters. These changes are:

• To enable RDRAND as an entropy source, we need to set CONFIG_ARCH_RANDOM=y in the kernel configuration, and add random.trust_cpu=1 to the kernel command line.
• To enable TPM as an entropy source, we need to set CONFIG_HW_RANDOM_TPM=y in the kernel configuration, and add rng_core.default_quality=1000 to the kernel command line.
• To enable jitterentropy as an entropy source, we need to set CONFIG_CRYPTO_JITTERENTROPY=y in the kernel configuration, and add kernel.jitterentropy.ll=10, kernel.jitterentropy.ml=10, kernel.jitterentropy.bs=64, and kernel.jitterentropy.bc=16 to the kernel command line. These parameters control how much jitter is generated by different methods.
• To enable external devices as entropy sources, you need to set CONFIG_HW_RANDOM=y in the kernel configuration.

I would like to hear your opinions and feedback on these options, and discuss which one is the best way forward for Heads.
As of today, crng is ready after tpm binary is called and after shredding some files. If one user is quick selecting menu options, the crng might not be ready when setting a TPM disk unlock key, while really improbable.

The goal here is to try to have crng ready as early as possible. Another option would be to wait for the entropy pool to full prior of leaving Heads init, but blocking is not pretty nor practical.

I propose:

• To not trust cpu extension first (requires coreboot config to pass explicitely random.trust_cpu=1 but impement all other changes and see how that goes.
• If crng is still not ready on real hardware when tpm and shredding calls happen, revisit the precedent option and modify init script to remove trust on cpu when "inside" of Heads (so aeraly tpm unseal operations and shredding of files happen on a crng that is ready.

@JonathonHall-Purism @saper others? comments?

---

Some sources:

• Intel's RDRAND and RDSEED: A Cautionary Tale: https://www.cryptologie.net/article/487/intels-rdrand-and-rdseed-a-cautionary-tale/
• Intel's RDRAND: A Backdoor?: https://www.schneier.com/blog/archives/2013/10/intels_rdrand.html
• RDRAND: The Case for Trusting CPU Hardware Random Number Generators: https://www.intel.com/content/www/us/en/developer/articles/technical/rdrand-the-case-for-trusting-cpu-hardware-random-number-generators.html

[tlaurion]

Edit: sorry. this comment was supposed to be in PR not here.

[tlaurion]

Generally, I would also prefer ed25519, but for now this is obviously not a real option, the main issue which is addressed is this one:
Most importantly, this would mean we would use ECDSA. I am not sure how reliable is random number generation under heads, it might be hard to guarantee the uniqueness of the k semi-private key. libgcrypt seems to have a "rfc6979" flag but I have no idea whether GnuPG uses it/can use it and how.

@saper @daringer I have experimented on that matter under #1476, which discussion should continue there. Some get home messages at time of writing these lines:

* This subjects is always evolving. Current HW CPU (RDRAND) was questioned a lot in the past and now the user needs to decide for itself what to trust.
  
  * CPU RDRAND is the fastests entropy feeder. Sandy/Ivy bridge being the first adding this CPU extension, it can feed at a rate of 400Mb+/s
  * TPM can be used as entropy source (with additional tooling), but generate entropy at a rate of 20bytes/second
  * Jitter can be used as a source of entropy, but rate depends of activity happening on the computer, which is basically none in our case.

* As of in master [45a4f9d](https://github.com/osresearch/heads/commit/45a4f9d0f3edc0e9fbf232402eb9e357f5a5c6e5) tpm and shred operations in code are using /dev/urandom, which is tapping into unready crng (spurs errors in dmesg)

* The kernel doesn't aggregate multiple entropy sources as of now, deferring the task to what would be iteractive changes there, including rng-tools, which depends on libcap-ng (stupid if you ask me in our use case, we do not need to have the deamon run as another user....) to aggregate tpm. jitter and cpu entropy

* By enabling and trusting CPU RDRAND, AMD/Intel/Vortio(qemu) have a ready cnrg in early init, removing errors from code tapping into /dev/urandom (unblocking), while we could tap into /dev/random (blocking) with [CRNG not ready and entropy used early at boot #1476](https://github.com/osresearch/heads/issues/1476)

* I checked what libgcrypt offers, and as of now, it is built without jitter backend.
  
  * by enabling the jitter backend, gnupg operations would use the kernel pool, but would mix it with jitter when generating in-memory keys instead of the USB Security dongle.

So TLDR:

* Trusting CPU HW RDRAND is the best option we have now to have early crng ready (calls to tpm and shred of secrets will happen with proper entropy, not being the case now)

* Generating to be inserted in LUKS slot Disk Unlock Key will take randomness in a better pool already (128bytes)

* When generating gnupg keys and subkeys in memory, reconfigured libgcrypt to include jitter will not trust RDRAND totally, but will mix jitterness in its keygen function.

@saper @daringer : opinions on that? I think the above will is going to be the state of #1478 prior of merging.

---

Quote taken from #1483 (comment)