2
0

Randomizer.cpp 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476
  1. /*
  2. ------- Strong random data generation on a Macintosh (pre - OS X) ------
  3. -- GENERAL: We aim to generate unpredictable bits without explicit
  4. user interaction. A general review of the problem may be found
  5. in RFC 1750, "Randomness Recommendations for Security", and some
  6. more discussion, of general and Mac-specific issues has appeared
  7. in "Using and Creating Cryptographic- Quality Random Numbers" by
  8. Jon Callas (www.merrymeet.com/jon/usingrandom.html).
  9. The data and entropy estimates provided below are based on my
  10. limited experimentation and estimates, rather than by any
  11. rigorous study, and the entropy estimates tend to be optimistic.
  12. They should not be considered absolute.
  13. Some of the information being collected may be correlated in
  14. subtle ways. That includes mouse positions, timings, and disk
  15. size measurements. Some obvious correlations will be eliminated
  16. by the programmer, but other, weaker ones may remain. The
  17. reliability of the code depends on such correlations being
  18. poorly understood, both by us and by potential interceptors.
  19. This package has been planned to be used with OpenSSL, v. 0.9.5.
  20. It requires the OpenSSL function RAND_add.
  21. -- OTHER WORK: Some source code and other details have been
  22. published elsewhere, but I haven't found any to be satisfactory
  23. for the Mac per se:
  24. * The Linux random number generator (by Theodore Ts'o, in
  25. drivers/char/random.c), is a carefully designed open-source
  26. crypto random number package. It collects data from a variety
  27. of sources, including mouse, keyboard and other interrupts.
  28. One nice feature is that it explicitly estimates the entropy
  29. of the data it collects. Some of its features (e.g. interrupt
  30. timing) cannot be reliably exported to the Mac without using
  31. undocumented APIs.
  32. * Truerand by Don P. Mitchell and Matt Blaze uses variations
  33. between different timing mechanisms on the same system. This
  34. has not been tested on the Mac, but requires preemptive
  35. multitasking, and is hardware-dependent, and can't be relied
  36. on to work well if only one oscillator is present.
  37. * Cryptlib's RNG for the Mac (RNDMAC.C by Peter Gutmann),
  38. gathers a lot of information about the machine and system
  39. environment. Unfortunately, much of it is constant from one
  40. startup to the next. In other words, the random seed could be
  41. the same from one day to the next. Some of the APIs are
  42. hardware-dependent, and not all are compatible with Carbon (OS
  43. X). Incidentally, the EGD library is based on the UNIX entropy
  44. gathering methods in cryptlib, and isn't suitable for MacOS
  45. either.
  46. * Mozilla (and perhaps earlier versions of Netscape) uses the
  47. time of day (in seconds) and an uninitialized local variable
  48. to seed the random number generator. The time of day is known
  49. to an outside interceptor (to within the accuracy of the
  50. system clock). The uninitialized variable could easily be
  51. identical between subsequent launches of an application, if it
  52. is reached through the same path.
  53. * OpenSSL provides the function RAND_screen(), by G. van
  54. Oosten, which hashes the contents of the screen to generate a
  55. seed. This is not useful for an extension or for an
  56. application which launches at startup time, since the screen
  57. is likely to look identical from one launch to the next. This
  58. method is also rather slow.
  59. * Using variations in disk drive seek times has been proposed
  60. (Davis, Ihaka and Fenstermacher, world.std.com/~dtd/;
  61. Jakobsson, Shriver, Hillyer and Juels,
  62. www.bell-labs.com/user/shriver/random.html). These variations
  63. appear to be due to air turbulence inside the disk drive
  64. mechanism, and are very strongly unpredictable. Unfortunately
  65. this technique is slow, and some implementations of it may be
  66. patented (see Shriver's page above.) It of course cannot be
  67. used with a RAM disk.
  68. -- TIMING: On the 601 PowerPC the time base register is guaranteed
  69. to change at least once every 10 addi instructions, i.e. 10
  70. cycles. On a 60 MHz machine (slowest PowerPC) this translates to
  71. a resolution of 1/6 usec. Newer machines seem to be using a 10
  72. cycle resolution as well.
  73. For 68K Macs, the Microseconds() call may be used. See Develop
  74. issue 29 on the Apple developer site
  75. (developer.apple.com/dev/techsupport/develop/issue29/minow.html)
  76. for information on its accuracy and resolution. The code below
  77. has been tested only on PowerPC based machines.
  78. The time from machine startup to the launch of an application in
  79. the startup folder has a variance of about 1.6 msec on a new G4
  80. machine with a defragmented and optimized disk, most extensions
  81. off and no icons on the desktop. This can be reasonably taken as
  82. a lower bound on the variance. Most of this variation is likely
  83. due to disk seek time variability. The distribution of startup
  84. times is probably not entirely even or uncorrelated. This needs
  85. to be investigated, but I am guessing that it not a majpor
  86. problem. Entropy = log2 (1600/0.166) ~= 13 bits on a 60 MHz
  87. machine, ~16 bits for a 450 MHz machine.
  88. User-launched application startup times will have a variance of
  89. a second or more relative to machine startup time. Entropy >~22
  90. bits.
  91. Machine startup time is available with a 1-second resolution. It
  92. is predictable to no better a minute or two, in the case of
  93. people who show up punctually to work at the same time and
  94. immediately start their computer. Using the scheduled startup
  95. feature (when available) will cause the machine to start up at
  96. the same time every day, making the value predictable. Entropy
  97. >~7 bits, or 0 bits with scheduled startup.
  98. The time of day is of course known to an outsider and thus has 0
  99. entropy if the system clock is regularly calibrated.
  100. -- KEY TIMING: A very fast typist (120 wpm) will have a typical
  101. inter-key timing interval of 100 msec. We can assume a variance
  102. of no less than 2 msec -- maybe. Do good typists have a constant
  103. rhythm, like drummers? Since what we measure is not the
  104. key-generated interrupt but the time at which the key event was
  105. taken off the event queue, our resolution is roughly the time
  106. between process switches, at best 1 tick (17 msec). I therefore
  107. consider this technique questionable and not very useful for
  108. obtaining high entropy data on the Mac.
  109. -- MOUSE POSITION AND TIMING: The high bits of the mouse position
  110. are far from arbitrary, since the mouse tends to stay in a few
  111. limited areas of the screen. I am guessing that the position of
  112. the mouse is arbitrary within a 6 pixel square. Since the mouse
  113. stays still for long periods of time, it should be sampled only
  114. after it was moved, to avoid correlated data. This gives an
  115. entropy of log2(6*6) ~= 5 bits per measurement.
  116. The time during which the mouse stays still can vary from zero
  117. to, say, 5 seconds (occasionally longer). If the still time is
  118. measured by sampling the mouse during null events, and null
  119. events are received once per tick, its resolution is 1/60th of a
  120. second, giving an entropy of log2 (60*5) ~= 8 bits per
  121. measurement. Since the distribution of still times is uneven,
  122. this estimate is on the high side.
  123. For simplicity and compatibility across system versions, the
  124. mouse is to be sampled explicitly (e.g. in the event loop),
  125. rather than in a time manager task.
  126. -- STARTUP DISK TOTAL FILE SIZE: Varies typically by at least 20k
  127. from one startup to the next, with 'minimal' computer use. Won't
  128. vary at all if machine is started again immediately after
  129. startup (unless virtual memory is on), but any application which
  130. uses the web and caches information to disk is likely to cause
  131. this much variation or more. The variation is probably not
  132. random, but I don't know in what way. File sizes tend to be
  133. divisible by 4 bytes since file format fields are often
  134. long-aligned. Entropy > log2 (20000/4) ~= 12 bits.
  135. -- STARTUP DISK FIRST AVAILABLE ALLOCATION BLOCK: As the volume
  136. gets fragmented this could be anywhere in principle. In a
  137. perfectly unfragmented volume this will be strongly correlated
  138. with the total file size on the disk. With more fragmentation
  139. comes less certainty. I took the variation in this value to be
  140. 1/8 of the total file size on the volume.
  141. -- SYSTEM REQUIREMENTS: The code here requires System 7.0 and above
  142. (for Gestalt and Microseconds calls). All the calls used are
  143. Carbon-compatible.
  144. */
  145. /*------------------------------ Includes ----------------------------*/
  146. #include "Randomizer.h"
  147. // Mac OS API
  148. #include <Files.h>
  149. #include <Folders.h>
  150. #include <Events.h>
  151. #include <Processes.h>
  152. #include <Gestalt.h>
  153. #include <Resources.h>
  154. #include <LowMem.h>
  155. // Standard C library
  156. #include <stdlib.h>
  157. #include <math.h>
  158. /*---------------------- Function declarations -----------------------*/
  159. // declared in OpenSSL/crypto/rand/rand.h
  160. extern "C" void RAND_add (const void *buf, int num, double entropy);
  161. unsigned long GetPPCTimer (bool is601); // Make it global if needed
  162. // elsewhere
  163. /*---------------------------- Constants -----------------------------*/
  164. #define kMouseResolution 6 // Mouse position has to differ
  165. // from the last one by this
  166. // much to be entered
  167. #define kMousePositionEntropy 5.16 // log2 (kMouseResolution**2)
  168. #define kTypicalMouseIdleTicks 300.0 // I am guessing that a typical
  169. // amount of time between mouse
  170. // moves is 5 seconds
  171. #define kVolumeBytesEntropy 12.0 // about log2 (20000/4),
  172. // assuming a variation of 20K
  173. // in total file size and
  174. // long-aligned file formats.
  175. #define kApplicationUpTimeEntropy 6.0 // Variance > 1 second, uptime
  176. // in ticks
  177. #define kSysStartupEntropy 7.0 // Entropy for machine startup
  178. // time
  179. /*------------------------ Function definitions ----------------------*/
  180. CRandomizer::CRandomizer (void)
  181. {
  182. long result;
  183. mSupportsLargeVolumes =
  184. (Gestalt(gestaltFSAttr, &result) == noErr) &&
  185. ((result & (1L << gestaltFSSupports2TBVols)) != 0);
  186. if (Gestalt (gestaltNativeCPUtype, &result) != noErr)
  187. {
  188. mIsPowerPC = false;
  189. mIs601 = false;
  190. }
  191. else
  192. {
  193. mIs601 = (result == gestaltCPU601);
  194. mIsPowerPC = (result >= gestaltCPU601);
  195. }
  196. mLastMouse.h = mLastMouse.v = -10; // First mouse will
  197. // always be recorded
  198. mLastPeriodicTicks = TickCount();
  199. GetTimeBaseResolution ();
  200. // Add initial entropy
  201. AddTimeSinceMachineStartup ();
  202. AddAbsoluteSystemStartupTime ();
  203. AddStartupVolumeInfo ();
  204. AddFiller ();
  205. }
  206. void CRandomizer::PeriodicAction (void)
  207. {
  208. AddCurrentMouse ();
  209. AddNow (0.0); // Should have a better entropy estimate here
  210. mLastPeriodicTicks = TickCount();
  211. }
  212. /*------------------------- Private Methods --------------------------*/
  213. void CRandomizer::AddCurrentMouse (void)
  214. {
  215. Point mouseLoc;
  216. unsigned long lastCheck; // Ticks since mouse was last
  217. // sampled
  218. #if TARGET_API_MAC_CARBON
  219. GetGlobalMouse (&mouseLoc);
  220. #else
  221. mouseLoc = LMGetMouseLocation();
  222. #endif
  223. if (labs (mLastMouse.h - mouseLoc.h) > kMouseResolution/2 &&
  224. labs (mLastMouse.v - mouseLoc.v) > kMouseResolution/2)
  225. AddBytes (&mouseLoc, sizeof (mouseLoc),
  226. kMousePositionEntropy);
  227. if (mLastMouse.h == mouseLoc.h && mLastMouse.v == mouseLoc.v)
  228. mMouseStill ++;
  229. else
  230. {
  231. double entropy;
  232. // Mouse has moved. Add the number of measurements for
  233. // which it's been still. If the resolution is too
  234. // coarse, assume the entropy is 0.
  235. lastCheck = TickCount() - mLastPeriodicTicks;
  236. if (lastCheck <= 0)
  237. lastCheck = 1;
  238. entropy = log2l
  239. (kTypicalMouseIdleTicks/(double)lastCheck);
  240. if (entropy < 0.0)
  241. entropy = 0.0;
  242. AddBytes (&mMouseStill, sizeof (mMouseStill), entropy);
  243. mMouseStill = 0;
  244. }
  245. mLastMouse = mouseLoc;
  246. }
  247. void CRandomizer::AddAbsoluteSystemStartupTime (void)
  248. {
  249. unsigned long now; // Time in seconds since
  250. // 1/1/1904
  251. GetDateTime (&now);
  252. now -= TickCount() / 60; // Time in ticks since machine
  253. // startup
  254. AddBytes (&now, sizeof (now), kSysStartupEntropy);
  255. }
  256. void CRandomizer::AddTimeSinceMachineStartup (void)
  257. {
  258. AddNow (1.5); // Uncertainty in app startup
  259. // time is > 1.5 msec (for
  260. // automated app startup).
  261. }
  262. void CRandomizer::AddAppRunningTime (void)
  263. {
  264. ProcessSerialNumber PSN;
  265. ProcessInfoRec ProcessInfo;
  266. ProcessInfo.processInfoLength = sizeof (ProcessInfoRec);
  267. ProcessInfo.processName = nil;
  268. ProcessInfo.processAppSpec = nil;
  269. GetCurrentProcess (&PSN);
  270. GetProcessInformation (&PSN, &ProcessInfo);
  271. // Now add the amount of time in ticks that the current process
  272. // has been active
  273. AddBytes (&ProcessInfo, sizeof (ProcessInfoRec),
  274. kApplicationUpTimeEntropy);
  275. }
  276. void CRandomizer::AddStartupVolumeInfo (void)
  277. {
  278. short vRefNum;
  279. long dirID;
  280. XVolumeParam pb;
  281. OSErr err;
  282. if (!mSupportsLargeVolumes)
  283. return;
  284. FindFolder (kOnSystemDisk, kSystemFolderType, kDontCreateFolder,
  285. &vRefNum, &dirID);
  286. pb.ioVRefNum = vRefNum;
  287. pb.ioCompletion = 0;
  288. pb.ioNamePtr = 0;
  289. pb.ioVolIndex = 0;
  290. err = PBXGetVolInfoSync (&pb);
  291. if (err != noErr)
  292. return;
  293. // Base the entropy on the amount of space used on the disk and
  294. // on the next available allocation block. A lot else might be
  295. // unpredictable, so might as well toss the whole block in. See
  296. // comments for entropy estimate justifications.
  297. AddBytes (&pb, sizeof (pb),
  298. kVolumeBytesEntropy +
  299. log2l (((pb.ioVTotalBytes.hi - pb.ioVFreeBytes.hi)
  300. * 4294967296.0D +
  301. (pb.ioVTotalBytes.lo - pb.ioVFreeBytes.lo))
  302. / pb.ioVAlBlkSiz - 3.0));
  303. }
  304. /*
  305. On a typical startup CRandomizer will come up with about 60
  306. bits of good, unpredictable data. Assuming no more input will
  307. be available, we'll need some more lower-quality data to give
  308. OpenSSL the 128 bits of entropy it desires. AddFiller adds some
  309. relatively predictable data into the soup.
  310. */
  311. void CRandomizer::AddFiller (void)
  312. {
  313. struct
  314. {
  315. ProcessSerialNumber psn; // Front process serial
  316. // number
  317. RGBColor hiliteRGBValue; // User-selected
  318. // highlight color
  319. long processCount; // Number of active
  320. // processes
  321. long cpuSpeed; // Processor speed
  322. long totalMemory; // Total logical memory
  323. // (incl. virtual one)
  324. long systemVersion; // OS version
  325. short resFile; // Current resource file
  326. } data;
  327. GetNextProcess ((ProcessSerialNumber*) kNoProcess);
  328. while (GetNextProcess (&data.psn) == noErr)
  329. data.processCount++;
  330. GetFrontProcess (&data.psn);
  331. LMGetHiliteRGB (&data.hiliteRGBValue);
  332. Gestalt (gestaltProcClkSpeed, &data.cpuSpeed);
  333. Gestalt (gestaltLogicalRAMSize, &data.totalMemory);
  334. Gestalt (gestaltSystemVersion, &data.systemVersion);
  335. data.resFile = CurResFile ();
  336. // Here we pretend to feed the PRNG completely random data. This
  337. // is of course false, as much of the above data is predictable
  338. // by an outsider. At this point we don't have any more
  339. // randomness to add, but with OpenSSL we must have a 128 bit
  340. // seed before we can start. We just add what we can, without a
  341. // real entropy estimate, and hope for the best.
  342. AddBytes (&data, sizeof(data), 8.0 * sizeof(data));
  343. AddCurrentMouse ();
  344. AddNow (1.0);
  345. }
  346. //------------------- LOW LEVEL ---------------------
  347. void CRandomizer::AddBytes (void *data, long size, double entropy)
  348. {
  349. RAND_add (data, size, entropy * 0.125); // Convert entropy bits
  350. // to bytes
  351. }
  352. void CRandomizer::AddNow (double millisecondUncertainty)
  353. {
  354. long time = SysTimer();
  355. AddBytes (&time, sizeof (time), log2l (millisecondUncertainty *
  356. mTimebaseTicksPerMillisec));
  357. }
  358. //----------------- TIMING SUPPORT ------------------
  359. void CRandomizer::GetTimeBaseResolution (void)
  360. {
  361. #ifdef __powerc
  362. long speed;
  363. // gestaltProcClkSpeed available on System 7.5.2 and above
  364. if (Gestalt (gestaltProcClkSpeed, &speed) != noErr)
  365. // Only PowerPCs running pre-7.5.2 are 60-80 MHz
  366. // machines.
  367. mTimebaseTicksPerMillisec = 6000.0D;
  368. // Assume 10 cycles per clock update, as in 601 spec. Seems true
  369. // for later chips as well.
  370. mTimebaseTicksPerMillisec = speed / 1.0e4D;
  371. #else
  372. // 68K VIA-based machines (see Develop Magazine no. 29)
  373. mTimebaseTicksPerMillisec = 783.360D;
  374. #endif
  375. }
  376. unsigned long CRandomizer::SysTimer (void) // returns the lower 32
  377. // bit of the chip timer
  378. {
  379. #ifdef __powerc
  380. return GetPPCTimer (mIs601);
  381. #else
  382. UnsignedWide usec;
  383. Microseconds (&usec);
  384. return usec.lo;
  385. #endif
  386. }
  387. #ifdef __powerc
  388. // The timebase is available through mfspr on 601, mftb on later chips.
  389. // Motorola recommends that an 601 implementation map mftb to mfspr
  390. // through an exception, but I haven't tested to see if MacOS actually
  391. // does this. We only sample the lower 32 bits of the timer (i.e. a
  392. // few minutes of resolution)
  393. asm unsigned long GetPPCTimer (register bool is601)
  394. {
  395. cmplwi is601, 0 // Check if 601
  396. bne _601 // if non-zero goto _601
  397. mftb r3 // Available on 603 and later.
  398. blr // return with result in r3
  399. _601:
  400. mfspr r3, spr5 // Available on 601 only.
  401. // blr inserted automatically
  402. }
  403. #endif