1506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes/* $OpenBSD: res_random.c,v 1.23 2015/10/05 02:57:16 guenther Exp $ */ 20f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 30f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes/* 40f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de> 50f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Copyright 2008 Damien Miller <djm@openbsd.org> 60f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * All rights reserved. 70f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 80f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using 90f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * such a mathematical system to generate more random (yet non-repeating) 100f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * ids to solve the resolver/named problem. But Niels designed the 110f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * actual system based on the constraints. 120f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 130f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Later modified by Damien Miller to wrap the LCG output in a 15-bit 140f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * permutation generator based on a Luby-Rackoff block cipher. This 150f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * ensures the output is non-repeating and preserves the MSB twiddle 160f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * trick, but makes it more resistant to LCG prediction. 170f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 180f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Redistribution and use in source and binary forms, with or without 190f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * modification, are permitted provided that the following conditions 200f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * are met: 210f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 1. Redistributions of source code must retain the above copyright 220f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * notice, this list of conditions and the following disclaimer. 230f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 2. Redistributions in binary form must reproduce the above copyright 240f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * notice, this list of conditions and the following disclaimer in the 250f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * documentation and/or other materials provided with the distribution. 260f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 270f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 280f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 290f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 300f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 310f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 320f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 330f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 340f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 350f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 360f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 370f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 380f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 390f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes/* 400f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * seed = random 15bit 410f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * n = prime, g0 = generator to n, 420f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * j = random so that gcd(j,n-1) == 1 430f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * g = g0^j mod n will be a generator again. 440f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 450f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * X[0] = random seed. 460f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator 470f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * with a = 7^(even random) mod m, 480f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * b = random with gcd(b,m) == 1 490f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * m = 31104 and a maximal period of m-1. 500f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 510f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * The transaction id is determined by: 520f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * id[n] = seed xor (g^X[n] mod n) 530f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 540f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Effectivly the id is restricted to the lower 15 bits, thus 550f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * yielding two different cycles by toggling the msb on and off. 560f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * This avoids reuse issues caused by reseeding. 570f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 580f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * The output of this generator is then randomly permuted though a 590f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * custom 15 bit Luby-Rackoff block cipher. 600f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 610f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 620f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <sys/types.h> 630f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <netinet/in.h> 640f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <sys/time.h> 650f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <resolv.h> 660f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 670f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <unistd.h> 680f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <stdlib.h> 690f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include <string.h> 700f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 710f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#include "thread_private.h" 720f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 730f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_OUT 180 /* Time after wich will be reseeded */ 740f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_MAX 30000 /* Uniq cycle, avoid blackjack prediction */ 750f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_GEN 2 /* Starting generator */ 760f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_N 32749 /* RU_N-1 = 2*2*3*2729 */ 770f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */ 780f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_M 31104 /* RU_M = 2^7*3^5 - don't change */ 790f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define RU_ROUNDS 11 /* Number of rounds for permute (odd) */ 800f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 810f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstruct prf_ctx { 820f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* PRF lookup table for odd rounds (7 bits input to 8 bits output) */ 830f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_char prf7[(RU_ROUNDS / 2) * (1 << 7)]; 840f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 850f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* PRF lookup table for even rounds (8 bits input to 7 bits output) */ 860f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_char prf8[((RU_ROUNDS + 1) / 2) * (1 << 8)]; 870f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes}; 880f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 890f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#define PFAC_N 3 900f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic const u_int16_t pfacts[PFAC_N] = { 910f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2, 920f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 3, 930f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2729 940f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes}; 950f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 960f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t ru_x; 970f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t ru_seed, ru_seed2; 980f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t ru_a, ru_b; 990f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t ru_g; 1000f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t ru_counter = 0; 1010f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t ru_msb = 0; 1020f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic struct prf_ctx *ru_prf = NULL; 1030f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic time_t ru_reseed; 104506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughesstatic pid_t ru_pid; 1050f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1060f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t pmod(u_int16_t, u_int16_t, u_int16_t); 1070f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic void res_initid(void); 1080f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1090f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes/* 1100f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Do a fast modular exponation, returned value will be in the range 1110f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * of 0 - (mod-1) 1120f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 1130f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int16_t 1140f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughespmod(u_int16_t gen, u_int16_t exp, u_int16_t mod) 1150f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes{ 1160f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_int16_t s, t, u; 1170f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1180f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes s = 1; 1190f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes t = gen; 1200f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u = exp; 1210f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1220f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes while (u) { 1230f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if (u & 1) 1240f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes s = (s * t) % mod; 1250f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u >>= 1; 1260f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes t = (t * t) % mod; 1270f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes } 1280f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes return (s); 1290f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes} 1300f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1310f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes/* 1320f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 15-bit permutation based on Luby-Rackoff block cipher 1330f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 1340f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic u_int 1350f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughespermute15(u_int in) 1360f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes{ 1370f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes int i; 1380f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_int left, right, tmp; 1390f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1400f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if (ru_prf == NULL) 1410f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes return in; 1420f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1430f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes left = (in >> 8) & 0x7f; 1440f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes right = in & 0xff; 1450f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1460f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* 1470f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Each round swaps the width of left and right. Even rounds have 1480f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * a 7-bit left, odd rounds have an 8-bit left. Since this uses an 1490f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * odd number of rounds, left is always 8 bits wide at the end. 1500f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 1510f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes for (i = 0; i < RU_ROUNDS; i++) { 1520f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if ((i & 1) == 0) 1530f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes tmp = ru_prf->prf8[(i << (8 - 1)) | right] & 0x7f; 1540f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes else 1550f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes tmp = ru_prf->prf7[((i - 1) << (7 - 1)) | right]; 1560f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes tmp ^= left; 1570f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes left = right; 1580f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes right = tmp; 1590f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes } 1600f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1610f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes return (right << 8) | left; 1620f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes} 1630f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1640f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes/* 1650f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Initializes the seed and chooses a suitable generator. Also toggles 1660f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * the msb flag. The msb flag is used to generate two distinct 1670f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * cycles of random numbers and thus avoiding reuse of ids. 1680f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * 1690f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * This function is called from res_randomid() when needed, an 1700f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * application does not have to worry about it. 1710f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 1720f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesstatic void 1730f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesres_initid(void) 1740f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes{ 1750f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_int16_t j, i; 1760f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_int32_t tmp; 1770f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes int noprime = 1; 1780f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes struct timespec ts; 1790f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1800f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_x = arc4random_uniform(RU_M); 1810f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1820f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* 15 bits of random seed */ 1830f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes tmp = arc4random(); 1840f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_seed = (tmp >> 16) & 0x7FFF; 1850f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_seed2 = tmp & 0x7FFF; 1860f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1870f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* Determine the LCG we use */ 1880f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes tmp = arc4random(); 1890f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_b = (tmp & 0xfffe) | 1; 1900f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M); 1910f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes while (ru_b % 3 == 0) 1920f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_b += 2; 1930f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1940f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes j = arc4random_uniform(RU_N); 1950f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 1960f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* 1970f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * Do a fast gcd(j,RU_N-1), so we can find a j with 1980f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * gcd(j, RU_N-1) == 1, giving a new generator for 1990f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes * RU_GEN^j mod RU_N 2000f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes */ 2010f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2020f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes while (noprime) { 2030f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes for (i = 0; i < PFAC_N; i++) 2040f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if (j % pfacts[i] == 0) 2050f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes break; 2060f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2070f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if (i >= PFAC_N) 2080f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes noprime = 0; 2090f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes else 2100f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes j = (j + 1) % RU_N; 2110f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes } 2120f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2130f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_g = pmod(RU_GEN, j, RU_N); 2140f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_counter = 0; 2150f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2160f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* Initialise PRF for Luby-Rackoff permutation */ 2170f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if (ru_prf == NULL) 2180f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_prf = malloc(sizeof(*ru_prf)); 2190f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes if (ru_prf != NULL) 2200f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes arc4random_buf(ru_prf, sizeof(*ru_prf)); 2210f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2220f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes clock_gettime(CLOCK_MONOTONIC, &ts); 2230f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_reseed = ts.tv_sec + RU_OUT; 2240f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_msb = ru_msb == 0x8000 ? 0 : 0x8000; 2250f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes} 2260f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2270f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesu_int 228506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes__res_randomid(void) 2290f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes{ 2300f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes struct timespec ts; 231506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes pid_t pid; 2320f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_int r; 2330f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes _THREAD_PRIVATE_MUTEX(random); 2340f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2350f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes clock_gettime(CLOCK_MONOTONIC, &ts); 236506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes pid = getpid(); 2370f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2380f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes _THREAD_PRIVATE_MUTEX_LOCK(random); 2390f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 240506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes if (ru_counter >= RU_MAX || ts.tv_sec > ru_reseed || pid != ru_pid) { 2410f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes res_initid(); 242506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes ru_pid = pid; 243506c6deff726c8c052ff5abb0cef57e63707bd1cElliott Hughes } 2440f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2450f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes /* Linear Congruential Generator */ 2460f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_x = (ru_a * ru_x + ru_b) % RU_M; 2470f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes ru_counter++; 2480f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2490f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes r = permute15(ru_seed ^ pmod(ru_g, ru_seed2 + ru_x, RU_N)) | ru_msb; 2500f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2510f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes _THREAD_PRIVATE_MUTEX_UNLOCK(random); 2520f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2530f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes return (r); 2540f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes} 255506c6deff726c8c052ff5abb0cef57e63707bd1cElliott HughesDEF_STRONG(__res_randomid); 2560f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2570f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#if 0 2580f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesint 2590f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughesmain(int argc, char **argv) 2600f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes{ 2610f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes int i, n; 2620f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes u_int16_t wert; 2630f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2640f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes res_initid(); 2650f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2660f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("Generator: %u\n", ru_g); 2670f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("Seed: %u\n", ru_seed); 2680f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("Reseed at %ld\n", ru_reseed); 2690f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("Ru_X: %u\n", ru_x); 2700f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("Ru_A: %u\n", ru_a); 2710f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("Ru_B: %u\n", ru_b); 2720f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 2730f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes n = argc > 1 ? atoi(argv[1]) : 60001; 2740f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes for (i=0;i<n;i++) { 2750f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes wert = res_randomid(); 2760f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes printf("%u\n", wert); 2770f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes } 2780f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes return 0; 2790f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes} 2800f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes#endif 2810f7d882bb7661f9601f3843b0e393b6155cd9571Elliott Hughes 282