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 190extern "C" void RAND_add (const void *buf, int num, double entropy); 191 192unsigned 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 216CRandomizer::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 246void 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 255void 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 295void 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 305void 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 312void 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 331void 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 372void 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 413void 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 419void CRandomizer::AddNow (double millisecondUncertainty) 420{ 421 long time = SysTimer(); 422 AddBytes (&time, sizeof (time), log2l (millisecondUncertainty * 423 mTimebaseTicksPerMillisec)); 424} 425 426//----------------- TIMING SUPPORT ------------------ 427 428void 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 447unsigned 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 466asm 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 477