3
$\begingroup$

Is Intel's RDSEED a true random number generator?

$\endgroup$
1
  • $\begingroup$ I removed your question about the software implementation. Implementation questions should be asked on Stackoverflow. $\endgroup$ Jun 26, 2019 at 7:44

3 Answers 3

6
$\begingroup$

Yes, RDSEED is a true random number generator.

From Wikipedia:

The entropy source for the RDSEED instruction runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz [...].

RDSEED is however used as a seed for (software implemented) PRNGs of arbitrary width.

$\endgroup$
2
  • 2
    $\begingroup$ I would say that we need to be pretty careful with citing Wikipedia. Unless the text is backed up by credible sources, we should probably tread with caution. Come to think of it, some of what we read, especially on sensitive topics such as cryptography, may be misinformation. $\endgroup$
    – Patriot
    Jun 28, 2019 at 11:59
  • 1
    $\begingroup$ @Patriot: A better source is electronicdesign.com/resources/article/21796238/… - it discusses the metastable flip-flop which settles due to thermal noise. The article also discusses how the entropy is "conditioned" or "whitened" by feeding it through AES. That article is by Michael Hamburg, one of the authors of a review of the internals, and the references it cites include "D. J. Johnston, "Mircoarchitecture Specification (MAS) for PP-DRNG," Intel Corporation (unpublished), V1.4, 2009." - David Johnston has posted on SO. $\endgroup$ Oct 7, 2022 at 11:35
3
$\begingroup$

Intel says it is a true RNG, and so do people who've looked at the design details Intel shared with them.

The possibility of it not being a true RNG are basically limited to NSA interference and a big coverup with Intel's knowledge (perhaps in the conditioning logic), or some kind of covert modification of the design that actually gets laid down in silicon. Perhaps one that makes the rdrand instruction return data from a pure CSPRNG seeded somehow, not using the true randomness that the RNG hardware has prepared.

Both of these are unlikely but impossible to rule out. It's been a decade since IvB was released, and nobody involved with the design has leaked any details about NSA interference or backdoors, or other shenanigans, and nobody's found anything reverse-engineering.

Other vendors (including AMD) have implemented rdrand in their CPUs, too, presumably with an independent design. (AMD infamously had a bug with their rdrand in Ryzen 3000, where it always returned 0xFFFFFFFF, eventually fixed with a microcode update.)

It's impossible to prove that randomness is true, and not from a sufficiently-good CSPRNG. And the transistors are so small that it's not particularly doable to actually reverse-engineer a real chip in the wild to see if it actually works the way Intel and others say they work.

It makes sense to mix it with other entropy sources if you have any available, like Linux does to implement /dev/random, out of an abundance of caution if nothing else. And because you need a fallback in case the CPU has a non-functioning rdrand; the instruction documentation allows it to return failure indefinitely, like if it fails its self-tests.

But there are entropy-mixing algorithms that don't lose (much) existing entropy if the new source being mixed in is actually not valuable. So it usually makes sense to use rdrand as one source of entropy. Especially for embedded systems, there often aren't any other good sources of entropy in early boot, so an HWRNG helps a lot, much better than nothing.


But with that out of the way, it's highly likely that it does work the way it's claimed to.

Intel and people who have reviewed the design have published some stuff about the internals. Understanding Intel's Ivy Bridge Random Number Generator is one such article, by Michael Hamburg of Cryptography Research, inc., one of the authors of an independent study of the design that Intel contracted out.

The true-randomness source is a metastable flip-flop (RS-NOR latch) which settles due to thermal noise.

This source of a stream of 0 and 1 bits is then conditioned, aka whitened, by feeding it through AES in counter mode.

Finally, the seed is passed to a pseudorandom generator, which generates the RNG's final output. Under normal load, the generator reseeds every time it produces an output, so its output should be almost completely statistically random. Under very heavy load, it can generate multiple blocks of output between reseeds. In this case, the generator has 256 bits of state, and finding patterns in it is as hard as breaking 128-bit AES.

