Source for gnu.javax.crypto.prng.Fortuna

   1: /* Fortuna.java -- The Fortuna PRNG.
   2:    Copyright (C) 2004, 2006 Free Software Foundation, Inc.
   3: 
   4: This file is a part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2 of the License, or (at
   9: your option) any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; if not, write to the Free Software
  18: Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
  19: USA
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version.  */
  37: 
  38: 
  39: package gnu.javax.crypto.prng;
  40: 
  41: import gnu.java.security.Registry;
  42: import gnu.java.security.hash.HashFactory;
  43: import gnu.java.security.hash.IMessageDigest;
  44: import gnu.java.security.prng.BasePRNG;
  45: import gnu.java.security.prng.LimitReachedException;
  46: import gnu.java.security.prng.RandomEvent;
  47: import gnu.java.security.prng.RandomEventListener;
  48: import gnu.javax.crypto.cipher.CipherFactory;
  49: import gnu.javax.crypto.cipher.IBlockCipher;
  50: 
  51: import java.io.IOException;
  52: import java.io.ObjectInputStream;
  53: import java.io.ObjectOutputStream;
  54: import java.io.Serializable;
  55: import java.security.InvalidKeyException;
  56: import java.util.Arrays;
  57: import java.util.Collections;
  58: import java.util.Iterator;
  59: import java.util.Map;
  60: 
  61: /**
  62:  * The Fortuna continuously-seeded pseudo-random number generator. This
  63:  * generator is composed of two major pieces: the entropy accumulator and the
  64:  * generator function. The former takes in random bits and incorporates them
  65:  * into the generator's state. The latter takes this base entropy and generates
  66:  * pseudo-random bits from it.
  67:  * <p>
  68:  * There are some things users of this class <em>must</em> be aware of:
  69:  * <dl>
  70:  * <dt>Adding Random Data</dt>
  71:  * <dd>This class does not do any polling of random sources, but rather
  72:  * provides an interface for adding random events. Applications that use this
  73:  * code <em>must</em> provide this mechanism. We use this design because an
  74:  * application writer who knows the system he is targeting is in a better
  75:  * position to judge what random data is available.</dd>
  76:  * <dt>Storing the Seed</dt>
  77:  * <dd>This class implements {@link Serializable} in such a way that it writes
  78:  * a 64 byte seed to the stream, and reads it back again when being
  79:  * deserialized. This is the extent of seed file management, however, and those
  80:  * using this class are encouraged to think deeply about when, how often, and
  81:  * where to store the seed.</dd>
  82:  * </dl>
  83:  * <p>
  84:  * <b>References:</b>
  85:  * <ul>
  86:  * <li>Niels Ferguson and Bruce Schneier, <i>Practical Cryptography</i>, pp.
  87:  * 155--184. Wiley Publishing, Indianapolis. (2003 Niels Ferguson and Bruce
  88:  * Schneier). ISBN 0-471-22357-3.</li>
  89:  * </ul>
  90:  */
  91: public class Fortuna
  92:     extends BasePRNG
  93:     implements Serializable, RandomEventListener
  94: {
  95:   private static final long serialVersionUID = 0xFACADE;
  96:   private static final int SEED_FILE_SIZE = 64;
  97:   private static final int NUM_POOLS = 32;
  98:   private static final int MIN_POOL_SIZE = 64;
  99:   private final Generator generator;
 100:   private final IMessageDigest[] pools;
 101:   private long lastReseed;
 102:   private int pool;
 103:   private int pool0Count;
 104:   private int reseedCount;
 105:   public static final String SEED = "gnu.crypto.prng.fortuna.seed";
 106: 
 107:   public Fortuna()
 108:   {
 109:     super(Registry.FORTUNA_PRNG);
 110:     generator = new Generator(CipherFactory.getInstance(Registry.RIJNDAEL_CIPHER),
 111:                               HashFactory.getInstance(Registry.SHA256_HASH));
 112:     pools = new IMessageDigest[NUM_POOLS];
 113:     for (int i = 0; i < NUM_POOLS; i++)
 114:       pools[i] = HashFactory.getInstance(Registry.SHA256_HASH);
 115:     lastReseed = 0;
 116:     pool = 0;
 117:     pool0Count = 0;
 118:     buffer = new byte[256];
 119:   }
 120: 
 121:   public void setup(Map attributes)
 122:   {
 123:     lastReseed = 0;
 124:     reseedCount = 0;
 125:     pool = 0;
 126:     pool0Count = 0;
 127:     generator.init(attributes);
 128:     try
 129:       {
 130:         fillBlock();
 131:       }
 132:     catch (LimitReachedException shouldNotHappen)
 133:       {
 134:         throw new RuntimeException(shouldNotHappen);
 135:       }
 136:   }
 137: 
 138:   public void fillBlock() throws LimitReachedException
 139:   {
 140:     if (pool0Count >= MIN_POOL_SIZE
 141:         && System.currentTimeMillis() - lastReseed > 100)
 142:       {
 143:         reseedCount++;
 144:         byte[] seed = new byte[0];
 145:         for (int i = 0; i < NUM_POOLS; i++)
 146:           if (reseedCount % (1 << i) == 0)
 147:             generator.addRandomBytes(pools[i].digest());
 148:         lastReseed = System.currentTimeMillis();
 149:         pool0Count = 0;
 150:       }
 151:     generator.nextBytes(buffer);
 152:   }
 153: 
 154:   public void addRandomByte(byte b)
 155:   {
 156:     pools[pool].update(b);
 157:     if (pool == 0)
 158:       pool0Count++;
 159:     pool = (pool + 1) % NUM_POOLS;
 160:   }
 161: 
 162:   public void addRandomBytes(byte[] buf, int offset, int length)
 163:   {
 164:     pools[pool].update(buf, offset, length);
 165:     if (pool == 0)
 166:       pool0Count += length;
 167:     pool = (pool + 1) % NUM_POOLS;
 168:   }
 169: 
 170:   public void addRandomEvent(RandomEvent event)
 171:   {
 172:     if (event.getPoolNumber() < 0 || event.getPoolNumber() >= pools.length)
 173:       throw new IllegalArgumentException("pool number out of range: "
 174:                                          + event.getPoolNumber());
 175:     pools[event.getPoolNumber()].update(event.getSourceNumber());
 176:     pools[event.getPoolNumber()].update((byte) event.getData().length);
 177:     pools[event.getPoolNumber()].update(event.getData());
 178:     if (event.getPoolNumber() == 0)
 179:       pool0Count += event.getData().length;
 180:   }
 181: 
 182:   // Reading and writing this object is equivalent to storing and retrieving
 183:   // the seed.
 184: 
 185:   private void writeObject(ObjectOutputStream out) throws IOException
 186:   {
 187:     byte[] seed = new byte[SEED_FILE_SIZE];
 188:     try
 189:       {
 190:         generator.nextBytes(seed);
 191:       }
 192:     catch (LimitReachedException shouldNeverHappen)
 193:       {
 194:         throw new Error(shouldNeverHappen);
 195:       }
 196:     out.write(seed);
 197:   }
 198: 
 199:   private void readObject(ObjectInputStream in) throws IOException
 200:   {
 201:     byte[] seed = new byte[SEED_FILE_SIZE];
 202:     in.readFully(seed);
 203:     generator.addRandomBytes(seed);
 204:   }
 205: 
 206:   /**
 207:    * The Fortuna generator function. The generator is a PRNG in its own right;
 208:    * Fortuna itself is basically a wrapper around this generator that manages
 209:    * reseeding in a secure way.
 210:    */
 211:   public static class Generator
 212:       extends BasePRNG
 213:       implements Cloneable
 214:   {
 215:     private static final int LIMIT = 1 << 20;
 216:     private final IBlockCipher cipher;
 217:     private final IMessageDigest hash;
 218:     private final byte[] counter;
 219:     private final byte[] key;
 220:     private boolean seeded;
 221: 
 222:     public Generator(final IBlockCipher cipher, final IMessageDigest hash)
 223:     {
 224:       super(Registry.FORTUNA_GENERATOR_PRNG);
 225:       this.cipher = cipher;
 226:       this.hash = hash;
 227:       counter = new byte[cipher.defaultBlockSize()];
 228:       buffer = new byte[cipher.defaultBlockSize()];
 229:       int keysize = 0;
 230:       for (Iterator it = cipher.keySizes(); it.hasNext();)
 231:         {
 232:           int ks = ((Integer) it.next()).intValue();
 233:           if (ks > keysize)
 234:             keysize = ks;
 235:           if (keysize >= 32)
 236:             break;
 237:         }
 238:       key = new byte[keysize];
 239:     }
 240: 
 241:     public byte nextByte()
 242:     {
 243:       byte[] b = new byte[1];
 244:       nextBytes(b, 0, 1);
 245:       return b[0];
 246:     }
 247: 
 248:     public void nextBytes(byte[] out, int offset, int length)
 249:     {
 250:       if (! seeded)
 251:         throw new IllegalStateException("generator not seeded");
 252:       int count = 0;
 253:       do
 254:         {
 255:           int amount = Math.min(LIMIT, length - count);
 256:           try
 257:             {
 258:               super.nextBytes(out, offset + count, amount);
 259:             }
 260:           catch (LimitReachedException shouldNeverHappen)
 261:             {
 262:               throw new Error(shouldNeverHappen);
 263:             }
 264:           count += amount;
 265:           for (int i = 0; i < key.length; i += counter.length)
 266:             {
 267:               fillBlock();
 268:               int l = Math.min(key.length - i, cipher.currentBlockSize());
 269:               System.arraycopy(buffer, 0, key, i, l);
 270:             }
 271:           resetKey();
 272:         }
 273:       while (count < length);
 274:       fillBlock();
 275:       ndx = 0;
 276:     }
 277: 
 278:     public void addRandomByte(byte b)
 279:     {
 280:       addRandomBytes(new byte[] { b });
 281:     }
 282: 
 283:     public void addRandomBytes(byte[] seed, int offset, int length)
 284:     {
 285:       hash.update(key);
 286:       hash.update(seed, offset, length);
 287:       byte[] newkey = hash.digest();
 288:       System.arraycopy(newkey, 0, key, 0, Math.min(key.length, newkey.length));
 289:       resetKey();
 290:       incrementCounter();
 291:       seeded = true;
 292:     }
 293: 
 294:     public void fillBlock()
 295:     {
 296:       if (! seeded)
 297:         throw new IllegalStateException("generator not seeded");
 298:       cipher.encryptBlock(counter, 0, buffer, 0);
 299:       incrementCounter();
 300:     }
 301: 
 302:     public void setup(Map attributes)
 303:     {
 304:       seeded = false;
 305:       Arrays.fill(key, (byte) 0);
 306:       Arrays.fill(counter, (byte) 0);
 307:       byte[] seed = (byte[]) attributes.get(SEED);
 308:       if (seed != null)
 309:         addRandomBytes(seed);
 310:       fillBlock();
 311:     }
 312: 
 313:     /**
 314:      * Resets the cipher's key. This is done after every reseed, which combines
 315:      * the old key and the seed, and processes that throigh the hash function.
 316:      */
 317:     private void resetKey()
 318:     {
 319:       try
 320:         {
 321:           cipher.reset();
 322:           cipher.init(Collections.singletonMap(IBlockCipher.KEY_MATERIAL, key));
 323:         }
 324:       // We expect to never get an exception here.
 325:       catch (InvalidKeyException ike)
 326:         {
 327:           throw new Error(ike);
 328:         }
 329:       catch (IllegalArgumentException iae)
 330:         {
 331:           throw new Error(iae);
 332:         }
 333:     }
 334: 
 335:     /**
 336:      * Increment `counter' as a sixteen-byte little-endian unsigned integer by
 337:      * one.
 338:      */
 339:     private void incrementCounter()
 340:     {
 341:       for (int i = 0; i < counter.length; i++)
 342:         {
 343:           counter[i]++;
 344:           if (counter[i] != 0)
 345:             break;
 346:         }
 347:     }
 348:   }
 349: }