Re: The Blum-Blum-Shub generator and a guessable seed

Steven Jones <sjones@xxxxxxxxxx> writes:

On Mon, 03 Apr 2006 13:16:21 +0200, Kristian Gjøsteen wrote:

Thomas B. <thetom@xxxxxxxxxxxxxxxxxxxxx> wrote:
The initial seed x_0 is derived from the system time in milliseconds. Now
my question: When an attacker can guess (brute force) x_0, is s/he able
to generate the same (pseudo-)random number output as the original BBS
PRNG?

Yes. BBS output is a deterministic function of the input. If you know the
input, you know the output. The input is the seed.

The system time is an awful seed. It contains next to no entropy from the
point of view of an attacker.

I think that this has to be qualified. First, the entropy does not come
from the system time itself, but from the unpredictability associated with
the instant at which it is read. Second, the bits of entropy that can be
extracted at a single read operation will depend on how fast the system
clock is updated. On a system running at 1 GHz, the tick counter gets
updated so quickly that a single read can extract 16 bits or more worth of
entropy.

"The initial seed x_0 is derived from the system time in milliseconds."
This has nothing to do with the system clock. Also the system time is
updated usually far less often than once per millisec, or your computer
would be spending all its time updating the time.




.

Relevant Pages