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
30typedef 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
42typedef 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
53static ch_randgen *sRandomEnv;
54static uint32 sRandomCount = 0;
55
56extern 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
70static inline void
71attach(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
94static inline void
95detach(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
118static inline void
119chseed(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
145static void
146reseed(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
177static inline uint64
178chrand(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
206static inline uint32
207chrand32(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
216static inline uint8
217chrand8(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
254static ch_randgen *
255new_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
281static void
282kill_chrand(ch_randgen *randgen)
283{
284	free(sRandomEnv);
285}
286
287
288//	#pragma mark -
289
290
291status_t
292yarrow_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
302void
303yarrow_uninit()
304{
305	CALLED();
306	kill_chrand(sRandomEnv);
307}
308
309
310status_t
311yarrow_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
344status_t
345yarrow_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
363void
364yarrow_enqueue_randomness(const uint64 value)
365{
366	CALLED();
367	chseed(sRandomEnv, value);
368}
369