1 /* Yarrow Random Number Generator (True Randomness Achieved in Software) *
2 * Copyright (c) 1998-2000 by Yarrow Charnot, Identikey <mailto://ycharnot@identikey.com>
3 * All Lefts, Rights, Ups, Downs, Forwards, Backwards, Pasts and Futures Reserved *
4 */
5
6 /* Made into a BeOS /dev/random and /dev/urandom by Daniel Berlin */
7
8
9 #include "yarrow_rng.h"
10
11 #include <stdlib.h>
12 #include <thread.h>
13
14
15 //#define TRACE_DRIVER
16 #ifdef TRACE_DRIVER
17 # define TRACE(x...) dprintf("random: " x)
18 #else
19 # define TRACE(x...) ;
20 #endif
21 #define CALLED() TRACE("CALLED %s\n", __PRETTY_FUNCTION__)
22
23
24 #define rotr32(x, n) ((((uint32)(x)) >> ((int) ((n) & 31))) | (((uint32)(x)) << ((int) ((32 - ((n) & 31))))))
25 #define rotl32(x, n) ((((uint32)(x)) << ((int) ((n) & 31))) | (((uint32)(x)) >> ((int) ((32 - ((n) & 31))))))
26
27 #define bswap32(x) \
28 ((rotl32((uint32)(x), 8) & 0x00ff00ff) | (rotr32((uint32)(x), 8) & 0xff00ff00))
29
30 typedef union _OCTET {
31 uint64 Q[1];
32 uint32 D[2];
33 uint16 W[4];
34 uint8 B[8];
35 } OCTET;
36
37 #define NK 257 /* internal state size */
38 #define NI 120 /* seed in increment */
39 #define NA 70 /* rand out increment A */
40 #define NB 139 /* rand out increment B */
41
42 typedef struct _ch_randgen {
43 OCTET ira[NK]; /* numbers live here */
44 OCTET *seedptr; /* next seed pointer */
45 OCTET *rndptrA; /* randomizing pointer #1 */
46 OCTET *rndptrB; /* randomizing pointer #2 */
47 OCTET *rndptrX; /* main randout pointer */
48 OCTET rndLeft; /* left rand accumulator */
49 OCTET rndRite; /* rite rand accumulator */
50 } ch_randgen;
51
52
53 static ch_randgen *sRandomEnv;
54 static uint32 sRandomCount = 0;
55
56 extern void hash_block(const unsigned char *block, const unsigned int block_byte_size, unsigned char *md);
57
58
59 #define HASH_BITS 160 /* I use Tiger. Modify it to match your HASH */
60 #define HASH_BLOCK_BITS 512 /* I use Tiger. Modify it to match your HASH */
61 #define HASH_BYTES (HASH_BITS / 8)
62 #define HASH_BLOCK_BYTES (HASH_BLOCK_BITS / 8)
63 #define HASH_OCTETS (HASH_BITS / 64)
64 #define HASH_BLOCK_OCTETS (HASH_BLOCK_BITS / 64)
65
66
67 /* attach by Yarrow Charnot. attaches x to y. can be seen as about 2-3 rounds of RC6 encryption
68 */
69
70 static inline void
attach(OCTET * y,const OCTET * x,const uint32 anyA,const uint32 anyB,const uint32 oddC,const uint32 oddD)71 attach(OCTET *y, const OCTET *x, const uint32 anyA, const uint32 anyB,
72 const uint32 oddC, const uint32 oddD)
73 {
74 OCTET _x;
75 OCTET _y;
76
77 _x.D[0] = x->D[0];
78 _x.D[1] = x->D[1];
79 _y.D[0] = y->D[0];
80 _y.D[1] = y->D[1];
81 _x.D[0] = rotl32(((bswap32(_x.D[0]) | 1) * x->D[1]), 5);
82 _x.D[1] = rotl32((bswap32(_x.D[1]) | 1) * x->D[0], 5);
83 _y.D[0] = (bswap32(rotl32(_y.D[0] ^ _x.D[0], _x.D[1])) + anyA) * oddC;
84 _y.D[1] = (bswap32(rotl32(_y.D[1] ^ _x.D[1], _x.D[0])) + anyB) * oddD;
85 y->D[1] = _y.D[0];
86 y->D[0] = _y.D[1];
87 }
88
89
90 /** detach by Yarrow Charnot. detaches x from y. can be seen as about
91 * 2-3 rounds of RC6 decryption.
92 */
93
94 static inline void
detach(OCTET * y,const OCTET * x,const uint32 sameA,const uint32 sameB,const uint32 invoddC,const uint32 invoddD)95 detach(OCTET *y, const OCTET *x, const uint32 sameA, const uint32 sameB,
96 const uint32 invoddC, const uint32 invoddD)
97 {
98 OCTET _x;
99 OCTET _y;
100
101 _x.D[0] = x->D[0];
102 _x.D[1] = x->D[1];
103 _y.D[0] = y->D[1];
104 _y.D[1] = y->D[0];
105 _x.D[0] = rotl32((bswap32(_x.D[0]) | 1) * x->D[1], 5);
106 _x.D[1] = rotl32((bswap32(_x.D[1]) | 1) * x->D[0], 5);
107 _y.D[0] = rotr32(bswap32(_y.D[0] * invoddC - sameA), _x.D[1]) ^ _x.D[0];
108 _y.D[1] = rotr32(bswap32(_y.D[1] * invoddD - sameB), _x.D[0]) ^ _x.D[1];
109 y->D[0] = _y.D[0];
110 y->D[1] = _y.D[1];
111 }
112
113
114 /** QUICKLY seeds in a 64 bit number, modified so that a subsequent call really
115 * "stirs" in another seed value (no bullshit XOR here!)
116 */
117
118 static inline void
chseed(ch_randgen * prandgen,const uint64 seed)119 chseed(ch_randgen *prandgen, const uint64 seed)
120 {
121 prandgen->seedptr += NI;
122 if (prandgen->seedptr >= (prandgen->ira + NK))
123 prandgen->seedptr -= NK;
124
125 attach(prandgen->seedptr, (OCTET *) &seed, 0x213D42F6U, 0x6552DAF9U,
126 0x2E496B7BU, 0x1749A255U);
127 }
128
129
130 /** The heart of Yarrow 2000 Chuma Random Number Generator: fast and reliable
131 * randomness collection.
132 * Thread yielding function is the most OPTIMAL source of randomness combined
133 * with a clock counter.
134 * It doesn't have to switch to another thread, the call itself is random enough.
135 * Test it yourself.
136 * This FASTEST way to collect minimal randomness on each step couldn't use the
137 * processor any LESS. Even functions based on just creation of threads and their
138 * destruction can not compare by speed.
139 * Temporary file creation is just a little extra thwart to bewilder the processor
140 * cache and pipes.
141 * If you make clock_counter() (system_time()) return all 0's, still produces a
142 * stream indistinguishable from random.
143 */
144
145 static void
reseed(ch_randgen * prandgen,const uint32 initTimes)146 reseed(ch_randgen *prandgen, const uint32 initTimes)
147 {
148 volatile uint32 i, j;
149 OCTET x, y;
150
151 x.Q[0] = 0;
152
153 for (j = initTimes; j; j--) {
154 for (i = NK * initTimes; i; i--) {
155 // TODO: Yielding sounds all nice in principle, but this will take
156 // ages (at least initTimes * initTimes * NK * quantum, i.e. ca. 49s
157 // for initTimes == 8) in a busy system. Since perl initializes its
158 // random seed on startup by reading from /dev/urandom, perl
159 // programs are all but unusable when at least one other thread
160 // hogs the CPU.
161 thread_yield();
162
163 // TODO: Introduce a clock_counter() function that directly returns
164 // the value of the hardware clock counter. This will be cheaper
165 // and will yield more randomness.
166 y.Q[0] += system_time();
167 attach(&x, &y, 0x52437EFFU, 0x026A4CEBU, 0xD9E66AC9U, 0x56E5A975U);
168 attach(&y, &x, 0xC70B8B41U, 0x9126B036U, 0x36CC6FDBU, 0x31D477F7U);
169 chseed(prandgen, y.Q[0]);
170 }
171 }
172 }
173
174
175 /* returns a 64 bit of Yarrow 2000 Chuma RNG random number */
176
177 static inline uint64
chrand(ch_randgen * prandgen)178 chrand(ch_randgen *prandgen)
179 {
180 prandgen->rndptrX++;
181 prandgen->rndptrA += NA;
182 prandgen->rndptrB += NB;
183 if (prandgen->rndptrX >= (prandgen->ira + NK)) {
184 prandgen->rndptrX -= NK;
185 reseed (prandgen, 1);
186 }
187
188 if (prandgen->rndptrA >= (prandgen->ira + NK))
189 prandgen->rndptrA -= NK;
190 if (prandgen->rndptrB >= (prandgen->ira + NK))
191 prandgen->rndptrB -= NK;
192
193 attach(&prandgen->rndLeft, prandgen->rndptrX, prandgen->rndptrA->D[0],
194 prandgen->rndptrA->D[1], 0x49A3BC71UL, 0x60E285FDUL);
195 attach(&prandgen->rndRite, &prandgen->rndLeft, prandgen->rndptrB->D[0],
196 prandgen->rndptrB->D[1], 0xC366A5FDUL, 0x20C763EFUL);
197
198 chseed(prandgen, prandgen->rndRite.Q[0]);
199
200 return prandgen->rndRite.Q[0] ^ prandgen->rndLeft.Q[0];
201 }
202
203
204 /** returns a 32 bit random number */
205
206 static inline uint32
chrand32(ch_randgen * prandgen)207 chrand32(ch_randgen *prandgen)
208 {
209 OCTET r = {{chrand(prandgen)}};
210 return r.D[0] ^ r.D[1];
211 }
212
213
214 /** returns an 8 bit random number */
215
216 static inline uint8
chrand8(ch_randgen * prandgen)217 chrand8(ch_randgen *prandgen)
218 {
219 OCTET r = {{chrand(prandgen)}};
220 return r.B[0] ^ r.B[1] ^ r.B[2] ^ r.B[3] ^ r.B[4] ^ r.B[5] ^ r.B[6] ^ r.B[7];
221 }
222
223 /* generates a cryptographically secure random big number 0 <= x < 32^n */
224 /* automatically reseeds if necessary or if requested 1/16 of the internal state or more */
225 /*
226 __inline void bigrand (ch_randgen *prandgen, unsigned __int32 *x, unsigned __int32 n)
227 {
228 unsigned int i;
229 OCTET block[HASH_BLOCK_OCTETS];
230 OCTET hash[HASH_OCTETS];
231 OCTET *j;
232 if (n >= NK/8) reseed (prandgen, 1);
233 for (*x++ = n; (signed) n > 0; )
234 {
235 for (i = 0; i < HASH_BLOCK_OCTETS; i++) block->Q[i] += chrand (prandgen) + hash
236 ->Q[i % HASH_OCTETS];
237 hash_block (block->B, HASH_BLOCK_BYTES, hash->B);
238 for (i = HASH_OCTETS, j = hash; i && ((signed) n > 0); i--, j++, x += 2, n -= 2)
239 {
240 attach ((OCTET *) &x, j, 0x0AEF7ED2U, 0x3F85C5C1U, 0xD3EFB373U,
241 0x13ECF0B9U);
242 }
243 }
244 }
245 */
246
247
248 /** Initializes Yarrow 2000 Chuma Random Number Generator.
249 * Reseeding about 8 times prior to the first use is recommended.
250 * More than 16 will probably be a bit too much as time increases
251 * by n^2.
252 */
253
254 static ch_randgen *
new_chrand(const unsigned int inittimes)255 new_chrand(const unsigned int inittimes)
256 {
257 ch_randgen *prandgen;
258
259 prandgen = (ch_randgen *)malloc(sizeof(ch_randgen));
260 if (prandgen == NULL)
261 return NULL;
262
263 prandgen->seedptr = prandgen->ira;
264 prandgen->rndptrX = prandgen->ira;
265 prandgen->rndptrA = prandgen->ira;
266 prandgen->rndptrB = prandgen->ira;
267 prandgen->rndLeft.Q[0] = 0x1A4B385C72D69E0FULL;
268 prandgen->rndRite.Q[0] = 0x9C805FE7361A42DBULL;
269 reseed (prandgen, inittimes);
270
271 prandgen->seedptr = prandgen->ira + chrand (prandgen) % NK;
272 prandgen->rndptrX = prandgen->ira + chrand (prandgen) % NK;
273 prandgen->rndptrA = prandgen->ira + chrand (prandgen) % NK;
274 prandgen->rndptrB = prandgen->ira + chrand (prandgen) % NK;
275 return prandgen;
276 }
277
278
279 /** Clean up after chuma */
280
281 static void
kill_chrand(ch_randgen * randgen)282 kill_chrand(ch_randgen *randgen)
283 {
284 free(sRandomEnv);
285 }
286
287
288 // #pragma mark -
289
290
291 status_t
yarrow_init()292 yarrow_init()
293 {
294 CALLED();
295 sRandomEnv = new_chrand(8);
296 if (sRandomEnv == NULL)
297 return B_NO_MEMORY;
298 return B_OK;
299 }
300
301
302 void
yarrow_uninit()303 yarrow_uninit()
304 {
305 CALLED();
306 kill_chrand(sRandomEnv);
307 }
308
309
310 status_t
yarrow_rng_read(void * cookie,void * _buffer,size_t * _numBytes)311 yarrow_rng_read(void* cookie, void *_buffer, size_t *_numBytes)
312 {
313 if (!IS_USER_ADDRESS(_buffer))
314 return B_BAD_ADDRESS;
315
316 sRandomCount += *_numBytes;
317
318 /* Reseed if we have or are gonna use up > 1/16th the entropy around */
319 if (sRandomCount >= NK/8) {
320 sRandomCount = 0;
321 reseed(sRandomEnv, 1);
322 }
323
324 /* ToDo: Yes, i know this is not the way we should do it. What we really should do is
325 * take the md5 or sha1 hash of the state of the pool, and return that. Someday.
326 */
327 int32 *buffer = (int32 *)_buffer;
328 uint32 i;
329 for (i = 0; i < *_numBytes / 4; i++) {
330 int32 data = chrand32(sRandomEnv);
331 if (user_memcpy(&buffer[i], &data, sizeof(data)) < B_OK)
332 return B_BAD_ADDRESS;
333 }
334 uint8 *buffer8 = (uint8 *)_buffer;
335 for (uint32 j = 0; j < *_numBytes % 4; j++) {
336 int8 data = chrand8(sRandomEnv);
337 if (user_memcpy(&buffer8[(i * 4) + j], &data, sizeof(data)) < B_OK)
338 return B_BAD_ADDRESS;
339 }
340 return B_OK;
341 }
342
343
344 status_t
yarrow_rng_write(void * cookie,const void * _buffer,size_t * _numBytes)345 yarrow_rng_write(void* cookie, const void *_buffer, size_t *_numBytes)
346 {
347 OCTET *buffer = (OCTET*)_buffer;
348
349 if (!IS_USER_ADDRESS(buffer))
350 return B_BAD_ADDRESS;
351
352 for (size_t i = 0; i < *_numBytes / sizeof(OCTET); i++) {
353 OCTET data;
354 if (user_memcpy(&data, buffer, sizeof(data)) < B_OK)
355 return B_BAD_ADDRESS;
356 chseed(sRandomEnv, data.Q[0]);
357 buffer++;
358 }
359 return B_OK;
360 }
361
362
363 void
yarrow_enqueue_randomness(const uint64 value)364 yarrow_enqueue_randomness(const uint64 value)
365 {
366 CALLED();
367 chseed(sRandomEnv, value);
368 }
369