# The Goldreich-Goldwasser-Micali Construction with bad PRGS

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?

-
For 4, each of these cells then becomes the new key for its own subtree. $\hspace{2.17 in}$ For 7, you haven't at all accounted for the PRG having a noticeable efficiently-measure bias, $\hspace{.83 in}$ you've just accounted for it only stretching by a factor of 2. $\;$ – Ricky Demer Oct 9 '13 at 18:38
I don't think I need to. I've already said that given any key, the cipher is indistinguishable from random with just $2 \times k$ bits of output. That's a premise of the argument. However, that doesn't stop the generator being completely distinguishable at, say, a few thousands bits. So I don't think that objection weighs on the proof! – Simon Johnson Oct 9 '13 at 19:24
Since you didn't name the thing actually being plugged into the GGM construction, I suppose "the PRG" defaults to "the pretty terrible stream cipher", which would mean I was wrong about 7. $\:$ I still believe I was right about 4, although otherwise your claim holds, pretty much by your argument. $\:$ This should not be a so surprising, since your claim's assumption amounts to "the thing actually being plugged into the GGM construction is a secure PRG". $\;\;\;$ – Ricky Demer Oct 9 '13 at 20:44
More generally, as described on page 38 of wisdom.weizmann.ac.il/~naor/COURSE/fc0607_lect15.ppt, lots of things like that are equivalent to each other. $\;$ – Ricky Demer Oct 9 '13 at 20:45
The pseudo-random generator used in GGM doesn't output a lot of bits. It outputs very few bits. But anyway, to distinguish the pseudo-random function from a random function, a bias in the PRG output is probably sufficient. Evaluating the function at a bunch of points would probably allow you to detect the bias. (Perhaps one could imagine a bias that is "self-correcting", so that the GGM construction fixes the PRG, but I wouldn't expect that in general.) – K.G. Oct 9 '13 at 20:54

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.

-