# Understanding PRGs: How can we expand randomness?

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

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, 2n-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 2n-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.

• In practice the biggest problem is figuring out if the seed material contains enough randomness already. That's where real systems fail quite often. – CodesInChaos Jul 20 '13 at 19:06
• So if I get you right, it is correct that if we consider the security of a 1024 bit key which was derived from a 128 bit key by a PRG, we still only have 2^7 possible keys and therefore did not improve security in terms of complicating the "exhaustive search"? – Karl Hardr Jul 22 '13 at 8:58
• @Fab: no, there are 2^128 possible 128-bit keys. To have only 2^7 possible keys you need 7-bit keys. – Tom Leek Jul 22 '13 at 11:07
• @Tom my bad messed it up there, obviously 2^128. However my question remains. If you expand the key, can you argue that you are working with the same amount of entropy and therefore no expansion in terms of how hard it is to break, or is there actually some argument for expanding the key? (except for the obvious practical need for a larger key, eg for stream ciphers) – Karl Hardr Jul 22 '13 at 11:43
• If any piece of data D (e.g. a 1024-bit RSA key pair) is deterministically generated from a 128-bit value V, then yes, you can conceptually enumerate all possible values for D by enumerating the 2^128 possible values for V and running the same deterministic algorithm. However, 2^128 is way too large for this "conceptually" to become a "practically". – Tom Leek Jul 22 '13 at 12:35

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.