On an embedded system with no external input, can haveged provide entropy?

Question

Take an example embedded system:

• Microprocessor
• Flash memory
• SDRAM

There is no UI and no network connection.

Can the CPU timing jitter that is used by haveged provide adequate true entropy to seed /dev/urandom?

Answer 1

This will depend on the exact system.

Haveged is highly dependent on the rdtsc instruction. For the vast majority of embedded systems in production today this is going to be extremely difficult (to the point of effective impossibility) to estimate.

With a basic enough stripped out OS (or no OS) on a single core CPU where the execution of every line of code on the device is both predictable and independent of external state then it may be closer to realistically possible.

Although on a device with absolutely no external input (other than power up/down) i'm struggling to see the use case for an CSRNG?

Answer 2

Generally, yes of course. You will not have huge amount of entropy, but usually you don't need huge amounts anyway.

First, CPU and memory run at different frquencies, with different timers. Different timers always, necessarily mean that they will eventually diverge and the divergence will eventually be measurable at every desired scale. You can observe this by dropping two ping-pong balls on a table, or by watching the turn signals of two cars at a traffic light. Even when they seem to be in perfect sync at a time, you only need to wait a few seconds, and they will be entirely out of sync. Eventually, an operation will take a cycle longer than it should.

Second, and more importantly, SDRAM has refresh cycles (about 15 times per second) during which the currently being-refreshed row cannot be read for some 3-4 cycles. This necessarily means that reading from memory (or writing) does not always take exactly the same time at all times and at all addresses.

In summary, this means that no matter what, the same identical code running on two identical computers, and even on the very same computer will not always take exactly the same time, even if everything else is 100% identical and there are no external sources. If your timer is of high enough resolution (and rdtsc sure is), you can measure this.

Similar applies to flash memory. Reading from flash memory is not 100% deterministic either, but writing to it even less so. The controller may have to flash a deleted block (which is much larger than the sector size) and partially copy an existing block, then write the data you want to write. This involves a variable (and, although not true random, unpredictable) amount of data being copied, which obviously takes a different time every time.

Add to that the fact that modern CPUs have hyperthreading and operating systems (well, most of them, usually) do some non-neglegible amount of multithreading. Hyperthreaded CPU cores share resources, some more and some less. It's quite possible that every now and then a particular sequence of operations takes a few cycles more than usual because the processor resource is in use by the hyperthread sibling. All in all, this is not 100% deterministic either.

Scheduling threads works with yet another timer. Yes, modern kernels are "tickless", but timeouts/waits which also invoke the scheduler, still work with a timer. Nowadays that'd probably be HPET, but it could as well be something much less reliable. In any case, it is yet another timer that is likely not (though possibly) in perfect sync with the CPU clock and that cannot possibly be in sync with both the CPU and RAM (since they're different speeds).

---

EDIT: In reply to below comment by @MikeOunsworth regarding not being able to generate lots of strong TLS sessions:

Obviously, you do not have enough entropy to run a webserver with TLS, not with a satisfying amount of security anyway, if anything depends on it.
However: If you do such a thing (if... the question explicitly states: "no network"), then you can easily get more entropy from the network. Do timing on handshakes, measure NTP roundtrips and jitter, DNS response time, you get it.

For a "typical" embedded device that that isn't controlling a nuclear weapon which is connected to the internet, I daresay that if you have as few as 30-40 bits of true random, you're good to go. Nobody is realistically going to be able to exploit the generator, let alone try (it's not worth the trouble). Taking the Linux implementation as example, the best attack that e.g. determines the previous state from a known state has 2⁶⁴ complexity. Now, assume you somehow know the complete state (because you know the seed and exactly how many random numbers were pulled so far, good divination skills needed) except those 40 bits of true random which you obviously cannot know. That's 2¹⁰⁴ complexity, good luck. Do you really think anyone will invest such an amount of resources to break into a single one of your puny little embedded devices? Wow, those gotta hold something really, really valuable.

Now, given the parameters of the actual question: Embedded system, flash storage, no UI, no network, you do not have this problem in the first place. You are not going to initiate three dozen TLS sessions per minute, you do not need loads of true random all the time, so it's pointless to object to the fact that this wouldn't work well.

What do you need a strong RNG for on a device which isn't connected to a network and which has flash storage? Well, unless your device is supposed to be a true random generator (what's the flash storage for then?), then you're most probably going to encrypt your drive, what else could you do (there's not many choices, really!).
That's something that ideally needs 128 bits (256 bits in super paranoia mode) of entropy once. We're talking once, not once every second. This should be not too much of a challenge.