Open Source Repository

Home /open-symphony/oscore-2.2.6 | Repository Home



com/opensymphony/module/random/Yarrow.java
/*
 * Copyright (c) 2002-2003 by OpenSymphony
 * All rights reserved.
 */
package com.opensymphony.module.random;


/* ====================================================================
 * The OpenSymphony Software License, Version 1.1
 *
 * (this license is derived and fully compatible with the Apache Software
 * License - see http://www.apache.org/LICENSE.txt)
 *
 * Copyright (c) 2001 The OpenSymphony Group. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        OpenSymphony Group (http://www.opensymphony.com/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "OpenSymphony" and "The OpenSymphony Group"
 *    must not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact [email protected] .
 *
 * 5. Products derived from this software may not be called "OpenSymphony"
 *    or "OSCore", nor may "OpenSymphony" or "OSCore" appear in their
 *    name, without prior written permission of the OpenSymphony Group.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 */
import java.io.*;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Properties;
import java.util.Random;


/**
 *
 * This class represents a Pseudo Random Number Generator (PRNG)
 * as specified by the Yarrow documentation (www.counterpane.com/yarrow)
 *
 * Most of the code in this class is based on FreeNet's Yarrow implementation.
 *
 @author Scott G. Miller <[email protected]>
 @author Victor Salaman <[email protected]>
 *
 */
public final class Yarrow extends Random {
    //~ Static fields/initializers /////////////////////////////////////////////

    private static final int Pt = 5;
    private static final int Pg = 10;
    private static String seedfile;
    private static final int FAST_THRESHOLD = 100;
    private static final int SLOW_THRESHOLD = 160;
    private static final int SLOW_K = 2;
    static final int[][] bitTable = {
        {00x0},
        {10x1},
        {10x3},
        {10x7},
        {10xf},
        {10x1f},
        {10x3f},
        {10x7f},
        {10xff},
        
        {20x1ff},
        {20x3ff},
        {20x7ff},
        {20xfff},
        {20x1fff},
        {20x3fff},
        {20x7fff},
        {20xffff},
        
        {30x1ffff},
        {30x3ffff},
        {30x7ffff},
        {30xfffff},
        {30x1fffff},
        {30x3fffff},
        {30x7fffff},
        {30xffffff},
        
        {40x1ffffff},
        {40x3ffffff},
        {40x7ffffff},
        {40xfffffff},
        {40x1fffffff},
        {40x3fffffff},
        {40x7fffffff},
        {40xffffffff}
    };

