Conforming Randomness To An Alphabet

Question

Imagine that we're trying to create a function to generate a random string conforming to a user-supplied alphabet. That way, users can generate random strings with given characters. Something like:

string random_string(int length, string alphabet)

Now, the alphabet could be any combination of characters from length 2 to 256. So, to generate hex characters, you'd pass the string "0123456789abcdef"...

So the question at hand is which is the better unbiased method to generate the desired random data, assuming a stream based full-byte random source (/dev/urandom, etc)...

Base Conversion

First, we compute how many "bytes" we need from the stream:

int bits_per_block = floor(log(strlen(alphabet), 2) + 1);
int bytes = ceil(length * bits_per_block / 8);

Then, fetch randomness from the stream up to the required number of bytes, and store it in a "buffer".

Now, walk the buffer and do a numeric base conversion between 256 and the destination base. Then substitute the destination base for the characters from the alphabet. That's it.

Note that you'd need to convert the entire random buffer, and then cut off the most significant part of the result to size it properly (because the ceil call can cause it to over-generate). This is good, because it means that every generated character of the result will be unbiased.

This has the advantage that you're always fetching a known amount of randomness, up to a maximum of 1 extra byte.

It has a disadvantage that it requires twice the memory (one for the buffer, and one for the return), and that it's fairly complex (base conversion is not trivial).

Here's a sample implementation in PHP of the base conversion algorithm, and here it is in action.

Value Picking

This is the standard integer generation algorithm. Basically, we'd have an algorithm like:

character generateByte(string alphabet) {
    int len = strlen(alphabet);
    int max = 256 - (len % 256);
    do {
        int byte = get_random_byte();
    } while (byte > max);
    return alphabet[byte % len];
}

Note that the max ensures that the maximum generated int is divisible by the len parameter. So if we were generating into base 10, max would be 250, and byte % 10 would therefore be unbiased.

It has the advantage that it's a lot easier to implement. But it has a disadvantage that it could not terminate, or use a LOT of randomness to generate a string, especially for some odd bases...

So, is the Base Conversion an appropriate route to take? Or should we stick with the "value picking" approach?

Answer 1

First of all, it's not true that, in the "Base Conversion" case, that the output is actually equidistributed. It is easy to show that, if the size of the alphabet isn't a power of 2, and that there is a bound on the amount of entropy you can draw, that no algorithm can generate a truly equidistributed output (although you can come arbitrarily close).

In the case of your algorithm, well, we can make a fairly bad case by considering an alphabet of 127 characters, and asking the algorithm for a string consisting of a single symbol; your algorithm will set bytes = 1, and thus draw a single random byte; this means that some (most) characters will be generated with probability $2^{-7}$, but a few will be generated with probability $2^{-8}$ (that is, a factor of 2 less). This can easily be fixed by requesting a fixed constant (say, 16 bytes) above what you actually need. This will reduce the ratio of probabilities for various strings to at most $1 + 2^{-128}$, which is probably good enough.

That said, I would personally recommend the value picking approach. The value of that approach is that it is simpler; and simpler means easier to get right (and to verify that it is right), and getting things right is quite important for security.

Now, one complaint with your version of the value picking approach would be that if the alphabet is small, it'll take quite a few random outputs before you come approach bytes in the correct range. This is easy to fix if you look at only the lower $n$ bits of the random output (where $2^n$ is the smallest power of 2 greater than or equal to the string size). With this change, the average number of random bytes the value picking approach will use will be less than twice the output size.