--- /dev/null
+/*
+------- 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
projects / cassiopeia.git / blobdiff