3
\$\begingroup\$

The function uses the Windows "Cryptography API: Next Generation" (bcrypt.h)'s BCryptGenRandom function to generate random bytes - one for each character.

It returns the number of characters (excluding NUL-terminator) written to the buffer, -1 in the case of a bad argument, or -2 in the case of an error.

Example usage of the function:

wchar_t str[9]; // 8 chars + NUL
rand_alphanum_str(str, sizeof (str));
printf("8 random alphanumeric characters: %wS\n", str);

Function code:

int rand_alphanum_str(WCHAR *buffer, size_t buffer_size) {
    if(!buffer || buffer_size < 2) { return -1; }

    int chars = buffer_size / sizeof (WCHAR) - 1; // -1 for null terminator

    // need one random byte per character to be generated
    unsigned char *rand_bytes = malloc(chars);
    if(!rand_bytes) { return -2; }

    // filling rand_bytes buffer
    if(!NT_SUCCESS(BCryptGenRandom(NULL, rand_bytes, chars,
                                   BCRYPT_USE_SYSTEM_PREFERRED_RNG))) {
        free(rand_bytes);
        return -2;
    }

    for(int i = 0; i < chars; ++i) {
        // rand_bytes[i] is in range [0, 255].
        // need a number in range [0, 61] - as there are 62 alphanumeric
        // characters

        // bit-twiddling to attempt to maintain a uniform distribution:

        // discard 2 least-significant bits - rand_bytes is now in [0, 63]
        rand_bytes[i] >>= 2;
        if((rand_bytes[i] >> 5) & 1U) {   // if the now most-significant bit is set,
            rand_bytes[i] &= ~(1UL << 1); // clear the 2nd least-significant bit
            // (only cleared if most-significant bit is set so as to avoid
            // throwing distribution off by having a bit which is never set)
        }
        // rand_bytes[i] is now in [0, 61]

        // of the 62 possible values of rand_bytes[i]:
        //   - [0, 9] represent numeric digits
        //   - [10, 35] represent uppercase letters
        //   - [36, 61] represent lowercase letters
        // the offset of rand_bytes[i] from the low end of the range it lies in
        // is added to said range's first ASCII value to give a random character
        // in that range
        if(rand_bytes[i] <= 9) {
            buffer[i] = L'0' + rand_bytes[i];
        } else if(rand_bytes[i] <= 35) {
            // -10 for offset from beginning of numeral range
            buffer[i] = L'A' + rand_bytes[i] - 10;
        } else {
            // -36 for offset from beginning of uppercase range
            buffer[i] = L'a' + rand_bytes[i] - 36;
        }
    }
    buffer[chars] = L'\0';

    free(rand_bytes);
    return chars;
}

Thank you!

\$\endgroup\$
1
  • \$\begingroup\$ Nikdaas. why 2 in buffer_size < 2? \$\endgroup\$ – chux - Reinstate Monica Jul 28 '20 at 20:30
4
\$\begingroup\$

The output is not uniformly distributed

The resulting characters in the output string are not uniformly distributed. In fact, some characters never occur in the output. After shifting a random byte right by two, if the result is larger than or equal to 32, you always clear the second least significant bit. So all values up to 32 are possible, but then it is 32, 33, 36, 37, 40, 41 and so on. And each value >= 32 that your algorithm generates is twice as likely as each value < 32.

The best solution is to first shift the random byte right by two, and then check i it is smaller than 62. If so, use it as it is. Otherwise, generate a new random byte and repeat the process.

Avoid allocating an array of random bytes

You are allocating an array to store the random bytes in. While it might seem efficient to do this, because you assumed you then only need one call to BCryptGenRandom(), this might be an issue if you want to generate large random strings. Also, if you want to have a proper uniformly distributed output, you might need to generate more random bytes than you originally anticipated.

Consider having a small array on the stack that you fill with random bytes, and use those to generate the alphanumeric characters. If you used up all the bytes, you fill the array with a new batch of random bytes.

\$\endgroup\$
0
\$\begingroup\$

int rand_alphanum_str(WCHAR *buffer, size_t buffer_size) {

buffer_size remains unchanged so it should be a constant.

if(!buffer || buffer_size < 2) { return -1; }

I'm not sure why the degenerated cases for buffer_size zero and one result in an error. If it is zero then just return 0 immediately. If it is 1 continue as normal.

wchar_t str[9]; // 8 chars + NUL
...
int chars = buffer_size / sizeof (WCHAR) - 1; // -1 for null terminator

Sorry, no. This makes it entirely unclear that 8 random characters need to be generated. A programmer would not expect to have to supply 9 to generate 8 characters. I'd either explicitly specify that the buffer needs to be 1 character bigger than the argument in the documentation to hold NUL, or I'd use a single, NUL-terminated mutable string as parameter (using different characters before the NUL, obviously).

// need one random byte per character to be generated

Why? I'd use an alphabet string as input (remember, const), and then select characters at random from that alphabet.


You can select a single character by simply asking for a random index in the range [0, size) where size is the size of the alphabet. Most libraries have a function for that (where you simply give the size, not the range). Then you select the character at that position. This makes your random string generator much more flexible and - of course - unbiased. I agree with the other answer that there is probably bias.

If you want to have it perform better then you can request one number in the range alphabet_size ^ password_size, and then perform base conversion using alphabet_size as base.

\$\endgroup\$

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.