[U-Boot] [PATCH 4/4] lib: uuid: Improve randomness of uuid values on RANDOM_UUID=y

[Eugeniu Rosca]

Hi Heinrich,

Thank you for reviewing this series.

On Tue, Apr 30, 2019 at 09:07:09PM +0200, Heinrich Schuchardt wrote:
[..]
> This patch may ameliorate the situation for GUIDs a bit. But I dislike:

In general, we can find reasons to dislike anything, since there is room
for improvement in virtually anything.

> 
> - This patch is a uuid only solution to introduce time ticks as source
>   of entropy.

I would like to clarify once again what this patch is about. It _fixes_
(hence I will rewrite the summary line in the next patch revision) a
concrete real-life problem of providing repeatable (not predictable -
which implies some effort in my mind - but literally repeatable) uuid
values on enabling CONFIG_RANDOM_UUID.

It is my understanding that CONFIG_RANDOM_UUID (based on its name
and help message) does promise random uuids to the user. If so, then
U-Boot simply breaks this promise.

While doing additional research on PRNG, it looks to me that there is
an established class of PRNG-specific problems, commonly known as
"unseeded randomness" for which I am also able to find below CVE/CWE:
 - https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2015-0285
   ("CVE-2015-0285 openssl: handshake with unseeded PRNG")
 - https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2015-9019
   ("CVE-2015-9019 libxslt: math.random() in xslt uses unseeded randomness")
 - https://cwe.mitre.org/data/definitions/336.html
   ("CWE-336: Same Seed in Pseudo-Random Number Generator (PRNG)")

The above tells me that using the same seed yields the same sequence
of random numbers. That's precisely the topic of this patch: simply
switching from unseeded PRNG to seeded PRNG.

And yes, this patch is deliberately limited to UUID naming function,
since it is lib/uuid's responsibility to seed the PRNG. The same is
true for other callers of rand() and rand_r(). All of them seed the
PRNG prior to getting a random value from it.

> - With timer ticks you possibly introduce very little entropy.

Theoretically, yes. Practically, the improvement to the current state
of affairs is huge and this has been testified by the test results
linked in the description. 

Again, this patch is not about improving the random pattern of the UUID
values (sorry for the misleading title). It is really about _enabling_
any kind of randomness in those values at all.

> - Our random number generator with only 32 state bits remains
>   sub-standard.

I believe this is orthogonal to my patch and can be improved
independently. In addition, whatever is the bit-width of U-Boot PRNG
(I can find shootouts between various 64/128/256-bit PRNG) its essence
will not change. It will remain a deterministic number generator,
whose randomness will still be dictated by the seed.

> 
> This is the current situation:
> 
> net/bootp.c uses the MAC address to seed the random number generator and
> uses random numbers for defining waits.
> 
> lib/uuid.c is using it for UUID generation.

I can see that rfc4122 suggests including MAC address in the UUID, but
it also warns that MAC address could be unavailable:

 -----------
   For systems with no IEEE address, a randomly or pseudo-randomly
   generated value may be used;
 -----------

The guess is right. Some SoCs like R-Car3 (in contrast to e.g. i.MX6)
don't provide any OTP memory/register containing their unique MAC
address. Needless to say some machines would never connect to IEEE
network. So, it looks to me that MAC address cannot be taken as
consistent source of entropy for UUID in U-Boot.

> 
> In the UEFI sub-system I would like to implement the EFI_RNG_PROTOCOL.
> Linux uses it for randomizing memory layout. iPXE needs it for secure
> network connections. This requires a good random number generator with
> sufficient entropy.
> 
> We already have implemented a single hardware random number generator in
> drivers/crypto/ace_sha.c (CONFIG_EXYNOS_ACE_SHA).
> 
> Many other CPUs come with a hardware random number generator. In Linux's
> drivers/char/hw_random/ I found, e.g.
> 
> - meson-rng.c (Amlogic)
> - mtk-rng.c (MediaTek)
> - st-rng.c (STMicroelectronics)
> - imx-rng.c (Freescale)

To the best of my knowledge, there is no HW RNG on R-Car3, so our only
option is currently U-Boot PRNG.

> 
> I think we should have a u-class for hardware RNGs as one source of entropy.
> 
> I would like a random number generator with a high number of state bits
> (> 127) that we initialize with hardware RNG bits and other sources of
> entropy. A nice discussion of how Linux does it can be found in [1].

All sound like future topics to me, orthogonal to this patch.
Let me know if I misunderstood anything. TIA!

> 
> Best regards
> 
> Heinrich
> 
> [1]
> https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN.pdf
> 

--
Best Regards,
Eugeniu.