Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
Your pooling algorithm looks strange. Why don't you use a fortuna like design? –  CodesInChaos Jul 10 '12 at 13:16
    
@CodeInChaos I'd never heard of it. So I use hash(entropy) as the key and compute AES(counter, key) where the hash is the key? Not really sure I understand the rest of the protocol. –  Polynomial Jul 10 '12 at 13:19
2  
The important part of fortuna isn't how it generates its output. The important part is how it accumulates entropy in different pools and mixes that entropy into generator state. –  CodesInChaos Jul 10 '12 at 13:35
    
@CodeInChaos That's the part I don't really understand. The Wikipedia article is a little vague. –  Polynomial Jul 10 '12 at 13:54
    
I'm concerned that your pool is losing entropy. You shouldn't need to gather nearly as much entropy as you seem to be trying to gather, which makes me worried. 64 bytes of entropy is sufficient to generate terabytes of random data with a sensible entropy pool design. –  David Schwartz Jul 11 '12 at 6:00
add comment

3 Answers

up vote 2 down vote accepted

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 )

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Where should the randomness for deciding the length of the sampling period come from? I agree with the approach from a practical standpoint, even though I doubt it will increase the amount of actual entropy being collected (you say it will produce "more random data"). –  SquareRootOfTwentyThree Aug 2 '12 at 5:36
    
When I write "more random data" I mean "more diverse". Hashing "noise" at frequent intervals will be more linear and predictive than sampling at "jittered" intervals. Which brings us to your interval-randomness question: how about a professional implementation? To be honest, I would avoid the concept of the OP all together and opt-in for a hardware random number generator instead of trying to "work around" the problem of not having access to something that provides real randomness. You'll have to agree that any shortcut towards REAL randomness is bound to cut big holes in any security efforts. –  user1364 Aug 3 '12 at 1:26
    
Your approach is overly-complex and arbitrary. There are well-understood ways to do this whose behavior is known and understood. XORing is much worse than hashing because hashing concentrates entropy while XORing can destroy it. A sensible entropy pool design makes the collection problem almost trivial, and no matter how good your collector is, a bad pool will still produce crappy output. –  David Schwartz Aug 10 '12 at 2:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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