11dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* $OpenBSD: res_random.c,v 1.17 2008/04/13 00:28:35 djm Exp $ */ 21dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 31dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* 41dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de> 51dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Copyright 2008 Damien Miller <djm@openbsd.org> 61dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Copyright 2008 Android Open Source Project (thread-safety) 71dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * All rights reserved. 81dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 91dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using 101dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * such a mathematical system to generate more random (yet non-repeating) 111dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * ids to solve the resolver/named problem. But Niels designed the 121dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * actual system based on the constraints. 131dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 141dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Later modified by Damien Miller to wrap the LCG output in a 15-bit 151dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * permutation generator based on a Luby-Rackoff block cipher. This 161dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * ensures the output is non-repeating and preserves the MSB twiddle 171dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * trick, but makes it more resistant to LCG prediction. 181dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 191dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Redistribution and use in source and binary forms, with or without 201dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * modification, are permitted provided that the following conditions 211dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * are met: 221dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 231dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * notice, this list of conditions and the following disclaimer. 241dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 251dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 261dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * documentation and/or other materials provided with the distribution. 271dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 281dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 291dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 301dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 311dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 321dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 331dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 341dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 351dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 361dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 371dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 381dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 391dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 401dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* 411dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * seed = random 15bit 421dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * n = prime, g0 = generator to n, 431dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * j = random so that gcd(j,n-1) == 1 441dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * g = g0^j mod n will be a generator again. 451dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 461dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * X[0] = random seed. 471dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator 481dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * with a = 7^(even random) mod m, 491dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * b = random with gcd(b,m) == 1 501dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * m = 31104 and a maximal period of m-1. 511dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 521dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * The transaction id is determined by: 531dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * id[n] = seed xor (g^X[n] mod n) 541dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 551dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Effectivly the id is restricted to the lower 15 bits, thus 561dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * yielding two different cycles by toggling the msb on and off. 571dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * This avoids reuse issues caused by reseeding. 581dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 591dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * The output of this generator is then randomly permuted though a 601dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * custom 15 bit Luby-Rackoff block cipher. 611dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 621dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 631dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <sys/types.h> 641dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <netinet/in.h> 651dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <sys/time.h> 661dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include "resolv_private.h" 671dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 681dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <unistd.h> 691dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <stdlib.h> 701dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#include <string.h> 711dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 721dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* BIONIC-BEGIN */ 731dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic pthread_mutex_t _res_random_lock = PTHREAD_MUTEX_INITIALIZER; 741dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define _RES_RANDOM_LOCK() pthread_mutex_lock(&_res_random_lock) 751dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define _RES_RANDOM_UNLOCK() pthread_mutex_unlock(&_res_random_lock) 761dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* BIONIC-END */ 771dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 781dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_OUT 180 /* Time after wich will be reseeded */ 791dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_MAX 30000 /* Uniq cycle, avoid blackjack prediction */ 801dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_GEN 2 /* Starting generator */ 811dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_N 32749 /* RU_N-1 = 2*2*3*2729 */ 821dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */ 831dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_M 31104 /* RU_M = 2^7*3^5 - don't change */ 841dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define RU_ROUNDS 11 /* Number of rounds for permute (odd) */ 851dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 861dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstruct prf_ctx { 871dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* PRF lookup table for odd rounds (7 bits input to 8 bits output) */ 881dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_char prf7[(RU_ROUNDS / 2) * (1 << 7)]; 891dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 901dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* PRF lookup table for even rounds (8 bits input to 7 bits output) */ 911dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_char prf8[((RU_ROUNDS + 1) / 2) * (1 << 8)]; 921dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project}; 931dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 941dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#define PFAC_N 3 951dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectconst static u_int16_t pfacts[PFAC_N] = { 961dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2, 971dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 3, 981dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2729 991dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project}; 1001dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1011dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t ru_x; 1021dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t ru_seed, ru_seed2; 1031dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t ru_a, ru_b; 1041dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t ru_g; 1051dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t ru_counter = 0; 1061dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t ru_msb = 0; 1071dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic struct prf_ctx *ru_prf = NULL; 1081dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic long ru_reseed; 1091dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1101dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t pmod(u_int16_t, u_int16_t, u_int16_t); 1111dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic void res_initid(void); 1121dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1131dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* 1141dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Do a fast modular exponation, returned value will be in the range 1151dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * of 0 - (mod-1) 1161dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 1171dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic u_int16_t 1181dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectpmod(u_int16_t gen, u_int16_t exp, u_int16_t mod) 1191dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 1201dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_int16_t s, t, u; 1211dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1221dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project s = 1; 1231dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project t = gen; 1241dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u = exp; 1251dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1261dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project while (u) { 1271dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (u & 1) 1281dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project s = (s * t) % mod; 1291dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u >>= 1; 1301dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project t = (t * t) % mod; 1311dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1321dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return (s); 1331dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 1341dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1351dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* 1361dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 15-bit permutation based on Luby-Rackoff block cipher 1371dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 1381dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectu_int 1391dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectpermute15(u_int in) 1401dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 1411dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project int i; 1421dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_int left, right, tmp; 1431dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1441dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (ru_prf == NULL) 1451dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return in; 1461dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1471dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project left = (in >> 8) & 0x7f; 1481dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project right = in & 0xff; 1491dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1501dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* 1511dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Each round swaps the width of left and right. Even rounds have 1521dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * a 7-bit left, odd rounds have an 8-bit left. Since this uses an 1531dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * odd number of rounds, left is always 8 bits wide at the end. 1541dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 1551dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project for (i = 0; i < RU_ROUNDS; i++) { 1561dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if ((i & 1) == 0) 1571dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project tmp = ru_prf->prf8[(i << (8 - 1)) | right] & 0x7f; 1581dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project else 1591dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project tmp = ru_prf->prf7[((i - 1) << (7 - 1)) | right]; 1601dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project tmp ^= left; 1611dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project left = right; 1621dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project right = tmp; 1631dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 1641dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1651dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return (right << 8) | left; 1661dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 1671dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1681dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project/* 1691dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Initializes the seed and chooses a suitable generator. Also toggles 1701dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * the msb flag. The msb flag is used to generate two distinct 1711dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * cycles of random numbers and thus avoiding reuse of ids. 1721dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * 1731dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * This function is called from res_randomid() when needed, an 1741dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * application does not have to worry about it. 1751dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 1761dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectstatic void 1771dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectres_initid(void) 1781dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 1791dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_int16_t j, i; 1801dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_int32_t tmp; 1811dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project int noprime = 1; 1821dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project struct timeval tv; 1831dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1841dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_x = arc4random_uniform(RU_M); 1851dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1861dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* 15 bits of random seed */ 1871dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project tmp = arc4random(); 1881dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_seed = (tmp >> 16) & 0x7FFF; 1891dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_seed2 = tmp & 0x7FFF; 1901dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1911dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* Determine the LCG we use */ 1921dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project tmp = arc4random(); 1931dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_b = (tmp & 0xfffe) | 1; 1941dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M); 1951dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project while (ru_b % 3 == 0) 1961dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_b += 2; 1971dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 1981dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project j = arc4random_uniform(RU_N); 1991dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2001dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* 2011dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * Do a fast gcd(j,RU_N-1), so we can find a j with 2021dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * gcd(j, RU_N-1) == 1, giving a new generator for 2031dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project * RU_GEN^j mod RU_N 2041dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project */ 2051dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2061dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project while (noprime) { 2071dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project for (i = 0; i < PFAC_N; i++) 2081dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (j % pfacts[i] == 0) 2091dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project break; 2101dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2111dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (i >= PFAC_N) 2121dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project noprime = 0; 2131dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project else 2141dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project j = (j + 1) % RU_N; 2151dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 2161dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2171dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_g = pmod(RU_GEN, j, RU_N); 2181dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_counter = 0; 2191dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2201dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* Initialise PRF for Luby-Rackoff permutation */ 2211dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (ru_prf == NULL) 2221dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_prf = malloc(sizeof(*ru_prf)); 2231dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (ru_prf != NULL) 2241dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project arc4random_buf(ru_prf, sizeof(*ru_prf)); 2251dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2261dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project gettimeofday(&tv, NULL); 2271dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_reseed = tv.tv_sec + RU_OUT; 2281dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_msb = ru_msb == 0x8000 ? 0 : 0x8000; 2291dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 2301dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2311dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectu_int 2321dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectres_randomid(void) 2331dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 2341dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project struct timeval tv; 2351dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_int result; 2361dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2371dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project _RES_RANDOM_LOCK() 2381dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project gettimeofday(&tv, NULL); 2391dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project if (ru_counter >= RU_MAX || tv.tv_sec > ru_reseed) 2401dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project res_initid(); 2411dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2421dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project /* Linear Congruential Generator */ 2431dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_x = (ru_a * ru_x + ru_b) % RU_M; 2441dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project ru_counter++; 2451dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2461dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project result = permute15(ru_seed ^ pmod(ru_g, ru_seed2 + ru_x, RU_N)) | ru_msb; 2471dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project _RES_RANDOM_UNLOCK() 2481dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return result; 2491dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 2501dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2511dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#if 0 2521dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectint 2531dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Projectmain(int argc, char **argv) 2541dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project{ 2551dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project int i, n; 2561dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project u_int16_t wert; 2571dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2581dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project res_initid(); 2591dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2601dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("Generator: %u\n", ru_g); 2611dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("Seed: %u\n", ru_seed); 2621dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("Reseed at %ld\n", ru_reseed); 2631dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("Ru_X: %u\n", ru_x); 2641dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("Ru_A: %u\n", ru_a); 2651dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("Ru_B: %u\n", ru_b); 2661dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 2671dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project n = argc > 1 ? atoi(argv[1]) : 60001; 2681dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project for (i=0;i<n;i++) { 2691dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project wert = res_randomid(); 2701dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project printf("%u\n", wert); 2711dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project } 2721dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project return 0; 2731dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project} 2741dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project#endif 2751dc9e472e19acfe6dc7f41e429236e7eef7ceda1The Android Open Source Project 276