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.

Re-reading my copy of Cryptography Engineering for the holidays, I was struck by the following question about the Fortuna RNG:

Why require an entropy source specify which pool a random event should go in?

(For code, see the add_random_event method in this python implementation).

The book discusses why you wouldn't want to just round-robin (or similar) all events, as a compromised source could force all good data into specific pools. This makes sense.

If I'm following the discussion correctly, each entropy source spreading it's events evenly across all pools is the desired behavior. This also makes sense.

What I don't quite get is why you couldn't attach a counter or similar to each entropy source and use that bit of Fortuna-managed data to route events. Seems like that would make it harder for an evil entropy source to influence particular pools, and simplify the accumulator interface a little bit. The cost is an additional bit of state per entropy source, which doesn't seem substantial.

Now since it seems obvious to me, I suspect there is a flaw in my reasoning. So, why is pool choice delegated to the entropy source instead of managed by Fortuna?

share|improve this question
    
"Seems like that would make it harder for an evil entropy source to influence particular pools" what do you mean by that? –  CodesInChaos Dec 24 '12 at 22:48
    
@codesinchaos that it would take more events (since it'd have they'd be evenly distributed, outside of the sources control) to force many events into one pool. –  Kevin Montrose Dec 25 '12 at 19:29
    
I still don't get your argument. Since the benign sources have separate counters that the evil source can't influence, the input from the begin sources is still evenly distributed no matter what the evil sources do. –  CodesInChaos Dec 25 '12 at 21:19
    
@CodesInChaos yes, an evil source could only direct its own input. I don't think Fortuna is broken or anything, just seemed odd to allow entropy sources to direct their events and was unsure why that is. –  Kevin Montrose Dec 25 '12 at 21:29
add comment

2 Answers 2

up vote 2 down vote accepted

I see essentially three ways to design this API:

  1. Take a pool
  2. Take a counter and have the accumulator calculate the pool as pool = counter mod poolCount
  3. Take a sourceId

Of these 2) seems clearly superior to 1) since the caller doesn't need to care how many pools there are, or how to distribute among the pools.

Comparing 1), 2) with 3) is more difficult, but I think for most situations 1) or 2) is preferable over 3).

If you look at a practical implementation, there will be three kinds of component, which don't trust each other: a) the pool b) some kind of service/daemon reading from the entropy source and feeding into the pool c) the actual entropy source.

Implementing method 1) is pretty easy for both pool and daemon:

  • The pool just needs to take care of thread safety, and feeds the entropy into the pool it's told.
  • The daemon just needs to take care of one counter per entropy source

Implementing method 3) is much harder in most circumstances:

You need some kind of sourceId which is different for each entropy source. Using simple integers is already annoying, since you now need a protocol by which a daemon can request a new sourceID. Then you need a process to deallocate them when the daemon terminates, which is problematic if it crashes.

But your biggest problem is that one malicious daemon could try to guess the sourceIDs of another daemon, possibly allowing it to feed that other daemon's data into specific (probably high-index) pools. This means that you need some kind of unforgeable sourceId, such as a random 128 bit value. But now keeping that counter becomes annoying for the pool, since it needs a hash table, not a simple index into an array. No biggy for high level languages, but annoying in c.

For an in process pool in .net or python seems seems OK, since you can use new object() to create an unforgeable ID and weak hashtables are available.

For a multi process setup, this seems like a bad idea. For example on a unixoid system you could have some deamon processes that gather entropy and feed it to the /dev/urandom device via a AddEntropy(counter, data) syscall. This would be much more complicated with a sourceId based design.

share|improve this answer
    
Off hand it seems like a process id (or equivalent kernel handle, if entropy sources are drivers) would be a pretty decent sourceId. But I guess the take away is that it's an engineering decision, not a cryptographic one then. –  Kevin Montrose Dec 24 '12 at 19:05
add comment

See the paper referred to in Bruce Schneier's blog at https://www.schneier.com/blog/archives/2014/03/the_security_of_7.html, which advocates selecting a fresh permutation of the pools for every N inputs, where N is the number of pools. If the adversary doesn't know the permutation, it makes it harder for him to direct the inputs he doesn't control to pools that will be used soon.

share|improve this answer
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.