Thread

Still wondering about random numbers...

Dr. Evil <drevil@sidereal.kz> — 2001-08-07T09:01:06Z

I am running on OpenBSD and Linux, both of which have
cryptographic-quality RNGs built in.  When I call RANDOM() in PG, do I
get the old C library random numbers, which are not very random, or do
I get high-quality random numbers from the crypto-RNG that's built in?
Any sugestions for getting high-quality random numbers?

Re: Still wondering about random numbers...

Joe Conway <joseph.conway@home.com> — 2001-08-07T15:27:44Z

> I am running on OpenBSD and Linux, both of which have
> cryptographic-quality RNGs built in.  When I call RANDOM() in PG, do I
> get the old C library random numbers, which are not very random, or do
> I get high-quality random numbers from the crypto-RNG that's built in?
> Any sugestions for getting high-quality random numbers?

Looking through the source, I find:

/*
 *  drandom  - returns a random number
 */
Datum
drandom(PG_FUNCTION_ARGS)
{
 float8  result;

 /* result 0.0-1.0 */
 result = ((double) random()) / ((double) MAX_RANDOM_VALUE);

 PG_RETURN_FLOAT8(result);
}

Looks like plain old C library random numbers. If you want to use
/dev/random or /dev/urandom, best bet would be to write your own C function.
You should also check through the contrib stuff -- I don't recall seeing RNG
functions in there, but I'm constantly amazed at what is in contrib that I
didn't notice before ;-)

HTH,

Joe

Re: Still wondering about random numbers...

Tom Lane <tgl@sss.pgh.pa.us> — 2001-08-07T16:00:56Z

"Joe Conway" <joseph.conway@home.com> writes:
> Looks like plain old C library random numbers. If you want to use
> /dev/random or /dev/urandom, best bet would be to write your own C function.
> You should also check through the contrib stuff -- I don't recall seeing RNG
> functions in there,

I don't see any in there either, but this seems like a fine candidate for
a contrib item.  I doubt we'd accept it into the mainstream for lack of
portability, but as a contrib item, why not?

			regards, tom lane

Re: Still wondering about random numbers...

lockhart@fourpalms.org — 2001-08-07T16:36:23Z

> > Looks like plain old C library random numbers. If you want to use
> > /dev/random or /dev/urandom, best bet would be to write your own C function.
> > You should also check through the contrib stuff -- I don't recall seeing RNG
> > functions in there,
> I don't see any in there either, but this seems like a fine candidate for
> a contrib item.  I doubt we'd accept it into the mainstream for lack of
> portability, but as a contrib item, why not?

configure is our friend. A better random number generator is always
welcome imho, and if it can be reliably supported through autoconf then
it would stand a chance to be included in the main tree. Especially
since the usage of random() seems to be very isolated in the code.
contrib/ is always a good first step though...

                    - Thomas

Re: Still wondering about random numbers...

John Gateley <gateley@jriver.com> — 2001-08-07T16:41:36Z

Joe Conway wrote:
> 
> > I am running on OpenBSD and Linux, both of which have
> > cryptographic-quality RNGs built in.  When I call RANDOM() in PG, do I
> > get the old C library random numbers, which are not very random, or do
> > I get high-quality random numbers from the crypto-RNG that's built in?
> > Any sugestions for getting high-quality random numbers?
> 
> Looking through the source, I find:
>  result = ((double) random()) / ((double) MAX_RANDOM_VALUE);

