OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Re: Using RC4 as a randomness pool
From: nnburk (nnburkdtgnet.com)
Date: Mon Oct 23 2000 - 14:09:32 CDT

You might want to look at what Jon Callas did in this regard. See:
http://www.merrymeet.com/jon/usingrandom.html or e-mail: mailto:Jon
Callas <joncallas.org>

N

"Niels Möller" wrote:
>
> 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