Appropriate sources of entropy

Posted May 24, 2008 17:49 UTC (Sat) by giraffedata (guest, #1954)
In reply to: Appropriate sources of entropy by aegl
Parent article: Appropriate sources of entropy

It seems implausible that an attacker can reliably observe or manipulate network traffic to sub nano-second precision

Why? All the physical processes that move bits along a network, and drive the CPU and memory states for processing them, are predictable with that precision. E.g. if I send two packets into a network N nanoseconds apart and nobody else is using that part of the network, why wouldn't the receiver register them as received N nanoseconds apart?

to post comments

Appropriate sources of entropy

Posted May 24, 2008 23:45 UTC (Sat) by dlang (guest, #313) [Link]

if there is no other traffic involved then you may have a point, but if there is no other
activity happening on the server other then what's initiated by the bad guy, there's nothing
interesting on the server for the bad guy to get.

if the server is doing anything else (talking to anyone else on the network, doing processing
of some kind, etc) then you start having things happen on the server that are not controlled
by the bad guy

Appropriate sources of entropy

Posted May 25, 2008 13:39 UTC (Sun) by kleptog (subscriber, #1183) [Link] (1 responses)

This is something I don't quite understand. Yes, the packets might be registered at the
network card exactly N nanoseconds apart, but between the time that the packet is registered
by the card and when entropy might be added there is:

- Waiting for the PCI bus to be free to check the status of the card
- The CPU finding the code to run which may involve looking up page tables, pulling code out
which may be in any number of caches, each of which take an unpredicatable amount of time to
respond.
- The process of DMAing the data to main memory takes an unpredictable amount of time,
depending on the state of the DRAM.
- The busses are shared between various CPUs which are doing other things at the same time.
- The execution time of CPU instructions is affected by branch prediction logic and
instruction scheduling algorithms. Hyperthreading makes it worse.

And you're saying that at the end of this there's not even a single bit of entropy? If the
machine were otherwise completely idle I might understand it but if you just register lots of
dubious sources and use as entropy the time between different dubious sources I don't see how
it could be in any way predictable.

If I had any idea how to do it, I'd create a device that tried to extract entropy from the
timer interrupt and see if there is any correlation to be found...

Appropriate sources of entropy

Posted May 26, 2008 16:34 UTC (Mon) by aegl (subscriber, #37581) [Link]

"the time between different dubious sources"

Agree with most of what you've said here ... but I have to comment that Linux doesn't use the time delta between different interrupt sources. It keeps a per-IRQ history and computes delta-t based on the previous interrupt using the same IRQ (if multiple devices are sharing the same IRQ, then this will be a cross-device time, but generally people try to arrange that devices do not share IRQs).

I have no idea why Linux does this ... in some cases using deltas between different interrupt sources would provide some defense against an attacker who does have tight control over the packets on one or more interfaces.

Appropriate sources of entropy

Posted May 29, 2008 10:01 UTC (Thu) by forthy (guest, #1525) [Link]

Actually, no, none of the physical processes are predictable to sub-ns precision. First, the sender's CPU uses cache - if some data is not in the cache, it will take more time to read in. Same happens on the receiver CPU - a single cache miss, and the counter will read differently (last few bits only, for sure).

Then, there's also clock synchronization. CPU clocks aren't synchronized, and the crystals aren't too precise - a 200MHz HT clock for an AMD processor can actually run at 201.xxMHz (the one I'm using right now is running at 201.155MHz, the other, very similar configured machines I've in the office have the last digits at 53, 54, 55, and 89). As outside attacker, you can't know the exact value (well, even as inside attacker you can't know the exact number - only to a limited precision), but you need to to inject deterministic data into the random number pool.

Also, today's networks are usually switched. So there's a store-and-forward switch in between. These switches can theoretically be quite deterministic, but their clock is slower than the CPU clock (25MHz for fast, 125MHz for Gb ethernet). This clock is not synchronized with the other PCs. So if you have a 2.5GHz CPU sending a packed through a single Gb switch, and receive it with another 2.5GHz CPU, you can add 4 bits of randomness into your pool. Chances are high that even more bits are random.

I suggest a challenge: Try to produce a deterministic pattern with full knowledge over both sides - e.g. by modifying the kernel's ping code so that it sends the rtdsc timestamp as answer). Whatever quality you achieve in this challenge will be the "dubious" part of the randomness, and the remaining noise can be added.