Secure embedded TRNGs are difficult
In an embedded system where the adversary is assumed to control the environment of the Target of Evaluation¹, like a Smart Card, making a TRNG is notoriously tricky. It's hard to ensure the output is truly unpredicatable.
When there is a hardware source, one line of attack freezes it, either literally (thru evaporation of a liquefied gas, lowering temperature thus reducing thermal noise and offsetting the comparator that translates noise to bits) or by other means (e.g. shorting the source's digital output line). A standard countermeasure tests if the source's output is "random enough", before feeding the output of that to a (CS)PRNG (it's pointless to test the output of a CSPRNG). It's difficult to make that test sensitive enough for security, satisfying evaluators, yet not degenerate into unacceptable field failure rate. And it might not be enough against more sophisticated attacks (I can vaguely imagine an adversary modulating the power supply to control the source's output, making it pass the source test, yet control the input of the CSPRNG, thus its output. And that naturally occurring conditions could have the same effect, perhaps explaining this embarrassing disaster).
For these reasons, only a fool, or one operating under pressure to deliver something good enough to pass a poorly designed test, would rely only on hardware source + source test + CSPRNG. It's best to add two ingredients to the mix:
- A secret key, injected at manufacturing, that is fed into the CSPRNG. When that remains secret, and all else except the CSPRNG itself fails, at least the output of the CSPRNG is secret until it leaks by other means.
- A counter in permanent memory, fed into the CSPRNG. When all else except the CSPRNG itself fails, at least the output of the CSPRNG is not reproducible from one power-on cycle to the next. Problem is making the counter demonstrably resisting power cut at that wrong moment (decided by the adversary, or it's common substitute Murphy). It's hard, or even impossible depending on hardware.
But do we need a TRNG for a Miller-Rabin primality test?
If we have to abide by some diktat standard mandating that a TRNG is used for the bases of the Miller-Rabin primality test, resistance is futile and we need a TRNG, see above. I disregard that in the rest of this answer.
what's the minimal set of requirements for an RNG for use in M-R test?
When we disregard the issue of side channels, it's sufficient that its output is unpredictable by whoever generates the candidate prime prior to that generation, and about uniform. That's not even necessary, see first bullet below.
We can do without a TRNG when at least one of the following holds:
- We generated the candidate prime with a procedure we trust to produce random candidates, as must be the case for RSA key generation²: a fixed set of bases will do (under plausible mathematical conjectures). Yes, a 1024-bit integer known to have been generated at random in $[2^{1023.5},2^{1024}]$ that further passes MR to bases $\{2,3,5\}$ is prime with probability of the contrary less than $2^{-80}$, that is certainty in all except mathematical circles. And for added
hope of getting rubber-stamped confidence, we can generate the bases with a public CSPRNG seeded with the prime tested.
- We have a secret at hand: a CSPRNG seeded with that secret and the prime tested will demonstrably do, even if we are validating³ the primality of an externally supplied prime candidate intended for an RSA moduli.
Wrapping it up: for an MR-test built into the generator, using fixed bases $\{2,3,5\}$ is enough for 1024-bit or more; and using about any sound generator seeded by the integer tested (and negligible or zero probability that two bases are identical) is ample. For an independent MR test, use such generator seeded with a secret and the integer tested.
¹ I'm using Common Criteria vocabulary to make it look like I'm familiar with it. That's common trickery.
² In this case, we can do with a very small number of MR base. See FIPS 186‑4 appendix F.1, or earlier table C.1, which boils down to: 3 bases will do for primes at least 1024‑bit (when we disregard the issue of strong primes, which is common practice, and reasonable at least for two-factors RSA with primes at least 1024‑bit).
³ In this case we need more MR bases, and I know no much better bound than at least $k/2$ tests for $2^{-k}$ residual probability that a composite creeps.