The random() function returns better (good?)
random numbers. The rand() function returns poor
random numbers. random() also depends on how
much state it is initialized with (and may or may
not be based on /dev/random, I don't know).

j

Re: Still wondering about random numbers...

Joe Conway <joseph.conway@home.com> — 2001-08-07T16:53:15Z

> > > Looks like plain old C library random numbers. If you want to use
> > > /dev/random or /dev/urandom, best bet would be to write your own C
function.
> > > You should also check through the contrib stuff -- I don't recall
seeing RNG
> > > functions in there,
> > I don't see any in there either, but this seems like a fine candidate
for
> > a contrib item.  I doubt we'd accept it into the mainstream for lack of
> > portability, but as a contrib item, why not?
>
> configure is our friend. A better random number generator is always
> welcome imho, and if it can be reliably supported through autoconf then
> it would stand a chance to be included in the main tree. Especially
> since the usage of random() seems to be very isolated in the code.
> contrib/ is always a good first step though...
>
>                     - Thomas

Sounds like there's some interest in this. I just wrote a function for
generating random initialization vectors from /dev/urandom within the past
week -- should be easy to make a pgsql contrib out of it. I'll send
something to patches in a couple of days or so.

-- Joe

Re: Still wondering about random numbers...

Bruno Wolff III <bruno@wolff.to> — 2001-08-07T19:15:50Z

On Tue, Aug 07, 2001 at 04:36:23PM +0000,
  Thomas Lockhart <lockhart@fourpalms.org> wrote:
> 
> configure is our friend. A better random number generator is always
> welcome imho, and if it can be reliably supported through autoconf then
> it would stand a chance to be included in the main tree. Especially
> since the usage of random() seems to be very isolated in the code.
> contrib/ is always a good first step though...

'Better' is in the eye of the beholder. /dev/random can stall for
very long periods of time waiting for entropy. Even /dev/urandom may
be overkill for some uses of random numbers. There is also the question
of how many bytes the function is going to return.

While it would be nice to have some access to /dev/random and /dev/urandom,
I don't know that replacing the current random function is the best way
to do this.

Re: Still wondering about random numbers...

Dr. Evil <drevil@sidereal.kz> — 2001-08-07T20:31:12Z

> 'Better' is in the eye of the beholder. /dev/random can stall for
> very long periods of time waiting for entropy. Even /dev/urandom may
> be overkill for some uses of random numbers. There is also the question
> of how many bytes the function is going to return.
>
> While it would be nice to have some access to /dev/random and /dev/urandom,
> I don't know that replacing the current random function is the best way
> to do this.

I'm the one who originally posted this question, and I agree, you have
a very good point.  /dev/random relies on a pool of entropy, which is
limited.  Applications which require a large volume of low-quality
random numbers (perhaps for rendering in a video game) should
definitely not use /dev/random, but applications which require a small
amount of high-quality randomness (generating cryptographic session
keys perhaps) should use it.  PG should have both calls available.  If
anyone has written a C function which calls the crypto-random
generator, which I could link in, if you would mail it to me, I would
be most appreciative, because I am using this to generate
cryptographic challenges, session keys and the like, which really do
need crypto-quality random numbers.

As an intermediate solution, I can use SHA1 to generate a sequence of
hashes, which does work as a fairly good crypto-RNG.  If anyone wants,
I can post the SHA1 code for PG.  It should really be in the
distribution, I think.  But then again, so should AES and RSA and
OpenPGP...

Re: Still wondering about random numbers...

Allan Engelhardt <allane@cybaea.com> — 2001-08-07T21:07:47Z

Bruno Wolff III wrote:

> On Tue, Aug 07, 2001 at 04:36:23PM +0000,
>   Thomas Lockhart <lockhart@fourpalms.org> wrote:
> >
> > configure is our friend. A better random number generator is always
> > welcome imho, and if it can be reliably supported through autoconf then
> > it would stand a chance to be included in the main tree. Especially
> > since the usage of random() seems to be very isolated in the code.
> > contrib/ is always a good first step though...
>
> 'Better' is in the eye of the beholder. /dev/random can stall for
> very long periods of time waiting for entropy.

On Intel i8x0 motherboards you can set the CONFIG_INTEL_RNG kernel parameter and access the hardware random entropy generator.

On other motherboards, reading from /dev/random can stall indefinitely.  This is not a Good Thing.  /dev/urandom is fine, but not rally better than rand(3) or random(3).

Is it actually possible to replace the built-in function?  I haven't checked.

If it is, then contrib is a fine place for the improvement.  If it isn't, then configure is probably our friend.

Just my £0.02.

Allan.

Re: Still wondering about random numbers...

Allan Engelhardt <allane@cybaea.com> — 2001-08-07T21:07:59Z

Bruno Wolff III wrote:

> On Tue, Aug 07, 2001 at 04:36:23PM +0000,
>   Thomas Lockhart <lockhart@fourpalms.org> wrote:
> >
> > configure is our friend. A better random number generator is always
> > welcome imho, and if it can be reliably supported through autoconf then
> > it would stand a chance to be included in the main tree. Especially
> > since the usage of random() seems to be very isolated in the code.
> > contrib/ is always a good first step though...
>
> 'Better' is in the eye of the beholder. /dev/random can stall for
> very long periods of time waiting for entropy.

On Intel i8x0 motherboards you can set the CONFIG_INTEL_RNG kernel parameter and access the hardware random entropy generator.

On other motherboards, reading from /dev/random can stall indefinitely.  This is not a Good Thing.  /dev/urandom is fine, but not rally better than rand(3) or random(3).

Is it actually possible to replace the built-in function?  I haven't checked.

If it is, then contrib is a fine place for the improvement.  If it isn't, then configure is probably our friend.

Just my £0.02.

Allan.

Re: Re: Still wondering about random numbers...

Bruce Momjian <pgman@candle.pha.pa.us> — 2001-08-07T22:44:10Z

> I'm the one who originally posted this question, and I agree, you have
> a very good point.  /dev/random relies on a pool of entropy, which is
> limited.  Applications which require a large volume of low-quality
> random numbers (perhaps for rendering in a video game) should
> definitely not use /dev/random, but applications which require a small
> amount of high-quality randomness (generating cryptographic session
> keys perhaps) should use it.  PG should have both calls available.  If
> anyone has written a C function which calls the crypto-random
> generator, which I could link in, if you would mail it to me, I would
> be most appreciative, because I am using this to generate
> cryptographic challenges, session keys and the like, which really do
> need crypto-quality random numbers.

Isn't /dev/random best used for seeding the random number generator,
rather than for getting random number?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Re: Still wondering about random numbers...

Dr. Evil <drevil@sidereal.kz> — 2001-08-08T00:34:44Z

> Isn't /dev/random best used for seeding the random number generator,
> rather than for getting random number?

It is best used for any situation when quality random numbers are
needed.  This includes seeding, and in some cases it may also include
generating session keys and other things.  It's good to have a
choice.  Right now I have a lot of pl/pgsql which calls plain old
RANDOM() to generate session keys, and that is not good.  Before I
launch this thing, I will need to find a way of getting better random
numbers.  If anyone has created a function like that for PG, please
mail me, because I need it.

Re: Re: Still wondering about random numbers...

Joe Conway <joseph.conway@home.com> — 2001-08-08T00:53:20Z

> > Isn't /dev/random best used for seeding the random number generator,
> > rather than for getting random number?
>
> It is best used for any situation when quality random numbers are
> needed.  This includes seeding, and in some cases it may also include
> generating session keys and other things.  It's good to have a
> choice.  Right now I have a lot of pl/pgsql which calls plain old
> RANDOM() to generate session keys, and that is not good.  Before I
> launch this thing, I will need to find a way of getting better random
> numbers.  If anyone has created a function like that for PG, please
> mail me, because I need it.

As I said earlier, I just recently created a function for something else I'm
working on which returns a binary string from /dev/urandom of whatever
length you request. I'm using it for initialization vectors (IVs) for 3des
cbc and for session keys. It should be relatively easy to turn into a pgsql
contrib function, so I'll post something to patches within the next couple
of days. It would not be intended to replace the standard RANDOM() function,
just compliment it. Biggest question in my mind is the return type -- should
it return pure binary as a bytea type, or hex as a text type? Any thoughts
on this?

I agree with other comments regarding /dev/random. During testing I found
that it can block for significant periods of time, especially when used
repetitively.

-- Joe

Re: Re: Still wondering about random numbers...

Doug McNaught <doug@wireboard.com> — 2001-08-08T03:15:14Z

Allan Engelhardt <allane@cybaea.com> writes:

> On other motherboards, reading from /dev/random can stall
> indefinitely.  This is not a Good Thing.  /dev/urandom is fine, but
> not rally better than rand(3) or random(3).

Wrong; it's still a lot better, especially if you have a reasonable
amount of entropy coming in--/dev/urandom uses the same entropy pool
as /dev/random and generates its data using a cryptographically secure
hash function.  This is still a lot better (for crypto purposes) than
the simple LCGs used in the standard C library functions.

See the random(4) manpage on your Linux system for more details.

-Doug
-- 
Free Dmitry Sklyarov! 
http://www.freesklyarov.org/ 

We will return to our regularly scheduled signature shortly.

Re: Re: Still wondering about random numbers...

Allan Engelhardt <allane@cybaea.com> — 2001-08-08T10:22:31Z

Doug McNaught wrote:

> Allan Engelhardt <allane@cybaea.com> writes:
>
> > On other motherboards, reading from /dev/random can stall
> > indefinitely.  This is not a Good Thing.  /dev/urandom is fine, but
> > not rally better than rand(3) or random(3).
>
> Wrong; it's still a lot better, especially if you have a reasonable
> amount of entropy coming in--/dev/urandom uses the same entropy pool
> as /dev/random and generates its data using a cryptographically secure
> hash function.  This is still a lot better (for crypto purposes) than
> the simple LCGs used in the standard C library functions.

Absolutely!  I had minor brain damage when I wrote the paragraph.  What I meant was:

"/dev/urandom is not really better than rand(3) or random(3) *in this situation* [i.e. when reads from /dev/random stalls and there is no system entropy]"

You don't get a lot of entropy from the standard /dev/random drivers on a system without users (pressing a key gives 10 bytes of entropy, moving the mouse ~8), but you do get a some so it is better.

As you said.

Allan.

RE: Re: Still wondering about random numbers...

Matt Block <matt@blockdev.net> — 2001-08-08T13:59:15Z

I'm almost dead certain (although I've been too lazy to actually look,)
that
network activity also fills the entropy pool (on Linux boxen).  I
conjecture 
this partly based on my headless "home services" box which acts as
firewall, 
web server, game server, pg server, blah, blah, and blah on my LAN.  It
has 
never wanted for entropy, and has actually never blocked on reads to
/dev/random
for any (human) appreciable lengths of time.  It drinks from the entropy
pool 
for key generation and suchlike frequently and deeply.

