Understanding PRGs: How can we expand randomness?

Question

I am getting a bit confused with the PRGs employed in cryptography.

Basically, a PRG is used to expand a random sequence (mostly a key) of length s to a length n>s, still looking random. Now while this is obviously not possible in a mathematical sense, the idea is that we achive reasonable randomness, meaning that an efficient distinguisher cannot tell the larger sequence apart from random (so we achieve randomness in a computational sense). My question is do we really?

Consider this example:
Input: k: {0,1}^2
PRG G: {0,1}^2 -> {0,1}^4
Output: k' = G(k) : {0,1}^4

This means our initial key can take on 4 possible values. Allthough our derived key covers a range of 16 values, it can only take on 4 out of these 16 values, since the PRG is deterministic. So what hinders me from mapping possible initial keys to output keys as an attack? I would thereby be able to reduce the search space from 16 to 4 values. So basically invert the expansion?

I would now argue that we do not achieve any expansion of randomness, as long as we have memory to store these mappings. Since there are some PRGs which are commonly used, this would provide an incentive for collaborative projects to map all or at least part of the keys to break security for many applications.

I am certain that I must have gotten something wrong above, but I cannot figure out where my error lies. Could you please help?

Many Thanks

Answer 1

A cryptographically secure PRNG starts with an initial state (often called "seed") which is unknown to the attacker. We can consider the state to be a sequence of n bits. From that state, the PRNG works deterministically and outputs a lot of bits, the internal state being updated continuously.

There is a generic attack which can be theoretically applied to all PRNG, which is called "exhaustive search" or "brute force": namely, try all possible values for the seed, until a match is found with the observed output. The cost of this attack is, on average, 2^n-1 "tries" (on average, you have to try half of the possible seed values before hitting the right one). This generic attack is thwarted by making n large enough that 2^n-1 is a ludicrously large value. Good algorithms traditionally use n = 128 or more, which is large enough.

Of course, with a 2-bit initial state, exhaustive search is very fast: only 4 seed values are possible !

So we need a large initial state. The hard part is then designing a PRNG such that the generic attack is also the best attack; i.e. that there is no "shortcut" using the PRNG structure which allows for efficiently pruning out a large proportion of candidate seeds without trying them all. This is hard and is not well substantiated by mathematical theory: mathematically, there is no proof that a secure PRNG can even exist at all; so we put together a lot of "scrambling operations" which mix data together and we hope for the best. Even harder is to design such a mixture so that the result is not only secure, but also fast. Currently, the best we can do is to have some cryptographers put a lot of thinking in a design, and then submit it to many other cryptographers who try to break it for some years. Surviving designs are then deemed "probably secure". See the eSTREAM portfolio for such an effort.

Answer 2

I would now argue that we do not achieve any expansion of randomness, as long as we have memory to store these mappings.

You are correct if you are only expecting a 4-bit output from your PRG.

Remember the definition of a secure PRG - given two inputs, one which is truly random and one which is generated using a PRG, there exist no adversary that can efficiently distinguish between the two.

Given a PRG that can produce an output of an arbitrary n-bit length, as is common with stream ciphers, I think that you are severely underestimating the amount of storage needed to fully map all the possible outputs of a PRG.