Cryptographic Random Numbers

Explanation with Dephi source explaining how to generate random numbers with proper sources of entropy and hash functions.

[Cryptographic Random Numbers]



//Source Code Bellow



Simply calling Randomize and using the Random() procedure is a severe security flaw in application seeking to pretect data with random numbers. A random number generator gets is 'randomness' from entropy. Borlands Random() procedure uses a 32bit seed as entropy, and that seed is generated by the Randomize procedure which gets its entropy the system time and date which are very probabilistic and can be tested for quickly.



To generate random numbers that cannot be differentiated from pure chaos is a VERY difficult task on a computer, mainly because you rely on internal states that are often too predictable. The idea is to gather entropy from the least predictable states of the system and dillute that entropy inside a much larger pool. The pool I refer to is the internal state of the random number generator.



WHAT IT IS:



There are important properties that have to be respected when generating random numbers. More specificaly, random numbers intended

for encryption. The properties that implicated in this random number gerenartors design are strongly based on Bruce Schneier's Yarrow (www.counterpane.com).



The first property is to ensure there is always anought entropy in the pool before outputing random numbers so that the pool never enters a weakened state where the next random numbers that are output have predictible information.



The next property comes in handy if you're going to be using the generator to make session keys that will change multiple times during a chat session. It is important that one compromised key will not reveal any of the previous keys nor any of the next keys that will be used. To do this we need to eliminate the mathematical relationship between the random numbers that are output and the state of the pool.



The third desired property implies that enven if the entropy gathered from your sources is of poor quality (fairly predictable) the pool must not suffer for the low entropy and the output random numbers must not show any evidence of this.



