a62d3877 |
1 | /* -*-c-*- |
2 | * |
a37d956f |
3 | * $Id: rand.c,v 1.2 1997/08/07 09:47:07 mdw Exp $ |
a62d3877 |
4 | * |
5 | * Random number generation |
6 | * |
7 | * (c) 1997 EBI |
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 $ |
a37d956f |
32 | * Revision 1.2 1997/08/07 09:47:07 mdw |
33 | * Fix address of the FSF. |
34 | * |
a62d3877 |
35 | * Revision 1.1 1997/08/07 09:46:05 mdw |
36 | * New source file added to maintain a randomness pool. |
37 | * |
38 | */ |
39 | |
40 | /*----- Header files ------------------------------------------------------*/ |
41 | |
42 | /* --- ANSI headers --- */ |
43 | |
44 | #include <ctype.h> |
45 | #include <errno.h> |
46 | #include <stdio.h> |
47 | #include <stdlib.h> |
48 | #include <string.h> |
49 | #include <time.h> |
50 | |
51 | /* --- Local headers --- */ |
52 | |
53 | #include "become.h" |
54 | #include "config.h" |
55 | #include "icrypt.h" |
56 | #include "md5.h" |
57 | #include "rand.h" |
58 | #include "tx.h" |
59 | #include "utils.h" |
60 | |
61 | /*----- Magic numbers -----------------------------------------------------*/ |
62 | |
63 | #define rand__seedBits 512 /* Number of random seed bits */ |
64 | |
65 | /*----- Persistant state --------------------------------------------------*/ |
66 | |
67 | static unsigned char rand__pool[rand__seedBits / 8]; /* Entropy pool */ |
68 | static size_t rand__i = 0; /* Index into entropy pool */ |
69 | static size_t rand__r = 0; /* Rotation to apply to next byte */ |
70 | |
71 | /*----- Main code ---------------------------------------------------------*/ |
72 | |
73 | /* --- @rand_read@ --- * |
74 | * |
75 | * Arguments: @FILE *fp@ = pointer to file to read from |
76 | * |
77 | * Returns: --- |
78 | * |
79 | * Use: Reads a random number seed from the stream. |
80 | */ |
81 | |
82 | void rand_read(FILE *fp) |
83 | { |
84 | tx_getBits(rand__pool, rand__seedBits, fp); |
85 | rand__i = 0; |
86 | rand__r = 0; |
87 | T( traceblk(TRACE_RAND, "rand: loaded randomness pool", |
88 | rand__pool, sizeof(rand__pool)); ) |
89 | } |
90 | |
91 | /* --- @rand_write@ --- * |
92 | * |
93 | * Arguments: @FILE *fp@ = pointer to file to write on |
94 | * |
95 | * Returns: --- |
96 | * |
97 | * Use: Writes a random number seed back to the stream. |
98 | */ |
99 | |
100 | void rand_write(FILE *fp) |
101 | { |
102 | rand_churn(); |
103 | tx_putBits(rand__pool, rand__seedBits, fp); |
104 | } |
105 | |
106 | /* --- @rand_clear@ --- * |
107 | * |
108 | * Arguments: --- |
109 | * |
110 | * Returns: --- |
111 | * |
112 | * Use: Clears the random number pool. |
113 | */ |
114 | |
115 | void rand_clear(void) |
116 | { |
117 | memset(rand__pool, 0, sizeof(rand__pool)); |
118 | T( trace(TRACE_RAND, "rand: cleared randomness pool"); ) |
119 | rand__i = 0; |
120 | rand__r = 0; |
121 | } |
122 | |
123 | /* --- @rand_encrypt@ --- * |
124 | * |
125 | * Arguments: @icrypt_job *j@ = pointer to an encryption job to apply |
126 | * |
127 | * Returns: --- |
128 | * |
129 | * Use: Encrypts the randomness pool with a given key. This should |
130 | * be done before use, in case the pool gets compromised. |
131 | */ |
132 | |
133 | void rand_encrypt(icrypt_job *j) |
134 | { |
135 | icrypt_encrypt(j, rand__pool, rand__pool, sizeof(rand__pool)); |
136 | rand__i = 0; |
137 | rand__r = 0; |
138 | T( traceblk(TRACE_RAND, "encrypted randomness pool", |
139 | rand__pool, sizeof(rand__pool)); ) |
140 | } |
141 | |
142 | /* --- @rand_add@ --- * |
143 | * |
144 | * Arguments: @const void *p@ = pointer to some data |
145 | * @size_t sz@ = size of the data in bytes |
146 | * |
147 | * Returns: --- |
148 | * |
149 | * Use: Adds entropy to the pool. |
150 | */ |
151 | |
152 | void rand_add(const void *p, size_t sz) |
153 | { |
154 | /* --- Method --- * |
155 | * |
156 | * Entropy is inserted byte-by-byte. The method used is derived from |
157 | * Linux's `drivers/char/random.c', which is in turn appears to be inspired |
158 | * by SHA-1. |
159 | * |
160 | * Imagine the randomness pool as 8 parallel shift registers. To insert |
161 | * a byte into the pool, XOR it with bytes picked according to a primitive |
162 | * polynomial mod 2, and rotate one place to the left. (The rotation is |
163 | * from SHA-1; it introduces some interaction between the registers.) |
164 | */ |
165 | |
166 | size_t i = rand__i; |
167 | const unsigned char *cp = p; |
168 | size_t mask = (rand__seedBits / 8) - 1; |
169 | size_t r = rand__r; |
170 | unsigned int x; |
171 | |
172 | /* --- Ensure the polynomial is valid --- * |
173 | * |
174 | * The current polynomal is %$x^{64} + x^4 + x^3 + x + 1$% (picked from |
175 | * Schneier's excellent book). If the pool size changes, though, I'll |
176 | * need another polynomial. |
177 | */ |
178 | |
179 | #if rand__seedBits / 8 != 64 |
180 | # error Change the polynomal in rand_add |
181 | #endif |
182 | |
183 | T( traceblk(TRACE_RAND, "rand: incoming entropy", p, sz); ) |
184 | |
185 | /* --- Add values to the entropy pool --- */ |
186 | |
187 | while (sz) { |
188 | x = *cp++ & 0xffu; |
189 | if (r) |
190 | x = ((x << r) | (x >> (8 - r))); |
191 | x ^= (rand__pool[i] ^ |
192 | rand__pool[(i + 1) & mask] ^ |
193 | rand__pool[(i + 3) & mask] ^ |
194 | rand__pool[(i + 4) & mask]); |
195 | rand__pool[i] = ((x << 1) | (x >> 7)) & 0xffu; |
196 | sz--; |
197 | i = (i + 1) & mask; |
198 | r = (r + 3) & 7; |
199 | } |
200 | |
201 | /* --- Update the global counters --- */ |
202 | |
203 | rand__r = r; |
204 | rand__i = i; |
205 | |
206 | T( traceblk(TRACE_RAND, "rand: added some entropy", |
207 | rand__pool, sizeof(rand__pool)); ) |
208 | } |
209 | |
210 | /* --- @rand_extract@ --- * |
211 | * |
212 | * Arguments: @unsigned char *b@ = pointer to output buffer |
213 | * @size_t sz@ = number of bytes wanted |
214 | * |
215 | * Returns: --- |
216 | * |
217 | * Use: Produces a number of random bytes. |
218 | */ |
219 | |
220 | void rand_extract(unsigned char *b, size_t sz) |
221 | { |
222 | /* --- Method --- * |
223 | * |
224 | * Hash the buffer with a secure hash (or, in this case, with MD5 and hope |
225 | * for the best...). If this gives us enough bytes, fill the output |
226 | * buffer; otherwise copy the whole hash out. The contribute the hash back |
227 | * into the randomness pool with @rand_add@ to provide some feedback. |
228 | * |
229 | * The secure hash gives us good mixing over the whole of the randomness |
230 | * pool, and attempts to ensure that an attacker receiving our random |
231 | * numbers can't predict any numbers we don't actually give him. |
232 | */ |
233 | |
234 | size_t c; |
235 | unsigned char mdbuf[MD5_HASHSIZE]; |
236 | md5 md; |
237 | |
238 | T( trace(TRACE_RAND, "rand: extracting entropy"); ) |
239 | |
240 | while (sz) { |
241 | c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; |
242 | md5_init(&md); |
243 | md5_buffer(&md, rand__pool, sizeof(rand__pool)); |
244 | md5_final(&md, mdbuf); |
245 | memcpy(b, mdbuf, c); |
246 | rand_add(mdbuf, c); |
247 | b += c; sz -= c; |
248 | } |
249 | burn(mdbuf); burn(md); |
250 | |
251 | T( trace(TRACE_RAND, "rand: finished extracting entropy"); ) |
252 | } |
253 | |
254 | /* --- @rand_churn@ --- * |
255 | * |
256 | * Arguments: --- |
257 | * |
258 | * Returns: --- |
259 | * |
260 | * Use: Churns the randomness pool completely. The pool is replaced |
261 | * by repeated MD5-ings of itself. |
262 | */ |
263 | |
264 | void rand_churn(void) |
265 | { |
266 | md5 md; |
267 | unsigned char mdbuf[MD5_HASHSIZE]; |
268 | size_t sz = sizeof(rand__pool); |
269 | size_t c; |
270 | |
271 | T( trace(TRACE_RAND, "rand: churning pool"); ) |
272 | |
273 | rand__i = 0; |
274 | rand__r = 0; |
275 | |
276 | while (sz) { |
277 | c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; |
278 | md5_init(&md); |
279 | md5_buffer(&md, rand__pool, sizeof(rand__pool)); |
280 | md5_final(&md, mdbuf); |
281 | rand_add(mdbuf, c); |
282 | sz -= c; |
283 | } |
284 | |
285 | rand__i = 0; |
286 | rand__r = 0; |
287 | |
288 | burn(mdbuf); burn(md); |
289 | |
290 | T( trace(TRACE_RAND, "rand: finished churning pool"); ) |
291 | } |
292 | |
293 | /*----- That's all, folks -------------------------------------------------*/ |