Improving the Quality of Randomness in Objective-C

Question

You are standing in a dungeon. Before you, there is a group of Level 5 Nerds. They want you to run a Dungeons and Dragons campaign for them.

You run a few sessions, your players are leveling up, and things are generally swell. Combat's a little slow, though. You decide to pull out your +4 Halberd of Objective-C and write an iPad app to automate NPC dice rolling in combat. The nerds move toward you, menacingly. "Algorithmically generated numbers," one snarls, "are a hollow imitation of true randomness! You shall not taint our holy campaign with your pseudorandom filth!"

You roll to convince him that arc4random_uniform() is more than sufficent ... and fail. The nerds will settle for nothing less than true randomness. They hold you prisoner as you desperately cling to your MacBook, and write a class that retrieves data from random.org.

NSDateFormatter *formatter = [[NSDateFormatter alloc] init];
[formatter setDateFormat:@"YYYY/YYYY-MM-dd"];
NSURL *url = [NSURL URLWithString:[NSString stringWithFormat:@"%@%@%@", 
                @"http://www.random.org/files/", 
                [formatter stringFromDate:[NSDate date]],
                @".bin"]];
NSURLConnection *theConnection = [[NSURLConnection alloc] initWithRequest:
                [NSURLRequest requestWithURL:url] delegate:self];

Once the data has been saved, you allow the generation of random numbers, 0-255, from the downloaded bytes.

-(int) nextInt:(int)start end:(int)end
{
    int upperBound = end - start + 1;
    unsigned char result;
    int maxModulo = 255 - (255 % upperBound);
    do {
        NSRange range = {index, sizeof(char)};
        [randos getBytes:&result range:range];
        index += sizeof(char);
    } while (result > maxModulo); //avoid modulo bias
    result = result % upperBound;
    result += start;
    return result;
}

The nerds seem satisfied, but a new enemy appears: another Dungeon Master! He demands you give him a copy of the software for his own purposes. The problem is evident--if you both use random.org data from the same day, you will get the same set of dice rolls!

So my question is as follows: how can I modify the random.org data such that it will retain something like "true randomness" but be different in each instance of the program? I can envision one solution that would entail getting some (purportedly random) touchpad movements from the user, like TrueCrypt does, but once I have that constant I'm unsure where to go from there. Somehow hash all the numbers using my constant? That will produce a much larger number; am I statistically okay if I just truncate or modulus that down to the dice roll? I don't know what algorithmic steps to take.

Answer 1

I have a different solution. One that will satisfy everyone, I should hope. Every time you want to generate a new die roll, do it this way:

Present a progress bar, and prompt the user to shake the device.

• While waiting, filter the acceleration data suitably (some low pass IIR should do nicely) and look for spikes with a certain given magnitude. Count level changes using hysteresis. Show a progress bar that shows the amount of shaking.
• At the same time, feed the raw acceleration data to a suitable cryptographic hash function, say, SHA-2.

When the progress bar gets all the way to the right, play the sound of dice rolling and use the output of the hash function (256 bits) to generate the die values. This will not work for more than 59d20. You can also save the hash function state as input to the next die roll.

Here's what you tell those nerds: The die roll is in no way algorithmically predictable. The only information used in determining the value of the die roll is how you shake the device, which is true for real dice as well. In theory you could shake the device the same way twice, just as in theory a highly skilled gambler could roll real dice to make them come up the way he wants.

How to use the output: You have 256 bits of random data, and want to get die rolls.

struct bits {
    unsigned data[8];
    unsigned pos;
};

// Get next n bits, or -1 if out of entropy.
int get_bits(struct bits *b, int n);

// Roll an n-sided die, or -1 if out of entropy
int uniform(struct bits *b, int n)
{
    int nbits, x;
    for (nbits = 0; (1 << nbits) < n; ++nbits);
    do {
        x = get_bits(b, nbits);
        if (x < 0)
            return -1;
    } while (x >= n);
    return x + 1;
}

This function works by slicing off a few bits of entropy at a time for your die rolls. So for a d8, you slice of 3 bits and use the result. For a d20, you slice off 5 bits for a d32, and reroll if the result is greater than 20. If you happen to run out of entropy (unlikely, but possible) for a given die roll, then I suggest printing a "die jacked" message and asking the user to shake some more for the remaining dice.

Footnote: The probability that you'll run out of entropy is very low, unless you roll a large number of dice. 256 bits is plenty. It takes 24d20 before the chance of running out of entropy even gets to 1%.

Answer 2

It's not really an answer and is a commentary, but it became long and here it is.

I can envision one solution that would entail getting some (purportedly random) touchpad movements from the user,

Note that arc4random_stir() reads from /dev/urandom, see the man page. So it seeds itself with the "environment".

Or, buy a radioactive source and a Geiger-counter, connect it to the USB, and generate the random number based on the reading of the counter. Nuclear decay is quantum mechanically random.