AWK - Truly random numbers

Author

Truly random numbers

Ted Davis

2004-05-12, 7:19 pm

Somebody please check my reasoning on this before I put a lot of time
into writing a truly random password generator.

The random numbers generated by gawk, and most if not all other
languages, are actually pseudorandom.

If I take the last, or last two, digits from the time field of ping
reports of remote sites, I should get truly random numbers, one or two
digits at a time.

The IP addresses will come from a list of origin sites for spam I have
received, and sites closer than 100 ms will be removed. The gawk
script to extract the addresses has already been written and run, so I
already have the unchecked list.

I may be missing some regularity or other systematic error in the ping
time numbers - if anyone knows of any reason why this won't work as
intended, please enlighten me. Other suggestions for getting truly
random numbers would also be welcome.

T.E.D. (tdavis@gearbox.maem.umr.edu - e-mail must contain "T.E.D." or my .sig in the body)

Don Stokes

2004-05-12, 7:19 pm

In article <peol90tac37bnjc4sf1hbvviuhlhbr4jqo@4ax.com>,
Ted Davis <tdavis@gearbox.maem.umr.edu> wrote:
>Somebody please check my reasoning on this before I put a lot of time
>into writing a truly random password generator.
>
>The random numbers generated by gawk, and most if not all other
>languages, are actually pseudorandom.
>
>If I take the last, or last two, digits from the time field of ping
>reports of remote sites, I should get truly random numbers, one or two
>digits at a time.
>
>The IP addresses will come from a list of origin sites for spam I have
>received, and sites closer than 100 ms will be removed. The gawk
>script to extract the addresses has already been written and run, so I
>already have the unchecked list.
>
>I may be missing some regularity or other systematic error in the ping
>time numbers - if anyone knows of any reason why this won't work as
>intended, please enlighten me. Other suggestions for getting truly
>random numbers would also be welcome.

If you have /dev/random and/or a /dev/urandom available on your system,
you could use something like:

function generate_password(len,
r, pw) {
pw = ""
while(length(pw) < len) {
getline r <"/dev/urandom"
gsub(/[^a-zA-Z0-9]/, "", r)
pw = pw r
}
close("/dev/urandom")
pw = substr(pw, 1, len)
return pw
}

I use /dev/urandom because it doesn't block; often if there are lots of
requests to /dev/random, the entropy pool gets depleted, and the call
blocks until it fills sufficiently to satisfy the request.

/dev/urandom falls back to a pseudo-random sequence (based on a very
large seed), but is regularly perturbed by new entropy as it becomes
available, so in practice it makes a pretty good randomness source
without actually needing to resort to "real" random data.

Turning such randomness into a number, in the absence of a proper ord()
call, is slightly challenging, but quite doable:

#
# Function to return an integer in the range 0 <= n < modulo.
#
function random(modulo,
mag, i, r) {
mag = 1
r = 0
do {
if(_random_ptr >= _random_len) {
if(!_random_len) {
for(i = 0; i < 256; i++)
_random_ord[sprintf("%c", i)] = i
}
getline _random <"/dev/urandom"
_random = _random RS
_random_len = length(_random)
_random_ptr = 0
}
r = r * 256 + _random_ord[substr(_random, ++_random_ptr, 1)]
mag = mag * 256
} while(mag < modulo)
return r % modulo
}

>T.E.D. (tdavis@gearbox.maem.umr.edu - e-mail must contain "T.E.D." or my
>.sig in the body)

-- don

Ted Davis

2004-05-12, 7:19 pm

On Fri, 07 May 2004 02:26:24 GMT, don@news.daedalus.co.nz (Don Stokes)
wrote:

>In article <peol90tac37bnjc4sf1hbvviuhlhbr4jqo@4ax.com>,
>Ted Davis <tdavis@gearbox.maem.umr.edu> wrote:

<snip>[color=darkred]
>If you have /dev/random and/or a /dev/urandom available on your system,
>you could use something like:
<snip>

Now *that* is interesting. It would work for me (not random() since
it is pseudorandom, but maybe urandom()), but not for the other people
(they insist that everything has to be done under Windows, and I can't
convince them to install cygwin). Maybe I can convert the project -
or at least part of it - into a CGI process running on a Linux
machine. It would certainly be simpler. Maybe not simpler, but at
least more elegant.

I know that crypto APIs exist under Windows, but I just don't use high
level Windows languages (no need to).

Thank you for your input. I added your message to my collection of
tips and tricks.

T.E.D. (tdavis@gearbox.maem.umr.edu)
SPAM filter: Messages to this address *must* contain "T.E.D."
somewhere in the body or they will be automatically rejected.