This may require netfilter.

  -- Matt

-----Original Message-----
From: pgsql-general-owner@postgresql.org
[mailto:pgsql-general-owner@postgresql.org] On Behalf Of Allan
Engelhardt
Sent: Wednesday, August 08, 2001 6:23 AM
To: Doug McNaught
Cc: Bruno Wolff III; pgsql-general@postgresql.org
Subject: Re: [GENERAL] Re: Still wondering about random numbers...

Doug McNaught wrote:

> Allan Engelhardt <allane@cybaea.com> writes:
>
> > On other motherboards, reading from /dev/random can stall 
> > indefinitely.  This is not a Good Thing.  /dev/urandom is fine, but 
> > not rally better than rand(3) or random(3).
>
> Wrong; it's still a lot better, especially if you have a reasonable 
> amount of entropy coming in--/dev/urandom uses the same entropy pool 
> as /dev/random and generates its data using a cryptographically secure

> hash function.  This is still a lot better (for crypto purposes) than 
> the simple LCGs used in the standard C library functions.

Absolutely!  I had minor brain damage when I wrote the paragraph.  What
I meant was:

"/dev/urandom is not really better than rand(3) or random(3) *in this
situation* [i.e. when reads from /dev/random stalls and there is no
system entropy]"

You don't get a lot of entropy from the standard /dev/random drivers on
a system without users (pressing a key gives 10 bytes of entropy, moving
the mouse ~8), but you do get a some so it is better.

