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

Revision 462, 19.5 KB checked in by lowjoel, 6 years ago (diff)

Cleaned up r443.

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