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

On Thu, 06 Apr 2006 17:58:43 +0000, Unruh wrote:

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.

My response was, like I said, a qualification. When I talked about a
system clock, or system time, I just meant any source available to the
system that is increased in a monotonically predictable way - hence my
reference to tick counters. My apologies for having been sloppy in this
respect.



.

Relevant Pages

  • Re: The Blum-Blum-Shub generator and a guessable seed
    ... to generate the same random number output as the original BBS ... The system time is an awful seed. ... It contains next to no entropy from the ... point of view of an attacker. ...
    (sci.crypt)
  • Re: The Blum-Blum-Shub generator and a guessable seed
    ... The system time is an awful seed. ... It contains next to no entropy from the ... point of view of an attacker. ... "The initial seed x_0 is derived from the system time in milliseconds." ...
    (sci.crypt)
  • Re: [opensuse] Time stability
    ... gps clock directly, instead of system time. ... As a result of our synchronization, we do that: read the system clock ... do measurements to ensure this is really so, ...
    (SuSE)
  • Re: System time not syncing with the domain
    ... >> the event log I get the following error... ... >> The time service has not been able to sync the system time X seconds ... The system clock is unsynchronized. ...
    (microsoft.public.windowsxp.embedded)
  • [PATCH] firewire: adopt read cycle timer ABI from raw1394
    ... in firewire-core's userspace ABI. ... The argument to the ioctl is ... * and also the system clock. ... * isochronous packet as a system time with microsecond accuracy. ...
    (Linux-Kernel)