    static {
        try {
            File file = new File(new File(System.getProperty("java.io.tmpdir"))"prng.seed." + System.currentTimeMillis());
            seedfile = file.toString();
            file.deleteOnExit();
        catch (Throwable t) {
            seedfile = "prng.seed";
        }
    }

    //~ Instance fields ////////////////////////////////////////////////////////

    public byte[] ZERO_ARRAY = new byte[16384];
    private Hashtable entropySeen;
    private MessageDigest fast_pool;
    private MessageDigest reseed_ctx;
    private MessageDigest slow_pool;
    private Rijndael cipher_ctx;
    private byte[] allZeroString;
    private byte[] counter;
    private byte[] output_buffer;
    private byte[] tmp;
    private boolean fast_select;
    private int fast_entropy;
    private int fetch_counter;
    private int output_count;
    private int slow_entropy;

    //~ Constructors ///////////////////////////////////////////////////////////

    public Yarrow() {
        try {
            accumulator_init();
            reseed_init();
            generator_init();
            entropy_init(seedfile);
        catch (RuntimeException e) {
            throw e;
        catch (Exception e) {
            throw new RuntimeException(e.getMessage());
        }
    }

    //~ Methods ////////////////////////////////////////////////////////////////

    public void acceptEntropy(EntropySource source, long data, int entropyGuess) {
        accept_entropy(data, source, Math.min(32, Math.min(estimateEntropy(source, data), entropyGuess)));
    }

    public void acceptTimerEntropy(EntropySource timer) {
        long now = System.currentTimeMillis();
        acceptEntropy(timer, now - timer.lastVal, 32);
    }

    public void makeKey(byte[] entropy, byte[] key, int offset, int len) {
        try {
            MessageDigest ctx = MessageDigest.getInstance("SHA1");
            int ic = 0;

            while (len > 0) {
                ic++;

                for (int i = 0; i < ic; i++) {
                    ctx.update((byte0);
                }

                ctx.update(entropy, 0, entropy.length);

                int bc;

                if (len > 20) {
                    ctx.digest(key, offset, 20);
                    bc = 20;
                else {
                    byte[] hash = ctx.digest();
                    bc = Math.min(len, hash.length);
                    System.arraycopy(hash, 0, key, offset, bc);
                }

                offset += bc;
                len -= bc;
            }

            wipe(entropy);
        catch (Exception e) {
            throw new RuntimeException("Could not generate key: " + e.getMessage());
        }
    }

    public void wipe(byte[] data) {
        System.arraycopy(ZERO_ARRAY, 0, data, 0, data.length);
    }

    protected int next(int bits) {
        int[] parameters = bitTable[bits];
        int offset = getBytes(parameters[0]);

        int val = output_buffer[offset];

        if (parameters[0== 4) {
            val += (((intoutput_buffer[offset + 1<< 24((intoutput_buffer[offset + 2<< 16((intoutput_buffer[offset + 3<< 8));
        else if (parameters[0== 3) {
            val += (((intoutput_buffer[offset + 1<< 16((intoutput_buffer[offset + 2<< 8));
        else if (parameters[0== 2) {
            val += ((intoutput_buffer[offset + 2<< 8);
        }

        return val & parameters[1];
    }

    private synchronized int getBytes(int count) {
        if ((fetch_counter + count> output_buffer.length) {
            fetch_counter = 0;
            generateOutput();

            return getBytes(count);
        }

        int rv = fetch_counter;
        fetch_counter += count;

        return rv;
    }

    private void accept_entropy(long data, EntropySource source, int actualEntropy) {
        MessageDigest pool = (fast_select ? fast_pool : slow_pool);
        pool.update((bytedata);
        pool.update((byte) (data >> 8));
        pool.update((byte) (data >> 16));
        pool.update((byte) (data >> 24));
        pool.update((byte) (data >> 32));
        pool.update((byte) (data >> 40));
        pool.update((byte) (data >> 48));
        pool.update((byte) (data >> 56));

        fast_select = !fast_select;

        if (fast_select) {
            fast_entropy += actualEntropy;

            if (fast_entropy > FAST_THRESHOLD) {
                fast_pool_reseed();
            }
        else {
            slow_entropy += actualEntropy;

            if (source != null) {
                Integer contributedEntropy = (IntegerentropySeen.get(source);

                if (contributedEntropy == null) {
                    contributedEntropy = new Integer(actualEntropy);
                else {
                    contributedEntropy = new Integer(actualEntropy + contributedEntropy.intValue());
                }

                entropySeen.put(source, contributedEntropy);

                if (slow_entropy >= (SLOW_THRESHOLD * 2)) {
                    int kc = 0;

                    for (Enumeration e = entropySeen.keys();
                            e.hasMoreElements();) {
                        Object key = e.nextElement();
                        Integer v = (IntegerentropySeen.get(key);

                        if (v.intValue() > SLOW_THRESHOLD) {
                            kc++;

                            if (kc >= SLOW_K) {
                                slow_pool_reseed();

                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    private void accumulator_init() throws NoSuchAlgorithmException {
        fast_pool = MessageDigest.getInstance("SHA1");
        slow_pool = MessageDigest.getInstance("SHA1");
        entropySeen = new Hashtable();
    }

    private void consumeBytes(byte[] bytes) {
        if (fast_select) {
            fast_pool.update(bytes, 0, bytes.length);
        else {
            slow_pool.update(bytes, 0, bytes.length);
        }

        fast_select = !fast_select;
    }

    private void consumeString(String str) {
        if (str == null) {
            return;
        }

        byte[] b = str.getBytes();
        consumeBytes(b);
    }

    private void counterInc() {
        for (int i = counter.length - 1; i >= 0; i--) {
            if (++counter[i!= 0) {
                break;
            }
        }
    }

    private void entropy_init(String seed) {
        Properties sys = System.getProperties();
        EntropySource startupEntropy = new EntropySource();

        for (Enumeration e = sys.propertyNames(); e.hasMoreElements();) {
            String key = (Stringe.nextElement();
            consumeString(key);
            consumeString(sys.getProperty(key));
        }

        try {
            consumeString(java.net.InetAddress.getLocalHost().toString());
        catch (Exception e) {
        }

        acceptEntropy(startupEntropy, System.currentTimeMillis()0);
        read_seed(seed);
    }

    private int estimateEntropy(EntropySource source, long newVal) {
        int delta = (int) (newVal - source.lastVal);
        int delta2 = delta - source.lastDelta;
        source.lastDelta = delta;

        int delta3 = delta2 - source.lastDelta2;
        source.lastDelta2 = delta2;

        if (delta < 0) {
            delta = -delta;
        }

        if (delta2 < 0) {
            delta2 = -delta2;
        }

        if (delta3 < 0) {
            delta3 = -delta3;
        }

        if (delta > delta2) {
            delta = delta2;
        }

        if (delta > delta3) {
            delta = delta3;
        }

        delta >>= 1;
        delta &= ((<< 121);

        delta |= (delta >> 8);
        delta |= (delta >> 4);
        delta |= (delta >> 2);
        delta |= (delta >> 1);
        delta >>= 1;
        delta -= ((delta >> 10x555);
        delta = (delta & 0x333((delta >> 20x333);
        delta += (delta >> 4);
        delta += (delta >> 8);

        source.lastVal = newVal;

        return (intdelta & 15;
    }

    private void fast_pool_reseed() {
        byte[] v0 = fast_pool.digest();
        byte[] vi = v0;

        for (byte i = 0; i < Pt; i++) {
            reseed_ctx.update(vi, 0, vi.length);
            reseed_ctx.update(v0, 0, v0.length);
            reseed_ctx.update(i);
            vi = reseed_ctx.digest();
        }

        makeKey(vi, tmp, 0, tmp.length);
        rekey(tmp);
        wipe(v0);
        fast_entropy = 0;
        write_seed(seedfile);
    }

    private void generateOutput() {
        counterInc();
        output_buffer = cipher_ctx.encipher(counter);

        if (output_count++ > Pg) {
            output_count = 0;
            nextBytes(tmp);
            rekey(tmp);
        }
    }

    private void generator_init() {
        cipher_ctx = new Rijndael();
        output_buffer = new byte[cipher_ctx.getBlockSize() 8];
        counter = new byte[cipher_ctx.getBlockSize() 8];
        allZeroString = new byte[cipher_ctx.getBlockSize() 8];
        tmp = new byte[cipher_ctx.getKeySize() 8];
        fetch_counter = output_buffer.length;
    }

    private void read_seed(String filename) {
        EntropySource seedFile = new EntropySource();

        DataInputStream dis = null;

        try {
            dis = new DataInputStream(new FileInputStream(filename));

            for (int i = 0; i < 32; i++) {
                acceptEntropy(seedFile, dis.readLong()64);
            }
        catch (Exception f) {
            Random rand = new Random();

            for (int i = 0; i < 32; i++) {
                acceptEntropy(seedFile, rand.nextLong()64);
            }
        finally {
            if (dis != null) {
                try {
                    dis.close();
                catch (IOException e) {
                }
            }
        }

        fast_pool_reseed();
    }

    private void rekey(byte[] key) {
        cipher_ctx.initialize(key);
        counter = cipher_ctx.encipher(allZeroString);
        wipe(key);
    }

    private void reseed_init() throws NoSuchAlgorithmException {
        reseed_ctx = MessageDigest.getInstance("SHA1");
    }

    private void slow_pool_reseed() {
        byte[] slow_hash = slow_pool.digest();
        fast_pool.update(slow_hash, 0, slow_hash.length);
        fast_pool_reseed();
        slow_entropy = 0;

        Integer ZERO = new Integer(0);

        for (Enumeration e = entropySeen.keys(); e.hasMoreElements();) {
            entropySeen.put(e.nextElement(), ZERO);
        }
    }

    private void write_seed(String filename) {
        DataOutputStream dos = null;

        try {
            dos = new DataOutputStream(new FileOutputStream(filename));

            for (int i = 0; i < 32; i++) {
                dos.writeLong(nextLong());
            }

            ;
        catch (IOException ex) {
            System.out.println(getClass().getName() " error writing seed file to " + filename + ": " + ex);
        finally {
            if (dos != null) {
                try {
                    dos.close();
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    //~ Inner Classes //////////////////////////////////////////////////////////

    public static class EntropySource {
        public int lastDelta;
        public int lastDelta2;
        public long lastVal;
    }
}