R help - May 2009 - can you tell what .Random.seed *was*?

Dear R-help,

Suppose I write a script that looks something like this:

#### script.R

set.seed(something)

x <- rnorm(100)
y <- runif(500)
# bunch of other stuff

save.image()

### end of script.R


Now, I give you a copy of my script.R (with the set.seed statement
removed, of course) together with the .RData file that was generated
by the save.image() command.



Question:
1) can you tell me what my original set.seed() value was?  (I wouldn't
be able to figure it out, but maybe someone can)

2) is it possible *in principle* to figure out what set.seed was,
given the above?  (OK, being able to figure it out in 2*10^68 years
doesn't count, but within a couple months is acceptable.)

3) does the answer change if there is a

remove(.Random.seed)

command right before the save.image() command?


Any thoughts would be appreciated.

Cheers,
Jay







***************************************************
G. Jay Kerns, Ph.D.
Associate Professor
Department of Mathematics & Statistics
Youngstown State University
Youngstown, OH 44555-0002 USA
Office: 1035 Cushwa Hall
Phone: (330) 941-3310 Office (voice mail)
-3302 Department
-3170 FAX
E-mail: gkerns at ysu.edu
http://www.cc.ysu.edu/~gjkerns/

On 5/14/2009 3:36 PM, G. Jay Kerns wrote:
> Dear R-help,
> 
> Suppose I write a script that looks something like this:
> 
> #### script.R
> 
> set.seed(something)
> 
> x <- rnorm(100)
> y <- runif(500)
> # bunch of other stuff
> 
> save.image()
> 
> ### end of script.R
> 
> 
> Now, I give you a copy of my script.R (with the set.seed statement
> removed, of course) together with the .RData file that was generated
> by the save.image() command.
> 
> 
> 
> Question:
> 1) can you tell me what my original set.seed() value was?  (I wouldn't
> be able to figure it out, but maybe someone can)
The only way I know is to test all 2^32 possible values of the seed.  I 
think cryptographers would know faster ways.
> 
> 2) is it possible *in principle* to figure out what set.seed was,
> given the above?  (OK, being able to figure it out in 2*10^68 years
> doesn't count, but within a couple months is acceptable.)
I think the brute force search would take about 4-5 days on my old 
computer, so a fast one could do it in a few hours.
> 
> 3) does the answer change if there is a
> 
> remove(.Random.seed)
> 
> command right before the save.image() command?
Not with the brute force search.  The cryptographers would probably be 
able to make use of the random seed pretty well.

Now, if the seed was removed just before the values were generated, the 
seed would be generated from the system clock.  If you knew the time 
that this occurred approximately, the search could be a lot faster.

On the other hand, if there was an unknown large amount of work between 
the time of seed generation and the generation of the values x and y, it 
would be much more difficult to brute force the solution, because most 
of the values of .Random.seed are not reachable either by the clock 
method or set.seed, they are only reachable by lots of calls to the 
underlying generator.  So for each seed value you'd need to do every 
possible number of RNG generations before generating x and y.

Duncan Murdoch


> 
> 
> Any thoughts would be appreciated.
> 
> Cheers,
> Jay
> 
> 
> 
> 
> 
> 
> 
> ***************************************************
> G. Jay Kerns, Ph.D.
> Associate Professor
> Department of Mathematics & Statistics
> Youngstown State University
> Youngstown, OH 44555-0002 USA
> Office: 1035 Cushwa Hall
> Phone: (330) 941-3310 Office (voice mail)
> -3302 Department
> -3170 FAX
> E-mail: gkerns at ysu.edu
> http://www.cc.ysu.edu/~gjkerns/
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

On Thu, May 14, 2009 at 3:36 PM, G. Jay Kerns <gkerns at ysu.edu>
wrote:
> set.seed(something)
> x <- rnorm(100)
> y <- runif(500)
> # bunch of other stuff
...
> Now, I give you a copy of my script.R (with the set.seed statement
> removed, of course) together with the .RData file that was generated
> by the save.image() command.
...
> 1) can you tell me what my original set.seed() value was?...
> 2) is it possible *in principle* to figure out what set.seed was,
> given the above?
Set.seed takes an integer argument, that is, 2^32-1 distinct values
(cf NA_integer_), so the very simplest approach, brute-force search,
has a hope of working:

whatseed <- function (v)  {
   i <- as.integer(-2^31+1); max <- as.integer(2^31-1)
   while (i<max) { set.seed(i); if (runif(1)==v) return(i); i<-i+1 }
}
> (OK, being able to figure it out in 2*10^68 years
> doesn't count, but within a couple months is acceptable.)
set.seed(-2^31+100000)
system.time(whatseed(runif(1)))
   user  system elapsed
   1.53    0.00    1.53

2^32*(1.53/100000)/3600
    => 18.25
18 hours
> 3) does the answer change if there is a
> remove(.Random.seed)
> command right before the save.image() command?
Depending on which RNG algorithm (RNGkind) you use, there may be
cryptographic techniques that are more efficient than brute-force
search, especially if the full internal state (.Random.seed) is
preserved.

This all assumes that the seed is set *only* with set.seed.  If
.Random.seed is modified directly, there are many more possibilities
for most of the RNGs.

             -s