0
$\begingroup$

Or specifically, does ChaCha20 hashing of the xoroshiro128+ random number generator result in a cryptographically secure random number generator?

$\endgroup$
  • 1
    $\begingroup$ Why just not using a chacha20 based prng ? $\endgroup$ – Ruggero Sep 24 '18 at 9:48
  • $\begingroup$ I use xoroshiro128+ in a microcontroller because of its speed, but it is not cryptographically secure. I hash this stream afterwards using ChaCha20. $\endgroup$ – Pietje Puk Sep 24 '18 at 10:23
  • 1
    $\begingroup$ but in this way you loose the speed advantage of xoroshiro128+ as ChaCha20 becomes the performance bottleneck. So why keeping it ? $\endgroup$ – Ruggero Sep 24 '18 at 12:39
  • $\begingroup$ Note that ChaCha20 is not a hash, so although you can XOR the random stream with the key stream generated using ChaCha20, that's still not called hashing. What are you planning to use as key? Note that the key should be random as well, and that you'd require a unique IV if you decide to reuse the key. $\endgroup$ – Maarten Bodewes Sep 24 '18 at 12:48
  • $\begingroup$ This is all a bit vague. What's the chip exactly? If it has an internal temperature sensor , I'm pretty sure it can run AES/ ChaCha. $\endgroup$ – Paul Uszak Sep 25 '18 at 21:24
1
$\begingroup$

A hash function is a "public" function. If some bad guy knows what the input might be then they are able to evaluating the hash function themselves and get the same output the good guys do. The only way that won't be a problem is if the input has really high entropy.

Insecure PRNGs only appear random to the human eye, but their output might follow enough of a pattern to make brute-force guessing of hash input possible. (Their output definitely has low entropy if their state space is low or if they're seeded with a 32 or 64-bit number.)

You can address the fact that hash functions are public by using a PRF (pseudo-random function) instead. PRFs can be built from hash functions. See the HMAC and SHAKE (SHA-3) algorithms. If the input to your PRF is non-repeating and your secret-key is not predictable then this is a secure PRNG based on the definition of a PRF.

If you do something like outputBlock = PRF(secretKey, rng.getRandom32Bits()) then the construction is not secure. Even if rng allowed you to sample from an ideal uniform random variable, this method would start repeating outputBlock(s) after around $2^{16}$ samples. (Due to the birthday problem, but even if that weren't a problem you would get repeats within $2^{32}$ blocks.

The improbable occurrence of repeated long outputBlock(s) would be a problem for meeting the requirements of a secure RNG. It might also be possible to perform a stronger attack (full state recovery) with knowledge of the insecure RNG's patterns by observing the pattern of repetitions.

However it is really easy to avoid the problem of repetition. Just use a $n$-bit counter for input and use less than $2^n$ blocks of output. A PRF, by definition, must produce output (on non-repeating input) indistinguishable from random (Even if input doesn't look random!) and, by definition, doesn't permit key recovery attacks no matter what the input is.

That gets you a secure RNG (potentially using just hash functions). But you then don't need the weak RNG.

Of course there are many faster secure PRNG algorithms out there. (Like using ChaCha20 key-stream output or the output produced by repeatedly encrypting a counter with a block cipher.) If you can use a hash and a few extra bytes of executable is acceptable then I don't see why you wouldn't want to base an RNG off of ChaCha. Hash functions implemented in software (compared to a dedicated CSPRNG algorithm) are going to be slow, require a large executable size, or both.

Large executable size meaning large for embedded systems. On a PC with GB of RAM it's neglible.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your comprehensive answer. By implementing a (by itself unsecure) PRNG on the microcontroller and optionally ChaCha20 on the pc I leave the possibility to just use the microcontroller when cryptographically secure numbers are not needed. When needed, switch the CSPRNG on. I periodically reseed the PRNG on the microcontroller using two seeds that are generated with an internal temperature sensor (von Neumann unbiased). Does that make a difference? However your suggestion using a PRF is interesting, I will look into it. $\endgroup$ – Pietje Puk Sep 24 '18 at 14:52
  • $\begingroup$ @PietjePuk Reseeding doesn't solve the problems. Insecure RNGs can be cracked after very little output has been used. Your hardware randomness source isn't great. And turning an entropy source into something useful for crypto is something that requires you to have a lot of prerequisite knowledge. Microcontroller security is a really complex subject as well. Lots of stuff off topic to the question. $\endgroup$ – Future Security Sep 25 '18 at 3:27
  • $\begingroup$ You are right, I will study crypto first as it is also very interesting. Thank you. $\endgroup$ – Pietje Puk Sep 25 '18 at 8:54

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.