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?
1 Answer
$\begingroup$
$\endgroup$
4
With the problem as initially stated (that is x = 1000, y = 100000, n = 128), 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/adversary/distinguisher
- 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 produced by the stated generator if S equals R (otherwise announces that R was random).
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 even lower if the PRSG is extremely poor) by brute-forcing the initial 128-bit seed.
-
$\begingroup$ Thanks fgrieu. One more question, so if the function is G(X) then how can a judge distinguish the distribution of G(X) from Y where X is the uniform distribution for the seed space and Y is the uniform distribution of the binary strings of length 100000? $\endgroup$– user1829Apr 2, 2012 at 6:15
-
1$\begingroup$ In the standard way: by seeing whether the 1001th to 100000th bits are as determined by the 873th to 1000th bits. $\endgroup$– user991Apr 2, 2012 at 6:49
-
$\begingroup$ See updated answer. Would you mind disclosing in which curriculum this exercise was asked, and why you found it difficult? $\endgroup$– fgrieu ♦Apr 2, 2012 at 7:05
-
$\begingroup$ Some crypto lectures I found online. Thanks for the help! $\endgroup$– user1829Apr 2, 2012 at 23:26