source: branches/eraser6/Manager/PRNG.cs @ 478

Revision 478, 19.8 KB checked in by lowjoel, 6 years ago (diff)

Reapplied my changes and reorganisations after Kaz accidentally removed them.

  • Property svn:keywords set to Id
Line 
1/*
2 * $Id$
3 * Copyright 2008 The Eraser Project
4 * Original Author: Joel Low <lowjoel@users.sourceforge.net>
5 * Modified By: Kasra Nasiri <cjax@users.sourceforge.net> @10/7/2008
6 * Modified By:
7 *
8 * This file is part of Eraser.
9 *
10 * Eraser is free software: you can redistribute it and/or modify it under the
11 * terms of the GNU General Public License as published by the Free Software
12 * Foundation, either version 3 of the License, or (at your option) any later
13 * version.
14 *
15 * Eraser is distributed in the hope that it will be useful, but WITHOUT ANY
16 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
17 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
18 *
19 * A copy of the GNU General Public License can be found at
20 * <http://www.gnu.org/licenses/>.
21 */
22
23using System;
24using System.Collections.Generic;
25using System.Text;
26
27using System.Threading;
28using System.Security.Cryptography;
29using System.Runtime.InteropServices;
30using System.Diagnostics;
31using System.Reflection;
32using System.IO;
33using Microsoft.Win32.SafeHandles;
34using Eraser.Util;
35
36namespace Eraser.Manager
37{
38    /// <summary>
39    /// An interface class for all pseudorandom number generators used for the
40    /// random data erase passes.
41    /// </summary>
42    public abstract class PRNG : Random
43    {
44        public override string ToString()
45        {
46            return Name;
47        }
48
49        /// <summary>
50        /// The name of this erase pass, used for display in the UI
51        /// </summary>
52        public abstract string Name
53        {
54            get;
55        }
56
57        /// <summary>
58        /// The GUID for this PRNG.
59        /// </summary>
60        public abstract Guid GUID
61        {
62            get;
63        }
64
65        /// <summary>
66        /// Reseeds the PRNG. This can be called by inherited classes, but its most
67        /// important function is to provide new seeds regularly. The PRNGManager
68        /// will call this function once in a whle to maintain the quality of
69        /// generated numbers.
70        /// </summary>
71        /// <param name="seed">An arbitrary length of information that will be
72        /// used to reseed the PRNG</param>
73        protected internal abstract void Reseed(byte[] seed);
74
75        #region Random members
76        public override int Next(int maxValue)
77        {
78            if (maxValue == 0)
79                return 0;
80            return Next() % maxValue;
81        }
82
83        public override int Next(int minValue, int maxValue)
84        {
85            if (minValue > maxValue)
86                throw new ArgumentOutOfRangeException("minValue", minValue, "minValue is greater than maxValue");
87            else if (minValue == maxValue)
88                return minValue;
89            return (Next() % (maxValue - minValue)) + minValue;
90        }
91
92        public unsafe override int Next()
93        {
94            //Declare a return variable
95            int result;
96            int* fResult = &result;
97
98            //Get the random-valued bytes to fill the int.
99            byte[] rand = new byte[sizeof(int)];
100            NextBytes(rand);
101
102            //Copy the random buffer into the int.
103            fixed (byte* fRand = rand)
104            {
105                byte* pResult = (byte*)fResult;
106                byte* pRand = fRand;
107                for (int i = 0; i != sizeof(int); ++i)
108                    *pResult++ = *pRand++;
109            }
110
111            return Math.Abs(result);
112        }
113
114        protected unsafe override double Sample()
115        {
116            //Declare a return variable
117            double result;
118            double* fResult = &result;
119
120            //Get the random-valued bytes to fill the int.
121            byte[] rand = new byte[sizeof(double)];
122            NextBytes(rand);
123
124            //Copy the random buffer into the int.
125            fixed (byte* fRand = rand)
126            {
127                byte* pResult = (byte*)fResult;
128                byte* pRand = fRand;
129                for (int i = 0; i != sizeof(double); ++i)
130                    *pResult++ = *pRand++;
131            }
132
133            return result;
134        }
135
136        public abstract override void NextBytes(byte[] buffer);
137        #endregion
138    }
139
140    /// <summary>
141    /// Class managing all the PRNG algorithms.
142    /// </summary>
143    public class PRNGManager
144    {
145        /// <summary>
146        /// Retrieves all currently registered erasure methods.
147        /// </summary>
148        /// <returns>A mutable list, with an instance of each PRNG.</returns>
149        public static Dictionary<Guid, PRNG> GetAll()
150        {
151            lock (ManagerLibrary.Instance.PRNGManager.prngs)
152                return ManagerLibrary.Instance.PRNGManager.prngs;
153        }
154
155        /// <summary>
156        /// Retrieves the instance of the PRNG with the given GUID.
157        /// </summary>
158        /// <param name="guid">The GUID of the PRNG.</param>
159        /// <returns>The PRNG instance.</returns>
160        public static PRNG GetInstance(Guid guid)
161        {
162            try
163            {
164                lock (ManagerLibrary.Instance.PRNGManager.prngs)
165                    return ManagerLibrary.Instance.PRNGManager.prngs[guid];
166            }
167            catch (KeyNotFoundException)
168            {
169                throw new FatalException("PRNG not found: " + guid.ToString());
170            }
171        }
172
173        /// <summary>
174        /// Allows plug-ins to register PRNGs with the main program. Thread-safe.
175        /// </summary>
176        /// <param name="method"></param>
177        public static void Register(PRNG prng)
178        {
179            lock (ManagerLibrary.Instance.PRNGManager.prngs)
180                ManagerLibrary.Instance.PRNGManager.prngs.Add(prng.GUID, prng);
181        }
182
183        /// <summary>
184        /// Allows the EntropyThread to get entropy to the PRNG functions as seeds.
185        /// </summary>
186        /// <param name="entropy">An array of bytes, being entropy for the PRNG.</param>
187        internal void AddEntropy(byte[] entropy)
188        {
189            lock (ManagerLibrary.Instance.PRNGManager.prngs)
190                foreach (PRNG prng in prngs.Values)
191                    prng.Reseed(entropy);
192        }
193
194        /// <summary>
195        /// Gets entropy from the EntropyThread.
196        /// </summary>
197        /// <returns>A buffer of arbitrary length containing random information.</returns>
198        public static byte[] GetEntropy()
199        {
200            return ManagerLibrary.Instance.PRNGManager.entropyThread.GetPool();
201        }
202       
203        /// <summary>
204        /// The entropy thread gathering entropy for the RNGs.
205        /// </summary>
206        internal EntropyPoller entropyThread = new EntropyPoller();
207
208        /// <summary>
209        /// The list of currently registered erasure methods.
210        /// </summary>
211        private Dictionary<Guid, PRNG> prngs = new Dictionary<Guid, PRNG>();
212    }
213
214    /// <summary>
215    /// A class which uses EntropyPoll class to fetch system data as a source of
216    /// randomness at "regular" but "random" intervals
217    /// </summary>
218    class EntropyPoller
219    {
220        public EntropyPoller()
221        {   
222            //Then start the thread which maintains the pool.
223            thread = new Thread(delegate()
224                {
225                    this.Main();
226                }
227            );
228            thread.Start();
229        }
230
231        /// <summary>
232        /// The PRNG entropy thread. This thread will run in the background, getting
233        /// random data to be used for entropy. This will maintain the integrity
234        /// of generated data from the PRNGs.
235        /// </summary>
236        private void Main()
237        {
238            //This entropy thread will utilize a polling loop.
239            DateTime lastAddedEntropy = DateTime.Now;
240            TimeSpan managerEntropySpan = new TimeSpan(0, 10, 0);
241            Stopwatch st = new Stopwatch();
242
243            while (thread.ThreadState != System.Threading.ThreadState.AbortRequested)
244            {
245                st.Start();
246                {
247                    FastAddEntropy();
248                    SlowAddEntropy();
249                }
250               
251                st.Stop(); 
252                Thread.Sleep(2000 + (int)(st.ElapsedTicks % 2049L));
253                st.Reset();
254
255                //Send entropy to the PRNGs for new seeds.
256                if (DateTime.Now - lastAddedEntropy > managerEntropySpan)
257                    ManagerLibrary.Instance.PRNGManager.AddEntropy(GetPool());
258            }
259        }
260       
261        /// <summary>
262        /// Stops the execution of the thread.
263        /// </summary>
264        public void Abort()
265        {
266            thread.Abort();
267        }
268
269        /// <summary>
270        /// The thread object.
271        /// </summary>
272        Thread thread;     
273    }
274   
275    /// <summary>
276    /// Provides means of generating random entropy from the system, user data
277    /// available from the kernel or dedicated harware.
278    /// </summary>
279    public class EntropySource
280    {
281        /// <summary>
282        /// The algorithm used for mixing
283        /// </summary>
284        private enum PRFAlgorithms
285        {
286            MD5,
287            SHA1,
288            RIPEMD160,
289            SHA256,
290            SHA384,
291            SHA512,
292        };
293
294        public EntropySource()
295        {
296            //Create the pool.
297            pool = new byte[sizeof(uint) * 128];
298
299            //Initialize the pool with some default information.
300            {
301                //Process startup information
302                KernelAPI.STARTUPINFO startupInfo = new KernelAPI.STARTUPINFO();
303                KernelAPI.GetStartupInfo(out startupInfo);
304                AddEntropy(startupInfo);
305
306                //System information
307                KernelAPI.SYSTEM_INFO systemInfo = new KernelAPI.SYSTEM_INFO();
308                KernelAPI.GetSystemInfo(out systemInfo);
309                AddEntropy(systemInfo);
310
311                FastAddEntropy();
312                SlowAddEntropy();
313
314                // set the default PRF algorithm
315                PRFAlgorithm = PRFAlgorithms.SHA512;
316                MixPool();
317            }
318
319            // apply whitening effect
320            PRFAlgorithm = PRFAlgorithms.RIPEMD160;
321            MixPool();
322
323            // set back to default hash algorithm
324            PRFAlgorithm = PRFAlgorithms.SHA512;
325        }
326
327        /// <summary>
328        /// Retrieves the current contents of the entropy pool.
329        /// </summary>
330        /// <returns>A byte array containing all the randomness currently found.</returns>
331        public byte[] GetPool()
332        {
333            //Mix and invert the pool
334            MixPool();
335            InvertPool();
336
337            //Return a safe copy
338            lock (pool)
339            {
340                byte[] result = new byte[pool.Length];
341                pool.CopyTo(result, 0);
342
343                return result;
344            }
345        }
346
347        /// <summary>
348        /// Inverts the contents of the pool
349        /// </summary>
350        private void InvertPool()
351        {
352            lock (poolLock)
353                unsafe
354                {
355                    fixed (byte* fPool = pool)
356                    {
357                        uint* pPool = (uint*)fPool;
358                        uint poolLength = (uint)(pool.Length / sizeof(uint));
359                        while (poolLength-- != 0)
360                            *pPool = (uint)(*pPool++ ^ unchecked((uint)-1));
361                    }
362                }
363        }
364
365        /// <summary>
366        /// Mixes the contents of the pool.
367        /// </summary>
368        private void MixPool()
369        {
370            lock (poolLock)
371            {
372                //Mix the last 128 bytes first.
373                const int mixBlockSize = 128;
374                int hashSize = PRF.HashSize / 8;
375                PRF.ComputeHash(pool, pool.Length - mixBlockSize, mixBlockSize).CopyTo(pool, 0);
376
377                //Then mix the following bytes until wraparound is required
378                int i = 0;
379                for (; i < pool.Length - hashSize; i += hashSize)
380                    Buffer.BlockCopy(PRF.ComputeHash(pool, i,
381                        i + mixBlockSize >= pool.Length ? pool.Length - i : mixBlockSize),
382                        0, pool, i, i + hashSize >= pool.Length ? pool.Length - i : hashSize);
383
384                //Mix the remaining blocks which require copying from the front
385                byte[] combinedBuffer = new byte[mixBlockSize];
386                for (; i < pool.Length; i += hashSize)
387                {
388                    Buffer.BlockCopy(pool, i, combinedBuffer, 0, pool.Length - i);
389
390                    Buffer.BlockCopy(pool, 0, combinedBuffer, pool.Length - i,
391                                mixBlockSize - (pool.Length - i));
392
393                    Buffer.BlockCopy(PRF.ComputeHash(combinedBuffer, 0, mixBlockSize), 0,
394                        pool, i, pool.Length - i > hashSize ? hashSize : pool.Length - i);
395                }
396            }
397        }
398
399        /// <summary>
400        /// Adds data which is random to the pool
401        /// </summary>
402        /// <param name="entropy">An array of data which will be XORed with pool
403        /// contents.</param>
404        public unsafe void AddEntropy(byte[] entropy)
405        {
406            lock (poolLock)
407                fixed (byte* pEntropy = entropy)
408                fixed (byte* pPool = pool)
409                {
410                    int size = entropy.Length;
411                    byte* mpEntropy = pEntropy;
412                    while (size > 0)
413                    {
414                        //Bring the pool position back to the front if we are at our end
415                        if (poolPosition >= pool.Length)
416                            poolPosition = 0;
417
418                        int amountToMix = Math.Min(size, pool.Length - poolPosition);
419                        MemoryXor(pPool + poolPosition, mpEntropy, amountToMix);
420                        mpEntropy = mpEntropy + amountToMix;
421                        size -= amountToMix;
422                    }
423                }
424        }
425
426        /// <summary>
427        /// XOR's memory a DWORD at a time.
428        /// </summary>
429        /// <param name="destination">The destination buffer to be XOR'ed</param>
430        /// <param name="source">The source buffer to XOR with</param>
431        /// <param name="size">The size of the source buffer</param>
432        private static unsafe void MemoryXor(byte* destination, byte* source, int size)
433        {
434            int wsize = size / sizeof(uint);
435            size -= wsize * sizeof(uint);
436            uint* d = (uint*)destination;
437            uint* s = (uint*)source;
438           
439            while (wsize-- > 0)
440                *d++ ^= *s++;
441
442            if (size > 0)
443            {
444                byte* db = (byte*)d,
445                      ds = (byte*)s;
446                while (size-- > 0)
447                    *db++ ^= *ds++;
448            }
449        }
450
451        /// <summary>
452        /// Adds data which is random to the pool
453        /// </summary>
454        /// <typeparam name="T">Any value type</typeparam>
455        /// <param name="entropy">A value which will be XORed with pool contents.</param>
456        public unsafe void AddEntropy<T>(T entropy) where T : struct
457        {
458            try
459            {
460                int sizeofObject = Marshal.SizeOf(entropy);
461                IntPtr memory = Marshal.AllocHGlobal(sizeofObject);
462                try
463                {
464                    Marshal.StructureToPtr(entropy, memory, false);
465                    byte[] dest = new byte[sizeofObject];
466
467                    //Copy the memory
468                    Marshal.Copy(memory, dest, 0, sizeofObject);
469
470                    //Add entropy
471                    AddEntropy(dest);
472                }
473                finally
474                {
475                    Marshal.FreeHGlobal(memory);
476                }
477            }
478            catch (OutOfMemoryException ex1)
479            {
480                // ignore this entropy source, we don't have enough memory!
481                string ignored = ex1.Message;
482            }
483        }
484
485        /// <summary>
486        /// Adds entropy to the pool. The sources of the entropy data is queried
487        /// quickly.
488        /// </summary>
489        private void FastAddEntropy()
490        {
491            //Add the free disk space to the pool
492            AddEntropy(new DriveInfo(new DirectoryInfo(Environment.SystemDirectory).
493                Root.FullName).TotalFreeSpace);
494
495            //Miscellaneous window handles
496            AddEntropy(UserAPI.GetCapture());
497            AddEntropy(UserAPI.GetClipboardOwner());
498            AddEntropy(UserAPI.GetClipboardViewer());
499            AddEntropy(UserAPI.GetDesktopWindow());
500            AddEntropy(UserAPI.GetForegroundWindow());
501            AddEntropy(UserAPI.GetMessagePos());
502            AddEntropy(UserAPI.GetMessageTime());
503            AddEntropy(UserAPI.GetOpenClipboardWindow());
504            AddEntropy(UserAPI.GetProcessWindowStation());
505            AddEntropy(KernelAPI.GetCurrentProcessId());
506            AddEntropy(KernelAPI.GetCurrentThreadId());
507            AddEntropy(KernelAPI.GetProcessHeap());
508
509            //The caret and cursor positions
510            UserAPI.POINT point;
511            UserAPI.GetCaretPos(out point);
512            AddEntropy(point);
513            UserAPI.GetCursorPos(out point);
514            AddEntropy(point);
515
516            //Amount of free memory
517            KernelAPI.MEMORYSTATUSEX memoryStatus = new KernelAPI.MEMORYSTATUSEX();
518            memoryStatus.dwLength = (uint)Marshal.SizeOf(memoryStatus);
519            if (KernelAPI.GlobalMemoryStatusEx(ref memoryStatus))
520            {
521                AddEntropy(memoryStatus.ullAvailPhys);
522                AddEntropy(memoryStatus.ullAvailVirtual);
523                AddEntropy(memoryStatus);
524            }
525
526            //Thread execution times
527            long creationTime, exitTime, kernelTime, userTime;
528            if (KernelAPI.GetThreadTimes(KernelAPI.GetCurrentThread(), out creationTime,
529                out exitTime, out kernelTime, out userTime))
530            {
531                AddEntropy(creationTime);
532                AddEntropy(kernelTime);
533                AddEntropy(userTime);
534            }
535
536            //Process execution times
537            if (KernelAPI.GetProcessTimes(KernelAPI.GetCurrentProcess(), out creationTime,
538                out exitTime, out kernelTime, out userTime))
539            {
540                AddEntropy(creationTime);
541                AddEntropy(kernelTime);
542                AddEntropy(userTime);
543            }
544
545            //Current system time
546            AddEntropy(DateTime.Now.Ticks);
547
548            //The high resolution performance counter
549            long perfCount = 0;
550            if (KernelAPI.QueryPerformanceCounter(out perfCount))
551                AddEntropy(perfCount);
552
553            //Ticks since start up
554            uint tickCount = KernelAPI.GetTickCount();
555            if (tickCount != 0)
556                AddEntropy(tickCount);
557
558            //CryptGenRandom
559            byte[] cryptGenRandom = new byte[160];
560            if (CryptAPI.CryptGenRandom(cryptGenRandom))
561                AddEntropy(cryptGenRandom);
562        }
563
564        /// <summary>
565        /// Adds entropy to the pool. The sources of the entropy data is queried
566        /// relatively slowly compared to the FastAddEntropy function.
567        /// </summary>
568        private void SlowAddEntropy()
569        {
570            //NetAPI statistics
571            unsafe
572            {
573                IntPtr netAPIStats = IntPtr.Zero;
574                if (NetAPI.NetStatisticsGet(null, NetAPI.SERVICE_WORKSTATION,
575                    0, 0, out netAPIStats) == 0)
576                {
577                    try
578                    {
579                        //Get the size of the buffer
580                        uint size = 0;
581                        NetAPI.NetApiBufferSize(netAPIStats, out size);
582                        byte[] entropy = new byte[size];
583
584                        //Copy the buffer
585                        Marshal.Copy(entropy, 0, netAPIStats, entropy.Length);
586
587                        //And add it to the pool
588                        AddEntropy(entropy);
589                    }
590                    finally
591                    {
592                        //Free the statistics buffer
593                        NetAPI.NetApiBufferFree(netAPIStats);
594                    }
595                }
596            }
597
598#if false
599            //Get disk I/O statistics for all the hard drives
600            for (int drive = 0; ; ++drive)
601            {
602                //Try to open the drive.
603                using (SafeFileHandle hDevice = File.CreateFile(
604                    string.Format("\\\\.\\PhysicalDrive%d", drive), 0,
605                    File.FILE_SHARE_READ | File.FILE_SHARE_WRITE, IntPtr.Zero,
606                    File.OPEN_EXISTING, 0, IntPtr.Zero))
607                {
608                    if (hDevice.IsInvalid)
609                        break;
610
611                    //This only works if the user has turned on the disk performance
612                    //counters with 'diskperf -y'. These counters are off by default
613                    if (File.DeviceIoControl(hDevice, IOCTL_DISK_PERFORMANCE, NULL, 0,
614                        &diskPerformance, sizeof(DISK_PERFORMANCE), &uSize, NULL))
615                    {
616                        addEntropy(&diskPerformance, uSize);
617                    }
618                }
619            }
620#endif
621
622            /*
623             Query performance data. Because the Win32 version of this API (through
624             registry) may be buggy, use the NT Native API instead.
625             
626             Scan the first 64 possible information types (we don't bother
627             with increasing the buffer size as we do with the Win32
628             version of the performance data read, we may miss a few classes
629             but it's no big deal).  In addition the returned size value for
630             some classes is wrong (eg 23 and 24 return a size of 0) so we
631             miss a few more things, but again it's no big deal.  This scan
632             typically yields around 20 pieces of data, there's nothing in
633             the range 65...128 so chances are there won't be anything above
634             there either.
635            */
636            uint dataWritten = 0;
637            byte[] infoBuffer = new byte[65536];
638            uint totalEntropy = 0;
639            for (uint infoType = 0; infoType < 64; ++infoType)
640            {
641                uint result = NTAPI.NtQuerySystemInformation(infoType, infoBuffer,
642                    (uint)infoBuffer.Length, out dataWritten);
643
644                if (result == 0 /*ERROR_SUCCESS*/ && dataWritten > 0)
645                {
646                    byte[] entropy = new byte[dataWritten];
647                    Buffer.BlockCopy(infoBuffer, 0, entropy, 0, (int)dataWritten);
648                    AddEntropy(entropy);
649                    totalEntropy += dataWritten;
650                }
651            }
652
653            AddEntropy(totalEntropy);
654
655            //Finally, our good friend CryptGenRandom()
656            byte[] cryptGenRandom = new byte[1536];
657            if (CryptAPI.CryptGenRandom(cryptGenRandom))
658                AddEntropy(cryptGenRandom);
659        }
660
661        /// <summary>
662        /// PRF algorithm handle
663        /// </summary>
664        private HashAlgorithm PRF
665        {
666            get
667            {
668                Type type = null;
669                switch (PRFAlgorithm)
670                {
671                    case PRFAlgorithms.MD5:
672                        type = typeof(MD5CryptoServiceProvider);
673                        break;
674                    case PRFAlgorithms.SHA1:
675                        type = typeof(SHA1Managed);
676                        break;
677                    case PRFAlgorithms.RIPEMD160:
678                        type = typeof(RIPEMD160Managed);
679                        break;
680                    case PRFAlgorithms.SHA256:
681                        type = typeof(SHA256Managed);
682                        break;
683                    case PRFAlgorithms.SHA384:
684                        type = typeof(SHA384Managed);
685                        break;
686                    default:
687                        type = typeof(SHA512Managed);
688                        break;
689                }
690
691                if (type.IsInstanceOfType(prfCache))
692                    return prfCache;
693                ConstructorInfo hashConstructor = type.GetConstructor(Type.EmptyTypes);
694                return prfCache = (HashAlgorithm)hashConstructor.Invoke(null);
695            }
696        }
697
698        /// <summary>
699        /// The last created PRF algorithm handle.
700        /// </summary>
701        private HashAlgorithm prfCache;
702
703        /// <summary>
704        /// PRF algorithm identifier
705        /// </summary>
706        private PRFAlgorithms PRFAlgorithm;
707
708        /// <summary>
709        /// The pool of data which we currently maintain.
710        /// </summary>
711        private byte[] pool;
712
713        /// <summary>
714        /// The next position where entropy will be added to the pool.
715        /// </summary>
716        private int poolPosition = 0;
717
718        /// <summary>
719        /// The lock guarding the pool array and the current entropy addition index.
720        /// </summary>
721        private object poolLock = new object();
722    }
723}
Note: See TracBrowser for help on using the repository browser.