What PRG expansion factors are safe?

Question

I'm trying to better understand the "cost" of randomness usage/generation in practice. I understand that generally, some (small) amount of "true" randomness is generated, and then a CSPRNG is applied to expand this out to a larger amount of pseudo-randomness.

I'm curious as to precisely how these "small" and "large" amounts are related in practice. If I want $k$ pseudo-random bits, that an adversary can't distinguish from random with less than $2^{\lambda}$ time, how many truly random bits do I need to seed my PRG with?

I understand this may depend on the particular CSPRNG I use. If it does, how does one find out this conversion factor for a particular CSPRNG.

Answer 1

In practical terms, you can take 32 bytes, and safely expand them into up to $2^{128}\cdot64$ bytes using ChaCha, which is more bytes than you can actually expand anything into even if you could enlist the help of all the queen's horses and all the queen's men even if they weren't busy putting Humpty together again.

Some practical PRGs are more limited. For example, by the birthday paradox, the distinguishing advantage against AES-256 grows with $q^2\!/2^{128}$ where $q$ is the number of blocks of output, so it falls apart around $2^{64}$ blocks and you should really limit yourself to well below that many, say $2^{32}$ under a single key in order to keep the distinguishing advantage below $1/2^{64}$. This is because AES is a permutation, and a permutation of 128-bit strings at that; in contrast, ChaCha is a function into 512-bit strings.