[cryptography] random extractor hobby algorithm

Krisztián Pintér pinterkr at gmail.com
Thu Mar 14 13:30:57 EDT 2013


dear list,

if you want to send me to hell, please first read the disclaimers on the bottom please. now let's just dive in.

i propose an algorithm for smoothing a weak random stream of bytes.

it is a combined-cycle rc4, that is, we continually feed the rc4 with the random input stream as "password", and at the same time we extract whitened stream on the output. the pseudocode would be, courtesy of wikipedia:
 
loop
    i := (i + 1) mod 256
    j := (j + S[i] + R) mod 256   // note the + R here
    swap values of S[i] and S[j]
    output S[(S[i] + S[j]) mod 256]
end loop

where R would be the next byte of the input stream. we input one byte per cycle, and discard the output until we collect enough entropy. assumed the input stream has an average entropy of x bits per byte, we feed 8/x bytes before we extract one byte of output. it is necessary to discard the first chunk of the output.

benefits:

1. white. the output satisfies every requirement we have for a random stream.
2. we don't lose entropy, we can extract as much as the input grants us on average.
3. no wait. you can add randomness as it arrives, you can extract as few as one byte.
4. robust. even if the input entropy drops, the output is unpredictable and smooth
5. avalanche effect. single bit change in the input changes the output entirely.
6. easy tuning of input/output ratio, even allows for below one ratios
7. blazing fast, small footprint and easy implementation
8. pools. it stores 1700 bit entropy in its belly.

problems:
1. can be run backwards if the internal state is compromised and the input entropy dropped severly below the estimated
2. ?

do you see any security problems with it?



DISCLAIMER:

yes, i'm aware that the problem is already solved in a number of reliable ways. yes, i'm aware that wise man does not use algorithms in cryptography that are not analyzed throughly by many experts. this idea came to me as part of my hobby project. this will not be implemented in any secure systems, nor any nonsecure systems for that matter, just a hobby project. i'm curious what more knowledgable minds can tell about this algorithm, mainly for educational purposes.





More information about the cryptography mailing list