Is a tree of CSPRNGs secure?

Question

Given two CSPRNGs $A$ and $B$ (of possibly the same family/algorithm), where $A$ is properly seeded from a high-entropy source, can $A$ be used to seed $B$ without compromising the security of either? Moreover, could a tree of such CSPRNGs rooted at $A$ be formed such that all generators can be used independently without revealing information about any other?

My loose attempt at proving this claim uses properties/assumptions gathered from here, here, and here:

Let $A$ be the root of a tree of CSPRNGs, each seeded by its parent. Assume that given the states of a subset of the non-root CSPRNGs, one can learn some secret property of one of the other non-root CSPRNGs not in the set.

Let $A'$ be an unknown source of randomness. By constructing a similar tree from its output and knowing the states of all non-root CSPRNGs, one can test for the above property to distinguish $A'$ from true randomness with non-negligible probability. This contradicts the indistinguishability of the CSPRNG, so it must be infeasible to find such a property.

Also (less rigorously):

Let $A$ be the root of a tree of CSPRNGs, each seeded by its parent. Assume that given the seeds and states of a subset of the non-root CSPRNGs, one can learn some secret piece of information about the root $A$. Then one can predict with non-negligible probability a bit of $A$'s past or future output other than the known seeds. This contradicts the security of the CSPRNG, so no such information can feasibly be obtained.

Together, these would mean that any CSPRNG in the tree is secure, needing only to trust the CSPRNGs in the path from it to the root.

Are these proofs and my conclusion correct for general CSPRNGs?

---

Note: A trivial counterexample for non-cryptographic PRNGs is the linear congruential generator, for which $A$ and $B$ would share identical states and produce identical results.

Answer 1

Yes, this is basically the Goldreich-Goldwasser-Micali construction of a PRF from a PRG. All leaves of the tree appear independently random, and furthermore the construction works even if the tree has exponentially many leaves (note that it is possible to compute the value at one leaf without computing the entire tree, by focusing just on the root-to-leaf path).

You can find a formal proof of security for this construction in section 6.3 of my book (PDF link).

Goldreich, Oded, Shafi Goldwasser, and Silvio Micali. "How To Construct Random Functions." Foundations of Computer Science, 1984. 25th Annual Symposium on. IEEE, 1984.

Answer 2

A PRNG maps a $n$ bit seed to an $m$ bit long output. An ideal PRNG maps seeds to outputs as if for every seed a corresponding element is chosen randomly from the set of all $2^m$ $m$-bit strings. (Specifically "randomly" meaning every string is independently sampled from a uniform distribution.)

If the number of $m$-bit outputs ($2^m$) is much larger than the number of possible seeds ($2^n$) then you should expect that no two seeds produce the same PRNG output. If $m < 2n$ then there are likely birthday collisions, making this statement untrue. No practical CSPRNG will have outputs this short or this long, so this is a non-issue. On the other hand, a bad CSPRNG might diverge from an ideal PRNG if (for example) it uses a construct with equivalent keys and this translates to equivalent seeds.

If you use any number of non-overlapping $n$-bit blocks of output from any ideal PRNG or from different independently seeded PRNGs then there will (should) be no correlation between blocks.

Non-overlapping blocks within the same PRNG's output should be independent. And outputs from PRNGs with two different seeds should be independent from each other. Therefore

Whatever reasoning we use about the $n$-bit random strings should apply equally well to two non-overlapping blocks from the same PRNG or two blocks from different PRNGs. So I assert all we should care about is the size of $n$ and how many PRNGs we try to initialize. (Assuming our PRNG choice is good.)

As a rule of thumb we say there is likely a collision (two equal independent samples) if we sample $2^{n/2}$ values from a uniform distribution of $2^n$ elements. The approximate probability of one or more collisions with $k$ samples of $n$-bit seeds is

$$P(k, n) = 1 - e^{{-k^2} \over {2^{n + 1}}}$$

For larger values of $k$ collisions become more likely. This means that instantiating more and more PRNGs increases the likliehood that two seeds will be produced twice. By increasing the number of bits used for the seed we can decrease the probability of collisions.

Once you get a collision between PRNG seeds you'll have different PRNGs producing the exact same output. This means that these PRNGs will spawn identical child RNGs and they'll spawn identical descendants themselves. It doesn't matter if it's a tree structure or PRNG A seeding PRNG B seeding PRNG C and so on. (The latter is a tree where all nodes have exactly one child.)

The repetition may start out as cyclic or it may begin between nodes on different "branches", but the finite nature of the problem means it will eventually happen if we're not limited with how high we can make $k$. However the finite nature of the real world limits how high we can make $k$, so we can use relatively small values of $n$ (512 bits if you're super paranoid) to rule out the possibility of it happening unless there is flaw in the CSPRNG design or an implementation error. (Or some person reuses the same seed for the root PRNG of two trees. Or a hacker or cosmic ray corrupts your RAM. Or...)

Terminology note: Some people use the term seed to refer to mixing additional entropy into an already initialized PRNG. For others it means only the parameter used to initialize a PRNG. I use the second choice.

CSPRNG note: I assume we have access to a CSPRNG implementation with a large enough state to accept long seeds. And I assume it is backtracking resistant if that is a concern for you. I don't think I need to go into how if a CSPRNG's state is leaked all future outputs will be compromised as well as outputs of its descendants. (This is an obvious property of any fully deterministic system.)