2
$\begingroup$

The standard Salsa20 core is a $\{0,1\}^{384} \to \{0,1\}^{512}$ PRF with a 16 byte constant ($\sigma$ for a 32-byte key), an 8 byte nonce, an 8 byte counter, and a 32 byte key. The hash function does not make any distinction between the types of input. This leaves 48 bytes which can be randomly chosen. If they are all chosen randomly and are kept secret, does that increase the keyspace to $2^{384}$, or is there some reason why the internal state of the cipher is limited to 256 bits? I ask this because the Linux kernel random driver (called CRNG) uses ChaCha20 to generate randomness.

The cipher state is initialized in the Linux kernel with the following function:

static void crng_initialize(struct crng_state *crng)
{
    int             i;
    unsigned long   rv;

    memcpy(&crng->state[0], "expand 32-byte k", 16);
    if (crng == &primary_crng)
        _extract_entropy(&input_pool, &crng->state[4],
                         sizeof(__u32) * 12, 0);
    else
        _get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
    for (i = 4; i < 16; i++) {
        if (!arch_get_random_seed_long(&rv) &&
            !arch_get_random_long(&rv))
                rv = random_get_entropy();
        crng->state[i] ^= rv;
    }
    crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
}

The state, kept in (struct crng_state *)crng->state, has the constant $\sigma$ for the first 16 bytes, and the last 48 bytes are generated randomly using _extract_entropy(), a function that returns the amount of entropy requested. Does this mean CRNG output has a $2^{384}$ keyspace?

If there is an attack against ChaCha20 that requires at least $2^{256}$ invocations of the cipher, then increasing the keysize does not increase security (even if 256 is already plenty). In other words, ChaCha20 with a 256-bit key is 256-bit secure, but I do not know if ChaCha20 with a 384-bit key is 384-bit secure. Would there be no attack faster than brute force for a 384-bit key?

I am fully aware that even a good 256-bit cipher is considered impossible to break with modern technology and that there is no practical reason to use a larger key. However sometimes it is useful to know how much entropy is present in a given amount of pseudorandom data.

$\endgroup$
3
$\begingroup$

Yes, you have control over $32$-byte key + $8$-byte nonce + $8$-byte counter totalling to a $384$-bit key and this is perfectly safe.

Your only responsibility for this function is to ensure that the $(\text{Key}, \text{Nonce})$ tuple never repeats. The PRG will increment and wrap the counter so this may start randomized. You can still increment the nonce. You could (but probably shouldn't) increment the key.

Alternatively you can use the much more standard IETF variant of chacha20 with a 96-bit nonce and $32$-bit counter or the Xchacha20 variant with $192$-bit randomized nonces and no exposed counter.

Edit: How are we certain that chacha20 is not capped to 256-bit security?

The constants, key, nonce and counter are all treated equally such that a $1$-$2$ bits changing in the counter is safe. The constants exist to weigh the control of the function away from the adversary. The adversary can control the $8$-byte nonce and $8$-byte counter, not the $32$-byte key nor $16$-byte constant. $16 / 64 = 1 / 4$. If the adversary could control the constants then they have $1 / 2$ of the input. A full $384$-bit key gives the adversary only the public constants worth of knowledge (and they know the counter increments). A $512$-bit key means the adversary knows no inputs.

$\endgroup$
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – cypherfox Mar 12 '18 at 6:56
  • $\begingroup$ Why shouldn't one increment the key? I mean of course it's unnecessary but would there be any actual cryptographic issues? $\endgroup$ – forest Mar 16 '18 at 7:47
  • 1
    $\begingroup$ No weaknesses come to mind and this is likely safe. By general rule of thumb you want distinct keys. IIUC chacha20 is conjectured to be related-key safe, which is why we can safely increment the counter and nonce; and the key isn't treated any differently. So I'd be surprised if there is any weakness - especially under this CSPRNG (not stream cipher) use. $\endgroup$ – cypherfox Mar 16 '18 at 11:05

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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