Random number challenge

Andrew Jorgensen andrew at jorgensenfamily.us
Thu Jun 12 09:24:27 MDT 2008


On Thu, 2008-06-12 at 09:08 -0600, Stuart Jansen wrote:
> On Wed, 2008-06-11 at 19:54 -0600, Andrew Jorgensen wrote:
> > This comes up every month at PLUG (for door prizes) so I thought I'd
> > ask here.  What's an easy to remember way to generate a random number
> > between 1 and some given number.  Language doesn't matter so long as
> > the code is easy enough for someone to remember the entire thing and
> > type it up at the drop of a hat.
> 
> The problem with most solutions post so far is that they depend on a
> pseudo-random number generator. That can be okay if the algorithm is
> statistically random and properly seeded. Unfortunately, most
> programmers that resort to something like rand() aren't able to evaluate
> the quality of the random number generator used, not are they likely to
> pick a good seed value.
> 
> For example, $PID is a poor choice because you're probably going to be
> running on a laptop. If you follow more of less the same process every
> time you boot your laptop for Plug, you'll very likely to end up with
> the same $PID. Now one could argue that's acceptable because the number
> will also be assigned randomly. I'm personally not comfortable with that
> assumption, however. Numbers would probably be assigned based on
> seating, and over time people tend to gravitate toward their favorite
> spot. Worse yet, a determined observer could determine a pattern and
> careful choose his seat to game the system.

I see this as a problem only if someone can use it to significantly
increase their chances of winning.  That just doesn't sound possible to
me.  The attacks you proposed so far all depend on all conditions being
exactly the same twice.  Last night, for instance, we had people not
count off if they weren't interested in the prize.  This would be
extremely hard to fix.

> Instead of compensating for these weaknesses, I propose abandoning the
> psuedo-random number generators and instead using a cryptographically
> appropriate true random number generator:
> 
> #!/bin/bash
> CEILING=20
> echo $[ $(od -t u4 /dev/random -N 4 -A n) % $CEILING + 1 ]

This completely fails the can-Andrew-remember-it test. :-)

So far I like the python one (though I agree that PID isn't a great
seed) and the bash one.  How is bash's $RANDOM seeded?

The trouble with seeds is that for normal pseudo-random algorithms if
you start with the same seed you will get exactly the same sequence of
numbers.  Emphasis on the pseudo.  But if there's a decent seed or if
the algorithm gathers some other random data to seed each execution then
it's good enough for door prizes.

What's the process on the binary grab bag?  It's been a while.




More information about the PLUG mailing list