1 /*
2 * Copyright (c) 1993-1995 Colin Plumb. All rights reserved.
3 * For licensing and other legal details, see the file legal.c.
4 *
5 * Get environmental noise.
6 */
7
8 #include "first.h"
9 #include <time.h> /* For time measurement code */
10
11 #ifndef MSDOS
12 #ifdef __MSDOS
13 #define MSDOS 1
14 #endif
15 #endif
16 #ifndef MSDOS
17 #ifdef __MSDOS__
18 #define MSDOS 1
19 #endif
20 #endif
21 #ifndef UNIX
22 #ifdef unix
23 #define UNIX 1
24 #endif
25 #endif
26 #ifndef UNIX
27 #ifdef __unix
28 #define UNIX 1
29 #endif
30 #endif
31 #ifndef UNIX
32 #ifdef __unix__
33 #define UNIX 1
34 #endif
35 #endif
36
37 #ifdef MSDOS
38
39 #if __BORLANDC__
40 #define far __far /* Borland C++ 3.1's <dos.h> kacks in ANSI mode. Ugh! */
41 #endif
42
43 #include <dos.h> /* for enable() and disable() */
44 #include <conio.h> /* for inp() and outp() */
45
46 /*
47 * This code gets as much information as possible out of 8253/8254 timer 0,
48 * which ticks every .84 microseconds. There are three cases:
49 * 1) Original 8253. 15 bits available, as the low bit is unused.
50 * 2) 8254, in mode 3. The 16th bit is available from the status register.
51 * 3) 8254, in mode 2. All 16 bits of the counters are available.
52 * (This is not documented anywhere, but I've seen it!)
53 *
54 * This code repeatedly tries to latch the status (ignored by an 8253) and
55 * sees if it looks like xx1101x0. If not, it's definitely not an 8254.
56 * Repeat this a few times to make sure it is an 8254.
57 */
58 static int
has8254(void)59 has8254(void)
60 {
61 int i, s1, s2;
62
63 for (i = 0; i < 5; i++) {
64 _disable();
65 outp(0x43, 0xe2); /* Latch status for timer 0 */
66 s1 = inp(0x40); /* If 8253, read timer low byte */
67 outp(0x43, 0xe2); /* Latch status for timer 0 */
68 s2 = inp(0x40); /* If 8253, read timer high byte */
69 _enable();
70 if ((s1 & 0x3d) != 0x34 || (s2 & 0x3d) != 0x34)
71 return 0; /* Ignoring status latch; 8253 */
72 }
73 return 1; /* Status reads as expected; 8254 */
74 }
75
76 /* TODO: It might be better to capture this data in a keyboard ISR */
77 static unsigned
read8254(void)78 read8254(void)
79 {
80 unsigned status, count;
81
82 _disable();
83 outp(0x43, 0xc2); /* Latch status and count for timer 0 */
84 status = inp(0x40);
85 count = inp(0x40);
86 count |= inp(0x40) << 8;
87 _enable();
88 /* The timer is usually in mode 3, but some motherboards use mode 2. */
89 if (status & 2)
90 count = count>>1 | (status & 0x80)<<8;
91
92 return count;
93 }
94
95 static unsigned
read8253(void)96 read8253(void)
97 {
98 unsigned count;
99
100 _disable();
101 outp(0x43, 0x00); /* Latch count for timer 0 */
102 count = (inp(0x40) & 0xff);
103 count |= (inp(0x40) & 0xff) << 8;
104 _enable();
105
106 return count >> 1;
107 }
108 #endif /* MSDOS */
109
110 #ifdef UNIX
111 /*
112 * This code uses five different timers, if available, in decreasing
113 * priority order:
114 * - gethrtime(), assumed unavailable unless USE_GETHRTIME=1
115 * - clock_gettime(), auto-detected unless overridden with USE_CLOCK_GETTIME
116 * - gettimeofday(), assumed available unless USE_GETTIMEOFDAY=0
117 * - getitimer(), auto-detected unless overridden with USE_GETITIMER
118 * - ftime(), assumed available unless USE_FTIME=0
119 *
120 * These are all accessed through the gettime(), timetype, and tickdiff()
121 * macros. The MINTICK constant is something to avoid the gettimeofday()
122 * glitch wherein it increments the return value even if no tick has occurred.
123 * When measuring the tick interval, if the difference between two successive
124 * times is not at least MINTICK ticks, it is ignored.
125 */
126
127 #include <sys/types.h>
128 #include <sys/times.h> /* for times() */
129 #include <stdlib.h> /* For qsort() */
130
131 #if !USE_GETHRTIME
132 #ifndef USE_CLOCK_GETTIME /* Detect using CLOCK_REALTIME from <time.h> */
133 #ifdef CLOCK_REALTIMExxx /* Stupid libc... */
134 #define USE_CLOCK_GETTIME 1
135 #else
136 #define USE_CLOCK_GETTIME 0
137 #endif
138 #endif
139
140 #if !USE_CLOCK_GETTIME
141 #include <sys/time.h> /* For gettimeofday(), getitimer(), or ftime() */
142
143 #ifndef USE_GETTIMEOFDAY
144 #define USE_GETTIMEOFDAY 1 /* No way to tell, so assume it's there */
145 #endif
146
147 #if !USE_GETTIMEOFDAY
148 #ifndef USE_GETITIMER /* Detect using ITIMER_REAL from <sys/time.h> */
149 #define USE_GETITIMER defined(ITIMER_REAL)
150 #endif
151
152 #if !USE_GETITIMER
153 #ifndef USE_FTIME
154 #define USE_FTIME 1
155 #endif
156
157 #endif /* !USE_GETITIMER */
158 #endif /* !USE_GETTIMEOFDAY */
159 #endif /* !USE_CLOCK_GETTIME */
160 #endif /* !USE_GETHRTIME */
161
162 #if USE_GETHRTIME
163
164 #define CHOICE_GETHRTIME 1
165 #include <sys/time.h>
166 typedef hrtime_t timetype;
167 #define gettime(s) (*(s) = gethrtime())
168 #define tickdiff(s,t) ((s)-(t))
169 #define MINTICK 0
170
171 #elif USE_CLOCK_GETTIME
172
173 #define CHOICE_CLOCK_GETTIME 1
174 typedef struct timespec timetype;
175 #define gettime(s) (void)clock_gettime(CLOCK_REALTIME, s)
176 #define tickdiff(s,t) (((s).tv_sec-(t).tv_sec)*1000000000 + \
177 (s).tv_nsec - (t).tv_nsec)
178
179 #elif USE_GETTIMEOFDAY
180
181 #define CHOICE_GETTIMEOFDAY 1
182 typedef struct timeval timetype;
183 #define gettime(s) (void)gettimeofday(s, (struct timezone *)0)
184 #define tickdiff(s,t) (((s).tv_sec-(t).tv_sec)*1000000+(s).tv_usec-(t).tv_usec)
185 #define MINTICK 1
186
187 #elif USE_GETITIMER
188
189 #define CHOICE_GETITIMER 1
190 #include <signal.h> /* For signal(), SIGALRM, SIG_IGN */
191 typedef struct itimerval timetype;
192 #define gettime(s) (void)getitimer(ITIMER_REAL, s)
193 #define tickdiff(s,t) (((t).it_value.tv_sec-(s).it_value.tv_sec)*1000000 + \
194 (t).it_value.tv_usec - (s).it_value.tv_usec)
195 #define MINTICK 1
196
197 #elif USE_FTIME /* Use ftime() */
198
199 #define CHOICE_FTIME 1
200 #include <sys/timeb.h>
201 typedef struct timeb timetype;
202 #define gettime(s) (void)ftime(s)
203 #define tickdiff(s,t) (((s).time-(t).time)*1000 + (s).millitm - (t).millitm)
204 #define MINTICK 0
205
206 #else
207
208 #error No clock available - please define one.
209
210 #endif /* End of complex choice of clock conditional */
211
212 #if CHOICE_CLOCK_GETTIME
213
214 static unsigned
noiseTickSize(void)215 noiseTickSize(void)
216 {
217 struct timespec res;
218
219 clock_getres(CLOCK_REALTIME, &res);
220 return res.tv_nsec;
221 }
222
223 #else /* Normal clock resolution estimation */
224
225 #if NOISEDEBUG
226 #include <stdio.h>
227 #endif
228
229 #define N 15 /* Number of deltas to try (at least 5, preferably odd) */
230
231 /* Function needed for qsort() */
232 static int
noiseCompare(void const * p1,void const * p2)233 noiseCompare(void const *p1, void const *p2)
234 {
235 return *(unsigned const *)p1 > *(unsigned const *)p2 ? 1 :
236 *(unsigned const *)p1 < *(unsigned const *)p2 ? -1 : 0;
237 }
238
239 /*
240 * Find the resolution of the high-resolution clock by sampling successive
241 * values until a tick boundary, at which point the delta is entered into
242 * a table. An average near the median of the table is taken and returned
243 * as the system tick size to eliminate outliers due to descheduling (high)
244 * or tv0 not being the "zero" time in a given tick (low).
245 *
246 * Some trickery is needed to defeat the habit systems have of always
247 * incrementing the microseconds field from gettimeofday() results so that
248 * no two calls return the same value. Thus, a "tick boundary" is assumed
249 * when successive calls return a difference of more than MINTICK ticks.
250 * (For gettimeofday(), this is set to 2 us.) This catches cases where at
251 * most one other task reads the clock between successive reads by this task.
252 * More tasks in between are rare enough that they'll get cut off by the
253 * median filter.
254 *
255 * When a tick boundary is found, the *first* time read during the previous
256 * tick (tv0) is subtracted from the new time to get microseconds per tick.
257 *
258 * Suns have a 1 us timer, and as of SunOS 4.1, they return that timer, but
259 * there is ~50 us of system-call overhead to get it, so this overestimates
260 * the tick size considerably. On SunOS 5.x/Solaris, the overhead has been
261 * cut to about 2.5 us, so the measured time alternates between 2 and 3 us.
262 * Some better algorithms will be required for future machines that really
263 * do achieve 1 us granularity.
264 *
265 * Current best idea: discard all this hair and use Ueli Maurer's entropy
266 * estimation scheme. Assign each input event (delta) a sequence number.
267 * 16 bits should be more than adequate. Make a table of the last time
268 * (by sequence number) each possibe input event occurred. For practical
269 * implementation, hash the event to a fixed-size code and consider two
270 * events identical if they have the same hash code. This will only ever
271 * underestimate entropy. Then use the number of bits in the difference
272 * between the current sequence number and the previous one as the entropy
273 * estimate.
274 *
275 * If it's desirable to use longer contexts, Maurer's original technique
276 * just groups events into non-overlapping pairs and uses the technique on
277 * the pairs. If you want to increment the entropy numbers on each keystroke
278 * for user-interface niceness, you can do the operation each time, but you
279 * have to halve the sequence number difference before starting, and then you
280 * have to halve the number of bits of entropy computed because you're adding
281 * them twice.
282 *
283 * You can put the even and odd events into separate tables to close Maurer's
284 * model exactly, or you can just dump them into the same table, which will
285 * be more conservative.
286 */
287 static unsigned
noiseTickSize(void)288 noiseTickSize(void)
289 {
290 unsigned i = 0, j = 0, diff, d[N];
291 timetype tv0, tv1, tv2;
292
293 gettime(&tv0);
294 tv1 = tv0;
295 do {
296 gettime(&tv2);
297 diff = (unsigned)tickdiff(tv2, tv1);
298 if (diff > MINTICK) {
299 d[i++] = diff;
300 tv0 = tv2;
301 j = 0;
302 } else if (++j >= 4096) /* Always getting <= MINTICK units */
303 return MINTICK + !MINTICK;
304 tv1 = tv2;
305 } while (i < N);
306
307 /* Return average of middle 5 values (rounding up) */
308 qsort(d, N, sizeof(d[0]), noiseCompare);
309 diff = (d[N/2-2]+d[N/2-1]+d[N/2]+d[N/2+1]+d[N/2+2]+4)/5;
310 #if NOISEDEBUG
311 fprintf(stderr, "Tick size is %u\n", diff);
312 #endif
313 return diff;
314 }
315
316 #endif /* Clock resolution measurement condition */
317
318 #endif /* UNIX */
319
320 #include "usuals.h"
321 #include "randpool.h"
322 #include "noise.h"
323
324 /*
325 * Add as much environmentally-derived random noise as possible
326 * to the randPool. Typically, this involves reading the most
327 * accurate system clocks available.
328 *
329 * Returns the number of ticks that have passed since the last call,
330 * for entropy estimation purposes.
331 */
332 word32
noise(void)333 noise(void)
334 {
335 word32 delta;
336
337 #if defined(MSDOS)
338 static unsigned deltamask = 0;
339 static unsigned prevt;
340 unsigned t;
341 time_t tnow;
342 clock_t cnow;
343
344 if (deltamask == 0)
345 deltamask = has8254() ? 0xffff : 0x7fff;
346 t = (deltamask & 0x8000) ? read8254() : read8253();
347 randPoolAddBytes((byte const *)&t, sizeof(t));
348 delta = deltamask & (t - prevt);
349 prevt = t;
350
351 /* Add more-significant time components. */
352 cnow = clock();
353 randPoolAddBytes((byte *)&cnow, sizeof(cnow));
354 tnow = time((time_t *)0);
355 randPoolAddBytes((byte *)&tnow, sizeof(tnow));
356 /* END OF DOS */
357 #elif defined(VMS)
358 word32 t[2]; /* little-endian 64-bit timer */
359 word32 d1; /* MSW of difference */
360 static word32 prevt[2];
361
362 SYS$GETTIM(t); /* VMS hardware clock increments by 100000 per tick */
363 randPoolAddBytes((byte const *)t, sizeof(t));
364 /* Get difference in d1 and delta, and old time in prevt */
365 d1 = t[1] - prevt[1] + (t[0] < prevt[0]);
366 prevt[1] = t[1];
367 delta = t[0] - prevt[0];
368 prevt[0] = t[0];
369
370 /* Now, divide the 64-bit value by 100000 = 2^5 * 5^5 = 32 * 3125 */
371 /* Divide value, MSW in d1 and LSW in delta, by 32 */
372 delta >>= 5;
373 delta |= d1 << (32-5);
374 d1 >>= 5;
375 /*
376 * Divide by 3125. This fits into 16 bits, so the following
377 * code is possible. 2^32 = 3125 * 1374389 + 1671.
378 *
379 * This code has confused people reading it, so here's a detailed
380 * explanation. First, since we only want a 32-bit result,
381 * reduce the input mod 3125 * 2^32 before starting. This
382 * amounts to reducing the most significant word mod 3125 and
383 * leaving the least-significant word alone.
384 *
385 * Then, using / for mathematical (real, not integer) division, we
386 * want to compute floor(d1 * 2^32 + d0) / 3125), which I'll denote
387 * using the old [ ] syntax for floor, so it's
388 * [ (d1 * 2^32 + d0) / 3125 ]
389 * = [ (d1 * (3125 * 1374389 + 1671) + d0) / 3125 ]
390 * = [ d1 * 1374389 + (d1 * 1671 + d0) / 3125 ]
391 * = d1 * 137438 + [ (d1 * 1671 + d0) / 3125 ]
392 * = d1 * 137438 + [ d0 / 3125 ] + [ (d1 * 1671 + d0 % 3125) / 3125 ]
393 *
394 * The C / operator, applied to integers, performs [ a / b ], so
395 * this can be implemented in C, and since d1 < 3125 (by the first
396 * modulo operation), d1 * 1671 + d0 % 3125 < 3125 * 1672, which
397 * is 5225000, less than 2^32, so it all fits into 32 bits.
398 */
399 d1 %= 3125; /* Ignore overflow past 32 bits */
400 delta = delta/3125 + d1*1374389 + (delta%3125 + d1*1671) / 3125;
401 /* END OF VMS */
402 #elif defined(UNIX)
403 timetype t;
404 static unsigned ticksize = 0;
405 static timetype prevt;
406
407 gettime(&t);
408 #if CHOICE_GETITIMER
409 /* If itimer isn't started, start it */
410 if (t.it_value.tv_sec == 0 && t.it_value.tv_usec == 0) {
411 /*
412 * start the timer - assume that PGP won't be running for
413 * more than 11 days, 13 hours, 46 minutes and 40 seconds.
414 */
415 t.it_value.tv_sec = 1000000;
416 t.it_interval.tv_sec = 1000000;
417 t.it_interval.tv_usec = 0;
418 signal(SIGALRM, SIG_IGN); /* just in case.. */
419 setitimer(ITIMER_REAL, &t, NULL);
420 t.it_value.tv_sec = 0;
421 }
422 randPoolAddBytes((byte const *)&t.it_value, sizeof(t.it_value));
423 #else
424 randPoolAddBytes((byte const *)&t, sizeof(t));
425 #endif
426
427 if (!ticksize)
428 ticksize = noiseTickSize();
429 delta = (word32)(tickdiff(t, prevt) / ticksize);
430 prevt = t;
431 /* END OF UNIX */
432 #else
433 #error Unknown OS - define UNIX or MSDOS or add code for high-resolution timers
434 #endif
435
436 return delta;
437 }
438