2
$\begingroup$

I need to generate secure pseudorandom numbers in an embedded system. Instead of having to port some RNG library, could I just use an existing SHA2 function as a random number generator (n-th random number is SHA2(seed + n))?

I'm worried that SHA2 hashes might not be evenly distributed (have bias towards certain sequences of bits).

$\endgroup$
  • $\begingroup$ NIST publication 800-90a should be helpful, see section 10.1 first. $\endgroup$ – David Schwartz Jun 19 at 23:36
  • 1
    $\begingroup$ In theory yes, this would work when modeling SHA-256 as a random oracle. In practice it is strongly recommended to wrap it in one of the constructions described in NIST SP 800-90a rev1 as pointed out by David. $\endgroup$ – SEJPM Jun 20 at 8:55
  • $\begingroup$ Unexplained is why you would have that particular worry; any reason why you would expect output that can be distinguished from random? $\endgroup$ – Maarten Bodewes Jun 20 at 10:31
2
$\begingroup$

While SHA2 (SHA-256, SHA-512) original design goals are limited to collision-resistance and (first and second) preimage resistance, it is not known that its computationally distinguishable from a random oracle for messages of fixed length¹. Thus $\text{SHA2}(\text{seed}+n)$ for incremental $n$ is a CSPRNG as far as we know, for a wide-enough random secret seed. If we generate $2^k$ outputs, and $+$ is addition², we need $b+k$ bits of $\text{seed}$ for $b$-bit security.

For added insurance, one could use $\text{HMAC-SHA2}(\text{key}\gets \text{seed},\text{message}\gets n)$, which requires very little extra code. Mihir Bellare's New Proofs for NMAC and HMAC: Security Without Collision-Resistance gives an argument of security³ for weaker assumption on the compression function. Main drawback is that HMAC requires more evaluations of the compression function for each output (four for a simple implementation, possibly down to two with precomputation).

I would use HMAC, with SHA-512 rather than SHA-256 for $b>120$ bit security, or/and truncate the output or XOR its two halves (which can only help security), just to err on the safe side.


Any of the above constructions has the drawback that earlier output can be found at little cost if the state of the generator is recovered.

Beware that an adversary having access to the embedded system could try to extract the random secret seed (using a JTAG port, probing, side-channel attack…), or replace it with a known value (e.g. erase that area of remanent storage).

Also, I emphasize that it is difficult to make a robust incremental $n$ facing adversaries that can cut the power at any time of their choice.

Any of the above three paragraphs might be enough to justify the complications of a TRNG with cryptographic strengthening (CSTRNG).


¹ This restriction is necessary due to the length-extension property.

² Concatenation is more usually noted $\mathbin\|$. In that case, we only need a $b$-bit seed.

³ With security level half the hash width, or the width of $\text{seed}$, whichever is lowest.

| improve this answer | |
$\endgroup$

Your Answer

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