]>
Commit | Line | Data |
---|---|---|
cc0e4a4a | 1 | # Improve res_randomid in the resolver. |
b2ec3c8a | 2 | |
cc0e4a4a MT |
3 | --- a/include/resolv.h |
4 | +++ b/include/resolv.h | |
5 | @@ -31,6 +31,7 @@ extern struct __res_state _res; | |
b2ec3c8a MT |
6 | # endif |
7 | ||
8 | /* Now define the internal interfaces. */ | |
9 | +extern unsigned int _shuffle_next (void); | |
10 | extern int __res_vinit (res_state, int); | |
11 | extern int __res_maybe_init (res_state, int); | |
12 | extern void _sethtent (int); | |
cc0e4a4a MT |
13 | --- a/resolv/Makefile |
14 | +++ b/resolv/Makefile | |
15 | @@ -29,7 +29,7 @@ distribute := ../conf/portability.h mapv4v6addr.h mapv4v6hostent.h \ | |
b2ec3c8a MT |
16 | Banner res_hconf.h res_debug.h README gai_misc.h ga_test.c |
17 | ||
18 | routines := herror inet_addr inet_ntop inet_pton nsap_addr res_init \ | |
19 | - res_hconf res_libc res-state | |
20 | + res_hconf res_libc res-state shuffle | |
21 | ||
22 | tests = tst-aton tst-leaks tst-inet_ntop | |
23 | xtests = tst-leaks2 | |
cc0e4a4a MT |
24 | --- a/resolv/res_init.c |
25 | +++ b/resolv/res_init.c | |
26 | @@ -570,7 +570,9 @@ net_mask(in) /* XXX - should really use system's version of this */ | |
b2ec3c8a MT |
27 | |
28 | u_int | |
29 | res_randomid(void) { | |
30 | - return 0xffff & __getpid(); | |
31 | +/* We should probably randomize the port number as well, | |
32 | + * but this may be better done in the kernel */ | |
33 | + return _shuffle_next(); | |
34 | } | |
35 | #ifdef _LIBC | |
36 | libc_hidden_def (__res_randomid) | |
cc0e4a4a MT |
37 | --- a/resolv/res_mkquery.c |
38 | +++ b/resolv/res_mkquery.c | |
39 | @@ -120,6 +120,7 @@ res_nmkquery(res_state statp, | |
b2ec3c8a MT |
40 | return (-1); |
41 | memset(buf, 0, HFIXEDSZ); | |
42 | hp = (HEADER *) buf; | |
cc0e4a4a | 43 | +#ifdef USE_OLD_RANDOMIZE_CODE |
b2ec3c8a MT |
44 | /* We randomize the IDs every time. The old code just |
45 | incremented by one after the initial randomization which | |
46 | still predictable if the application does multiple | |
cc0e4a4a | 47 | @@ -137,6 +138,9 @@ res_nmkquery(res_state statp, |
b2ec3c8a MT |
48 | } |
49 | while ((randombits & 0xffff) == 0); | |
50 | statp->id = (statp->id + randombits) & 0xffff; | |
51 | +#else | |
cc0e4a4a | 52 | + statp->id = res_randomid (); |
b2ec3c8a MT |
53 | +#endif |
54 | hp->id = statp->id; | |
55 | hp->opcode = op; | |
56 | hp->rd = (statp->options & RES_RECURSE) != 0; | |
cc0e4a4a MT |
57 | --- /dev/null |
58 | +++ b/resolv/shuffle.c | |
b2ec3c8a MT |
59 | @@ -0,0 +1,258 @@ |
60 | +/* | |
61 | + * Written by Solar Designer and placed in the public domain. | |
62 | + */ | |
63 | + | |
64 | +#include <unistd.h> | |
65 | +#include <fcntl.h> | |
66 | +#include <resolv.h> | |
67 | + | |
68 | +#ifdef __linux__ | |
69 | +#define DEVICE "/dev/urandom" | |
70 | +#else | |
71 | +#undef DEVICE | |
72 | +#endif | |
73 | + | |
74 | +#if defined(DEVICE) && defined(_LIBC) | |
75 | +#define CONSERVE_KERNEL_RANDOMNESS | |
76 | +#else | |
77 | +#undef CONSERVE_KERNEL_RANDOMNESS | |
78 | +#endif | |
79 | + | |
80 | +#ifdef DEVICE | |
81 | +#include <errno.h> | |
82 | +#endif | |
83 | + | |
84 | +#include <stdlib.h> | |
85 | +#include <string.h> | |
86 | +#include <sys/time.h> | |
87 | +#include <sys/times.h> | |
88 | + | |
89 | +#ifdef TEST | |
90 | +#include <stdio.h> | |
91 | +#endif | |
92 | + | |
93 | +#define DIV 0x8000 | |
94 | + | |
95 | +static unsigned char pool[0x100]; | |
96 | + | |
97 | +static struct { | |
98 | + unsigned int base, xor; | |
99 | + unsigned char s[0x80]; | |
100 | +} seed_c; | |
101 | +static unsigned char seed_f[0x100]; | |
102 | + | |
103 | +static struct { | |
104 | + unsigned int msb; | |
105 | + unsigned int a, b; | |
106 | + unsigned int n; | |
107 | +} state; | |
108 | + | |
109 | +static void pool_update(unsigned int seed) | |
110 | +{ | |
111 | + int i, x; | |
112 | + | |
cc0e4a4a | 113 | + __srandom(seed ^ __random()); |
b2ec3c8a | 114 | + for (i = 0; i < sizeof(pool); i++) { |
cc0e4a4a | 115 | + x = __random(); |
b2ec3c8a MT |
116 | + pool[i] += (x >> 16) ^ x; |
117 | + } | |
118 | +} | |
119 | + | |
120 | +#ifdef DEVICE | |
121 | +static int read_loop(int fd, char *buffer, int count) | |
122 | +{ | |
123 | + int offset, block; | |
124 | + | |
125 | + offset = 0; | |
126 | + while (count > 0) { | |
cc0e4a4a | 127 | + block = __read(fd, &buffer[offset], count); |
b2ec3c8a MT |
128 | + |
129 | + if (block < 0) { | |
130 | + if (errno == EINTR) continue; | |
131 | + return block; | |
132 | + } | |
133 | + if (!block) return offset; | |
134 | + | |
135 | + offset += block; | |
136 | + count -= block; | |
137 | + } | |
138 | + | |
139 | + return offset; | |
140 | +} | |
141 | + | |
142 | +static int read_random(char *buffer, int count) | |
143 | +{ | |
144 | + int fd; | |
145 | +#ifdef CONSERVE_KERNEL_RANDOMNESS | |
146 | + unsigned int seed[2]; | |
147 | + | |
148 | + if (count > sizeof(pool)) | |
149 | + return -1; | |
150 | +#endif | |
151 | + | |
cc0e4a4a | 152 | + if ((fd = __open(DEVICE, O_RDONLY)) < 0) |
b2ec3c8a MT |
153 | + return -1; |
154 | + | |
155 | +#ifdef CONSERVE_KERNEL_RANDOMNESS | |
156 | + if (read_loop(fd, (char *)seed, sizeof(seed)) != sizeof(seed)) { | |
cc0e4a4a | 157 | + __close(fd); |
b2ec3c8a MT |
158 | + return -1; |
159 | + } | |
cc0e4a4a | 160 | + __close(fd); |
b2ec3c8a MT |
161 | + |
162 | + memset(pool, 'X', sizeof(pool)); | |
163 | + pool_update(seed[0]); | |
164 | + pool_update(seed[1]); | |
165 | + | |
166 | + memcpy(buffer, pool, count); | |
167 | +#else | |
168 | + count = read_loop(fd, buffer, count); | |
cc0e4a4a | 169 | + __close(fd); |
b2ec3c8a MT |
170 | +#endif |
171 | + | |
172 | + return count; | |
173 | +} | |
174 | +#else | |
175 | +#define read_random(buffer, count) (-1) | |
176 | +#endif | |
177 | + | |
178 | +static void shuffle_init() | |
179 | +{ | |
180 | + struct timeval tv; | |
181 | + | |
182 | + if (read_random((char *)seed_f, sizeof(seed_f)) != sizeof(seed_f)) { | |
183 | + memset(pool, 'X', sizeof(pool)); | |
cc0e4a4a MT |
184 | + pool_update(__getpid()); |
185 | + pool_update(__getppid()); | |
186 | + if (!__gettimeofday(&tv, NULL)) { | |
b2ec3c8a MT |
187 | + pool_update(tv.tv_sec); |
188 | + pool_update(tv.tv_usec); | |
189 | + } | |
190 | + | |
191 | + memcpy(seed_f, pool, sizeof(seed_f)); | |
192 | + } | |
193 | + | |
194 | + state.msb = 0; | |
195 | + state.n = DIV; /* force a reseed() */ | |
196 | +} | |
197 | + | |
198 | +static void reseed() | |
199 | +{ | |
200 | + struct tms buf; | |
201 | + | |
202 | + if (read_random((char *)&seed_c, sizeof(seed_c)) != sizeof(seed_c)) { | |
cc0e4a4a | 203 | + pool_update(__times(&buf)); |
b2ec3c8a MT |
204 | + pool_update(buf.tms_utime); |
205 | + pool_update(buf.tms_stime); | |
206 | + | |
207 | + memcpy(&seed_c, pool, sizeof(seed_c)); | |
208 | + } | |
209 | + | |
210 | + seed_c.base &= 0x1fff; | |
211 | + seed_c.base <<= 3; | |
212 | + seed_c.base += DIV + 3; | |
213 | + seed_c.xor &= (DIV - 1); | |
214 | + state.msb ^= 0x8000; | |
215 | + state.a = 1; | |
216 | + state.b = 1; | |
217 | + state.n = 0; | |
218 | +} | |
219 | + | |
220 | +/* | |
221 | + * Now, time for a puzzle. Think of division by DIV in seed_c.base. | |
222 | + * This is not as slow as it might appear: the inner loop needs only | |
223 | + * a few iterations per call, on average. | |
224 | + */ | |
225 | +static unsigned int shuffle_1_next() | |
226 | +{ | |
227 | + if (state.n >= DIV - 1) | |
228 | + reseed(); | |
229 | + | |
230 | + if (state.n && state.b <= state.a) { | |
231 | + do { | |
232 | + state.b = ++state.a; | |
233 | + do { | |
234 | + state.b *= seed_c.base; | |
235 | + state.b %= DIV; | |
236 | + } while (state.b > state.a); | |
237 | + } while (state.a != state.b); | |
238 | + } | |
239 | + | |
240 | + state.b *= seed_c.base; | |
241 | + state.b %= DIV; | |
242 | + state.n++; | |
243 | + | |
244 | + return state.b ^ seed_c.xor; | |
245 | +} | |
246 | + | |
247 | +/* | |
248 | + * The idea behind shuffle_2 is David Wagner's (any bugs are mine, | |
249 | + * of course). | |
250 | + */ | |
251 | +static unsigned int shuffle_2(unsigned int x) | |
252 | +{ | |
253 | + unsigned int i, sum; | |
254 | + | |
255 | + sum = 0; | |
256 | + for (i = 0; i < 8; i++) { | |
257 | + sum += 0x79b9; | |
258 | + x ^= ((unsigned int)seed_c.s[(x ^ sum) & 0x7f]) << 7; | |
259 | + x = ((x & 0xff) << 7) | (x >> 8); | |
260 | + } | |
261 | + | |
262 | + return x; | |
263 | +} | |
264 | + | |
265 | +/* | |
266 | + * A full 16-bit permutation. This one can't be re-seeded, but still | |
267 | + * makes some attacks quite a bit harder. | |
268 | + */ | |
269 | +static unsigned int shuffle_3(unsigned int x) | |
270 | +{ | |
271 | + unsigned int i, sum; | |
272 | + | |
273 | + sum = 0; | |
274 | + for (i = 0; i < 8; i++) { | |
275 | + sum += 0x79b9; | |
276 | + x ^= ((unsigned int)seed_f[(x ^ sum) & 0xff]) << 8; | |
277 | + x = ((x & 0xff) << 8) | (x >> 8); | |
278 | + } | |
279 | + | |
280 | + return x; | |
281 | +} | |
282 | + | |
283 | +unsigned int _shuffle_next() | |
284 | +{ | |
285 | + static int initialized = 0; | |
286 | + unsigned int pid, x; | |
287 | + | |
288 | +/* This isn't MT-safe, but the resolver itself isn't safe, anyway */ | |
289 | + if (!initialized) { | |
290 | + shuffle_init(); | |
291 | + initialized = 1; | |
292 | + } | |
293 | + | |
294 | +/* Make sure the sequence we generate changes after fork() */ | |
cc0e4a4a | 295 | + pid = __getpid(); |
b2ec3c8a MT |
296 | + |
297 | + x = shuffle_1_next(); | |
298 | + x ^= pid & 0x7fff; | |
299 | + x = shuffle_2(x); | |
300 | + x |= state.msb; | |
301 | + x ^= (pid >> 15) & 0xffff; | |
302 | + x = shuffle_3(x); | |
303 | + | |
304 | + return x; | |
305 | +} | |
306 | + | |
307 | +#ifdef TEST | |
308 | +int main() | |
309 | +{ | |
310 | + int i; | |
311 | + | |
312 | + for (i = 0; i < 0xfffe; i++) | |
313 | + printf("%u\n", _shuffle_next()); | |
314 | + | |
315 | + return 0; | |
316 | +} | |
317 | +#endif |