diff options
Diffstat (limited to 'openssl/MacOS/Randomizer.cpp')
| -rw-r--r-- | openssl/MacOS/Randomizer.cpp | 476 |
1 files changed, 476 insertions, 0 deletions
diff --git a/openssl/MacOS/Randomizer.cpp b/openssl/MacOS/Randomizer.cpp new file mode 100644 index 000000000..cceb6bde4 --- /dev/null +++ b/openssl/MacOS/Randomizer.cpp @@ -0,0 +1,476 @@ +/* +------- 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 |