Proposal for a CSPRNG (aka Secure Random Number Generator)

Bill Frantz (frantz@communities.com)
Fri, 02 Oct 1998 12:15:40 -0700

• Next message: bram: "Re: Why GNU GPL is bad for crypto deployment"
• Previous message: Mok-Kong Shen: "Re: An Extension of My Encryption Algorithm WEAK3"

This generator is an example of a class of algorithms I have been
calling Continuously Seeded Pseudo Random Number Generators (CSPRNGs).
It is the result of the criticisms given to the last such design I
posted some months ago. It attempts to address all attacks described
in Kelsey, Schneier, Wagner, and Hall's paper, "Cryptanalytic Attacks
on Pseudorandom Number Generators". FSE '98, or <http://www.cs.berkeley.edu/~daw/prngs-fse98.ps>.

If no serious holes are poked in the design, it will replace the CSPRNG
in the E runtime library. (E is an open source environment for secure
distributed persistent computation. See <http://www.erights.org/>.

I would like to thank David Wagner for his comments during this
algorithm's development. He has been extremely patient and helpful.

The most important criticisms or the last generator (IMHO) were it's
failure to protect against State Compromise Extension Attacks, where
the attacker gains access to the internal state, and can use the output
of the generator to recover the entropy that has been added by guessing
the entropy input; and the use of MD5 with a counter to generate the
output.

Since one of the normal modes of operation for a CSPRNG is to save
entropy on a disk file, protection against state compromise extension
attacks is a high priority in my view. I think compromising a disk
file is a lot easier than reading some random piece of virtual memory.

The new generator uses Arc4 (aka RC4(tm)), a stream cypher by Ron
Rivest, as the output function. The basic outline is:

(1) The internal state of the PRNG is the Arc4 S box + the two
indexes I and J.

(2) Entropy seeding is buffered and mixed with a secure hash until
80 bits have been accumulated. Then it is used as an Arc4 key to
run the Arc4 key schedule. The principle difference between this
use and Arc4's use as a stream cypher is that the S boxes are not
returned to their initial state before running the key schedule.
Not reinitializing the S boxes allows the previous entropy to affect
the state.

(3) When entropy is to be saved to the disk, some number of bytes
(at least 20, but better some much larger number) are read out of
the generator with nextBytes() and written to the disk. The code
might look like:
   byte[] saved = new byte[256];
   generator.nextBytes(saved);
   //... write saved to the disk

(4) When restarting the generator, the bytes are read from the
disk and passed back as a seed. The estimated entropy of the
seed is set so the generator won't delay waiting for seeding.
E.g.
   generator.setSeed(saved, 160);

Since the relevant Java code is short, I'll just include it here (and
set the mailer not to linefold so it will still be readable).

------------------------------------------------
    /** The minimum entropy before the generator will run nextBytes() */
    private static final int MIN_ENTROPY = 160; //Bits

    //State
    
    /** The Arc4 S box structure */
       // Initialization sets myArc4SBox to the bytes 0 .. 255
    private transient byte[] myArc4SBox
            = new byte[256];
            
    /**The Arc4 value i */
    private transient int myArc4I = 0;
    
    /** The Arc4 value j */
    private transient int myArc4J = 0;
    
    /** Bits of entropy in the Arc4SBox */
    private int myAvailableEntropy = 0;
    
    /** First time switch to avoid Roos' weak key attack on the Arc4 cypher */
    private boolean myFirstTime = true;

    /** Entropy distilling function for setSeed() */
        // Initialization sets myMD to an instance of MD5, paranoids use SHA1
    private MessageDigest myMD = null;

    /** The amount of entropy in the buffer we keep before adding it to the
     * pool. This pool protects against the State Compromise Extension
     * Attack David Wagner identified as a weakness in the previous design.
     * See http://www.cs.berkeley.edu/~daw/prngs-fse98.ps */
    private int myBufferedEntropy = 0;
    
    /** The buffer we keep for entropy before adding it to the pool */
    private byte[] myEntropyBuffer = new byte[1];

------------------------------------------------
    /**
      * This method is the preferred way to provide entropy for later use. In
      * practical systems, any source of entropy available can be mixed in using
      * this method. Examples include: User interface events, disk I/O timings,
      * and random data from quantum-mechanically based hardware.
      *
      * @param seed the seed.
      * @param entropy an estimate of the amount of entropy in seed in bits.
      *
      * @exception IllegalArgumentException entropy estimate is less than 0 bits.
      * @exception IllegalArgumentException entropy estimate is greater than 8
      * bits for every byte of the seed.
      */

    public synchronized void setSeed(byte seed[], int entropy) {
        //... Input sanity check removed
        //Add the entropy we're about to buffer to the counter.
        myBufferedEntropy += entropy;

        while (true) {
            myMD.update(myEntropyBuffer);
            myMD.update(long2bytes(MicroTime.queryTimer())); // Stir in the time
            myEntropyBuffer = myMD.digest(seed);
        if (myBufferedEntropy < 80) break;

            // We have enough entropy to run the Arc5 key schedule
            myAvailableEntropy += 80;
            myBufferedEntropy -= 80;
            for (int i=0; i<256; i++) {
                int j = 0xff & (i
                                 + myArc4SBox[i]
                                 + myEntropyBuffer[i%myEntropyBuffer.length]);
                // Swap bytes a S[i] and S[j]
                byte s = myArc4SBox[i];
                myArc4SBox[i] = myArc4SBox[j];
                myArc4SBox[j] = s;
            }
        }

        if (myAvailableEntropy > 850) {//Arc4 can be in about 2**1700 states
            myAvailableEntropy = 850; //Never more than 1/2 full
        }
    }

------------------------------------------------
    /**
      * This method provides the secure random output.
      *
      * @param bytes the byte array which will receive the secure random output.
      */

    public void nextBytes(byte bytes[]) {
        if (myAvailableEntropy < MIN_ENTROPY) { // Need to gather entropy
            //... Code to wait until seeded removed
        }
        if (myFirstTime) {
            byte[] junk = new byte[256];
            runArc4(junk); // Suck of first bytes to avoid weak key attack
            myFirstTime = false;
        }
        runArc4(bytes);
    }

    /**
     * This routine is the Arc4 PRNG
     *
     * @param bytes is the byte array to receive the output.
     */
    private synchronized void runArc4(byte[] bytes) {
        for (int cursor=0; cursor < bytes.length; cursor++) {
            myArc4I = (myArc4I + 1) & 0xff;
            myArc4J = (myArc4J + myArc4SBox[myArc4I]) & 0xff;
            
            // Swap bytes a S[myArc4I] and S[myArc4J]
            byte s = myArc4SBox[myArc4I];
            myArc4SBox[myArc4I] = myArc4SBox[myArc4J];
            myArc4SBox[myArc4J] = s;
            
            bytes[cursor] = myArc4SBox[ (myArc4I+myArc4J) & 0xff ];
        }
    }

• Next message: bram: "Re: Why GNU GPL is bad for crypto deployment"
• Previous message: Mok-Kong Shen: "Re: An Extension of My Encryption Algorithm WEAK3"