At 3:22 PM -0700 7/27/99, Jon Callas wrote:
>I built a PRNG that used an RC4 variant as John Kelsey said. The thing is
>also actually very Yarrow-like. I modified it later to use a state array
>512 long instead of 256 long, just so it would have a larger entropy pool.
>
>When I added more entropy, I added entropy using the same basic algorithm
>as RC4 key setup. The difference was that the S-array was not 0..256, but
>whatever the state of the array was. You simply *don't* use the input
>mechanism that Anonymous described.
>
>I'll also note that the state-loop that Anonymous described can easily be
>detected and corrected. Given that this is a PRNG, not a cipher,
>predictability is not a requirement (although you can algorithmically
>correct in a way that will still make it a cipher).
>
>Someday, I need to update the Entropy Manager (as I called it) and
>re-release it.
>
> Jon
I believe the input mechanism Anonymous described *is* the RC4 key setup
mechanism. In any case, I take Anonymous' remarks about the brittle nature
of RC4 very seriously. I wouldn't mess with it just to double the entropy
pool. If you think more entropy is needed, build a side buffer or run two
copies of RC4.
There is a lot to be said for using a known cryptographic object like RC4
to build other tools. It is very valuable to be able to translate any
imagined attack on the system your are proposing into an equivalant attack
on RC4. You then incorporate all past and future analysis of RC4 to your
system.
Anyway here is my latest nonce maker proposal, based on the thread so far
(in pseudocode):
private unsigned byte i, j, S[256]
mix(K) {
i = i + 1
j = j + S[i] + K
swap S[i] and S[j]
t = S[i] + S[j]
return S[t]
}
setup() {
i = j = 0
for m = 0 to 255 S[m] = m
for m = 1 to 256 mix(get_a_true_random_byte())
i = j = 0
for m = 1 to 256 mix(0)
}
deposit(string) {
prev = mix(0)
for m = 1 to length(string) prev = mix(string[m-1] xor prev)
i = j = 0
}
getnonce(length) {
bytestring nonce
deposit(current_time())
for m = 1 to length concatinate (nonce, mix(0))
return nonce
}
mix is equivalent to the RC4 setup loop. It is also the RC4 cipher loop if
K=0. The indicies i and j are reinitialized every time mix is run in setup
mode to keep out of the repeated state. All entropy deposits are
RC4-encoded to prevent any chosen-entropy attack.
You would call deposit at opportune times like key presses, mouse moves,
disk and network I/O. Because i and j are reset so often and because nonces
and deposits are likely to be short, the begining of the S arrray will get
more mixing than the rest of the array. Therefore, it might be desirable to
stir the S array throughly every so often, perhaps by calling mix(0)
repeatedly during idle time.
Arnold Reinhold
