]>
Commit | Line | Data |
---|---|---|
0ea34655 AP |
1 | /* |
2 | ------- Strong random data generation on a Macintosh (pre - OS X) ------ | |
3 | ||
4 | -- GENERAL: We aim to generate unpredictable bits without explicit | |
5 | user interaction. A general review of the problem may be found | |
6 | in RFC 1750, "Randomness Recommendations for Security", and some | |
7 | more discussion, of general and Mac-specific issues has appeared | |
8 | in "Using and Creating Cryptographic- Quality Random Numbers" by | |
9 | Jon Callas (www.merrymeet.com/jon/usingrandom.html). | |
10 | ||
11 | The data and entropy estimates provided below are based on my | |
12 | limited experimentation and estimates, rather than by any | |
13 | rigorous study, and the entropy estimates tend to be optimistic. | |
14 | They should not be considered absolute. | |
15 | ||
16 | Some of the information being collected may be correlated in | |
17 | subtle ways. That includes mouse positions, timings, and disk | |
18 | size measurements. Some obvious correlations will be eliminated | |
19 | by the programmer, but other, weaker ones may remain. The | |
20 | reliability of the code depends on such correlations being | |
21 | poorly understood, both by us and by potential interceptors. | |
22 | ||
23 | This package has been planned to be used with OpenSSL, v. 0.9.5. | |
24 | It requires the OpenSSL function RAND_add. | |
25 | ||
26 | -- OTHER WORK: Some source code and other details have been | |
27 | published elsewhere, but I haven't found any to be satisfactory | |
28 | for the Mac per se: | |
29 | ||
30 | * The Linux random number generator (by Theodore Ts'o, in | |
31 | drivers/char/random.c), is a carefully designed open-source | |
32 | crypto random number package. It collects data from a variety | |
33 | of sources, including mouse, keyboard and other interrupts. | |
34 | One nice feature is that it explicitly estimates the entropy | |
35 | of the data it collects. Some of its features (e.g. interrupt | |
36 | timing) cannot be reliably exported to the Mac without using | |
37 | undocumented APIs. | |
38 | ||
39 | * Truerand by Don P. Mitchell and Matt Blaze uses variations | |
40 | between different timing mechanisms on the same system. This | |
41 | has not been tested on the Mac, but requires preemptive | |
42 | multitasking, and is hardware-dependent, and can't be relied | |
43 | on to work well if only one oscillator is present. | |
44 | ||
45 | * Cryptlib's RNG for the Mac (RNDMAC.C by Peter Gutmann), | |
46 | gathers a lot of information about the machine and system | |
47 | environment. Unfortunately, much of it is constant from one | |
48 | startup to the next. In other words, the random seed could be | |
49 | the same from one day to the next. Some of the APIs are | |
50 | hardware-dependent, and not all are compatible with Carbon (OS | |
51 | X). Incidentally, the EGD library is based on the UNIX entropy | |
52 | gathering methods in cryptlib, and isn't suitable for MacOS | |
53 | either. | |
54 | ||
55 | * Mozilla (and perhaps earlier versions of Netscape) uses the | |
56 | time of day (in seconds) and an uninitialized local variable | |
57 | to seed the random number generator. The time of day is known | |
58 | to an outside interceptor (to within the accuracy of the | |
59 | system clock). The uninitialized variable could easily be | |
60 | identical between subsequent launches of an application, if it | |
61 | is reached through the same path. | |
62 | ||
63 | * OpenSSL provides the function RAND_screen(), by G. van | |
64 | Oosten, which hashes the contents of the screen to generate a | |
65 | seed. This is not useful for an extension or for an | |
66 | application which launches at startup time, since the screen | |
67 | is likely to look identical from one launch to the next. This | |
68 | method is also rather slow. | |
69 | ||
70 | * Using variations in disk drive seek times has been proposed | |
71 | (Davis, Ihaka and Fenstermacher, world.std.com/~dtd/; | |
72 | Jakobsson, Shriver, Hillyer and Juels, | |
73 | www.bell-labs.com/user/shriver/random.html). These variations | |
74 | appear to be due to air turbulence inside the disk drive | |
75 | mechanism, and are very strongly unpredictable. Unfortunately | |
76 | this technique is slow, and some implementations of it may be | |
77 | patented (see Shriver's page above.) It of course cannot be | |
78 | used with a RAM disk. | |
79 | ||
80 | -- TIMING: On the 601 PowerPC the time base register is guaranteed | |
81 | to change at least once every 10 addi instructions, i.e. 10 | |
82 | cycles. On a 60 MHz machine (slowest PowerPC) this translates to | |
83 | a resolution of 1/6 usec. Newer machines seem to be using a 10 | |
84 | cycle resolution as well. | |
85 | ||
86 | For 68K Macs, the Microseconds() call may be used. See Develop | |
87 | issue 29 on the Apple developer site | |
88 | (developer.apple.com/dev/techsupport/develop/issue29/minow.html) | |
89 | for information on its accuracy and resolution. The code below | |
90 | has been tested only on PowerPC based machines. | |
91 | ||
92 | The time from machine startup to the launch of an application in | |
93 | the startup folder has a variance of about 1.6 msec on a new G4 | |
94 | machine with a defragmented and optimized disk, most extensions | |
95 | off and no icons on the desktop. This can be reasonably taken as | |
96 | a lower bound on the variance. Most of this variation is likely | |
97 | due to disk seek time variability. The distribution of startup | |
98 | times is probably not entirely even or uncorrelated. This needs | |
99 | to be investigated, but I am guessing that it not a majpor | |
100 | problem. Entropy = log2 (1600/0.166) ~= 13 bits on a 60 MHz | |
101 | machine, ~16 bits for a 450 MHz machine. | |
102 | ||
103 | User-launched application startup times will have a variance of | |
104 | a second or more relative to machine startup time. Entropy >~22 | |
105 | bits. | |
106 | ||
107 | Machine startup time is available with a 1-second resolution. It | |
108 | is predictable to no better a minute or two, in the case of | |
109 | people who show up punctually to work at the same time and | |
110 | immediately start their computer. Using the scheduled startup | |
111 | feature (when available) will cause the machine to start up at | |
112 | the same time every day, making the value predictable. Entropy | |
113 | >~7 bits, or 0 bits with scheduled startup. | |
114 | ||
115 | The time of day is of course known to an outsider and thus has 0 | |
116 | entropy if the system clock is regularly calibrated. | |
117 | ||
118 | -- KEY TIMING: A very fast typist (120 wpm) will have a typical | |
119 | inter-key timing interval of 100 msec. We can assume a variance | |
120 | of no less than 2 msec -- maybe. Do good typists have a constant | |
121 | rhythm, like drummers? Since what we measure is not the | |
122 | key-generated interrupt but the time at which the key event was | |
123 | taken off the event queue, our resolution is roughly the time | |
124 | between process switches, at best 1 tick (17 msec). I therefore | |
125 | consider this technique questionable and not very useful for | |
126 | obtaining high entropy data on the Mac. | |
127 | ||
128 | -- MOUSE POSITION AND TIMING: The high bits of the mouse position | |
129 | are far from arbitrary, since the mouse tends to stay in a few | |
130 | limited areas of the screen. I am guessing that the position of | |
131 | the mouse is arbitrary within a 6 pixel square. Since the mouse | |
132 | stays still for long periods of time, it should be sampled only | |
133 | after it was moved, to avoid correlated data. This gives an | |
134 | entropy of log2(6*6) ~= 5 bits per measurement. | |
135 | ||
136 | The time during which the mouse stays still can vary from zero | |
137 | to, say, 5 seconds (occasionally longer). If the still time is | |
138 | measured by sampling the mouse during null events, and null | |
139 | events are received once per tick, its resolution is 1/60th of a | |
140 | second, giving an entropy of log2 (60*5) ~= 8 bits per | |
141 | measurement. Since the distribution of still times is uneven, | |
142 | this estimate is on the high side. | |
143 | ||
144 | For simplicity and compatibility across system versions, the | |
145 | mouse is to be sampled explicitly (e.g. in the event loop), | |
146 | rather than in a time manager task. | |
147 | ||
148 | -- STARTUP DISK TOTAL FILE SIZE: Varies typically by at least 20k | |
149 | from one startup to the next, with 'minimal' computer use. Won't | |
150 | vary at all if machine is started again immediately after | |
151 | startup (unless virtual memory is on), but any application which | |
152 | uses the web and caches information to disk is likely to cause | |
153 | this much variation or more. The variation is probably not | |
154 | random, but I don't know in what way. File sizes tend to be | |
155 | divisible by 4 bytes since file format fields are often | |
156 | long-aligned. Entropy > log2 (20000/4) ~= 12 bits. | |
157 | ||
158 | -- STARTUP DISK FIRST AVAILABLE ALLOCATION BLOCK: As the volume | |
159 | gets fragmented this could be anywhere in principle. In a | |
160 | perfectly unfragmented volume this will be strongly correlated | |
161 | with the total file size on the disk. With more fragmentation | |
162 | comes less certainty. I took the variation in this value to be | |
163 | 1/8 of the total file size on the volume. | |
164 | ||
165 | -- SYSTEM REQUIREMENTS: The code here requires System 7.0 and above | |
166 | (for Gestalt and Microseconds calls). All the calls used are | |
167 | Carbon-compatible. | |
168 | */ | |
169 | ||
170 | /*------------------------------ Includes ----------------------------*/ | |
171 | ||
172 | #include "Randomizer.h" | |
173 | ||
174 | // Mac OS API | |
175 | #include <Files.h> | |
176 | #include <Folders.h> | |
177 | #include <Events.h> | |
178 | #include <Processes.h> | |
179 | #include <Gestalt.h> | |
180 | #include <Resources.h> | |
181 | #include <LowMem.h> | |
182 | ||
183 | // Standard C library | |
184 | #include <stdlib.h> | |
185 | #include <math.h> | |
186 | ||
187 | /*---------------------- Function declarations -----------------------*/ | |
188 | ||
189 | // declared in OpenSSL/crypto/rand/rand.h | |
190 | extern "C" void RAND_add (const void *buf, int num, double entropy); | |
191 | ||
192 | unsigned long GetPPCTimer (bool is601); // Make it global if needed | |
193 | // elsewhere | |
194 | ||
195 | /*---------------------------- Constants -----------------------------*/ | |
196 | ||
197 | #define kMouseResolution 6 // Mouse position has to differ | |
198 | // from the last one by this | |
199 | // much to be entered | |
200 | #define kMousePositionEntropy 5.16 // log2 (kMouseResolution**2) | |
201 | #define kTypicalMouseIdleTicks 300.0 // I am guessing that a typical | |
202 | // amount of time between mouse | |
203 | // moves is 5 seconds | |
204 | #define kVolumeBytesEntropy 12.0 // about log2 (20000/4), | |
205 | // assuming a variation of 20K | |
206 | // in total file size and | |
207 | // long-aligned file formats. | |
208 | #define kApplicationUpTimeEntropy 6.0 // Variance > 1 second, uptime | |
209 | // in ticks | |
210 | #define kSysStartupEntropy 7.0 // Entropy for machine startup | |
211 | // time | |
212 | ||
213 | ||
214 | /*------------------------ Function definitions ----------------------*/ | |
215 | ||
216 | CRandomizer::CRandomizer (void) | |
217 | { | |
218 | long result; | |
219 | ||
220 | mSupportsLargeVolumes = | |
221 | (Gestalt(gestaltFSAttr, &result) == noErr) && | |
222 | ((result & (1L << gestaltFSSupports2TBVols)) != 0); | |
223 | ||
224 | if (Gestalt (gestaltNativeCPUtype, &result) != noErr) | |
225 | { | |
226 | mIsPowerPC = false; | |
227 | mIs601 = false; | |
228 | } | |
229 | else | |
230 | { | |
231 | mIs601 = (result == gestaltCPU601); | |
232 | mIsPowerPC = (result >= gestaltCPU601); | |
233 | } | |
234 | mLastMouse.h = mLastMouse.v = -10; // First mouse will | |
235 | // always be recorded | |
236 | mLastPeriodicTicks = TickCount(); | |
237 | GetTimeBaseResolution (); | |
238 | ||
239 | // Add initial entropy | |
240 | AddTimeSinceMachineStartup (); | |
241 | AddAbsoluteSystemStartupTime (); | |
242 | AddStartupVolumeInfo (); | |
243 | AddFiller (); | |
244 | } | |
245 | ||
246 | void CRandomizer::PeriodicAction (void) | |
247 | { | |
248 | AddCurrentMouse (); | |
249 | AddNow (0.0); // Should have a better entropy estimate here | |
250 | mLastPeriodicTicks = TickCount(); | |
251 | } | |
252 | ||
253 | /*------------------------- Private Methods --------------------------*/ | |
254 | ||
255 | void CRandomizer::AddCurrentMouse (void) | |
256 | { | |
257 | Point mouseLoc; | |
258 | unsigned long lastCheck; // Ticks since mouse was last | |
259 | // sampled | |
260 | ||
261 | #if TARGET_API_MAC_CARBON | |
262 | GetGlobalMouse (&mouseLoc); | |
263 | #else | |
264 | mouseLoc = LMGetMouseLocation(); | |
265 | #endif | |
266 | ||
267 | if (labs (mLastMouse.h - mouseLoc.h) > kMouseResolution/2 && | |
268 | labs (mLastMouse.v - mouseLoc.v) > kMouseResolution/2) | |
269 | AddBytes (&mouseLoc, sizeof (mouseLoc), | |
270 | kMousePositionEntropy); | |
271 | ||
272 | if (mLastMouse.h == mouseLoc.h && mLastMouse.v == mouseLoc.v) | |
273 | mMouseStill ++; | |
274 | else | |
275 | { | |
276 | double entropy; | |
277 | ||
278 | // Mouse has moved. Add the number of measurements for | |
279 | // which it's been still. If the resolution is too | |
280 | // coarse, assume the entropy is 0. | |
281 | ||
282 | lastCheck = TickCount() - mLastPeriodicTicks; | |
283 | if (lastCheck <= 0) | |
284 | lastCheck = 1; | |
285 | entropy = log2l | |
286 | (kTypicalMouseIdleTicks/(double)lastCheck); | |
287 | if (entropy < 0.0) | |
288 | entropy = 0.0; | |
289 | AddBytes (&mMouseStill, sizeof (mMouseStill), entropy); | |
290 | mMouseStill = 0; | |
291 | } | |
292 | mLastMouse = mouseLoc; | |
293 | } | |
294 | ||
295 | void CRandomizer::AddAbsoluteSystemStartupTime (void) | |
296 | { | |
297 | unsigned long now; // Time in seconds since | |
298 | // 1/1/1904 | |
299 | GetDateTime (&now); | |
300 | now -= TickCount() / 60; // Time in ticks since machine | |
301 | // startup | |
302 | AddBytes (&now, sizeof (now), kSysStartupEntropy); | |
303 | } | |
304 | ||
305 | void CRandomizer::AddTimeSinceMachineStartup (void) | |
306 | { | |
307 | AddNow (1.5); // Uncertainty in app startup | |
308 | // time is > 1.5 msec (for | |
309 | // automated app startup). | |
310 | } | |
311 | ||
312 | void CRandomizer::AddAppRunningTime (void) | |
313 | { | |
314 | ProcessSerialNumber PSN; | |
315 | ProcessInfoRec ProcessInfo; | |
316 | ||
317 | ProcessInfo.processInfoLength = sizeof (ProcessInfoRec); | |
318 | ProcessInfo.processName = nil; | |
319 | ProcessInfo.processAppSpec = nil; | |
320 | ||
321 | GetCurrentProcess (&PSN); | |
322 | GetProcessInformation (&PSN, &ProcessInfo); | |
323 | ||
324 | // Now add the amount of time in ticks that the current process | |
325 | // has been active | |
326 | ||
327 | AddBytes (&ProcessInfo, sizeof (ProcessInfoRec), | |
328 | kApplicationUpTimeEntropy); | |
329 | } | |
330 | ||
331 | void CRandomizer::AddStartupVolumeInfo (void) | |
332 | { | |
333 | short vRefNum; | |
334 | long dirID; | |
335 | XVolumeParam pb; | |
336 | OSErr err; | |
337 | ||
338 | if (!mSupportsLargeVolumes) | |
339 | return; | |
340 | ||
341 | FindFolder (kOnSystemDisk, kSystemFolderType, kDontCreateFolder, | |
342 | &vRefNum, &dirID); | |
343 | pb.ioVRefNum = vRefNum; | |
344 | pb.ioCompletion = 0; | |
345 | pb.ioNamePtr = 0; | |
346 | pb.ioVolIndex = 0; | |
347 | err = PBXGetVolInfoSync (&pb); | |
348 | if (err != noErr) | |
349 | return; | |
350 | ||
351 | // Base the entropy on the amount of space used on the disk and | |
352 | // on the next available allocation block. A lot else might be | |
353 | // unpredictable, so might as well toss the whole block in. See | |
354 | // comments for entropy estimate justifications. | |
355 | ||
356 | AddBytes (&pb, sizeof (pb), | |
357 | kVolumeBytesEntropy + | |
358 | log2l (((pb.ioVTotalBytes.hi - pb.ioVFreeBytes.hi) | |
359 | * 4294967296.0D + | |
360 | (pb.ioVTotalBytes.lo - pb.ioVFreeBytes.lo)) | |
361 | / pb.ioVAlBlkSiz - 3.0)); | |
362 | } | |
363 | ||
364 | /* | |
365 | On a typical startup CRandomizer will come up with about 60 | |
366 | bits of good, unpredictable data. Assuming no more input will | |
367 | be available, we'll need some more lower-quality data to give | |
368 | OpenSSL the 128 bits of entropy it desires. AddFiller adds some | |
369 | relatively predictable data into the soup. | |
370 | */ | |
371 | ||
372 | void CRandomizer::AddFiller (void) | |
373 | { | |
374 | struct | |
375 | { | |
376 | ProcessSerialNumber psn; // Front process serial | |
377 | // number | |
378 | RGBColor hiliteRGBValue; // User-selected | |
379 | // highlight color | |
380 | long processCount; // Number of active | |
381 | // processes | |
382 | long cpuSpeed; // Processor speed | |
383 | long totalMemory; // Total logical memory | |
384 | // (incl. virtual one) | |
385 | long systemVersion; // OS version | |
386 | short resFile; // Current resource file | |
387 | } data; | |
388 | ||
389 | GetNextProcess ((ProcessSerialNumber*) kNoProcess); | |
390 | while (GetNextProcess (&data.psn) == noErr) | |
391 | data.processCount++; | |
392 | GetFrontProcess (&data.psn); | |
393 | LMGetHiliteRGB (&data.hiliteRGBValue); | |
394 | Gestalt (gestaltProcClkSpeed, &data.cpuSpeed); | |
395 | Gestalt (gestaltLogicalRAMSize, &data.totalMemory); | |
396 | Gestalt (gestaltSystemVersion, &data.systemVersion); | |
397 | data.resFile = CurResFile (); | |
398 | ||
399 | // Here we pretend to feed the PRNG completely random data. This | |
400 | // is of course false, as much of the above data is predictable | |
401 | // by an outsider. At this point we don't have any more | |
402 | // randomness to add, but with OpenSSL we must have a 128 bit | |
403 | // seed before we can start. We just add what we can, without a | |
404 | // real entropy estimate, and hope for the best. | |
405 | ||
406 | AddBytes (&data, sizeof(data), 8.0 * sizeof(data)); | |
407 | AddCurrentMouse (); | |
408 | AddNow (1.0); | |
409 | } | |
410 | ||
411 | //------------------- LOW LEVEL --------------------- | |
412 | ||
413 | void CRandomizer::AddBytes (void *data, long size, double entropy) | |
414 | { | |
415 | RAND_add (data, size, entropy * 0.125); // Convert entropy bits | |
416 | // to bytes | |
417 | } | |
418 | ||
419 | void CRandomizer::AddNow (double millisecondUncertainty) | |
420 | { | |
421 | long time = SysTimer(); | |
422 | AddBytes (&time, sizeof (time), log2l (millisecondUncertainty * | |
423 | mTimebaseTicksPerMillisec)); | |
424 | } | |
425 | ||
426 | //----------------- TIMING SUPPORT ------------------ | |
427 | ||
428 | void CRandomizer::GetTimeBaseResolution (void) | |
429 | { | |
430 | #ifdef __powerc | |
431 | long speed; | |
432 | ||
433 | // gestaltProcClkSpeed available on System 7.5.2 and above | |
434 | if (Gestalt (gestaltProcClkSpeed, &speed) != noErr) | |
435 | // Only PowerPCs running pre-7.5.2 are 60-80 MHz | |
436 | // machines. | |
437 | mTimebaseTicksPerMillisec = 6000.0D; | |
438 | // Assume 10 cycles per clock update, as in 601 spec. Seems true | |
439 | // for later chips as well. | |
440 | mTimebaseTicksPerMillisec = speed / 1.0e4D; | |
441 | #else | |
442 | // 68K VIA-based machines (see Develop Magazine no. 29) | |
443 | mTimebaseTicksPerMillisec = 783.360D; | |
444 | #endif | |
445 | } | |
446 | ||
447 | unsigned long CRandomizer::SysTimer (void) // returns the lower 32 | |
448 | // bit of the chip timer | |
449 | { | |
450 | #ifdef __powerc | |
451 | return GetPPCTimer (mIs601); | |
452 | #else | |
453 | UnsignedWide usec; | |
454 | Microseconds (&usec); | |
455 | return usec.lo; | |
456 | #endif | |
457 | } | |
458 | ||
459 | #ifdef __powerc | |
460 | // The timebase is available through mfspr on 601, mftb on later chips. | |
461 | // Motorola recommends that an 601 implementation map mftb to mfspr | |
462 | // through an exception, but I haven't tested to see if MacOS actually | |
463 | // does this. We only sample the lower 32 bits of the timer (i.e. a | |
464 | // few minutes of resolution) | |
465 | ||
466 | asm unsigned long GetPPCTimer (register bool is601) | |
467 | { | |
468 | cmplwi is601, 0 // Check if 601 | |
469 | bne _601 // if non-zero goto _601 | |
470 | mftb r3 // Available on 603 and later. | |
471 | blr // return with result in r3 | |
472 | _601: | |
473 | mfspr r3, spr5 // Available on 601 only. | |
474 | // blr inserted automatically | |
475 | } | |
476 | #endif |