Cryptographically strong pseudo-random seq. generators

Question

If a pseudo-random sequence generator is built so that it uses an n-bit seed and outputs a string that is of length x. Let's say one wants to generate a bit string of length y and uses the previous PRSG over and over to obtain y bits out of the x bits produced per run. In order to stop repetitions the last n bits of each x bit output is used as a seed for the next output. Why is this not cryptographically strong?

Answer 1

With the problem as stated, the main weakness is that knowledge of the 873th to 1000th bits of the sequence is enough to trivially determine its 1001th to 100000th bits. That's because these 873th to 1000th bits are both part of the output and used as seed for the rest of the sequence.

Update: In order to test if a sequence is produced by the stated generator, or uniformly random, a judge

• asks for one sample sequence R;
• extracts the first 1000 bits, giving S;
• repeat 99 times: seed PRSG with the last 128 bits of S, generate 1000 bits, and append them to S;
• announce that R was likely produced by the stated generator iff S equals R.

In theory, the judge has odds $2^{-99000}$ of announcing that a sequence was produced by the stated generator when it was uniformly random (and never errs in the other direction). If the judge had enough computing power for an average $2^{127}$ PRSG, he could further reduce these ridiculously low odds to about $2^{-99872}$ (or lower if the PRSG is extremely poor) by brute-forcing the initial 128-bit seed.