As you said.

Allan.

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

Re: Re: Still wondering about random numbers...

Doug McNaught <doug@wireboard.com> — 2001-08-08T14:00:54Z

Allan Engelhardt <allane@cybaea.com> writes:

> "/dev/urandom is not really better than rand(3) or random(3) *in
> this situation* [i.e. when reads from /dev/random stalls and there
> is no system entropy]"

I would still disagree.  The difference for crypto purposes between a
CRNG seeded with real entropy (/dev/urandom) and an LCG (libc
functions) is huge.  The former is useful (with caveats); the latter
is trivially breakable.

-Doug
-- 
Free Dmitry Sklyarov! 
http://www.freesklyarov.org/ 

We will return to our regularly scheduled signature shortly.

Random strings

Joe Conway <joseph.conway@home.com> — 2001-08-08T18:01:59Z

> > generating session keys and other things.  It's good to have a
> > choice.  Right now I have a lot of pl/pgsql which calls plain old
> > RANDOM() to generate session keys, and that is not good.  Before I
> > launch this thing, I will need to find a way of getting better random
> > numbers.  If anyone has created a function like that for PG, please
> > mail me, because I need it.
>
> As I said earlier, I just recently created a function for something else
I'm
> working on which returns a binary string from /dev/urandom of whatever
> length you request. I'm using it for initialization vectors (IVs) for 3des
> cbc and for session keys. It should be relatively easy to turn into a
pgsql
> contrib function, so I'll post something to patches within the next couple
> of days. It would not be intended to replace the standard RANDOM()
function,
> just compliment it. Biggest question in my mind is the return type --
should
> it return pure binary as a bytea type, or hex as a text type? Any thoughts
> on this?
>

