| /* |
| ------- Strong random data generation on a Macintosh (pre - OS X) ------ |
| |
| -- GENERAL: We aim to generate unpredictable bits without explicit |
| user interaction. A general review of the problem may be found |
| in RFC 1750, "Randomness Recommendations for Security", and some |
| more discussion, of general and Mac-specific issues has appeared |
| in "Using and Creating Cryptographic- Quality Random Numbers" by |
| Jon Callas (www.merrymeet.com/jon/usingrandom.html). |
| |
| The data and entropy estimates provided below are based on my |
| limited experimentation and estimates, rather than by any |
| rigorous study, and the entropy estimates tend to be optimistic. |
| They should not be considered absolute. |
| |
| Some of the information being collected may be correlated in |
| subtle ways. That includes mouse positions, timings, and disk |
| size measurements. Some obvious correlations will be eliminated |
| by the programmer, but other, weaker ones may remain. The |
| reliability of the code depends on such correlations being |
| poorly understood, both by us and by potential interceptors. |
| |
| This package has been planned to be used with OpenSSL, v. 0.9.5. |
| It requires the OpenSSL function RAND_add. |
| |
| -- OTHER WORK: Some source code and other details have been |
| published elsewhere, but I haven't found any to be satisfactory |
| for the Mac per se: |
| |
| * The Linux random number generator (by Theodore Ts'o, in |
| drivers/char/random.c), is a carefully designed open-source |
| crypto random number package. It collects data from a variety |
| of sources, including mouse, keyboard and other interrupts. |
| One nice feature is that it explicitly estimates the entropy |
| of the data it collects. Some of its features (e.g. interrupt |
| timing) cannot be reliably exported to the Mac without using |
| undocumented APIs. |
| |
| * Truerand by Don P. Mitchell and Matt Blaze uses variations |
| between different timing mechanisms on the same system. This |
| has not been tested on the Mac, but requires preemptive |
| multitasking, and is hardware-dependent, and can't be relied |
| on to work well if only one oscillator is present. |
| |
| * Cryptlib's RNG for the Mac (RNDMAC.C by Peter Gutmann), |
| gathers a lot of information about the machine and system |
| environment. Unfortunately, much of it is constant from one |
| startup to the next. In other words, the random seed could be |
| the same from one day to the next. Some of the APIs are |
| hardware-dependent, and not all are compatible with Carbon (OS |
| X). Incidentally, the EGD library is based on the UNIX entropy |
| gathering methods in cryptlib, and isn't suitable for MacOS |
| either. |
| |
| * Mozilla (and perhaps earlier versions of Netscape) uses the |
| time of day (in seconds) and an uninitialized local variable |
| to seed the random number generator. The time of day is known |
| to an outside interceptor (to within the accuracy of the |
| system clock). The uninitialized variable could easily be |
| identical between subsequent launches of an application, if it |
| is reached through the same path. |
| |
| * OpenSSL provides the function RAND_screen(), by G. van |
| Oosten, which hashes the contents of the screen to generate a |
| seed. This is not useful for an extension or for an |
| application which launches at startup time, since the screen |
| is likely to look identical from one launch to the next. This |
| method is also rather slow. |
| |
| * Using variations in disk drive seek times has been proposed |
| (Davis, Ihaka and Fenstermacher, world.std.com/~dtd/; |
| Jakobsson, Shriver, Hillyer and Juels, |
| www.bell-labs.com/user/shriver/random.html). These variations |
| appear to be due to air turbulence inside the disk drive |
| mechanism, and are very strongly unpredictable. Unfortunately |
| this technique is slow, and some implementations of it may be |
| patented (see Shriver's page above.) It of course cannot be |
| used with a RAM disk. |
| |
| -- TIMING: On the 601 PowerPC the time base register is guaranteed |
| to change at least once every 10 addi instructions, i.e. 10 |
| cycles. On a 60 MHz machine (slowest PowerPC) this translates to |
| a resolution of 1/6 usec. Newer machines seem to be using a 10 |
| cycle resolution as well. |
| |
| For 68K Macs, the Microseconds() call may be used. See Develop |
| issue 29 on the Apple developer site |
| (developer.apple.com/dev/techsupport/develop/issue29/minow.html) |
| for information on its accuracy and resolution. The code below |
| has been tested only on PowerPC based machines. |
| |
| The time from machine startup to the launch of an application in |
| the startup folder has a variance of about 1.6 msec on a new G4 |
| machine with a defragmented and optimized disk, most extensions |
| off and no icons on the desktop. This can be reasonably taken as |
| a lower bound on the variance. Most of this variation is likely |
| due to disk seek time variability. The distribution of startup |
| times is probably not entirely even or uncorrelated. This needs |
| to be investigated, but I am guessing that it not a majpor |
| problem. Entropy = log2 (1600/0.166) ~= 13 bits on a 60 MHz |
| machine, ~16 bits for a 450 MHz machine. |
| |
| User-launched application startup times will have a variance of |
| a second or more relative to machine startup time. Entropy >~22 |
| bits. |
| |
| Machine startup time is available with a 1-second resolution. It |
| is predictable to no better a minute or two, in the case of |
| people who show up punctually to work at the same time and |
| immediately start their computer. Using the scheduled startup |
| feature (when available) will cause the machine to start up at |
| the same time every day, making the value predictable. Entropy |
| >~7 bits, or 0 bits with scheduled startup. |
| |
| The time of day is of course known to an outsider and thus has 0 |
| entropy if the system clock is regularly calibrated. |
| |
| -- KEY TIMING: A very fast typist (120 wpm) will have a typical |
| inter-key timing interval of 100 msec. We can assume a variance |
| of no less than 2 msec -- maybe. Do good typists have a constant |
| rhythm, like drummers? Since what we measure is not the |
| key-generated interrupt but the time at which the key event was |
| taken off the event queue, our resolution is roughly the time |
| between process switches, at best 1 tick (17 msec). I therefore |
| consider this technique questionable and not very useful for |
| obtaining high entropy data on the Mac. |
| |
| -- MOUSE POSITION AND TIMING: The high bits of the mouse position |
| are far from arbitrary, since the mouse tends to stay in a few |
| limited areas of the screen. I am guessing that the position of |
| the mouse is arbitrary within a 6 pixel square. Since the mouse |
| stays still for long periods of time, it should be sampled only |
| after it was moved, to avoid correlated data. This gives an |
| entropy of log2(6*6) ~= 5 bits per measurement. |
| |
| The time during which the mouse stays still can vary from zero |
| to, say, 5 seconds (occasionally longer). If the still time is |
| measured by sampling the mouse during null events, and null |
| events are received once per tick, its resolution is 1/60th of a |
| second, giving an entropy of log2 (60*5) ~= 8 bits per |
| measurement. Since the distribution of still times is uneven, |
| this estimate is on the high side. |
| |
| For simplicity and compatibility across system versions, the |
| mouse is to be sampled explicitly (e.g. in the event loop), |
| rather than in a time manager task. |
| |
| -- STARTUP DISK TOTAL FILE SIZE: Varies typically by at least 20k |
| from one startup to the next, with 'minimal' computer use. Won't |
| vary at all if machine is started again immediately after |
| startup (unless virtual memory is on), but any application which |
| uses the web and caches information to disk is likely to cause |
| this much variation or more. The variation is probably not |
| random, but I don't know in what way. File sizes tend to be |
| divisible by 4 bytes since file format fields are often |
| long-aligned. Entropy > log2 (20000/4) ~= 12 bits. |
| |
| -- STARTUP DISK FIRST AVAILABLE ALLOCATION BLOCK: As the volume |
| gets fragmented this could be anywhere in principle. In a |
| perfectly unfragmented volume this will be strongly correlated |
| with the total file size on the disk. With more fragmentation |
| comes less certainty. I took the variation in this value to be |
| 1/8 of the total file size on the volume. |
| |
| -- SYSTEM REQUIREMENTS: The code here requires System 7.0 and above |
| (for Gestalt and Microseconds calls). All the calls used are |
| Carbon-compatible. |
| */ |
| |
| /*------------------------------ Includes ----------------------------*/ |
| |
| #include "Randomizer.h" |
| |
| // Mac OS API |
| #include <Files.h> |
| #include <Folders.h> |
| #include <Events.h> |
| #include <Processes.h> |
| #include <Gestalt.h> |
| #include <Resources.h> |
| #include <LowMem.h> |
| |
| // Standard C library |
| #include <stdlib.h> |
| #include <math.h> |
| |
| /*---------------------- Function declarations -----------------------*/ |
| |
| // declared in OpenSSL/crypto/rand/rand.h |
| extern "C" void RAND_add (const void *buf, int num, double entropy); |
| |
| unsigned long GetPPCTimer (bool is601); // Make it global if needed |
| // elsewhere |
| |
| /*---------------------------- Constants -----------------------------*/ |
| |
| #define kMouseResolution 6 // Mouse position has to differ |
| // from the last one by this |
| // much to be entered |
| #define kMousePositionEntropy 5.16 // log2 (kMouseResolution**2) |
| #define kTypicalMouseIdleTicks 300.0 // I am guessing that a typical |
| // amount of time between mouse |
| // moves is 5 seconds |
| #define kVolumeBytesEntropy 12.0 // about log2 (20000/4), |
| // assuming a variation of 20K |
| // in total file size and |
| // long-aligned file formats. |
| #define kApplicationUpTimeEntropy 6.0 // Variance > 1 second, uptime |
| // in ticks |
| #define kSysStartupEntropy 7.0 // Entropy for machine startup |
| // time |
| |
| |
| /*------------------------ Function definitions ----------------------*/ |
| |
| CRandomizer::CRandomizer (void) |
| { |
| long result; |
| |
| mSupportsLargeVolumes = |
| (Gestalt(gestaltFSAttr, &result) == noErr) && |
| ((result & (1L << gestaltFSSupports2TBVols)) != 0); |
| |
| if (Gestalt (gestaltNativeCPUtype, &result) != noErr) |
| { |
| mIsPowerPC = false; |
| mIs601 = false; |
| } |
| else |
| { |
| mIs601 = (result == gestaltCPU601); |
| mIsPowerPC = (result >= gestaltCPU601); |
| } |
| mLastMouse.h = mLastMouse.v = -10; // First mouse will |
| // always be recorded |
| mLastPeriodicTicks = TickCount(); |
| GetTimeBaseResolution (); |
| |
| // Add initial entropy |
| AddTimeSinceMachineStartup (); |
| AddAbsoluteSystemStartupTime (); |
| AddStartupVolumeInfo (); |
| AddFiller (); |
| } |
| |
| void CRandomizer::PeriodicAction (void) |
| { |
| AddCurrentMouse (); |
| AddNow (0.0); // Should have a better entropy estimate here |
| mLastPeriodicTicks = TickCount(); |
| } |
| |
| /*------------------------- Private Methods --------------------------*/ |
| |
| void CRandomizer::AddCurrentMouse (void) |
| { |
| Point mouseLoc; |
| unsigned long lastCheck; // Ticks since mouse was last |
| // sampled |
| |
| #if TARGET_API_MAC_CARBON |
| GetGlobalMouse (&mouseLoc); |
| #else |
| mouseLoc = LMGetMouseLocation(); |
| #endif |
| |
| if (labs (mLastMouse.h - mouseLoc.h) > kMouseResolution/2 && |
| labs (mLastMouse.v - mouseLoc.v) > kMouseResolution/2) |
| AddBytes (&mouseLoc, sizeof (mouseLoc), |
| kMousePositionEntropy); |
| |
| if (mLastMouse.h == mouseLoc.h && mLastMouse.v == mouseLoc.v) |
| mMouseStill ++; |
| else |
| { |
| double entropy; |
| |
| // Mouse has moved. Add the number of measurements for |
| // which it's been still. If the resolution is too |
| // coarse, assume the entropy is 0. |
| |
| lastCheck = TickCount() - mLastPeriodicTicks; |
| if (lastCheck <= 0) |
| lastCheck = 1; |
| entropy = log2l |
| (kTypicalMouseIdleTicks/(double)lastCheck); |
| if (entropy < 0.0) |
| entropy = 0.0; |
| AddBytes (&mMouseStill, sizeof (mMouseStill), entropy); |
| mMouseStill = 0; |
| } |
| mLastMouse = mouseLoc; |
| } |
| |
| void CRandomizer::AddAbsoluteSystemStartupTime (void) |
| { |
| unsigned long now; // Time in seconds since |
| // 1/1/1904 |
| GetDateTime (&now); |
| now -= TickCount() / 60; // Time in ticks since machine |
| // startup |
| AddBytes (&now, sizeof (now), kSysStartupEntropy); |
| } |
| |
| void CRandomizer::AddTimeSinceMachineStartup (void) |
| { |
| AddNow (1.5); // Uncertainty in app startup |
| // time is > 1.5 msec (for |
| // automated app startup). |
| } |
| |
| void CRandomizer::AddAppRunningTime (void) |
| { |
| ProcessSerialNumber PSN; |
| ProcessInfoRec ProcessInfo; |
| |
| ProcessInfo.processInfoLength = sizeof (ProcessInfoRec); |
| ProcessInfo.processName = nil; |
| ProcessInfo.processAppSpec = nil; |
| |
| GetCurrentProcess (&PSN); |
| GetProcessInformation (&PSN, &ProcessInfo); |
| |
| // Now add the amount of time in ticks that the current process |
| // has been active |
| |
| AddBytes (&ProcessInfo, sizeof (ProcessInfoRec), |
| kApplicationUpTimeEntropy); |
| } |
| |
| void CRandomizer::AddStartupVolumeInfo (void) |
| { |
| short vRefNum; |
| long dirID; |
| XVolumeParam pb; |
| OSErr err; |
| |
| if (!mSupportsLargeVolumes) |
| return; |
| |
| FindFolder (kOnSystemDisk, kSystemFolderType, kDontCreateFolder, |
| &vRefNum, &dirID); |
| pb.ioVRefNum = vRefNum; |
| pb.ioCompletion = 0; |
| pb.ioNamePtr = 0; |
| pb.ioVolIndex = 0; |
| err = PBXGetVolInfoSync (&pb); |
| if (err != noErr) |
| return; |
| |
| // Base the entropy on the amount of space used on the disk and |
| // on the next available allocation block. A lot else might be |
| // unpredictable, so might as well toss the whole block in. See |
| // comments for entropy estimate justifications. |
| |
| AddBytes (&pb, sizeof (pb), |
| kVolumeBytesEntropy + |
| log2l (((pb.ioVTotalBytes.hi - pb.ioVFreeBytes.hi) |
| * 4294967296.0D + |
| (pb.ioVTotalBytes.lo - pb.ioVFreeBytes.lo)) |
| / pb.ioVAlBlkSiz - 3.0)); |
| } |
| |
| /* |
| On a typical startup CRandomizer will come up with about 60 |
| bits of good, unpredictable data. Assuming no more input will |
| be available, we'll need some more lower-quality data to give |
| OpenSSL the 128 bits of entropy it desires. AddFiller adds some |
| relatively predictable data into the soup. |
| */ |
| |
| void CRandomizer::AddFiller (void) |
| { |
| struct |
| { |
| ProcessSerialNumber psn; // Front process serial |
| // number |
| RGBColor hiliteRGBValue; // User-selected |
| // highlight color |
| long processCount; // Number of active |
| // processes |
| long cpuSpeed; // Processor speed |
| long totalMemory; // Total logical memory |
| // (incl. virtual one) |
| long systemVersion; // OS version |
| short resFile; // Current resource file |
| } data; |
| |
| GetNextProcess ((ProcessSerialNumber*) kNoProcess); |
| while (GetNextProcess (&data.psn) == noErr) |
| data.processCount++; |
| GetFrontProcess (&data.psn); |
| LMGetHiliteRGB (&data.hiliteRGBValue); |
| Gestalt (gestaltProcClkSpeed, &data.cpuSpeed); |
| Gestalt (gestaltLogicalRAMSize, &data.totalMemory); |
| Gestalt (gestaltSystemVersion, &data.systemVersion); |
| data.resFile = CurResFile (); |
| |
| // Here we pretend to feed the PRNG completely random data. This |
| // is of course false, as much of the above data is predictable |
| // by an outsider. At this point we don't have any more |
| // randomness to add, but with OpenSSL we must have a 128 bit |
| // seed before we can start. We just add what we can, without a |
| // real entropy estimate, and hope for the best. |
| |
| AddBytes (&data, sizeof(data), 8.0 * sizeof(data)); |
| AddCurrentMouse (); |
| AddNow (1.0); |
| } |
| |
| //------------------- LOW LEVEL --------------------- |
| |
| void CRandomizer::AddBytes (void *data, long size, double entropy) |
| { |
| RAND_add (data, size, entropy * 0.125); // Convert entropy bits |
| // to bytes |
| } |
| |
| void CRandomizer::AddNow (double millisecondUncertainty) |
| { |
| long time = SysTimer(); |
| AddBytes (&time, sizeof (time), log2l (millisecondUncertainty * |
| mTimebaseTicksPerMillisec)); |
| } |
| |
| //----------------- TIMING SUPPORT ------------------ |
| |
| void CRandomizer::GetTimeBaseResolution (void) |
| { |
| #ifdef __powerc |
| long speed; |
| |
| // gestaltProcClkSpeed available on System 7.5.2 and above |
| if (Gestalt (gestaltProcClkSpeed, &speed) != noErr) |
| // Only PowerPCs running pre-7.5.2 are 60-80 MHz |
| // machines. |
| mTimebaseTicksPerMillisec = 6000.0D; |
| // Assume 10 cycles per clock update, as in 601 spec. Seems true |
| // for later chips as well. |
| mTimebaseTicksPerMillisec = speed / 1.0e4D; |
| #else |
| // 68K VIA-based machines (see Develop Magazine no. 29) |
| mTimebaseTicksPerMillisec = 783.360D; |
| #endif |
| } |
| |
| unsigned long CRandomizer::SysTimer (void) // returns the lower 32 |
| // bit of the chip timer |
| { |
| #ifdef __powerc |
| return GetPPCTimer (mIs601); |
| #else |
| UnsignedWide usec; |
| Microseconds (&usec); |
| return usec.lo; |
| #endif |
| } |
| |
| #ifdef __powerc |
| // The timebase is available through mfspr on 601, mftb on later chips. |
| // Motorola recommends that an 601 implementation map mftb to mfspr |
| // through an exception, but I haven't tested to see if MacOS actually |
| // does this. We only sample the lower 32 bits of the timer (i.e. a |
| // few minutes of resolution) |
| |
| asm unsigned long GetPPCTimer (register bool is601) |
| { |
| cmplwi is601, 0 // Check if 601 |
| bne _601 // if non-zero goto _601 |
| mftb r3 // Available on 603 and later. |
| blr // return with result in r3 |
| _601: |
| mfspr r3, spr5 // Available on 601 only. |
| // blr inserted automatically |
| } |
| #endif |