Cryptographic Random Numbers

Problem/Question/Abstract:

The time comes in many security related applications to generate random numbers. If done poorly, the entire application will be compromised (think netscape's CSS!). This article demonstrates a TRUE random number generator implemented in 3 layers.

Answer:

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:

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.
a latency calculator that gets 4bits of entropy from the high-resolution timer when called by the main app (this is used by calling   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. My 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.