If RdRand is supported, it is fully trusted

[msoosgds]

The system reseeds every time from RdRand in case RdRand is available, and does not use urandom at all, which typically uses multiple sources of randomness. This means that the RdRand by Intel is fully trusted, /dev/urandom will not play a part. It would be possible to use urandom for seeding&generation and then XOR in RdRand, whitening the output. The security should only improve, and time spent would be essentially the same. Affected code:

int s2n_drbg_generate(struct s2n_drbg *drbg, struct s2n_blob *blob)
{
    uint8_t all_zeros[32] = { 0 };
    struct s2n_blob zeros = {.data = all_zeros,.size = sizeof(all_zeros) };
    if (blob->size > S2N_DRBG_GENERATE_LIMIT) {
        S2N_ERROR(S2N_ERR_DRBG_REQUEST_SIZE);
    }

    /* If either the entropy generator is set, for prediction resistance,
     * or if we reach the definitely-need-to-reseed limit, then reseed.
     */
    if (drbg->entropy_generator || drbg->bytes_used + blob->size + S2N_DRBG_BLOCK_SIZE >= S2N_DRBG_RESEED_LIMIT) {
        GUARD(s2n_drbg_seed(drbg, &zeros));
    }

    GUARD(s2n_drbg_bits(drbg, blob));
    GUARD(s2n_drbg_update(drbg, &zeros));

    return 0;
}

Instantiate will always set entropy_generator if RdRand is available:

int s2n_drbg_instantiate(struct s2n_drbg *drbg, struct s2n_blob *personalization_string)
{
    [...]
    /* After initial seeding, pivot to RDRAND if available and not overridden */
    if (drbg->entropy_generator == NULL && s2n_cpu_supports_rdrand()) {
        drbg->entropy_generator = s2n_get_rdrand_data;
    }
    return 0;
}

[alexw91]

I believe this was known behavior at the time of the PR (See: #248 (comment)) @SalusaSecondus can you comment on this?

[colmmacc]

urandom is used in all cases for instantiation and generation, and then we pivot to rdrand() for reseeding. We could do a XOR construction, and the latest NIST NRBG constructions do define those ... but here we're confirming to the DRBG spec which is to reseed. We do want to conform to a published specification, as we are formally verifying our implementations.

One of the interesting things about a simple XOR construction is that it's the construction that's easiest to attack if the hardware isn't trusted ( https://blog.cr.yp.to/20140205-entropy.html ). It requires the attacker to no extra work, they can fully control the output bit-for-bit. With the DRBG reseed construction, an attacker who controls entropy is forced to do at least as much as work as AES_CTR to control or predict the final output. That said, the difference is only quantitative not qualitative; any attacker who controls your source of entropy essentially controls the whole stack.

[SalusaSecondus]

@colmmacc beat me to much of this, but to provide my independently reasoned response :-)

I disagree with the statement that RDRAND is fully trusted and believe that we take reasonable precautions against issues with it.

1. The initial seed (384 bits) is from /dev/urandom. This, by itself, is sufficient entropy for the DRBG to run for an extremely long time without security issues.
2. RDRAND is not directly XORed into the DRBG, but is instead mixed in according to the NIST specification. This means that it (at worse) will add no entropy, rather than any chance to lower entropy or steer the DRBG into a known (and thus compromised) state
3. RDRAND is not directly exposed to the callers, which means that even if it is not trustworthy (and/or backdoored) s2n is protected against it by the masking provided by the DRBG.

So, absolute worse case, we lose prediction resistance, but maintain a DRBG based on 384 bits of entropy. Personally, I think this scenario is so unlikely as to be essentially impossible. (Not that I fully trust RDRAND, but the various ways in which it might be untrustworthy are still likely to introduce entropy with the weaknesses mitigated by this construction.) That's not too bad. Have you actually measured the time difference to ensure that it would be negligible?

[msoosgds]

I was wrong in my analysis, you first seed it with data from urandom then change the entropy source to RdRand, so you do get 256 bits of entropy first (32B * 8b=256b, I can't seem to find the 384b):

/* Seed / update the DRBG */
    GUARD(s2n_drbg_seed(drbg, &ps));

    /* After initial seeding, pivot to RDRAND if available and not overridden */
    if (drbg->entropy_generator == NULL && s2n_cpu_supports_rdrand()) {
        drbg->entropy_generator = s2n_get_rdrand_data;
    }

However, this 256b is collected at the "worst" time: at startup, which for an isolated system (e.g. virtual machine just spinned up with minimal interfaces) may not have much entorpy. Which begs the question... in case RdRand is not available, do you only add new entropy after 34359738368 bytes have been produced? That's kinda scary, I'd think. Again, this 256b of urandom data could be right after startup that you use for so long.

[SalusaSecondus]

I was also wrong, it is 256b, not 384b. (I've been reading the specs for the AES-CTR-DRBG based on AES-256, which uses 384b of entropy, unlike the 256b of entropy used by the AES-128 form used in s2n.)

As for lack of prediction resistance when RDRAND isn't present, you are correct. We originally had it however it was removed in 0819910 due to performance issues.

[alexw91]

So would adding support for the getrandom() syscall if it is supported by the OS address everyone's concerns?

From the link:

The other feature provided by this new system call is the ability to
request randomness from the /dev/urandom entropy pool, but to block
until at least 128 bits of entropy has been accumulated in the
/dev/urandom entropy pool.

We already have an open issue for adding the syscall here: #17

[SalusaSecondus]

@alexw91 That sounds reasonable. Any chance we can benchmark it?

@colmmacc , do you have input on this?

[msoosgds]

@alexw91 I would be very weary of blocking calls. You'll have plenty of entries with "system hangs on s2e call" in the issue tracker. That's not the solution, I think. Instead, entropy pools (a la Fortuna https://www.schneier.com/academic/fortuna/ ) is I think the right solution. It should call urandom (i.e. non-blocking), but Fortuna has pools that are used to re-seed at different (exponentially different) intervals. That fixes the issue of "when to reseed" -- because too soon means not enough entropy has been accumulated, and too late means too much randomness has been used already that leaked information/was insecure. Take a look at its design, it's really very well-done (and designed by one of the best in the field).

PS: an advantage to having a blocking call would be that we'd get feedback on how many times it blocks on virtual or embedded systems. I'm afraid it won't be too glorious a feedback, but it would be a very good data point.

[raycoll]

To boot, getrandom() is only available on the the most bleeding-edge glibc :/

[SalusaSecondus]

I think we're in a place where we can close this issue. As noted earlier #17 moves s2n to getrandom()/getentropy() when available as strictly better alternatives to /dev/urandom (which remains acceptable from a security perspective).

As noted, getrandom() can block very early in the boot process, however this is generally believed to be the best possible behavior. Once a system is up and running there is no risk of blocking (which is the major concern). I am familiar with the Fortuna construction but it doesn't help us here. According to the specifications, getrandom() blocks only at the beginning before 128 bits of entropy are collected. Any attempt to use entropy prior to that point (even passed through Fortuna) is at risk of being insecure. So, we are either insecure (and do not know it) or we have to estimate entropy and continue reseeding Fortuna until we believe that 128 bits of entropy have been collected (which just means that we block, rather than the method we call block). It also seems unlikely that s2n would be initialized so early in the boot process that there is no available entropy.

Finally, both Colm and I addressed why we believe that the current design properly handles varying levels of trust in RDRAND and thus never considers it "fully trusted" but rather only uses it for additional entropy to be added to a system which we believe has already been properly seeded.

---

Unless significant objections are raised, I will close this issue next week.