2

Problem space

I'm way out of my pay grade, I'm trying to figure out

  • How much randomness does a call to random() actually provide in PostgreSQL?

    SELECT random();
    
  • Whether or not you can reasonably guess that much randomness?

What I know

  1. I know it's not as random as people want it to be, it's just inefficient. Having concluded long ago that md5() is a waste of time, I can just compare the sizes.

    --produces "8" (in bytes)
    SELECT pg_column_size(random());
    
    --produces "36" (in bytes)
    SELECT pg_column_size(md5(random()::text));
    

    That's a lot of wasted space. I know we can store md5() in UUID which will take 16 bytes. But, that's still 8 bytes of waste space from our original 8 byte random().

  2. I know PostgreSQL currently generates random numbers like this,

    result = (double) random() / ((double) MAX_RANDOM_VALUE + 1);
    
    PG_RETURN_FLOAT8(result);
    

    And, I know that PG_RETURN_FLOAT8(result) is a macro that calls Float8GetDatum(result).

  3. The docs on random() say this,

    The characteristics of the values returned by random() depend on the system implementation. It is not suitable for cryptographic applications; see pgcrypto module for an alternative.

  4. I believe that 8 byte float, is an Standard 754 IEEE float under the hood, also from the docs.

    The data types real and double precision are inexact, variable-precision numeric types. In practice, these types are usually implementations of IEEE Standard 754 for Binary Floating-Point Arithmetic (single and double precision, respectively), to the extent that the underlying processor, operating system, and compiler support it.

  5. I know that the full precision of IEEE 754 supports the following states that our random() does not support.

    1. Negative numbers
    2. Not-a-number
    3. Infinity
    4. Negative Infinity
  6. I know that IEEE reserves 11 bits for the exponent, and we're guaranteed to have that in a position that yields numbers in the range of (0,1). From the docs,

    random value in the range 0.0 <= x < 1.0.

  7. Not sure how accurate (I would prefer this checked with the above information), but for an 8-byte double the docs say

    variable-precision, inexact 15 decimal digits precision

With all of that is anyone fluent enough in 754, and C to actually tell me how random a call to random() really is.

Why I am asking

I made a suggestion to generate session keys not using md5(random()::text) stored in text, but instead to use pgcrypto's gen_random_uuid() now I'm wondering how much it matters.

3

random() can have at most 64 bits of significance, since it's a double precision float. That assumes perfect random number generation and all that.

We only produce a random significand, the sign and exponent is fixed. The fractional part of the significand is 52 bits.

So ... about 2^52 possible values.

It looks like you're thinking of the rainbow table as a mapping of the md5 of the text representation of a double precision float back to the original float. Assuming you're using extra_float_digits = 3, that'd take up roughly 128 * 2^52 bytes, so a couple of exabytes, in exchange for reducing your search space from 2^128 to 2^52. Not that exciting, really.

I'd still want a good reason not to just use a uuid-ossp's uuid_generate_v4(). How big can your session tables really be? You know PostgreSQL has huge per-row overheads right?


Separately, you don't have to use uuid to store an md5, or format it as text. You can also use bytea. It'll be packed into a short-varlena Datum which has a 1-byte length so it'll take up 17 bytes. (See: VARSIZE_ANY in src/include/postgres.h, and src/backend/utils/adt/varlena.c).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.