The Goldreich-Goldwasser-Micali Construction with bad PRGS

Question

I understand that if we have a secure PRG then the Goldreich-Goldwasser-Micali construction gives us a secure PRF.

However, what I've not been able to find much material on is how will the GGM construction fairs when the PRG is less than perfect.

Suppose we used AES-128 in CTR mode as the PRG to generate 256-bits of output for use in this construction. I don't think anyone would argue whether this was secure or not. They might say it's horribly slow but let's ignore that for now.

What happens if we replace AES-128 in CTR mode with a bad PRG. One that has a bias that's significant? Let's say we had a bias in our PRG of $ \epsilon = {1\over2^{16}}$. That would be a pretty terrible stream cipher and completely broken normally.

However, my intuition leads me to think the whole construction might even be secure with such a terrible PRG because we're only producing a stream double the key length. As such, the set of keys fed in to the next layer should still be pretty much uniform.

In fact, I'm tempted to claim that as long as there's no attack that can distinguish the PRG using only the first $2 \times k$ bits, the overall scheme is secure.

The argument goes like this:

1. The key at the top of the tree is seed to the prg. This is selected at random from the set of all possible keys.
2. We then feed this seed in to the prg. The prg can not be distinguished from random with the $2 \times k$ bits generated from it.
3. Thus the two cells below it can not be distinguished from random.
4. One of these cells then becomes the new key to the next layer down.
5. Given that this key could not be distinguished from random we replace it conceptually with a real random key.
6. The situation is now symmetric with step one, except we're now one step removed from the root of the tree.
7. We can now re-run steps 1-6 for each level in the tree and have a provably secure prf from a horribly bias prg.

That seems like it proves too much to me; it's an absurdly strong result.

Am I right or does the construction succumb in the presence of a wonky PRG in a way I haven't anticipated?

Answer 1

I know I'm answering my own question, but there's actually quite a nice worked example which completely refutes my question. I thought I'd share.

Suppose I use the GGM construction with the underlying PRG being RC4.

RC4 has a lot of problems, one of which is the fact that the second byte is basically twice as likely to be zero than it should be: $2\over 256$.

For longer key-streams, the biases settle down and the cipher can be used relatively safely. Google, for example, uses RC4 for in SSL.

However, the GGM really punishes RC4. Every stream that RC4 generates is short. An attacker can use this to distinguish the resulting PRF from random very easily. Here's how.

The attacker requests that you compute your PRF on values of his choice. He can craft those values so that the tree that is navigated in GGM always returns the left hand side of the expanded bit stream. These are the first bytes out of RC4.

He can then simply look at the second byte of the result of PRF(x) and count the number of times its zero. After a pretty trivial number of queries, he's clearly able to distinguish the PRF from a random function.

We're now in a position where the GGM has actually has poorer security than the underlying PRG! This nicely refutes my question.

The message is that a bias in the PRG should be assumed to render GGM insecure.