5
$\begingroup$

As far as I understand, the key stream of the ChaCha20 cipher may be used as a seeded PRNG, where the seed is used to set the key and the nonce. As described in RFC7539, ChaCha20 can be used with a 256-bit (32-byte) key and a 96-bit (12-byte) nonce, allowing a seed of maximum 352 bits (44 bytes), thus limiting the counter to 32 bits (4 bytes).

My problem is, how can I use this PRNG if I want to provide a larger seed? Say, I seed the PRNG from an entropy source where I a can guarantee a minimum of about 4 bits of entropy per byte, and want to seed the PRNG with 64 bytes or more to be confident that it has been provided about 256 bits of entropy.

I reckon a cryptographic hash function, such as SHA256 or SHA512, could be used to compress the collected entropy bytes to be used as a seed, but it would be desirable if this could be solved by only using the available ChaCha20 primitive.

Another possibility seems to be to use ChaCha20 to construct a Davies–Meyer one-way compression function, treating a variable-length seed as blocks of 44 bytes (to input as key and nonce for the next block), taking the final 44 byte output as input seed to the PRNG.

It seems that Davies–Meyer was designed to be used with block ciphers, but ChaCha20 is a stream cipher.

My questions are:

  1. Are there any obvious problems with using Davis-Meyer like this?
  2. Are there any obviously better approaches to feed this PRNG with a variable-length seed?
$\endgroup$

2 Answers 2

2
$\begingroup$

Davies–Meyer? That would be a very unusual way of seeding a PRNG. The standard way of entropy extraction is to use a vetted hash algorithm such as SHAx. I'm not quite sure how you want to use your RNG, and I'm having trouble deciphering how many bits of what you want. I'm going to assume that you simply want 256 bits of entropy to inject into the state.

Having an entropy source available changes things somewhat compared to a plain PRNG. You don't need a key or a nonce in this case. You'd collect 128 bytes from your entropy source. It's twice 64 as NIST recommend that you double the input entropy for each bit of output entropy when using a hash based extractor. Then run it through SHA256 and inject into ChaCha in place of the nonce and key.

Further I'm also assuming that this is to be only a PRNG. With seeding from a true entropy source, you won't be able to repeat the output sequence. Intuitively it feels wrong to use a PRNG to self seed, but I can't demonstrate this mathematically. Follow the hash route as it's the obvious way, well proven and likely to be simpler than rolling your own recursive version of Davies-Mayer.

$\endgroup$
1
$\begingroup$

ChaCha20 is a PRF, so you can use it as an extractor. k0 and k1 being two random 256-bit keys, compute E(k0,E(k1,0)), and use half the output as a key. Remaining bits can be used for the nonce, but in case (k0,k1) repeats, you may want to use a different source for the nonce, even a simple timestamp.

$\endgroup$
1
  • $\begingroup$ Here you mean $E(k, n)$ where $k$ is the 256-bit key and $n$ is the...128-bit input? So you truncate $E(k_1, 0)$ to a 128-bit chaining value to feed it into $n \mapsto E(k_0, n)$? $\endgroup$ Dec 19, 2017 at 23:21

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.