Be consistent with capitalisation of object names.
[openssl.git] / MacOS / Randomizer.cpp
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