OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Using RC4 as a randomness pool
From: Niels Möller (nisselysator.liu.se)
Date: Mon Oct 23 2000 - 10:23:40 CDT

Is there anything obviously wrong with using rc4 (aka arcfour) as a
randomness pool? It's a lot simpler than most other pools I've seen
described.

To me, a randomness pool is an object supporting two operations:

1. Extraction of n bytes of (pseudo) random data, where n varies.

2. Stirring in n bytes of random data extracted from the environment
   into the pool (also varying n).

These operations can be performed in any order (although there are some
requirements on the seeding of the pool, more below).

I want a single "one-size-fits-all" pool, used for all randomness I
need, random padding, iv:s, session keys, etc. So extraction, also of
small amounts of data, has to be reasonably efficient. I don't want to
do any heavy processing of the state each time I need I 3 bytes of
random padding.

For an rc4-based pool, the internal state is a permutation S[0x100], of 0, 1, ...,
0xff, and two eight-bit counters i and j.

Extracting a singel byte OUT (operation 1) is done by

  i = (i + 1) % 0x100;
  j = (j + S[i]) % 0x100
  SWAP(S[i], S(j]);
  out = (S[i] + S[j]) % 0x100

Stirring a single byte IN into the pool (operation 2) is done by

  i = (i + 1) % 0x100;
  j = (j + S[i] + in) % 0x100
  SWAP(S[i], S(j]);

So far, this is very simple, the amount of internal state seems
reasonable, and rc4 is designed not to leak useful information to an
attacker observing its output.

The pool has to be seeded properly; for initial seeding, it seems
reasonable to use the usual rc4 keysetup (which makes sure that all
bytes of the state are affected). When the generator is used, data
should not be stirred into the pool a byte at a time, but one should
have a staging-area which is poured into the pool when the staging
area is believed to contain at least some 80 bits of entropy.

It seems reasonable to do the initial seeding using a key that is the
sha1-hash of a "slow-poll" (using Peter Gutmanns termonology), and
filling the staging area by hashing the outputs of successive
slow-polls and stir the digest into the pool when the estimate of the
entropy in the staging area is above some threshold.

One potential problem with this design is that if the contents of the
pool is captured in any way, all output since the previous reseed
until the next reseed is revealed (this is because the mixing used
when generating the output is reversible). However, the window is
bounded by the reseeds, assuming that the input to the reseed contains
enough entropy, and that the way the key is mixed into the pool
protects the key.

So I'm not sure this is a real problem, for two reasons:

* If an attacker can get temporary access to the internal pool state,
  he can most likely observe all randomness generated during that
  period directly.

* It seems inevitable that knowledge of the pool reveals some window
  of output (all output until the next reseed). Shifting this window a
  little into the past doesn't seem like a big deal.

(BTW, I've read Peter Gutmanns usenix paper, although I found it a
little difficult to understand all the details of that pool. I have
tried to read his recently updated version of that paper, but I have
been unable to find any copy that I could print out without errors).

Best regards,
/Niels