fighting entropy hunger (Of a PRNG)

[a_Lex]

The scenario is the following - some relatively large amount of entropy is required by an automatic system (no human around to wiggle mice and harass keyboards).

The PRNG is, basically, Fortuna as described in "Practical Cryptography".

adversary can influence the system, mostly the network adapter (can send arbitrary packets to it and selectively drop incoming and outgoing packets)

The adversary can perform any amount of measures of conditions inside and outside the chassis (including taking external measures of HDD behavior), but won't go for sophisticated power and RF emission analysis.

If that wasn't bad enough, this is a first boot up scenario, and there is no human input.


So, this begs for some tweak to the "classic" entropy collection routine...

What would you suggest?
_________________
A good walker leaves no track behind.

The wise man is merciless

[Dwonis]

I'm not entirely clear on the scenario (can you provide more details), but does anything stop you from writing a unique seed to the hard drive or flash during manufacturing?

[a_Lex]

Well, what else I can add to this scenario...

No, nothing forbids the protagonist from shipping the machine with randomness (sort of seed-file), but nothing prevents the adversary from attempting to get that unique seed prior to actual boot up...

Oh, here is one thing what I let out (damn this weak coffe) - the adversary will be able ti inspect the machine before boot-up. And though he is unlikely to install sophisticated stuff (RF analysis, sci-fi bus tricks), he will look through the hard drive checking for "seed files", and do some other mundane-but-effective stuff to recover as much data as possible.
_________________
A good walker leaves no track behind.

The wise man is merciless

[Dwonis]

I think you need to add space-age, military-grade security.

You are still being very vague about what the bounds of the problem are.

What about adding a hardware RNG? What about audio-entropyd? Can the attacker do anything once the machine is installed (e.g. the janitor), or is he limited to gathering information only before that (e.g. the shipping guy)? How many of these might be applicable?

There is a lot of information on the web about generating random numbers. What have you already looked at, and why won't that work?

If this is a hypothetical scenario here for our amusement, I think you need to specify precisely what the limits of the protagonist and the adversary are. On the other hand, if this is something you're actually implementing, then you should come out and say, in detail, what it's for.

[a_Lex]

[a_Lex]

Any other ideas on how to fight entropy shortage?
_________________
A good walker leaves no track behind.

The wise man is merciless

[Dwonis]

I think it's time to clarify the roles that entropy and PRNGs play in generating random numbers.

First, let's talk about entropy. Consider the following game played between two acquaintances at a busy restaurant: Alice chooses a number (R_i) between 1 and N, and writes this number onto a paper napkin, making sure that Bob can't see the number she writes. Bob, knowing N, writes his guess onto his own napkin. Then, both Alice and Bob reveal their napkins. Bob wins if the number on his napkin matches the number on Alice's napkin. Otherwise, Alice and Bob each write down new numbers and the process is repeated. Alice wins if Bob fails to guess a number correctly before their food arrives.[1]

It is in Alice's best interests to try to choose each number independently, because if Bob can find a predictable pattern in her numbers, he will have a better chance of winning the game. This brings us to a definition of entropy:

* Let P be the probability that Bob will guess R_i on any given trial. Then, the entropy in R_i is log2(1/P) bits.[2]

In other words, entropy is an measure of how unlikely it is that an adversary will be able to predict the output of your random number generator.[3]

About PRNGs...

Cryptographically secure pseudorandom number generators (PRNGs) are deterministic functions that are designed generate numbers that are indistinguishable from random numbers, assuming certain limits on the resources of an adversary. Because they are deterministic, the entropy of the complete output of a PRNG is never more than the entropy of its input.[4]

* So, if an adversary can predict the input to your PRNG (by reading the hard drive, messing around with the network controller, taking measurements from inside and outside the chassis, etc.) then he can predict the output just as easily, regardless of what algorithm you use to scramble your input.

What you need to do is to find some source of input that will remain secret to your adversary. A hardware RNG might provide that. On the other hand, perhaps you can redesign your system so that it doesn't need to generate a random secret until after it has collected the necessary entropy.

Not every security problem can be solved with cryptography. This may be one of those problems.

Cheers!
--
Footnotes:

[1] N is going to be reasonably small. Before the game starts, Alice selects the number N, writes it onto another napkin, and sets this napkin on the table where both she and Bob can see it. N must be small enough that it can be written on the napkin, but large enough that Bob is unlikely to guess R_i within the allotted time. Also, Alice knows that Bob has played this game with her other friends before, so if Alice can win with a small N, she will have something to brag about.

[2] For comparison, the length of R_i is simply log2(N) bits.

[3] This definition of entropy actually depends on how smart the attacker is. Designers of security systems like to assume attackers who are very smart (at design time, every attacker is from the future) so when they talk about "entropy", they are usually referring to worst-case or minimum entropy ("min-entropy"), not Shannon entropy.

[4] This is under the standard assumption that an attacker can find out your PRNG algorithm ahead of time (Kerckhoffs' assumption). If you wanted to ignore Kerckhoffs' assuption, then you could say that a PRNG can add up to length(PRNG) bits of entropy to its input. However, that would mean that you would basically be using the PRNG as a one-time pad, so you would be required to never reuse your PRNG algorithm, and to keep it a secret. Obviously, you want to be able to reuse your PRNG algorithm, and it's hard to keep an algorithm secret (it's doubtful that even the U.S. military relies on the secrecy of its crypto algorithms) so the safe assumption is that a PRNG adds no entropy to its input.

[a_Lex]

Oh, well, I am back.

Today I was reminded of this little "hypothetical scenario" (which is odd and makes me feel uneasy).

So, a box, w/o seed file has to gather enough "cryptographic-quality" (as in [3]) entropy to securely seed and continuously re-seed Fortuna.

No user, no mouse, and carefully monitored network traffic.

HDD is also inspected (but the contents are not modified)

My idea is

to equip this hypothetical box with two hardware RNGs, for instance a Quantis plus an SG100 TRNG would look nice (well, yeah, spending $1500 on Quantis, hurts, so one might consider the option of filling the ever-available serial and USB ports with 2-3 cheaper HRNG, for instance combo of SG100 TRNG, RM-60 and a Pars Mutaf Wif-Fi gizmo seems like a decent "tight-budget" solution.)

If the system has via padlock we can count on yet one more more-or-less decent HRNG.

Then, the program environment has HAVEG(E) implemented. HAVEG output is used as merely one more source of randomness for the entropy pool.

Now, we start the system, perform some disk-diagnostics and self-test, and begin polling the entropy sources (our two or more HRNGs, HAVEG, as well as disk behavior, interrupts, date/time, discrepancies in driver behavior, maybe some other sources if available).

All theese sources (at least two hardware random generators, preferably different, HAVEG, disk behavior discrepancies etc...) are used to fill up the Fortuna entropy pool.

To make things even less deterministic, some source polling tricks may be introduced.

For instance, we may check the last two bits of entropy pool contents:

00 - wait X "time" before next polling, poll HAVEG first and all the rest sources afterwards

01 - wait X "time" before next polling, poll all sources but HAVEG (this vastly changes HAVEG state), and only then poll HAVEG

10 wait 2X "time" before next polling, poll HAVEG first and all the rest sources afterwards

11 wait 2X "time" before next polling, poll all sources but HAVEG (this vastly changes HAVEG state), and only then poll HAVEG


Oh, and, one more thing...

being slightly paranoid and having a modern box with at least P IV and 1 Gb RAM, we can afford to have a LARGE entropy pool.

Will this system set-up securely seed its Fortuna despite the attacker's efforts?
_________________
A good walker leaves no track behind.

The wise man is merciless

[data]