a62d3877 |
1 | /* -*-c-*- |
2 | * |
c758e654 |
3 | * $Id: rand.c,v 1.3 1998/01/12 16:46:23 mdw Exp $ |
a62d3877 |
4 | * |
5 | * Random number generation |
6 | * |
c758e654 |
7 | * (c) 1998 EBI |
a62d3877 |
8 | */ |
9 | |
10 | /*----- Licencing notice --------------------------------------------------* |
11 | * |
12 | * This file is part of Become. |
13 | * |
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. |
18 | * |
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. |
23 | * |
24 | * You should have received a copy of the GNU General Public License |
a37d956f |
25 | * along with `become'; if not, write to the Free Software Foundation, |
26 | * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
a62d3877 |
27 | */ |
28 | |
29 | /*----- Revision history --------------------------------------------------* |
30 | * |
31 | * $Log: rand.c,v $ |
c758e654 |
32 | * Revision 1.3 1998/01/12 16:46:23 mdw |
33 | * Fix copyright date. |
34 | * |
a37d956f |
35 | * Revision 1.2 1997/08/07 09:47:07 mdw |
36 | * Fix address of the FSF. |
37 | * |
a62d3877 |
38 | * Revision 1.1 1997/08/07 09:46:05 mdw |
39 | * New source file added to maintain a randomness pool. |
40 | * |
41 | */ |
42 | |
43 | /*----- Header files ------------------------------------------------------*/ |
44 | |
45 | /* --- ANSI headers --- */ |
46 | |
47 | #include <ctype.h> |
48 | #include <errno.h> |
49 | #include <stdio.h> |
50 | #include <stdlib.h> |
51 | #include <string.h> |
52 | #include <time.h> |
53 | |
54 | /* --- Local headers --- */ |
55 | |
56 | #include "become.h" |
57 | #include "config.h" |
58 | #include "icrypt.h" |
59 | #include "md5.h" |
60 | #include "rand.h" |
61 | #include "tx.h" |
62 | #include "utils.h" |
63 | |
64 | /*----- Magic numbers -----------------------------------------------------*/ |
65 | |
66 | #define rand__seedBits 512 /* Number of random seed bits */ |
67 | |
68 | /*----- Persistant state --------------------------------------------------*/ |
69 | |
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 */ |
73 | |
74 | /*----- Main code ---------------------------------------------------------*/ |
75 | |
76 | /* --- @rand_read@ --- * |
77 | * |
78 | * Arguments: @FILE *fp@ = pointer to file to read from |
79 | * |
80 | * Returns: --- |
81 | * |
82 | * Use: Reads a random number seed from the stream. |
83 | */ |
84 | |
85 | void rand_read(FILE *fp) |
86 | { |
87 | tx_getBits(rand__pool, rand__seedBits, fp); |
88 | rand__i = 0; |
89 | rand__r = 0; |
90 | T( traceblk(TRACE_RAND, "rand: loaded randomness pool", |
91 | rand__pool, sizeof(rand__pool)); ) |
92 | } |
93 | |
94 | /* --- @rand_write@ --- * |
95 | * |
96 | * Arguments: @FILE *fp@ = pointer to file to write on |
97 | * |
98 | * Returns: --- |
99 | * |
100 | * Use: Writes a random number seed back to the stream. |
101 | */ |
102 | |
103 | void rand_write(FILE *fp) |
104 | { |
105 | rand_churn(); |
106 | tx_putBits(rand__pool, rand__seedBits, fp); |
107 | } |
108 | |
109 | /* --- @rand_clear@ --- * |
110 | * |
111 | * Arguments: --- |
112 | * |
113 | * Returns: --- |
114 | * |
115 | * Use: Clears the random number pool. |
116 | */ |
117 | |
118 | void rand_clear(void) |
119 | { |
120 | memset(rand__pool, 0, sizeof(rand__pool)); |
121 | T( trace(TRACE_RAND, "rand: cleared randomness pool"); ) |
122 | rand__i = 0; |
123 | rand__r = 0; |
124 | } |
125 | |
126 | /* --- @rand_encrypt@ --- * |
127 | * |
128 | * Arguments: @icrypt_job *j@ = pointer to an encryption job to apply |
129 | * |
130 | * Returns: --- |
131 | * |
132 | * Use: Encrypts the randomness pool with a given key. This should |
133 | * be done before use, in case the pool gets compromised. |
134 | */ |
135 | |
136 | void rand_encrypt(icrypt_job *j) |
137 | { |
138 | icrypt_encrypt(j, rand__pool, rand__pool, sizeof(rand__pool)); |
139 | rand__i = 0; |
140 | rand__r = 0; |
141 | T( traceblk(TRACE_RAND, "encrypted randomness pool", |
142 | rand__pool, sizeof(rand__pool)); ) |
143 | } |
144 | |
145 | /* --- @rand_add@ --- * |
146 | * |
147 | * Arguments: @const void *p@ = pointer to some data |
148 | * @size_t sz@ = size of the data in bytes |
149 | * |
150 | * Returns: --- |
151 | * |
152 | * Use: Adds entropy to the pool. |
153 | */ |
154 | |
155 | void rand_add(const void *p, size_t sz) |
156 | { |
157 | /* --- Method --- * |
158 | * |
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 |
161 | * by SHA-1. |
162 | * |
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.) |
167 | */ |
168 | |
169 | size_t i = rand__i; |
170 | const unsigned char *cp = p; |
171 | size_t mask = (rand__seedBits / 8) - 1; |
172 | size_t r = rand__r; |
173 | unsigned int x; |
174 | |
175 | /* --- Ensure the polynomial is valid --- * |
176 | * |
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. |
180 | */ |
181 | |
182 | #if rand__seedBits / 8 != 64 |
183 | # error Change the polynomal in rand_add |
184 | #endif |
185 | |
186 | T( traceblk(TRACE_RAND, "rand: incoming entropy", p, sz); ) |
187 | |
188 | /* --- Add values to the entropy pool --- */ |
189 | |
190 | while (sz) { |
191 | x = *cp++ & 0xffu; |
192 | if (r) |
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; |
199 | sz--; |
200 | i = (i + 1) & mask; |
201 | r = (r + 3) & 7; |
202 | } |
203 | |
204 | /* --- Update the global counters --- */ |
205 | |
206 | rand__r = r; |
207 | rand__i = i; |
208 | |
209 | T( traceblk(TRACE_RAND, "rand: added some entropy", |
210 | rand__pool, sizeof(rand__pool)); ) |
211 | } |
212 | |
213 | /* --- @rand_extract@ --- * |
214 | * |
215 | * Arguments: @unsigned char *b@ = pointer to output buffer |
216 | * @size_t sz@ = number of bytes wanted |
217 | * |
218 | * Returns: --- |
219 | * |
220 | * Use: Produces a number of random bytes. |
221 | */ |
222 | |
223 | void rand_extract(unsigned char *b, size_t sz) |
224 | { |
225 | /* --- Method --- * |
226 | * |
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. |
231 | * |
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. |
235 | */ |
236 | |
237 | size_t c; |
238 | unsigned char mdbuf[MD5_HASHSIZE]; |
239 | md5 md; |
240 | |
241 | T( trace(TRACE_RAND, "rand: extracting entropy"); ) |
242 | |
243 | while (sz) { |
244 | c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; |
245 | md5_init(&md); |
246 | md5_buffer(&md, rand__pool, sizeof(rand__pool)); |
247 | md5_final(&md, mdbuf); |
248 | memcpy(b, mdbuf, c); |
249 | rand_add(mdbuf, c); |
250 | b += c; sz -= c; |
251 | } |
252 | burn(mdbuf); burn(md); |
253 | |
254 | T( trace(TRACE_RAND, "rand: finished extracting entropy"); ) |
255 | } |
256 | |
257 | /* --- @rand_churn@ --- * |
258 | * |
259 | * Arguments: --- |
260 | * |
261 | * Returns: --- |
262 | * |
263 | * Use: Churns the randomness pool completely. The pool is replaced |
264 | * by repeated MD5-ings of itself. |
265 | */ |
266 | |
267 | void rand_churn(void) |
268 | { |
269 | md5 md; |
270 | unsigned char mdbuf[MD5_HASHSIZE]; |
271 | size_t sz = sizeof(rand__pool); |
272 | size_t c; |
273 | |
274 | T( trace(TRACE_RAND, "rand: churning pool"); ) |
275 | |
276 | rand__i = 0; |
277 | rand__r = 0; |
278 | |
279 | while (sz) { |
280 | c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; |
281 | md5_init(&md); |
282 | md5_buffer(&md, rand__pool, sizeof(rand__pool)); |
283 | md5_final(&md, mdbuf); |
284 | rand_add(mdbuf, c); |
285 | sz -= c; |
286 | } |
287 | |
288 | rand__i = 0; |
289 | rand__r = 0; |
290 | |
291 | burn(mdbuf); burn(md); |
292 | |
293 | T( trace(TRACE_RAND, "rand: finished churning pool"); ) |
294 | } |
295 | |
296 | /*----- That's all, folks -------------------------------------------------*/ |