4

I have a random number generator that runs in constant time.

The prototype for this function is as follows:

uint8_t rand();

What I want to be able to do is create a function that randomly returns an uint8_t such that the output is between 0 and max where max is the maximum number to be returned. The prototype for such a function would be:

uint8_t randi(uint8_t max);

There are algorithms online to do this and on stack overflow. For example, https://stackoverflow.com/a/6852396/1444313. But my problem is that I want to achieve this in constant time. I can't find any method that does this in constant time.

Additionally i'm running on an ARM Cortex-m0 without hardware division so using the % operator is not possible.

Does anyone have any suggestions or pointers on how I would achieve this in constant time?

Thanks

Community
  • 1
  • 1
Dave_Peachy
  • 498
  • 3
  • 12
  • I don't see the problem, any remotely plausible implementation of software division of constant-length integers will have constant time complexity. The constant factors may be a tad higher than the alternatives though, of which the easiest solution is to reverse the process and multiply `max` and then divide by the constant `MAX` (in uint64_t precision if required) . The advantage is that division by a constant can easily be optimized into a straightforward multiplication/shift/add sequence by the compiler in the worst case, or by hand if you don't trust the optimizer. – doynax Mar 17 '17 at 17:56
  • Mandatory xkcd link: https://xkcd.com/221/ – pmg Mar 17 '17 at 18:12
  • @doynax I'm not sure I understand your method from your explaination, could you write an answer if you think this would work? Thanks. – Dave_Peachy Mar 17 '17 at 18:18
  • "i'm running on an ARM Cortex-m0 without hardware division so using the % operator is not possible." implies `/` is not usable either (due to non-constant time). Is that so? – chux - Reinstate Monica Mar 17 '17 at 19:01
  • I suspect the answer is impossible, yet vanishingly small timing differences can be had. It becomes a question of do you need constant time in an absolute sense or nearly constant time in a practical one? Just some odd _random_ thoughts. – chux - Reinstate Monica Mar 17 '17 at 19:39
  • @chux Constant number of instructions executed would be fine. – Dave_Peachy Mar 17 '17 at 19:57
  • How about creating an array of random numbers in the background which is kept topped up. Then the function can simply read the one at the front of the queue. Some care will be needed to manage the queue for "constant time". – Realtime Rik Mar 17 '17 at 20:07
  • @RealtimeRik Saying i'm on a cortex-m0, there isn't much of a background to run things in. – Dave_Peachy Mar 17 '17 at 21:20
  • The m0 is a surprisingly powerful little device. It can happily run a small RTOS. The biggest issue is normally the amount of RAM/ROM on the chip not the processing power. You could easily run a timer interrupt to generate your numbers, or call a generate function as part of a round robin scheduler. – Realtime Rik Mar 17 '17 at 21:37
  • I'm currently using rather a large proportion of the resources on the chip so i'm not sure if this would be practical. However, if running it in the foreground is not going to be constant time, how would running it in the background be? – Dave_Peachy Mar 17 '17 at 21:40
  • Its hard to say as I don't know how your system operates and how your scheduling works. However if you could do the calculation at some time when you don't care you could then get the number when you need it in a deterministic manner. It all depends on how your system works and how often you need to get a random number? – Realtime Rik Mar 17 '17 at 21:46
  • Yeah that makes sense. It's annoying there isn't a solution to this though, as it seems like a simple problem. Thanks for your help. – Dave_Peachy Mar 17 '17 at 21:47
  • @Dave_Peachy: I simply meant `(max * (rand() << 16 | rand() << 8 | rand())) >> 24`, that is extracting the randomness off of the top instead of the bottom to turn a division by a variable into a division by a constant (in this case a fast bit-shift). Chain up sufficient entropy sources to render the resulting non-uniformity insignificant to the application. – doynax Mar 17 '17 at 21:50
  • Random number stuff is always surprisingly complex, especially if you want truly random number. There is a huge amount of stuff on the web about it. Last time I needed to use a random number, I was using a STM32F2 which (by luck rather than judgement) happened to have a rather good hardware random number generator. – Realtime Rik Mar 17 '17 at 21:52

5 Answers5

4

