randLIB.c

00001 /*
00002  * Copyright (c) 2014-2015 ARM Limited. All rights reserved.
00003  * SPDX-License-Identifier: Apache-2.0
00004  * Licensed under the Apache License, Version 2.0 (the License); you may
00005  * not use this file except in compliance with the License.
00006  * You may obtain a copy of the License at
00007  *
00008  * http://www.apache.org/licenses/LICENSE-2.0
00009  *
00010  * Unless required by applicable law or agreed to in writing, software
00011  * distributed under the License is distributed on an AS IS BASIS, WITHOUT
00012  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  * See the License for the specific language governing permissions and
00014  * limitations under the License.
00015  */
00016 #include <stdint.h>
00017 #include <limits.h>
00018 #include "randLIB.h"
00019 #include "platform/arm_hal_random.h"
00020 
00021 /**
00022  * This library is made for getting random numbers for timing needs in
00023  * protocols, plus to generate dynamic ports, random IDs etc.
00024  *
00025  * **not safe to use for security or cryptographic operations.**
00026  *
00027  * Base implementation is a pseudo-RNG, but may also use a system RNG.
00028  * Replay of sequence by reseeding is not possible.
00029  *
00030  * Base pseudo-RNG is the xoroshiro128+ generator by Marsaglia, Blackman and
00031  * Vigna:
00032  *
00033  * http://xoroshiro.di.unimi.it/
00034  *
00035  * Certainly not the fastest for 32-bit or smaller platforms, but speed
00036  * is not critical. None of the long operations in the core are actually hard,
00037  * unlike the divisions and multiplies in the utility functions below, where we
00038  * do try to keep the operations narrow.
00039  */
00040 
00041 /* On some platforms, read from a system RNG, rather than use our own */
00042 /* RANDLIB_PRNG disables this and forces use of the PRNG (useful for test only?) */
00043 #ifndef RANDLIB_PRNG
00044 #ifdef __linux
00045 #define RANDOM_DEVICE "/dev/urandom"
00046 #endif
00047 #endif // RANDLIB_PRNG
00048 
00049 /* RAM usage - 16 bytes of state (or a FILE * pointer and underlying FILE, which
00050  * will include a buffer) */
00051 #ifdef RANDOM_DEVICE
00052 #include <stdio.h>
00053 static FILE *random_file;
00054 #else
00055 static uint64_t state[2];
00056 #endif
00057 
00058 #ifdef RANDLIB_PRNG
00059 void randLIB_reset(void)
00060 {
00061     state[0] = 0;
00062     state[1] = 0;
00063 }
00064 #endif
00065 
00066 #ifndef RANDOM_DEVICE
00067 static inline uint64_t rol(uint64_t n, int bits)
00068 {
00069     return (n << bits) | (n >> (64 - bits));
00070 }
00071 
00072 /* Lower-quality generator used only for initial seeding, if platform
00073  * isn't returning multiple seeds itself. Multiplies are rather heavy
00074  * for lower-end platforms, but this is initialisation only.
00075  */
00076 static uint64_t splitmix64(uint64_t *seed)
00077 {
00078     uint64_t z = (*seed += UINT64_C(0x9E3779B97F4A7C15));
00079     z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
00080     z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
00081     return z ^ (z >> 31);
00082 }
00083 #endif // RANDOM_DEVICE
00084 
00085 void randLIB_seed_random(void)
00086 {
00087 #ifdef RANDOM_DEVICE
00088     if (!random_file) {
00089         random_file = fopen(RANDOM_DEVICE, "rb");
00090     }
00091 #else
00092     arm_random_module_init();
00093 
00094     /* We exclusive-OR with the current state, in case they make this call
00095      * multiple times,or in case someone has called randLIB_add_seed before
00096      * this. We don't want to potentially lose entropy.
00097      */
00098 
00099     /* Spell out expressions so we get known ordering of 4 seed calls */
00100     uint64_t s = (uint64_t) arm_random_seed_get() << 32;
00101     state[0] ^= ( s | arm_random_seed_get());
00102 
00103     s = (uint64_t) arm_random_seed_get() << 32;
00104     state[1] ^= s | arm_random_seed_get();
00105 
00106     /* This check serves to both to stir the state if the platform is returning
00107      * constant seeding values, and to avoid the illegal all-zero state.
00108      */
00109     if (state[0] == state[1]) {
00110         randLIB_add_seed(state[0]);
00111     }
00112 #endif // RANDOM_DEVICE
00113 }
00114 
00115 void randLIB_add_seed(uint64_t seed)
00116 {
00117 #ifndef RANDOM_DEVICE
00118     state[0] ^= splitmix64(&seed);
00119     state[1] ^= splitmix64(&seed);
00120     /* This is absolutely necessary, but I challenge you to add it to line coverage */
00121     if (state[1] == 0 && state[0] == 0) {
00122         state[0] = 1;
00123     }
00124 #else
00125     (void)seed;
00126 #endif
00127 }
00128 
00129 uint8_t randLIB_get_8bit(void)
00130 {
00131     uint64_t r = randLIB_get_64bit();
00132     return (uint8_t) (r >> 56);
00133 }
00134 
00135 uint16_t randLIB_get_16bit(void)
00136 {
00137     uint64_t r = randLIB_get_64bit();
00138     return (uint16_t) (r >> 48);
00139 }
00140 
00141 uint32_t randLIB_get_32bit(void)
00142 {
00143     uint64_t r = randLIB_get_64bit();
00144     return (uint32_t) (r >> 32);
00145 }
00146 
00147 
00148 uint64_t randLIB_get_64bit(void)
00149 {
00150 #ifdef RANDOM_DEVICE
00151     if (!random_file) {
00152         return 0;
00153     }
00154     uint64_t result;
00155     if (fread(&result, sizeof result, 1, random_file) != 1) {
00156         result = 0;
00157     }
00158     return result;
00159 #else
00160     const uint64_t s0 = state[0];
00161     uint64_t s1 = state[1];
00162     const uint64_t result = s0 + s1;
00163 
00164     s1 ^= s0;
00165     state[0] = rol(s0, 55) ^ s1 ^ (s1 << 14);
00166     state[1] = rol(s1, 36);
00167 
00168     return result;
00169 #endif
00170 }
00171 
00172 void *randLIB_get_n_bytes_random(void *ptr, uint8_t count)
00173 {
00174     uint8_t *data_ptr = ptr;
00175     uint64_t r = 0;
00176     for (uint_fast8_t i = 0; i < count; i++) {
00177         /* Take 8 bytes at a time */
00178         if (i % 8 == 0) {
00179             r = randLIB_get_64bit();
00180         } else {
00181             r >>= 8;
00182         }
00183         data_ptr[i] = (uint8_t) r;
00184     }
00185     return data_ptr;
00186 }
00187 
00188 uint16_t randLIB_get_random_in_range(uint16_t min, uint16_t max)
00189 {
00190     /* This special case is potentially common, particularly in this routine's
00191      * first user (Trickle), so worth catching immediately */
00192     if (min == max) {
00193         return min;
00194     }
00195 
00196 #if UINT_MAX >= 0xFFFFFFFF
00197     const unsigned int rand_max = 0xFFFFFFFFu; // will use rand32
00198 #else
00199     const unsigned int rand_max = 0xFFFFu; // will use rand16
00200 
00201     /* 16-bit arithmetic below fails in this extreme case; we can optimise it */
00202     if (max - min == 0xFFFF) {
00203         return randLIB_get_16bit();
00204     }
00205 #endif
00206 
00207     /* We get rand_max values from rand16 or 32() in the range [0..rand_max-1], and
00208      * need to divvy them up into the number of values we need. And reroll any
00209      * odd values off the end as we insist every value having equal chance.
00210      *
00211      * Using the range [0..rand_max-1] saves long division on the band
00212      * calculation - it means rand_max ends up always being rerolled.
00213      *
00214      * Eg, range(1,2), rand_max = 0xFFFF:
00215      * We have 2 bands of size 0x7FFF (0xFFFF/2).
00216      *
00217      * We roll: 0x0000..0x7FFE -> 1
00218      *          0x7FFF..0xFFFD -> 2
00219      *          0xFFFE..0xFFFF -> reroll
00220      * (calculating band size as 0x10000/2 would have avoided the reroll cases)
00221      *
00222      * Eg, range(1,3), rand_max = 0xFFFFFFFF:
00223      * We have 3 bands of size 0x55555555 (0xFFFFFFFF/3).
00224      *
00225      * We roll: 0x00000000..0x555555554 -> 1
00226      *          0x55555555..0xAAAAAAAA9 -> 2
00227      *          0xAAAAAAAA..0xFFFFFFFFE -> 3
00228      *          0xFFFFFFFF              -> reroll
00229      *
00230      * (Bias problem clearly pretty insignificant there, but gets worse as
00231      * range increases).
00232      */
00233     const unsigned int values_needed = max + 1 - min;
00234     /* Avoid the need for long division, at the expense of fractionally
00235      * increasing reroll chance. */
00236     const unsigned int band_size = rand_max / values_needed;
00237     const unsigned int top_of_bands = band_size * values_needed;
00238     unsigned int result;
00239     do {
00240 #if UINT_MAX > 0xFFFF
00241         result = randLIB_get_32bit();
00242 #else
00243         result = randLIB_get_16bit();
00244 #endif
00245     } while (result >= top_of_bands);
00246 
00247     return min + (uint16_t)(result / band_size);
00248 }
00249 
00250 uint32_t randLIB_randomise_base(uint32_t base, uint16_t min_factor, uint16_t max_factor)
00251 {
00252     uint16_t random_factor = randLIB_get_random_in_range(min_factor, max_factor);
00253 
00254     /* 32x16-bit long multiplication, to get 48-bit result */
00255     uint32_t hi = (base >> 16) * random_factor;
00256     uint32_t lo = (base & 0xFFFF) * random_factor;
00257     /* Add halves, and take top 32 bits of 48-bit result */
00258     uint32_t res = hi + (lo >> 16);
00259 
00260     /* Randomisation factor is *2^15, so need to shift up 1 more bit, avoiding overflow */
00261     if (res & 0x80000000) {
00262         res = 0xFFFFFFFF;
00263     } else {
00264         res = (res << 1) | ((lo >> 15) & 1);
00265     }
00266 
00267     return res;
00268 }