Per the discussion yesterday, here's a patch. There are two versions of
essentially the same function. They both take an int as the number of
requested random bytes, and generate a random binary string of the requested
length from /dev/urandom. The first one (randomstr_hex) converts the binary
to hex and returns it as text, and the other (randomstr_bytea) does the
needed escaping of special characters and returns bytea.

Let me know if you have any other thoughts on how this can be improved. I
didn't bother to create a function to return a random 0 - 1 interval float
(ala random()) because in most cases where cryptographic quality random
values are needed, the provided forms are the most useful ones (I think).

-- Joe

integer quoting

Ryan Mahoney <ryan@paymentalliance.net> — 2001-08-08T18:03:22Z

Is there any reason why integer values should *not* be quoted in statements 
passed to pgsql?  it seems like there are few benefits of this practice, 
curios what the drawbacks may be.

TIA!

Ryan Mahoney

Re: Re: Still wondering about random numbers...

Allan Engelhardt <allane@cybaea.com> — 2001-08-08T19:13:24Z

Doug McNaught wrote:

> Allan Engelhardt <allane@cybaea.com> writes:
>
> > "/dev/urandom is not really better than rand(3) or random(3) *in
> > this situation* [i.e. when reads from /dev/random stalls and there
> > is no system entropy]"
>
> I would still disagree.  The difference for crypto purposes between a
> CRNG seeded with real entropy (/dev/urandom) and an LCG (libc
> functions) is huge.  The former is useful (with caveats); the latter
> is trivially breakable.

Fair comment.  I agree.  Thanks for the clarification.


Allan.

Re: Random strings

Peter Eisentraut <peter_e@gmx.net> — 2001-08-08T19:21:09Z

Joe Conway writes:

> Per the discussion yesterday, here's a patch. There are two versions of
> essentially the same function. They both take an int as the number of
> requested random bytes, and generate a random binary string of the requested
> length from /dev/urandom. The first one (randomstr_hex) converts the binary
> to hex and returns it as text, and the other (randomstr_bytea) does the
> needed escaping of special characters and returns bytea.

Perhaps one of these returning bytea would be enough and you can use
the new encode functions to convert them to a format of choice.  Also, why
aren't you using /dev/random?

-- 
Peter Eisentraut   peter_e@gmx.net   http://funkturm.homeip.net/~peter

Re: Random strings

Joe Conway <joseph.conway@home.com> — 2001-08-08T20:25:22Z

