3 * $Id: rand.c,v 1.3 1998/01/12 16:46:23 mdw Exp $
5 * Random number generation
10 /*----- Licencing notice --------------------------------------------------*
12 * This file is part of Become.
14 * Become is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
19 * Become is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
24 * You should have received a copy of the GNU General Public License
25 * along with `become'; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
29 /*----- Revision history --------------------------------------------------*
32 * Revision 1.3 1998/01/12 16:46:23 mdw
35 * Revision 1.2 1997/08/07 09:47:07 mdw
36 * Fix address of the FSF.
38 * Revision 1.1 1997/08/07 09:46:05 mdw
39 * New source file added to maintain a randomness pool.
43 /*----- Header files ------------------------------------------------------*/
45 /* --- ANSI headers --- */
54 /* --- Local headers --- */
64 /*----- Magic numbers -----------------------------------------------------*/
66 #define rand__seedBits 512 /* Number of random seed bits */
68 /*----- Persistant state --------------------------------------------------*/
70 static unsigned char rand__pool
[rand__seedBits
/ 8]; /* Entropy pool */
71 static size_t rand__i
= 0; /* Index into entropy pool */
72 static size_t rand__r
= 0; /* Rotation to apply to next byte */
74 /*----- Main code ---------------------------------------------------------*/
76 /* --- @rand_read@ --- *
78 * Arguments: @FILE *fp@ = pointer to file to read from
82 * Use: Reads a random number seed from the stream.
85 void rand_read(FILE *fp
)
87 tx_getBits(rand__pool
, rand__seedBits
, fp
);
90 T( traceblk(TRACE_RAND
, "rand: loaded randomness pool",
91 rand__pool
, sizeof(rand__pool
)); )
94 /* --- @rand_write@ --- *
96 * Arguments: @FILE *fp@ = pointer to file to write on
100 * Use: Writes a random number seed back to the stream.
103 void rand_write(FILE *fp
)
106 tx_putBits(rand__pool
, rand__seedBits
, fp
);
109 /* --- @rand_clear@ --- *
115 * Use: Clears the random number pool.
118 void rand_clear(void)
120 memset(rand__pool
, 0, sizeof(rand__pool
));
121 T( trace(TRACE_RAND
, "rand: cleared randomness pool"); )
126 /* --- @rand_encrypt@ --- *
128 * Arguments: @icrypt_job *j@ = pointer to an encryption job to apply
132 * Use: Encrypts the randomness pool with a given key. This should
133 * be done before use, in case the pool gets compromised.
136 void rand_encrypt(icrypt_job
*j
)
138 icrypt_encrypt(j
, rand__pool
, rand__pool
, sizeof(rand__pool
));
141 T( traceblk(TRACE_RAND
, "encrypted randomness pool",
142 rand__pool
, sizeof(rand__pool
)); )
145 /* --- @rand_add@ --- *
147 * Arguments: @const void *p@ = pointer to some data
148 * @size_t sz@ = size of the data in bytes
152 * Use: Adds entropy to the pool.
155 void rand_add(const void *p
, size_t sz
)
159 * Entropy is inserted byte-by-byte. The method used is derived from
160 * Linux's `drivers/char/random.c', which is in turn appears to be inspired
163 * Imagine the randomness pool as 8 parallel shift registers. To insert
164 * a byte into the pool, XOR it with bytes picked according to a primitive
165 * polynomial mod 2, and rotate one place to the left. (The rotation is
166 * from SHA-1; it introduces some interaction between the registers.)
170 const unsigned char *cp
= p
;
171 size_t mask
= (rand__seedBits
/ 8) - 1;
175 /* --- Ensure the polynomial is valid --- *
177 * The current polynomal is %$x^{64} + x^4 + x^3 + x + 1$% (picked from
178 * Schneier's excellent book). If the pool size changes, though, I'll
179 * need another polynomial.
182 #if rand__seedBits / 8 != 64
183 # error Change the polynomal in rand_add
186 T( traceblk(TRACE_RAND
, "rand: incoming entropy", p
, sz
); )
188 /* --- Add values to the entropy pool --- */
193 x
= ((x
<< r
) | (x
>> (8 - r
)));
194 x
^= (rand__pool
[i
] ^
195 rand__pool
[(i
+ 1) & mask
] ^
196 rand__pool
[(i
+ 3) & mask
] ^
197 rand__pool
[(i
+ 4) & mask
]);
198 rand__pool
[i
] = ((x
<< 1) | (x
>> 7)) & 0xffu
;
204 /* --- Update the global counters --- */
209 T( traceblk(TRACE_RAND
, "rand: added some entropy",
210 rand__pool
, sizeof(rand__pool
)); )
213 /* --- @rand_extract@ --- *
215 * Arguments: @unsigned char *b@ = pointer to output buffer
216 * @size_t sz@ = number of bytes wanted
220 * Use: Produces a number of random bytes.
223 void rand_extract(unsigned char *b
, size_t sz
)
227 * Hash the buffer with a secure hash (or, in this case, with MD5 and hope
228 * for the best...). If this gives us enough bytes, fill the output
229 * buffer; otherwise copy the whole hash out. The contribute the hash back
230 * into the randomness pool with @rand_add@ to provide some feedback.
232 * The secure hash gives us good mixing over the whole of the randomness
233 * pool, and attempts to ensure that an attacker receiving our random
234 * numbers can't predict any numbers we don't actually give him.
238 unsigned char mdbuf
[MD5_HASHSIZE
];
241 T( trace(TRACE_RAND
, "rand: extracting entropy"); )
244 c
= (sz
>= sizeof(mdbuf
)) ?
sizeof(mdbuf
) : sz
;
246 md5_buffer(&md
, rand__pool
, sizeof(rand__pool
));
247 md5_final(&md
, mdbuf
);
252 burn(mdbuf
); burn(md
);
254 T( trace(TRACE_RAND
, "rand: finished extracting entropy"); )
257 /* --- @rand_churn@ --- *
263 * Use: Churns the randomness pool completely. The pool is replaced
264 * by repeated MD5-ings of itself.
267 void rand_churn(void)
270 unsigned char mdbuf
[MD5_HASHSIZE
];
271 size_t sz
= sizeof(rand__pool
);
274 T( trace(TRACE_RAND
, "rand: churning pool"); )
280 c
= (sz
>= sizeof(mdbuf
)) ?
sizeof(mdbuf
) : sz
;
282 md5_buffer(&md
, rand__pool
, sizeof(rand__pool
));
283 md5_final(&md
, mdbuf
);
291 burn(mdbuf
); burn(md
);
293 T( trace(TRACE_RAND
, "rand: finished churning pool"); )
296 /*----- That's all, folks -------------------------------------------------*/