1/*      $OpenBSD: arc4random.c,v 1.19 2008/06/04 00:50:23 djm Exp $        */
2
3/*
4 * Copyright (c) 1996, David Mazieres <dm@uun.org>
5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20/*
21 * Arc4 random number generator for OpenBSD.
22 *
23 * This code is derived from section 17.1 of Applied Cryptography,
24 * second edition, which describes a stream cipher allegedly
25 * compatible with RSA Labs "RC4" cipher (the actual description of
26 * which is a trade secret).  The same algorithm is used as a stream
27 * cipher called "arcfour" in Tatu Ylonen's ssh package.
28 *
29 * Here the stream cipher has been modified always to include the time
30 * when initializing the state.  That makes it impossible to
31 * regenerate the same random sequence twice, so this can't be used
32 * for encryption, but will generate good random numbers.
33 *
34 * RC4 is a registered trademark of RSA Laboratories.
35 */
36
37#include <fcntl.h>
38#include <limits.h>
39#include <stdlib.h>
40#include <unistd.h>
41#include <sys/types.h>
42#include <sys/param.h>
43#include <sys/time.h>
44#include "thread_private.h"
45
46/* BIONIC-BEGIN */
47/* this lock should protect the global variables in this file */
48static pthread_mutex_t  _arc4_lock = PTHREAD_MUTEX_INITIALIZER;
49#define  _ARC4_LOCK()      pthread_mutex_lock(&_arc4_lock)
50#define  _ARC4_UNLOCK()    pthread_mutex_unlock(&_arc4_lock)
51/* BIONIC-END */
52
53#ifdef __GNUC__
54#define inline __inline
55#else                           /* !__GNUC__ */
56#define inline
57#endif                          /* !__GNUC__ */
58
59struct arc4_stream {
60        u_int8_t i;
61        u_int8_t j;
62        u_int8_t s[256];
63};
64
65static int rs_initialized;
66static struct arc4_stream rs;
67static pid_t arc4_stir_pid;
68static int arc4_count;
69
70static inline u_int8_t arc4_getbyte(void);
71
72static inline void
73arc4_init(void)
74{
75        int     n;
76
77        for (n = 0; n < 256; n++)
78                rs.s[n] = n;
79        rs.i = 0;
80        rs.j = 0;
81}
82
83static inline void
84arc4_addrandom(u_char *dat, int datlen)
85{
86        int     n;
87        u_int8_t si;
88
89        rs.i--;
90        for (n = 0; n < 256; n++) {
91                rs.i = (rs.i + 1);
92                si = rs.s[rs.i];
93                rs.j = (rs.j + si + dat[n % datlen]);
94                rs.s[rs.i] = rs.s[rs.j];
95                rs.s[rs.j] = si;
96        }
97        rs.j = rs.i;
98}
99
100static void
101arc4_stir(void)
102{
103#if 1  /* BIONIC-BEGIN */
104	int     i, fd;
105	union {
106		struct timeval tv;
107		u_int rnd[128 / sizeof(u_int)];
108	}       rdat;
109	int	n;
110
111        if (!rs_initialized) {
112                arc4_init();
113                rs_initialized = 1;
114        }
115
116	fd = open("/dev/urandom", O_RDONLY);
117	if (fd != -1) {
118		read(fd, rdat.rnd, sizeof(rdat.rnd));
119		close(fd);
120	}
121        else
122        {
123	    /* fd < 0 ?  Ah, what the heck. We'll just take
124	     * whatever was on the stack. just add a little more
125             * time-based randomness though
126             */
127            gettimeofday(&rdat.tv, NULL);
128        }
129
130        arc4_stir_pid = getpid();
131	arc4_addrandom((void *) &rdat, sizeof(rdat));
132#else  /* BIONIC-END */
133        int     i, mib[2];
134        size_t        len;
135        u_char rnd[128];
136
137        if (!rs_initialized) {
138                arc4_init();
139                rs_initialized = 1;
140        }
141
142        mib[0] = CTL_KERN;
143        mib[1] = KERN_ARND;
144
145        len = sizeof(rnd);
146        sysctl(mib, 2, rnd, &len, NULL, 0);
147
148        arc4_stir_pid = getpid();
149        arc4_addrandom(rnd, sizeof(rnd));
150#endif
151        /*
152         * Discard early keystream, as per recommendations in:
153         * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
154         */
155        for (i = 0; i < 256; i++)
156                (void)arc4_getbyte();
157        arc4_count = 1600000;
158}
159
160static inline u_int8_t
161arc4_getbyte(void)
162{
163        u_int8_t si, sj;
164
165        rs.i = (rs.i + 1);
166        si = rs.s[rs.i];
167        rs.j = (rs.j + si);
168        sj = rs.s[rs.j];
169        rs.s[rs.i] = sj;
170        rs.s[rs.j] = si;
171        return (rs.s[(si + sj) & 0xff]);
172}
173
174u_int8_t
175__arc4_getbyte(void)
176{
177        u_int8_t val;
178
179        _ARC4_LOCK();
180        if (--arc4_count == 0 || !rs_initialized)
181                arc4_stir();
182        val = arc4_getbyte();
183        _ARC4_UNLOCK();
184        return val;
185}
186
187static inline u_int32_t
188arc4_getword(void)
189{
190        u_int32_t val;
191        val = arc4_getbyte() << 24;
192        val |= arc4_getbyte() << 16;
193        val |= arc4_getbyte() << 8;
194        val |= arc4_getbyte();
195        return val;
196}
197
198void
199arc4random_stir(void)
200{
201        _ARC4_LOCK();
202        arc4_stir();
203        _ARC4_UNLOCK();
204}
205
206void
207arc4random_addrandom(u_char *dat, int datlen)
208{
209        _ARC4_LOCK();
210        if (!rs_initialized)
211                arc4_stir();
212        arc4_addrandom(dat, datlen);
213        _ARC4_UNLOCK();
214}
215
216u_int32_t
217arc4random(void)
218{
219        u_int32_t val;
220        _ARC4_LOCK();
221        arc4_count -= 4;
222        if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != getpid())
223                arc4_stir();
224        val = arc4_getword();
225        _ARC4_UNLOCK();
226        return val;
227}
228
229void
230arc4random_buf(void *_buf, size_t n)
231{
232        u_char *buf = (u_char *)_buf;
233        _ARC4_LOCK();
234        if (!rs_initialized || arc4_stir_pid != getpid())
235                arc4_stir();
236        while (n--) {
237                if (--arc4_count <= 0)
238                        arc4_stir();
239                buf[n] = arc4_getbyte();
240        }
241        _ARC4_UNLOCK();
242}
243
244/*
245 * Calculate a uniformly distributed random number less than upper_bound
246 * avoiding "modulo bias".
247 *
248 * Uniformity is achieved by generating new random numbers until the one
249 * returned is outside the range [0, 2**32 % upper_bound).  This
250 * guarantees the selected random number will be inside
251 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
252 * after reduction modulo upper_bound.
253 */
254u_int32_t
255arc4random_uniform(u_int32_t upper_bound)
256{
257        u_int32_t r, min;
258
259        if (upper_bound < 2)
260                return 0;
261
262#if (ULONG_MAX > 0xffffffffUL)
263        min = 0x100000000UL % upper_bound;
264#else
265        /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
266        if (upper_bound > 0x80000000)
267                min = 1 + ~upper_bound;                /* 2**32 - upper_bound */
268        else {
269                /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
270                min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
271        }
272#endif
273
274        /*
275         * This could theoretically loop forever but each retry has
276         * p > 0.5 (worst case, usually far better) of selecting a
277         * number inside the range we need, so it should rarely need
278         * to re-roll.
279         */
280        for (;;) {
281                r = arc4random();
282                if (r >= min)
283                        break;
284        }
285
286        return r % upper_bound;
287}
288
289#if 0
290/*-------- Test code for i386 --------*/
291#include <stdio.h>
292#include <machine/pctr.h>
293int
294main(int argc, char **argv)
295{
296        const int iter = 1000000;
297        int     i;
298        pctrval v;
299
300        v = rdtsc();
301        for (i = 0; i < iter; i++)
302                arc4random();
303        v = rdtsc() - v;
304        v /= iter;
305
306        printf("%qd cycles\n", v);
307}
308#endif
309