5
$\begingroup$

Miller-Rabin tests the compositeness of candidate numbers (hence, input $x$) that's often used as a primality test.

The M-R test requires different random numbers for accuracy and confidence in the primality of $x$. To obtain such random numbers, I want to obtain them from a lightweight embeddable RNG, instead of a CSPRNG implemented elsewhere in my project.

So Q1: what's the minimal set of requirements for an RNG for use in M-R test, in addition to guarantee of distinct dissimilar output?

Now. The way I intend to use the RNG, is to seed it with the entire value of $x$ with an additional nonce (64-bit maximum) that's input to the M-R test routine. This means the RNG should be able to accept variable-sized seed, and an additional nonce.

An additional property I desire, is that it have a small state, for example, 128-bit if such implementation is possible and optimally efficient (I would consider slightly larger states if it's more efficient).

So Q2: is there a an existing RNG that meets the criteria (~128-bit state, variable-length seed, nonce)? And preferablely one that's based on one of those from the on-going NIST Lightweight Cryptography Project?

If not, Q3: what commonly-used constructs (LFSR, anti-circular bit-patterns) can I use to design a suitable RNG?


Last-minute clarification

When I say "embeddable", I mean incorporating the RNG code into that for the implementation of the M-R test.

And I'm not asking about RNG for generating RSA primes, I'm asking about a small RNG for use inside M-R test.

$\endgroup$
6
  • $\begingroup$ I don't understand the question. The god of primality isn't really interested in whether the number stream is invertible or cryptographically secure. So why can't you just use anything (SHA1PRNG, /dev/urandom/, Mersenne Twister, Xoroshiro128, etc., etc.)? $\endgroup$
    – Paul Uszak
    Commented Feb 15, 2021 at 13:16
  • $\begingroup$ @PaulUszak The point is to minimize code size and memory usage. Those other algorithms you mentioned has large footprint. $\endgroup$
    – DannyNiu
    Commented Feb 15, 2021 at 13:51
  • $\begingroup$ Xoroshiro128 is pretty small. And it's NIST approved. $\endgroup$
    – Paul Uszak
    Commented Feb 15, 2021 at 14:08
  • $\begingroup$ @PaulUszak In that case, I suggest you post it as an answer to my Q2. $\endgroup$
    – DannyNiu
    Commented Feb 15, 2021 at 14:14
  • $\begingroup$ I'm still not entirely clear what you're asking. A 'built in', 'embedded' M-R test? Embedded in what; AVR, SoC, ESP8266, Spartan, Verilog? Some of those have TRNGs inside already = 0 footprint. Is this for key exchange? $\endgroup$
    – Paul Uszak
    Commented Feb 15, 2021 at 15:15

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Embedded TRNGs are pretty common these days. Even kiddie kit like ESP32/RPi has them (>30MB/s) . A lot of professional u_controllers too as you simply purchase an IP licence like TRNG-IP-76 and burn it. So interestingly, you make a TRNG with software! $\endgroup$
    – Paul Uszak
    Commented Feb 15, 2021 at 13:28
  • $\begingroup$ @Paul Uszak: I wouldn't trust you if you told me you trust these and build that (which I find beautiful). And I'd be inclined to consider believable claims of being able to predict future output of an ESP32 (or even TRNG-IP-76) running in an environment that the attacker controls. $\endgroup$
    – fgrieu
    Commented Feb 15, 2021 at 13:40
  • $\begingroup$ Also: the TRNG-IP-76 seems to be "designed for compliance with Federal Information Processing Standards", but I'm ready to bet that "FIPS approved" applies at best to a particular product using it. Call me old school, but that the marketing puts essentially a lie on the title line lowers my confidence in the whole smurf, even if the rest of spec is impressive (it is). $\endgroup$
    – fgrieu
    Commented Feb 15, 2021 at 14:04
  • $\begingroup$ You re-open a sore that has afflicted this forum for many years. Does a true random number generator have to be EMP/CIA/BBC hardened to be a true random number generator? Can we distribute them nation wide, or do we keep them secure in our man caves? You will be familiar with my efforts regarding entropy sources, yet I posit that they are perfectly secure. Otherwise the ‘attacker(?)’ would have be be in my cave with me and my cat. And Dom will have you. The mixing of commercial and amateur TRNG's specifications just confounds arguments here, and doesn’t help privacy/democracy or herein debate. $\endgroup$
    – Paul Uszak
    Commented Feb 21, 2021 at 1:26
2
$\begingroup$

I'll leave Q1 and Q2 for others, here's an 128-bit transformation based on ChaCha20 and Gimli's round constant.

First 4 32-bit words are mixed together using the ChaCha quarter-round function (in [1] and [2]). For completeness, it will be repeated here:

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

where + is arithmetic addition, ^ is bitwise xor, and <<< is left-rotation.

Next, interleave the 10 quarter-round function with 4 XORs with round constants from Gimli[3]:

a ^= 0x9e377900 | 1;
qround(a,b,c,d)
a ^= 0x9e377900 | 2;
qround(a,b,c,d)
qround(a,b,c,d)
a ^= 0x9e377900 | 3;
qround(a,b,c,d)
qround(a,b,c,d)
qround(a,b,c,d)
a ^= 0x9e377900 | 4;
qround(a,b,c,d)
qround(a,b,c,d)
qround(a,b,c,d)
qround(a,b,c,d)

After compiling with -O3 optimization flag, and executed $2^{20}$ iterations, this custom construct spent 0.047sec in user space (contrast: kernel space), while Gimli spent 0.108sec, which has a factor of over 2x.


[1]: Daniel J. Bernstein, ChaCha, a variant of Salsa20, https://cr.yp.to/chacha/chacha-20080128.pdf

[2]: ChaCha20 and Poly1305 for IETF Protocols https://www.rfc-editor.org/rfc/rfc8439

[3]: Daniel J. Bernstein, et al., Gimli: a cross-platform permutation, https://gimli.cr.yp.to/papers.html

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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