3
$\begingroup$

(Moved from StackOverflow)

In the Usage documentation for libsodium, before calling the initialization function sodium_init, they suggest you check the entropy count of the system's CSPRNG (i.e. use ioctl to query RNDGETENTCNT). That makes sense. In the example code, they check that the entropy is at least 160.

What's special about the 160 value?

The Linux CSPRNG now uses ChaCha20, right? But I would think that would require more than 160 bits of randomness to be initialized (e.g. it looks like the getrandom syscall in more-recent kernels blocks until it gets randomness of at least twice the ChaCha20 keylength, which would be 512 bits).

$\endgroup$

2 Answers 2

0
$\begingroup$

[Update: See Frank Denis's answer for the real reason from the author of the software, which has to do with whether or not sodium_init will block, not the security of the system. I retain the answer below for discussion of security analysis relevant to the number 160.]

The standard way to wait until the system entropy pool is seeded is to read a single byte from /dev/random. This works in Linux and has worked for decades on just about every operating system and doesn't require fancy Linux-specific ioctls—and if you want your application to be able to handle waiting at boot-time, it makes sure that you are actually testing the blocking code path because /dev/random can block at any time and doesn't restrict itself to blocking once at boot when you're probably not testing your code until you deploy it into the field.

At best, this RNDGETENTCNT test is useful to discriminate between a completely broken environment, like a VM with no entropy source hooked up from the host (e.g., virtio-rng), and a not completely broken environment.

  • If you have a real entropy source or a boot-time seed derived from one, the entropy should be at least 256 bits immediately at boot.
  • If you have nothing at all on a virtualized system without many interrupts happening and without any disk I/O and so on, the entropy will probably be pretty close to 0. In this case you can raise an alarm.

It won't help you to discriminate between a secure environment and an insecure environment.

  • If you have some interrupts happening and some typing happening but no serious RNG or seed, the bogus entropy estimator will give you some bogus number that may be above or below 160 bits. Maybe the system is in an unpredictable state; maybe it's not. The system can't tell the difference between interrupt timing of a human typing unpredictably and interrupt timing of a carefully timed onslaught of network packets to fool the entropy estimator.

It is up to you to arrange the system engineering for security: e.g., make sure you have a hardware RNG, or make sure your VM is hooked up to the host's hardware RNG, or make sure you seed your pool with 512 fair coin tosses with no cameras pointed at you. (Why 512? Maybe your coin tosses aren't uniform, but close to it.

So what's the number 160? I don't know, and from the above reasoning I think it doesn't really mean much, but here's my guess. Suppose you aim for a ‘128-bit security level’. The naive interpretation is that this requires the adversary's state of knowledge about your system to have 128 bits of entropy, or close to it.

If you take the bogus entropy estimator at face value, then 160 bits is 128 plus a conservative slop: had we used 128 bits of input, and hashed it to 128 bits of output, there would be only about $2^{128} (1 - e^{-1}) \approx 2^{127.34}$ expected possible outcomes, losing nearly a bit of entropy. NIST recommends that the factor below $2^{128}$ be no less than $1 - 2^{-64}$ in SP800-90C. Hashing 160 bits of input to 128 bits of output, in contrast, gives about $2^{128} (1 - e^{-2^{32}})$ expected possible outcomes. ($e^{-2^{32}}$ is essentially zero even in comparison to $2^{-64}$.)

However, that's only a naive interpretation of a ‘128-bit security level’. The entropy is really a proxy for the cost of a successful attack. The naive interpretation is that when there are $2^{128}$ equiprobable possibilities which the adversary must try by brute force, the expected cost is $2^{127}$ trials, which is more than any adversary can try. But in practice, an adversary is interested in attacking one of many users: compromise one user in a network, and you probably have a foothold from which to compromise other users in the network.

For a generic preimage search for the first of $t$ targets among $n$ possibilities, like finding one AES key used by any of $t$ users, the expected cost is $O(n/t)$. For a generic discrete log search like finding an X25519 key among $n$ possibilities, it's different: $O(\sqrt n)$ for the first of $t$ users, $O(\sqrt{n t})$ for all of $t$ users. This is why if X25519 has a 128-bit security level then AES-128 has a much less than 128-bit security level.

To make sure the cost of recovering secret keys is near $2^{128}$ even if you have as many users as there are humans on the planet today, you can make sure there are $2^{160}$ possibilities the adversary must consider. Personally I consider this number to be a little uncomfortably conservative—it is not hard to imagine an application with more keys than humans on the planet—and prefer to aim for 256 bits of entropy in the pool by, e.g., hashing 512 mostly fair coin tosses into it.


P.S. RNDGETENTCNT itself is a bit silly: it serves as a side channel for the raw data going into the entropy pool, because increments to it are computed by the kernel's entropy estimator from the raw data. This may even serve as a side channel for, e.g., duration between keystrokes of an operator typing. That's not a problem you can address in your application, of course, except by refusing to expose the output of RNDGETENTCNT from your application.

$\endgroup$
7
  • 1
    $\begingroup$ With security is $O(\sqrt{n/t})$ for $t$ users, for a 256-bit ECC curve with $n=2^{256}$, a seed of $128+b$ bits is good to $t=2^{2b}$ users, isn't it? I'm not seeing an application with $>2^{60}$ public keys in the forthcoming decade. $\endgroup$
    – fgrieu
    Jul 18, 2018 at 10:13
  • $\begingroup$ Regarding the advice to wait for sufficient entropy by simply reading from /dev/random: doesn't that result in waiting for less entropy? Reads from /dev/random block until the entropy estimate is >= read_wakeup_threshold, which defaults to 64 bits. $\endgroup$ Jul 18, 2018 at 13:58
  • $\begingroup$ I wonder if your point about entropy > 160 serving only to discriminate a completely-broken system from an at-least-not-completely-broken one is the real reason for the libsodium documentation's advice to perform this check. $\endgroup$ Jul 18, 2018 at 14:00
  • $\begingroup$ Regarding the PS, you can already detect keystrokes in userspace with a accurate timer, or even by abusing /dev/ptmx as a side-channel. I believe the kernel uses a push_to_pool workqueue which is called periodically and not the instant more randomness is injected. You thus only get to tell when input pool data spills over to the blocking pool. So I don't think this ioctl is a side-channel risk. $\endgroup$
    – forest
    Jul 21, 2018 at 1:57
  • 1
    $\begingroup$ @fgrieu For a generic preimage search on the function $s \mapsto \operatorname{X25519}([H(s)]x^{-1}(9))$, the cost is $O(n/t)$. For that cost to be about $2^{128}$ with a 256-bit curve, or in general to meet the cost of a generic discrete log computation, you need a seed of $b$ bits for $t = 2^b$ users. $\endgroup$ Feb 18, 2019 at 22:15
4
$\begingroup$

The internal RNG uses a 256 bit seed, and on Linux, a byte is read from /dev/random to check that the pool is seeded.

The reason for requiring 160 bits to be available without blocking is unrelated.

During initialisation, the library reads and discards 32 bits from the RNG to check that it is available and working.

Shortly after, it will need 128 extra bits for the canary protecting guarded memory allocations.

Hence, if 160 bits are not immediately available, sodium_init() will block. This will happen even if the application doesn't need to generate any keys.

$\endgroup$
3
  • $\begingroup$ Good answer, sounds logical... can you add a supporting reference to illustrate it is more than supposition? $\endgroup$
    – rmalayter
    Feb 19, 2019 at 3:03
  • 1
    $\begingroup$ @rmalayter I wrote that code. $\endgroup$ Feb 19, 2019 at 7:16
  • $\begingroup$ I supposed that was the case... indicating the authority of your statements in the answer somehow would be helpful. It’s not bragging, and the whole point of SO sites are to provide future readers accurate answers. I wouldn’t want your answer to be discounted by some future visitor because it has no supporting evidence and they don’t recognize your name. $\endgroup$
    – rmalayter
    Feb 19, 2019 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.