Entropy of system data - use all and hash, or trim least significant bits?

Question

I'm working on a background entropy collector for key generation that monitors hardware and produces an entropy pool.

Here's my list of sources:

• Mouse position
• Keyboard timings (i.e. time between keystrokes)
• Network
  • Bytes sent
  • Bytes received
  • Datagrams sent
  • Datagrams received
• Processor (per CPU)
  • Interrupts/sec
  • Queued DPCs/sec
  • C3 Transitions/sec
• Memory
  • Page Faults/sec
  • Transition Faults/sec
• Disk
  • Write bytes/sec
  • Read bytes/sec
• Process (total)
  • IO Read Bytes/sec
  • IO Write Bytes/sec
  • IO Other Bytes/sec
  • Page Faults/sec
• USB
  • Interrupt Bytes/sec
  • Controller PCI Interrupts/sec
• Time taken to fetch all of the above data (measured using QueryPerformanceCounter)

These stats are collected once every 330ms. At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool, giving me roughly 200 bytes per second.

The pool is initially populated by the hash of a single timestamp value indicating the system boot time. When the pool reaches 64KB, I xor with the oldest 64-byte block. This is somewhat warned against in another question, but I don't foresee a problem because the pool is very large and the reasoning for removing old data is size. Keys are generated by computing a cryptographic hash of the entire entropy pool.

This seems reasonable, but I wonder whether SHA512 is overkill. Would I be better off extracting the least significant bits of each statistic into a bitstream? If so, how many? Are there any other issues with my approach?

Answer 1

What you are doing sounds a lot like what the /dev/random and /dev/urandom or the PRNGD on many systems already do: those systems take an arbitrary large sequence of numbers (from a true hardware random number generator if available, or else from environmental noise such as keystroke timing) and feed it into a CSPRNG. The CSPRNG internally maintains an "entropy pool", and thoroughly "mixes" the pool whenever it produces a new output value. The output is made available via /dev/random and /dev/urandom .

• Have you considered possibly using the /dev/random or PRNGD already running and available on your system?
• Have you considered possibly downloading the source code to some CSPRNG that has already been written, tested, debugged, and checked for security flaws, rather than writing your own from scratch?

At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool

Would I be better off extracting the least significant bits of each statistic into a bitstream?

Rather than collecting a batch of data, hashing it, and then feeding that into the CSPRNG, it's better to simply feed the batch of data directly onto the CSPRNG. (The CSPRNG already handles the "hashing" stuff internally). At best, your hash operation preserves whatever entropy exists in the source data; at worst, it is unnecessarily throwing away some of that entropy. SHA512 is an excellent hash function, so hashing the incoming data with SHA512 is OK but unnecessary. (The idea of "XOR all the collected bits" seems to throw away too much entropy).

The high-order bits of most of those statistics have very little usable entropy -- however, assuming the CSPRNG is properly written, that doesn't hurt anything. A properly written CSPRNG is just as secure even when one of the inputs doesn't have any entropy -- such as an input that is always "000000000000000...". If, hypothetically, you are forced to cut back on the number of inputs to your CSPRNG in order for some reason, you would want to preserve as much entropy as possibly by cutting out such zero-entropy (all-zeroes) and low-entropy (high-order bits of these other stats) before cutting out higher-entropy sources.

When the pool reaches 64KB...

Wow. That many bits in the entropy pool is overkill in our universe.

Keys are generated by computing a cryptographic hash of the entire entropy pool.

Yes, that's how most CSPRNG produce their output values.

• FreeBSD and AIX implement /dev/random using the Yarrow algorithm
• OpenBSD implements /dev/random using an algorithm based on RC4 (is this the same as ISAAC ?)
• Fortuna
• My understanding is that many other CSPRNG implementations have a way to feed in more bits of entropy.

(I'm re-using a lightly edited of a previous answer I wrote, PRNG taking advantage of very large seed )

Answer 2

Which I'm no expert here, I'm pretty sure you shouldn't do things like extract the least significant bits from you data (or even xor them). Imagine you'd use something like clock and look at the least significant decimal digits: on my computer the number always ends with three zeros. Similar things could happen to you data.

At the same time, using SHA-512 is surely an overkill. As you 100 bytes most probably don't have 64 bytes of entropy, you should use a shorter hash. While MD5 isn't recommended for new designs, I could imagine it could do the job (things like broken w.r.t. collisions are meaningless here). Maybe SHA-1 could be just right (and possibly much faster than SHA-512).

That said, I'd recommend to read this paper.

Answer 3

I would avoid the approach. While at first it looks like you're collector the most diverse entropy, most "sources" you use tend to create repeatable or sequentially alike data. This is underlined by the fact that you're collecting the stats at fixed intervals.

If your goal is to create real entropy for key generation you should be aware of the security implications as it's bound to happens that frequently, not enough entropy is introduced into your hash and your hash is bound to reduce itself to a smaller group of colliding hashes.

The question if SHA512 is overkill underlines the issues with your approach, as a hash can only be as safe as the entropy the sources provide. Since your hash is only represents the final result of your data, it wraps it up to a bit-length to something smaller, and therefore more predictable.

You might as well simply XOR all the "collected bits" when incoming, and achieve a better randomness than hashing the aggregate data into a hashed result with whatever algorithm.

My 2 cents: poll the data at random intervals, and poll random pieces from the incoming data, XOR-ing multiple sources randomly too (and not all at the same time). Finally, cut a fixed piece of bits from a random position and store that. This approach is not only faster, but also produces less predictable and more random data. If implemented correctly, this would enable streaming encryption/decryption due to it's speed. Hashing can - even when modern computers are really fast - waste valuable time that - when it's summed up to the time lost per day, week or month - something you would want to avoid whenever possible. After all, in cryptography and everywhere else: every microsecond counts.