| |
|
Using
ARC4 for a random number generator
|
|
|
|
Implementation using ARC4
ARC4 works well as a stream cipher for a random number generator
for a number of reasons. First, it's a stream cipher that works with
8-bits at a time. This is nice because we can retrieve arbitrary lengths
of data with no extra steps. Secondly, ARC4 is quite small and fast.
This is nice because any program using the random number system won't suffer
a large size increases or performance loss by using the generator.
ARC4 has one added benefit as well, which will be discussed below.
First, let us look at the design of ARC4.
The heart of the ARC4 algorithm is a strong random number generator in which
the key is the seed value. For encryption, the random data generated
by the algorithm is XORed with the plaintext to produce the encrypted text.
The state of ARC4 consists of an array of 256 8-bit values and two 8-bit
indexes.
State : array[
0..255
] of
byte;
x :
byte;
y :
byte;
ARC4's key scheduling is laid out like this:
Loop
256 times
Set
State[ LoopCount ] to LoopCount
Set
x to 0
Set
y to 0
Loop
256 times the
following
y = y + Key[ KeyIndex
] + State[ x ] modules 256
Swap( State[ x ]
, State[ y ] )
KeyIndex = KeyIndex
+ 1 modules
KeyLength
x = x + 1
modules 256
Reset
x to 0
Reset
y to 0
The cipher works on a block of data like this:
Loop
for number of bytes to cipher
x = x + 1
modules 256
y = y + State[ x
] modules 256
Swap( State[ x ]
, State[ y ] )
XOR_Byte = State[
State[ x ] + State[ y ] modules 256 ]
OutputData[ LoopCount
] = InputData[ LoopCount ] xor XOR_Byte
We can quickly convert ARC4 into just random number generator by simply
using 'XOR_Byte' instead of XORing with anything. The loop
above would then turn into this:
Loop
for number of bytes to retrieve
x = x + 1
modules 256
y = y + State[ x
] modules 256
Swap( State[ x ]
, State[ y ] )
OutputData[ LoopCount
] = State[ State[ x ] + State[ y ] modules 256
]
Now look at the key scheduler and the stream generator and
note the relationship of 'x', 'y' and 'State' in these two processes.
'x' is continually counting up and is used as an index info 'State' when
modifying 'y'. The state at index 'x' and index 'y' and then swapped.
In both scheduling and generation, 'y' is modified by adding 'State[ x
]'. The difference is, during scheduling, the key is also added to 'y'.
We could merge the processes of these two functions by making
a new function we'll call 'ClockARC4'. It will look like
this:
x = x + 1
modules 256
y = y + KeyByte + State[ x ]
modules 256
Swap( State[ x ] , State[ y
] )
Now, the key scheduling becomes this:
Loop
256 times
Set
State[ LoopCount ] to LoopCount
Set
x to 255
Set
y to 0
Loop
256 times the
following
y = y + Key[ KeyIndex
] + State[ x ] modules 256
Swap( State[ x ]
, State[ y ] )
KeyIndex = KeyIndex
+ 1 modules
KeyLength
x = x + 1
modules 256
Reset
x to 0
Reset
y to 0
Note that 'x' is set to 255 instead of 0. This is because
in the key scheduling, 'x' is incremented at the end of the loop rather
than at the beginning. To address this, we set 'x' to 255 so that
after being incremented, 'x' becomes 0-- thus working with incrementing
'x' at the beginning of the loop rather than the end.
The random stream generation now becomes this:
Loop
for number of bytes to retrieve
ClockARC4( 0
)
OutputData[ LoopCount
] = State[ State[ x ] + State[ y ] modules 256
]
See now that we call 'ClockARC4' with 0, because
we are not modifying the state with any external data. We could
actually place any static number in this parameter and not effect the
strength of the algorithm-- but we would effect output. Doing this
would nether add nor subtract from the strength of the generator.
Now the relationship between the key scheduling and stream
generation is clear. We can see the difference is that we add external
data to the 'y' index during key scheduling. What's useful about
this relationship is that we can continue to clock in external data while
also getting stream data. When used as a cipher, this isn't too
useful because you must modify the state in exactly the same way as in
manner to create the XOR stream used to decipher the data. Since
this can all be done when the algorithm starts, why bother?
However, when trying to generate random data, the ability
to clock in external data is useful. The random number generator
is initialized by running the key scheduler with real-world random data
as the key, we're essentially just calling 'ClockARC4' with the
real-world random data. If we acquire more real-world random data,
we can immediately apply it to state by clocking it in, thus effecting
the future output of the algorithm.
With this we can see how measuring the key delay as a source
for random data can be applied when the data becomes available.
The key delay function then would become:
function GetChar
: char;
var RandomData
: byte;
begin
{ Measure
time until key is pressed }
RandomData
:= 0;
while not KeyPressed
do
Inc(
RandomData );
{ Pass
random data to generator }
ClockARC4(
RandomData );
{ Return
key that was pressed }
GetChar
:= ReadKey;
end;
In the Cypher libraries, the process described above is performed in
in the unit 'RandUnit.Pas'
|