In the strictest sense the requirements are impossible to meet. As long as your RNG produces a uniform distribution in binary, there's no way to map that to a non-power-of-two range without either discarding some results or having an imperfect distribution.

You can either make the imperfection trivially small, or you can make the discard case trivially rare. Since a rare discard represents a surprise timing anomaly when it happens (and by making it rarer you only make it more surprising) consider this solution, which is constant time and can be adapted to your specific rand() function this way:

int n = max + 1;
int r = n / 2;
for (int i = 0; i < 6; ++i) {
    r = (rand() * n + r) >> 8;
}
return r;

This extracts 48 random bits as an fraction between 0 and 1 and multiplies it by n, retaining only the integer portion which will be a value no greater than max. The bias is less than one in a trillion preference for some values over others. If you're not happy about that then you can change 6 to something larger.

That kind of bias means that if you drew 1000 random numbers per second, it'd take well over 30 years before you could see one result occur one more time than it should, and statistical noise would still swamp that.

You can make this a lot faster by replacing rand() with something that produces many more random bits in a single call, and iterating only once or twice.

sh1
  • 4,324
  • 17
  • 30
0

To help clarify OP' dilemma, below are 2 simple solution that do not meet OP's goals.

What does not work:

Non-uniform distribution unless max +1 is a power of 2.

uint8_t randi_fail1(uint8_t max) {
  return rand()%(max + 1);
}

Uniform distribution, but not uniform time.

uint8_t randi_fail2(uint8_t max) {
  unsigned n = (256/(max+1))*(max+1);
  unsigned r;
  do {
    r = rand();  // 0 - 255
  } while (r >= n);
  return r/(max+1);
}
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • I have fallen foul of the non uniform distribution problem before. Easy trap to fall into and a surprisingly tricky to ensure you have the distribution 100% uniform. – Realtime Rik Mar 17 '17 at 20:12
0

Here is a solution that meets your requirement, but may not like!

Make 255 arrays of 256 or 65536 random values, call it uint8_t randval[255][256];

Now each randval[N][M] <= N; in other words, the subarrays are specialized for the randi max parameter.

uint8_t randi(uint8_t max)
{
    return (max == 0u) ? 0u : randval[max - 1][rand()];
}

Note that randval can be constructed at compile time, or can be updated in the background as suggested by @Realtime Rik. Of course, if constructed at compile time, it can be const, and stored in flash.

Doug Currie
  • 40,708
  • 1
  • 95
  • 119
  • Hey thanks for your reply. I'm on a ARM Cortex-m0 which has 4k memory and 32k flash I don't think I can fit that on there! – Dave_Peachy Mar 17 '17 at 21:24
0

Both the input and output are 8-bit bytes, so why not get your random value, multiply by your 'max', and shift right by 8 to divide by 256? I've done this to pick a random letter by getting a value 0-25 (8-bit random, multiply by 26, take the top byte).

Mike
  • 1
0

The table-based answer here ensures constant-time execution on ideal hardware, but in real-life it is betrayed by the memory access timing being timeable, and the access data-dependent (randval[..][rand()], which will vary in time due to CPU-level caching): https://stackoverflow.com/a/42867281

The uniform distribution suggestion here is the way to go: https://stackoverflow.com/a/42865274 Usually what you want when something is to be constant time in terms of security, it is merely that your code is clear of data-dependent code paths - memory access and instruction branches - not that the timing is actually constant.

To shield the bound from being exposed, you can supply an upper bound (e.g. 64 bits) and use techniques similar to the constant_time_select_int used here in the FIPS module of boringssl (no idea why the regular crypto code in boringssl does not use constant-time implementations) to obtain the wanted samples - but note that in most scenarios it is merely the values returned by the random number generator, not the range, that is considered sensitive: https://github.com/google/boringssl/blob/master/crypto/fipsmodule/bn/cmp.c#L77

For more inspiration see the random number generator / wrapper functions from boringssl: https://github.com/google/boringssl/blob/master/crypto/fipsmodule/bn/random.c and from the OCaml library eqaf (be aware that the latter is specialized to work on individual bytes and as thus the comparison function compare(a,b){ return (a - b) } is not designed to handle the case of a=0, b=INT_MIN): https://github.com/mirage/eqaf/blob/master/lib/eqaf.ml#L111-L124

Guest
  • 1