Reducing crypto-random values to a useless entropy

Question

Supposing I have generated random data from CryptGenRandom (or similar PRNG), at what point does futzing with the values make it not-so-random that it's useless? Or is sufficiently random in enough to make it sufficiently random out?

Basically I'm looking at a key generation algorithm that generates an 8 digit 0-9 value from the output of CryptGenRandom. I realize the final output is limited anyway, but it's a protocol implementation to be 8 digits of 0-9.

Put another way, if I need to generate such values, what's the best approach?

EDIT: My first question was more in the general sense and the second was a clarification on what I actually need to accomplish. Suppose I have generated a 256 bit random value. I need to reduce the 256 bits to say 64 bits, but further constrain that to a numeric value (in this case 8 digits).

Removing half the bits has an effect on the usefulness of being cryptographically random (as it reduces the entropy? or is this a false assumption?). Reducing that further to just be numeric values surely has an effect on usefulness as well. Given that then,

Q1: In a general sense if I had to reduce the length of a random value, what methods should I avoid?

Q2: OR more specifically, am I being dumb about generating an 8 digit number?

Answer 1

There are exactly 10⁸ = 100000000 possible sequences of eight digits. The best you can hope for is to select one of these with uniform probability.

The generic way would look like this (in pseudo C code):

for (;;) {
    unsigned char buf[4];
    uint32_t val;

    GetRandomBytesFromPRNG(buf, sizeof buf);
    val = (uint32_t)buf[0] | ((uint32_t)buf[1] << 8)
        | ((uint32_t)buf[2] << 16) | ((uint32_t)buf[3] << 24);
    val &= 0x07FFFFFF;
    if (val < 100000000) {
        return val; /* that's your code in the 8-digit range */
    }
}

Basically, we generate random values uniformly in the 0..2²⁷-1 range:

• Produce four bytes.
• Decode these into a 32-bit integer (here with big-endian convention, but that's arbitrary).
• Truncate to a 27-bit integer.

Why 2²⁷ ? Because that's the smallest power of two which is greater than 100000000 (2²⁷ is equal to 134217728).

At that point, we have a value in the 0..134217727 range, with uniform probability. If it falls into my target range (0..99999999), then that's good, we have our value. Convert that into decimal to get your 8 digits. If the value does not fall in the range, then we try again. Probability of looping is 25.49% each time, so it converges quickly (less than one chance in a billion to loop more than 15 times).

This is the way things are done with Java's Random.nextInt(int). A counting argument can be used to show that it is not feasible to really reach a uniform selection without some kind of loop (namely, no power of 2 is a multiple of 10⁸).

Alternate method: generate a big 160-bit integer, then divide it by 10⁸; the remainder will be your 8-digit code. This method has a slight bias, but less than 2^-128, so it is negligible. This method also guarantees a fixed amount of random bytes from your PRNG. However, computations on integers which do not fit in a machine register can be expensive, so this method will usually be less efficient than the loop above.

---

Remember that what you get as a "key" is hardly worth that name: enumerating all possible 8-digit sequences can be done in a fraction of a second. It will be hard to make some decent cryptography out of that. Such a code will nonetheless be quite good if used as, say, a one-time registration password.

Answer 2

I'm not sure what you mean by reducing to "useless entropy". You want informational entropy to increase. The entropy of a password on a list of common passwords with thousand entries is lg(1000) ~ 10. The entropy of a password chosen by picking uniformly 8 random digits is lg(10^8) ~ 26.6, where entropy is calculated as base-2 logarithm (lg) of total number of possibilities when all possibilities are selected at the same probability, like in Tom Leek's answer (assuming a the one byte PRNG is uniformly distributed). Uniform distribution is important for many applications, but in this case it makes only a trivial difference to the entropy.

If you just did the most naive treatment and just generated a random unsigned four byte number (between 0 and 2^32 - 1 = 4294967295) and just calculated its modulus mod 10^8:

def generate_password():
    return FourBytePRNG() % (10**8)

you only lose about a 0.00002 bits of entropy from over-representing numbers between 0 and 94967295 (each number would occur with probability 43/2^32 as 2^32 / 10^8 ~ 42.94) and under representing numbers from 94967296 to 99999999 (would occur with probability 42/2^32).

The entropy in this case can be calculated using the general formula for entropy (Entropy = Sum( - p lg(p) ) = Sum(p lg (1/p) ), where you sum over all the individual cases each with a probability of occurring of p. This evaluates to (94967295-0+1)*(43./2**32)* lg(2**32/43) + (99999999-94967296+1)*(42/2^32)*lg(2**32/42) = 26.57540 bits. Note for the uniform distribution (where all 10^8 numbers have p = 1/10^8 as the probability of being selected), you get Sum(p lg (1/p)) = 10**8 * (1/10**8) * lg(10**8/1) = lg(10**8) = 26.57542 bits.

I'd argue in this case this loss of 0.00002 bits of entropy is irrelevant. Yes, an attacker is slightly more likely to brute force if they try numbers from 0 to 94967295 first, but the difference doesn't matter in this case. Granted, its probably good practice to use Tom Leek's method when building random libraries, etc when you don't know the use-case and the small bias against the largest numbers could be very significant (for say simulations).

But for your specific case, I wouldn't worry about having a perfectly uniform distribution. If you want more security, just make the password longer/more complex and out of the range that can be easily brute forced.

EDIT: If you start with a 256-bit number from a cryptographic PRNG (between 0 and 2^256 - 1), I'd simply take the modulus 10^8 for this purpose; random256 % (100000000). This will slightly over represent numbers 0 to 29639936 (2^256 % 10^8 = 29639936), (they'd occur roughly 10^-78 times more than uniform distribution would predict) but this would have only the most trivial effect on the entropy -- wolfram alpha gives the difference in entropy is beyond wolfram alpha's ability to tell the difference from uniform distribution. This assumes that you can take do modular arithmetic on the result of your 256-bit random number conveniently. Alternatively, you can just drop all but 32 or 64 bits of it, and get something that again, for your scheme the simplest method will provide near indistinguishable security (off from uniform distribution by 2x10^-5 bits (starting with 32-bit rand) and 10^-15 bits (starting with a 64-bit rand). Or you can use Tom's method if you care about that last 2x10^-5 bits of entropy.