There's a buffer that rdrand instructions pull from; in IvB there weren't enough cores to ever exhaust it and make it set CF=0 (according to David Johnston's answer on Stack Overflow; and he should know since he designed the hardware buffer logic and wrote librdrand), but later CPUs can exhaust the buffer.

After microcode updates to fix possible MDS vulnerabilities, rdrand is vastly slower on some Intel CPUs. RdRand Performance As Bad As ~3% Original Speed With CrossTalk/SRBDS Mitigation. See also updated timing numbers on https://uops.info/, like one per 3554 cycles on Skylake. See the Performance / internals of rdrand / rdseed section at the bottom of an SO answer I wrote. Performance of using it, and practicalities like whether to make your retry loop infinite.

$\endgroup$
2
  • $\begingroup$ Re. 1st sentence: you're relying on hearsay since modern CPUs can't be physically audited. Public design does not guarantee private implementation. $\endgroup$
    – Paul Uszak
    Oct 7, 2022 at 12:36
  • 2
    $\begingroup$ @PaulUszak: The entire first half of my answer is dedicated to making that point. Keep reading beyond the TL:DR, which I intentionally phrased as "Intel says". $\endgroup$ Oct 7, 2022 at 12:37
2
$\begingroup$

No one knows, so we can't say because of the two obstacles of non auditability and computational indistinguishably. But it's not looking good at all.

Since the device is completely unverifiable, it could do anything. All we know for certain is that it is impossible to mathematically verify true randomness. Computational indistinguishably means that the output could simply be any decent $ \operatorname{E}_{k \; \oplus \; cpuid} (ctr) $ like CSPRNG. Intel state that it's AES-CBC-MAC throughout anyway.

Wikipedia is not the oracle of all truth, and has to be ignored in this context. The primary verification of the device is ANALYSIS OF INTEL’S IVY BRIDGE DIGITAL RANDOM NUMBER GENERATOR. That was followed up with an academic report, A Provable-Security Analysis of Intel’s Secure Key RNG. Unfortunately for users, both reports are based on a raw entropy rate of ~0.5 bits/bit. And to be a gold standard TRNG, (entropy out) < (entropy in). But it says in those reports:-

"We did not have access to Ivy Bridge parts, so Intel provided us with testing data from pre-production chips. These chips allow access to the raw ES output, a capability which is disabled in production chips. "

The whole analysis is built on sand. Many factors create reasons for suspicion:-

  1. It is not in the interest of the US government/NSA/security community to produce fast secure random number generators for public use. Cui bono?
  2. The NSA has form on this, with many examples publicly available.
  3. All public analysis of the chip is based on unverified data samples supplied by Intel themselves. Is ~0.5 bits/bit real?
  4. The primary analysis of RDSEED was paid for by Intel which is a huge conflict of interest, tantamount to marking your own homework. From that report's front page - "This report was prepared by Cryptography Research, Inc. (CRI) under contract to Intel Corporation".
  5. The entropy source operates at a suspiciously high 3GHz. Academic laboratory TRNG's have only recently attained this rate using optical means (green line below). If true, I would expect huge correlation at this sample rate. Injecting 1% entropy into a CSPRNG stream does not make a TRNG.
  6. The pink marked devices show how easy/common it is to over-hype your TRNG. These marked devices have exceeded a very conservative engineering limit (Shannon-Hartley) beyond which it is mathematically impossible to extract any more entropy. Some others appear to be suspiciously right on the limit. limits From Recommendations and illustrations for the evaluation of photonic random number generators.
  7. The entropy source is an atypical circuit not replicated in the hacker community, and the only detailed analysis is by Intel themselves and unpublished. (C. E. Dike, "3 Gbps Binary RNG Entropy Source," Intel Corporation (unpublished), 2011.)
  8. The typical completely in-silicon TRNG is synthesised via multiple ring oscillators. Inverters are easy to burn in their hundreds. There are numerous examples at all levels of academia and commerce. Intel chose not to for some reason, preferring to go analogue on an otherwise entirely digital die.
  9. There is no raw entropy source available for inspection, and even if there was, the level of integration means that we can't verify that the source is actually used.
  10. *nix developers do not trust it.

But the best for last. Even Intel could not convince it's own agent that it's a good TRNG:-

Under heavy load, it should provide security equivalent to 128-bit AES, even against an attacker who can see some of its outputs and, after a good reseed, force the ES to output nonrandom, known values.

-Cryptography Research, Inc. (CRI).

If you accept that an effective TRNG has information theoretic security via the entropy input/output ratio, Intel's isn't. Given all the evidence against, and who benefits if it isn't, I have to conclude it's a CSPRNG (at best), and not a TRNG. Most of the *nix community agrees with me.

$\endgroup$
5
  • 4
    $\begingroup$ I'd consider that "it's too uncertain to be used as a TRNG" a better phrase. It could very well be a TRNG (and personally I expect it to be so, if just because of the fallout produced if it isn't). However I agree that it certainly hasn't been proven to be one beyond reasonable doubt. In the end though it is a TRNG - or an RNG based on a TRNG - or it isn't, and that doesn't depend on opinion. $\endgroup$
    – Maarten Bodewes
    Jun 28, 2019 at 10:54
  • 3
    $\begingroup$ Although there are some good points in this answer, the last paragraph is nonsense. A TRNG has no inputs, and the RDSEED chip has no inputs. It's most definitely not a CSPRNG: there is an entropy source, and the question here is the quality of this entropy source. The cited sentence from CRI does say that it's a good TRNG, providing sufficient entropy against a reasonably powerful attacker. As you note this is a biased source, but it doesn't at all say what you claim it says. $\endgroup$ Aug 2, 2019 at 6:46
  • $\begingroup$ @Gilles Great comment! Why do you believe that my direct quotation isn't? The I/O ratio relates to the Shannon-Hartley criteria across the extractor. This is where true magic can exist. And we know nothing of the source and/or biases as it can't be audited. I'd have thought that you'd have known the construct's dodgy from your Unix persona. All the development influencers have abandoned RDThing. It's pretty clear they're right to do so. $\endgroup$
    – Paul Uszak
    Aug 2, 2019 at 10:51
  • $\begingroup$ "It is not in the interest of the US government/NSA/security community to produce fast secure random number generators for public use." Intel isn't part of the government, so why would they care? $\endgroup$
    – Sparkette
    Feb 10, 2022 at 4:08
  • 1
    $\begingroup$ @flarn2006 They are under US jurisdiction which includes a shed load of security legislation, esp. > 9/11. Just as I am (even in the UK) subject to the US Cloud Act via bi-lateral international treaty with the US. Sigh. Plus they are heavily contracted to the US government and money talks. $\endgroup$
    – Paul Uszak
    Feb 10, 2022 at 11:36

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.