Title: Cryptographic Random Numbers
Question: 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:
//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 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.
http://www.eccentrix.com/computer/drmungkee/NSCrypt.txt
(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-LastTimeInterval then
begin
if (xmouse.cursorpos.x)and(ymouse.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.KeyReserveend;
end.
(C)Copyright DrMungkee, 2001 (www.drmungkee.com, drmungkee@hotmail.com)