Doug McClure

2004-05-12, 7:19 pm

Donald Knuth's book on random number generation discusses using
pseudo-random numbers and then shuffling them to remove any remaining
non-randomness. For example, he generates some random numbers and puts
them into an array. Then when a random number is required, he extracts
one from a random position and then generates a new number to replace
it. As I recall, he says that this can give good randomization from a
relatively poor random number generator.

He also cautions against using home-brew random number generation and
shows how one algorithm (that certainly looked like it would produce
random numbers) actually began cycling relatively quickly.

Here is a link you might find useful:

http://home.t-online.de/home/mok-ko.../oldwebpage.htm

DKM

On Thu, 06 May 2004 20:18:33 -0500, Ted Davis
<tdavis@gearbox.maem.umr.edu> wrote:

>Somebody please check my reasoning on this before I put a lot of time
>into writing a truly random password generator.
>
>The random numbers generated by gawk, and most if not all other
>languages, are actually pseudorandom.
>
>If I take the last, or last two, digits from the time field of ping
>reports of remote sites, I should get truly random numbers, one or two
>digits at a time.
>
>The IP addresses will come from a list of origin sites for spam I have
>received, and sites closer than 100 ms will be removed. The gawk
>script to extract the addresses has already been written and run, so I
>already have the unchecked list.
>
>I may be missing some regularity or other systematic error in the ping
>time numbers - if anyone knows of any reason why this won't work as
>intended, please enlighten me. Other suggestions for getting truly
>random numbers would also be welcome.
>
>
>T.E.D. (tdavis@gearbox.maem.umr.edu - e-mail must contain "T.E.D." or my .sig in the body)

To contact me directly, send EMAIL to (single letters all)
DEE_KAY_EMM AT EarthLink.net. [For example X_X_X@EarthLink.net.]

Gerard C Blais

2004-07-01, 8:55 pm

A possibly easier method is to use the low-order n digits from a
microsecond time of day clock...

On Thu, 06 May 2004 20:18:33 -0500, Ted Davis
<tdavis@gearbox.maem.umr.edu> wrote:

>Somebody please check my reasoning on this before I put a lot of time
>into writing a truly random password generator.
>
>The random numbers generated by gawk, and most if not all other
>languages, are actually pseudorandom.
>
>If I take the last, or last two, digits from the time field of ping
>reports of remote sites, I should get truly random numbers, one or two
>digits at a time.
>
>The IP addresses will come from a list of origin sites for spam I have
>received, and sites closer than 100 ms will be removed. The gawk
>script to extract the addresses has already been written and run, so I
>already have the unchecked list.
>
>I may be missing some regularity or other systematic error in the ping
>time numbers - if anyone knows of any reason why this won't work as
>intended, please enlighten me. Other suggestions for getting truly
>random numbers would also be welcome.
>
>
>T.E.D. (tdavis@gearbox.maem.umr.edu - e-mail must contain "T.E.D." or my .sig in the body)

Michael Zawrotny

2004-07-02, 3:55 pm

On Thu, 01 Jul 2004 16:29:39 -0400, Gerard C Blais <gerard.blais@mci.com> wrote:
>
> On Thu, 06 May 2004 20:18:33 -0500, Ted Davis
> <tdavis@gearbox.maem.umr.edu> wrote:
>

[ snip ]
[color=darkred]
> A possibly easier method is to use the low-order n digits from a
> microsecond time of day clock...

If you have it, a much easier way to do it is by reading from either
/dev/random or /dev/urandom as is appropriate. The former is more
random, but will block if system entry is low. The latter won't block,
but stirs the available entropy around with a cryptographich hash
function when there is little entropy available.
[color=darkred]

That may or may not really matter, depending on your threat model.
Only you can decide. Depending on how secure the password needs
to be, I would either:'

1. Read n bits (128, 256, 512, ... as determined by the difficulty
of breaking by brute force that you need) from one of the above
devices, then base 64 encode it to yield the password.

2. Read 32 bits from one of the above devices, convert it to an
unsigned integer, and use it as the seed in a call to srand().

The first one is clearly far more secure, but depending on your end
use for the password the second might be sufficient and is probably
faster (e.g. if you needed to autogenerate thousands of temporary
passwords for new accounts that the users would have to change as
part of their first login).

The important thing is to analyze the threat model (how strong do
the passwords need to be), and balance that against the performance
requirements, if any exist.

Mike

--
Michael Zawrotny
Institute of Molecular Biophysics
Florida State University | email: zawrotny@sb.fsu.edu
Tallahassee, FL 32306-4380 | phone: (850) 644-0069

Sponsored Links