> > Per the discussion yesterday, here's a patch. There are two versions of
> > essentially the same function. They both take an int as the number of
> > requested random bytes, and generate a random binary string of the
requested
> > length from /dev/urandom. The first one (randomstr_hex) converts the
binary
> > to hex and returns it as text, and the other (randomstr_bytea) does the
> > needed escaping of special characters and returns bytea.
>
> Perhaps one of these returning bytea would be enough and you can use
> the new encode functions to convert them to a format of choice.  Also, why
> aren't you using /dev/random?

Very nice. I hadn't looked encode/decode yet. I'll rework the patch and just
leave the bytea as you suggested.

As far as /dev/random, the issue it that it blocks when it runs out of
entropy. As a small test, I recompiled with /dev/random and tried:

   select randomstr_bytea(8), foo from bar;

where bar has about 120 rows. I was still waiting a minute later. When
requesting one at a time (but resubmitting relatively quickly), it works
fine until about the 35th request in a row, then it blocks briefly (~2
seconds). The same test with /dev/urandom returns instantly. Perhaps there
should be an option to use either. For instances where only a few truly
random bytes is needed (i.e. one session key), use /dev/random. When you
need many random bytes quickly, use /dev/urandom?

-- Joe

Re: Random strings

Joe Conway <joseph.conway@home.com> — 2001-08-09T07:02:58Z

> > Perhaps one of these returning bytea would be enough and you can use
> > the new encode functions to convert them to a format of choice.  Also,
why
> > aren't you using /dev/random?
>

Here's a revised patch. This one has only one user function, randomstr(int
binlen, text source). It allows any length request (well, limited by int)
against a source of 'urandom', or a maximum of 64 bytes against a source of
'random'. I also added a couple of examples to the readme to show how to use
randomstr() with encode() to get hex or base64 output.

On a side note, in the last version of this, I had a function which escaped
the binary C string so that I could feed it to byteain. In this version, I
decided to populate the varlena struct directly, because it seemed an awful
waste to escape the binary just so that byteain could unescape it. But I'm
not sure this is considered a "good thing", or a "bad thing". I'd appreciate
any guidance.

Thanks,

Joe

Re: Random strings

Peter Eisentraut <peter_e@gmx.net> — 2001-08-09T15:35:13Z

Joe Conway writes:

> seconds). The same test with /dev/urandom returns instantly. Perhaps there
> should be an option to use either. For instances where only a few truly
> random bytes is needed (i.e. one session key), use /dev/random. When you
> need many random bytes quickly, use /dev/urandom?

Not sure if this is intuitive.  How many bytes is "a few"?  Maybe just be
honest about it and name them randomstr and urandomstr or such.

-- 
Peter Eisentraut   peter_e@gmx.net   http://funkturm.homeip.net/~peter

Re: Random strings

Joe Conway <joseph.conway@home.com> — 2001-08-09T17:13:18Z

> > seconds). The same test with /dev/urandom returns instantly. Perhaps
there
> > should be an option to use either. For instances where only a few truly
> > random bytes is needed (i.e. one session key), use /dev/random. When you
> > need many random bytes quickly, use /dev/urandom?
>
> Not sure if this is intuitive.  How many bytes is "a few"?  Maybe just be
> honest about it and name them randomstr and urandomstr or such.
>

In the patch that I sent last night, I explicitly limited /dev/random to 64
bytes. I agree that this is not very intuitive, but for specific purposes,
such as generating a session key for tripledes (24 byte/192 bit random
string yielding 168 bits for a the key) periodically, it is quite useful.
There's a tradeoff here between cryptographic strength (favoring
/dev/random) and application performance (favoring /dev/urandom) that will
vary significantly from application to application. It's nice to have the
option depending on your needs.

Having said that, I'm not married to the idea that we should provide access
to both /dev/random and /dev/urandom. I'd be happy to roll another patch,
limited to just urandom, and renaming the function if you feel strongly
about it. (should we move this discussion back to hackers to get a wider
audience?)

-- Joe