I have tested this unit extensively. The final and most crucial test centered around the third property. To make an extreme case, I started the pool with nothing but zeros in it and generated ~12MB (100,000,000 bits). I used the DieHard battery of tests (http://stat.fsu.edu/~geo/diehard.html) and it passed all 15 with flying colors... without collecting any entropy. With this I am satisfied of the random number generator's performance and submit it to you to use as a secure alternative to what is commonly seen in programs.





HOW TO IT WORKS:



-two entropy gatherers are created:



[1] a thread that tracks mouse movement at random intervals taking 4bits of entropy from the mouse position and state of the system's high-resolution timer.



[2] a latency calculator that gets 4bits of entropy from the high-resolution timer when called by the main app (this is used by alling

TKeyGenerator.AddLatency on the OnKeyDown event of an edit box, to count harddrive latency, or irq latency)



When either of the entropy gatherers has accumulated 32bits, it sends it to the entropy pool.



-The entroyp pool takes in entropy 32bits at a time and uses it to fill an entropy buffer of 256bits, when the buffer is full, a primary reseed is executed.



-The primary reseed updates the primary pool (a Hash Context: internal state of a hash function) with the entropy and XORs it with the pool's seed (this seed is used similarly the way randomize generates randseed). After every primary reseed, the seed (with now 256bits of entropy) is ready to be used to output random numbers if the calling application so desires it, but it will continue to reseed and gather entropy regardless regardless of that. After 8 primary reseeds have taken place, a secondary reseed is executed.



-The secondary reseed updates the secondary pool with the contents of the primary pool and then flushes the contents of the primary pool into a state with no entropy. The secondary pool is persistant in that it is never flushed and will carry entropy bits from various reseeds. A completly new seed is generated from the secondary reseed (where as the primary on modifies it with entropy). This secondary reseed prevents backtracking properties (gessing previous states of the pool) and ensures there is entropy in the pool even under conditions where new entropy is of poor quality.



-When the calling application needs to generate a key it calls SafeGetKey which ensures that no more than 8 sets of 256bits of random numbers can be generated from a single reseed. To do this a key reserve counter is incremented every primary reseed, and cannot exceed 8. When a you generate a set of random numbers the key reserve is decremented and the function will return fasle if the key reserve is at 0. NOTE: an application can ignore the key reserve and call ForceGetKey. This is very risky practice and I seriously discourage you from using this function.



-The random output created by GetKey is a generated with the entropy pool's seed. The seed is used as an encryption key and then permuted (with an expansion-compression). The new seed is used as data to be encrypted. It is encrypted with the previous seed and expanded-compressed in 64 rounds. These rounds ensure that it is impossible to determine the state of the seed, the primary pool, the secondary pool or the entorpy buffer; in turn, preventing anyone from finding the previous or next outputs.



NOTES:

-Assign a variable of type TKeyGenerator and call it's .Create. This will start the process. When you are done, call .Destropy.



-You can use .KeyCount to find out the state of the key reserve (how many GetKey calls can be made before the next reseed). I strongly condone raising the value of MAX_KEY_RESERVE.



-You can manipulate the speed at which entropy is gathered from the mouse by setting the MOUSE_INTERVAL constant (in milli-seconds). A value lower than 10 is unrecommended.



-No error checking is done to ensure there is a high-frequency counter on the system, this should be verified by the calling application. If there is no such counter, the random number generator will work but will output non-random numbers.



-The application must provide 32 BYTES of memory space in a variable to pass to the GetKey functions. No error checking is done here.



-You may change KEY_BUILD_ROUNDS to any value greater than or equal to 32, but larger than 64 is quite useless.





/*********************************************************************

/*********************************************************************

                             - IMPORTANT NOTE -



The source bellow is part of a library in progress cummulating 3 years of my research. If you want to use it in a program, a little bit of credit would be nice.



NSCrypt.pas contains a pseudo random number generator that comes from an unknown source, and these implementations of Haval and Rijndael are [severe] modifications of David Barton's haval.pas and rijndael.pas found in the DCPcrypt 1.3 component suite.



Download NSCrypt.txt and rename it NSCrypt.pas (silly webhost) I've included the cryptographic functions sepperatly because they total 1300 lines together.



http://www.eccentrix.com/computer/drmungkee/NSCrypt.txt

(the actual website is www.drmungkee.com)

/*********************************************************************

/*********************************************************************



//you'll have to deal with the documentation above.



unit NoiseSpunge;



interface



uses Windows,Classes,Controls,NSCrypt;



const

      SEED_SIZE=8;

      PRIMARY_RESEED=SEED_SIZE;

      SECONDARY_RESEED=SEED_SIZE;



      //parameters

      MAX_KEY_RESERVE=8;

      KEY_BUILD_ROUNDS=64;

      MOUSE_INTERVAL=10;



type

   Key256 = array[0..SEED_SIZE-1] of longword;



   TNoiseSpungeAddEntropy = procedure(Block:longword) of object;

   TNoiseSpungeProcedure = procedure of object;



   TMouseCollector = class(TThread)

   protected

      PCtx:Prng_CTX;

      x,y:integer;

      Block:longword;

      BitsGathered:longword;

      Interval,Frequency,ThisTime,LastTime:TLargeInteger;

      SendMouseEntropy:TNoiseSpungeAddEntropy;

   public

      constructor Create;

      procedure SyncSendMouseEntropy;

      procedure Execute; override;

   end;



   TLatencyCollector = class

   protected

      Block:longword;

      BitsGathered:longword;

      Time:TLargeInteger;

      SendLatencyEntropy:TNoiseSpungeAddEntropy;

   public

      constructor Create;

      procedure MeasureLatency;

   end;



   TEntropyPool = class

   protected

      Seed:Key256;

      EntropyBuffer:Key256;

      PrimaryPool:Haval_CTX;

      SecondaryPool:Haval_CTX;

      PrimaryReseedCount:byte;

      EntropyCount:byte;

      KeyReserve:byte;

      procedure PermuteSeed;

      procedure PrimaryReseed;

      procedure SecondaryReseed;

      procedure AddEntropy(Block:longword);

   public

      constructor Create;

   end;



   TKeyGenerator = class

   protected

      EntropyPool:TEntropyPool;

      MouseCollector:TMouseCollector;

      LatencyCollector:TLatencyCollector;

   public

      AddLatency:TNoiseSpungeProcedure;

      constructor Create;

      destructor Destroy; override;

      function KeyCount:byte;

      function SafeGetKey(var Key):boolean;

      procedure ForcedGetKey(var Key);

   end;




implementation



constructor TMouseCollector.Create;

begin

   inherited Create(true);

   Randomize;

   PrngInit(@PCtx,RandSeed);

   FreeOnTerminate:=true;

   Priority:=tpNormal;

   Resume;

end;



procedure TMouseCollector.SyncSendMouseEntropy;

begin

   SendMouseEntropy(Block);

end;



procedure TMouseCollector.execute;

var NilHandle:pointer;

    Idled:boolean;

begin

   NilHandle:=nil;

   BitsGathered:=0;

   Idled:=false;

   QueryPerformanceFrequency(Frequency);

   repeat

      if Idled=false then

      begin

         MsgWaitForMultipleObjects(0,NilHandle,false,MOUSE_INTERVAL,0);

         Idled:=true;

      end;

      QueryPerformanceCounter(ThisTime);

      if ThisTime-LastTime>Interval then

      begin

         if (x<>mouse.cursorpos.x)and(y<>mouse.cursorpos.y) then

         begin

            x:=mouse.cursorpos.x;

            y:=mouse.cursorpos.y;

            Inc(Block,(((x and 15)xor(y and 15))xor(ThisTime and 15))shl

               BitsGathered);

            Inc(BitsGathered,4);

            if BitsGathered=32 then

            begin

               PrngInit(@PCtx,Block);

               Synchronize(SyncSendMouseEntropy);

               Block:=0;

               BitsGathered:=0;

            end;

            Interval:=((((Prng(@PCtx) mod MOUSE_INTERVAL) div 2)+MOUSE_INTERVAL)

               *Frequency)div 1000;

            QueryPerformanceCounter(LastTime);

            Idled:=false;

         end else

         begin

            QueryPerformanceCounter(LastTime);

            Idled:=false;

         end;

      end;

   until Terminated=true;

end;



constructor TLatencyCollector.Create;

begin

   inherited Create;

   Block:=0;

   BitsGathered:=0;

end;



procedure TLatencyCollector.MeasureLatency;

begin

   QueryPerformanceCounter(Time);

   Inc(Block,(Time and 15)shl BitsGathered);

   Inc(BitsGathered,4);

   if BitsGathered=32 then

   begin

      SendLatencyEntropy(Block);

      Block:=0;

      BitsGathered:=0;

   end;

end;



constructor TEntropyPool.Create;

begin

   inherited Create;

   HavalInit(@PrimaryPool);

   HavalInit(@SecondaryPool);

   FillChar(Seed,SizeOf(Seed),0);

   EntropyCount:=0;

   PrimaryReseedCount:=0;

   KeyReserve:=0;

end;



procedure TEntropyPool.PermuteSeed;

var TempBuffer:array[0..1]of Key256;

    PCtx:Prng_CTX;

    HCtx:Haval_CTX;

    i:byte;

begin

   for i:=0 to SEED_SIZE-1 do

   begin

      PrngInit(@PCtx,Seed[i]);

      TempBuffer[0,i]:=Prng(@PCtx);

      TempBuffer[1,i]:=Prng(@PCtx);

   end;

   HavalInit(@HCtx);

   HavalUpdate(@HCtx,TempBuffer,SizeOf(TempBuffer));

   HavalOutput(@HCtx,Seed);

end;



procedure TEntropyPool.PrimaryReseed;

var TempSeed:Key256;

    i:byte;

begin

   HavalUpdate(@PrimaryPool,EntropyBuffer,SizeOf(EntropyBuffer));

   if PrimaryReseedCount
   begin

      HavalOutput(@PrimaryPool,TempSeed);

      for i:=0 to SEED_SIZE-1 do Seed[i]:=Seed[i] xor TempSeed[i];

      Inc(PrimaryReseedCount);

   end else SecondaryReseed;

   FillChar(EntropyBuffer,SizeOf(EntropyBuffer),0);

   if KeyReserve
   EntropyCount:=0;

end;



procedure TEntropyPool.SecondaryReseed;

begin

   HavalOutput(@PrimaryPool,Seed);

   HavalUpdate(@SecondaryPool,Seed,SizeOf(Seed));

   HavalOutput(@SecondaryPool,Seed);

   PermuteSeed;

   HavalInit(@PrimaryPool);

   PrimaryReseedCount:=0;

end;



procedure TEntropyPool.AddEntropy(Block:longword);

begin

   Move(Block,pointer(longword(@EntropyBuffer)+(EntropyCount*SizeOf(Block)))^,SizeOf(Block));

   Inc(EntropyCount,1);

   if EntropyCount=PRIMARY_RESEED then PrimaryReseed;

end;



constructor TKeyGenerator.Create;

begin

   inherited Create;

   EntropyPool:=TEntropyPool.Create;

   MouseCollector:=TMouseCollector.Create;

   MouseCollector.SendMouseEntropy:=EntropyPool.AddEntropy;

   LatencyCollector:=TLatencyCollector.Create;

   LatencyCollector.SendLatencyEntropy:=EntropyPool.AddEntropy;

   AddLatency:=LatencyCollector.MeasureLatency;

end;



destructor TKeyGenerator.Destroy;

begin

   MouseCollector.terminate;

   LatencyCollector.destroy;

   EntropyPool.destroy;

   inherited Destroy;

end;



function TKeyGenerator.KeyCount:byte;

begin

   Result:=EntropyPool.KeyReserve;

end;



function TKeyGenerator.SafeGetKey(var Key):boolean;

var TempSeed:Key256;

    TempBuffer:array[0..1]of Key256;

    RCtx:Rijndael_CTX;

    PCtx:Prng_CTX;

    HCtx:Haval_CTX;

    i,j:byte;

begin

   if EntropyPool.KeyReserve=0 then

   begin

      Exit;

      Result:=false;

   end else Result:=true;

   Move(EntropyPool.Seed,TempSeed,SizeOf(TempSeed));

   EntropyPool.PermuteSeed;

   RijndaelInit(@RCtx,EntropyPool.Seed);

   for i:=0 to KEY_BUILD_ROUNDS-1 do

   begin

      RijndaelEncrypt(@RCtx,TempSeed[0]);

      RijndaelEncrypt(@RCtx,TempSeed[4]);

      for j:=0 to SEED_SIZE-1 do

      begin

         PrngInit(@pctx,TempSeed[j]);

         TempBuffer[0,j]:=Prng(@PCtx);

         TempBuffer[1,j]:=Prng(@PCtx);

      end;

      HavalInit(@HCtx);

      HavalUpdate(@HCtx,TempBuffer,SizeOf(TempBuffer));

      HavalOutput(@HCtx,TempSeed);

   end;

   Move(TempSeed,Key,SizeOf(TempSeed));

   Dec(EntropyPool.KeyReserve,1);

end;



procedure TKeyGenerator.ForcedGetKey(var Key);

var TempSeed:Key256;

    TempBuffer:array[0..1]of Key256;

    RCtx:Rijndael_CTX;

    PCtx:Prng_CTX;

    HCtx:Haval_CTX;

    i,j:byte;

begin

   Move(EntropyPool.Seed,TempSeed,SizeOf(TempSeed));

   EntropyPool.PermuteSeed;

   RijndaelInit(@RCtx,EntropyPool.Seed);

   for i:=0 to KEY_BUILD_ROUNDS-1 do

   begin

      RijndaelEncrypt(@RCtx,TempSeed[0]);

      RijndaelEncrypt(@RCtx,TempSeed[4]);

      for j:=0 to SEED_SIZE-1 do

      begin

         PrngInit(@pctx,TempSeed[j]);

         TempBuffer[0,j]:=Prng(@PCtx);

         TempBuffer[1,j]:=Prng(@PCtx);

      end;

      HavalInit(@HCtx);

      HavalUpdate(@HCtx,TempBuffer,SizeOf(TempBuffer));

      HavalOutput(@HCtx,TempSeed);

   end;

   Move(TempSeed,Key,SizeOf(TempSeed));

   if EntropyPool.KeyReserve<0 then Dec(EntropyPool.KeyReserve,1);

end;



end.



(C)Copyright DrMungkee, 2001 (www.drmungkee.com, drmungkee@hotmail.com)

 

Share this article!

Follow us!

Find more helpful articles: