git.ozlabs.org Git - ccan/blob - ccan/isaac/_info

   1 /**
   2  * isaac - A fast, high-quality pseudo-random number generator.
   3  *
   4  * ISAAC (Indirect, Shift, Accumulate, Add, and Count) is the most advanced of
   5  * a series of pseudo-random number generators designed by Robert J. Jenkins
   6  * Jr. in 1996: http://www.burtleburtle.net/bob/rand/isaac.html
   7  *
   8  * To quote:
   9  *   No efficient method is known for deducing their internal states.
  10  *   ISAAC requires an amortized 18.75 instructions to produce a 32-bit value.
  11  *   There are no cycles in ISAAC shorter than 2**40 values.
  12  *   The expected cycle length is 2**8295 values.
  13  *   ...
  14  *   ISAAC-64 generates a different sequence than ISAAC, but it uses the same
  15  *   principles.
  16  *   It uses 64-bit arithmetic.
  17  *   It generates a 64-bit result every 19 instructions.
  18  *   All cycles are at least 2**72 values, and the average cycle length is
  19  *    2**16583.
  20  *
  21  * An additional, important comment from Bob Jenkins in 2006:
  22  *
  23  *   Seeding a random number generator is essentially the same problem as
  24  *   encrypting the seed with a block cipher.
  25  *   ISAAC should be initialized with the encryption of the seed by some
  26  *   secure cipher.
  27  *   I've provided a seeding routine in my implementations, which nobody has
  28  *   broken so far, but I have less faith in that initialization routine than
  29  *   I have in ISAAC.
  30  *
  31  * A number of attacks on ISAAC have been published.
  32  *
  33  * [Pudo01] can recover the entire internal state and has expected running time
  34  * less than the square root of the number of states, or 2**4121 (4.67E+1240).
  35  *
  36  *   @MISC{Pudo01,
  37  *     author="Marina Pudovkina",
  38  *     title="A Known Plaintext Attack on the {ISAAC} Keystream Generator",
  39  *     howpublished="Cryptology ePrint Archive, Report 2001/049",
  40  *     year=2001,
  41  *     note="\url{http://eprint.iacr.org/2001/049}",
  42  *   }
  43  *
  44  * [Auma06] reveals a large set of weak states, consisting of those for which
  45  * the first value is repeated one or more times elsewhere in the state
  46  * vector.
  47  *
  48  *   @MISC{Auma06,
  49  *     author="Jean-Philippe Aumasson",
  50  *     title="On the Pseudo-Random Generator {ISAAC}",
  51  *     howpublished="Cryptology ePrint Archive, Report 2006/438",
  52  *     year=2006,
  53  *     note="\url{http://eprint.iacr.org/2006/438}",
  54  *   }
  55  *
  56  * These induce a bias in the output relative to the repeated value.
  57  *
  58  * The seed values used as input below are scrambled before being used, so any
  59  * duplicates in them do not imply duplicates in the resulting internal state,
  60  * however the chances of some duplicate existing elsewhere in a random state
  61  * are just over 255/2**32, or merely 1 in 16 million.
  62  *
  63  * Such states are, of course, much rarer in ISAAC-64.
  64  *
  65  * It is not clear if an attacker can tell from just the output if ISAAC is in
  66  * a weak state, or deduce the full internal state in any case except that
  67  * where all or almost all of the entries in the state vector are identical.
  68  *
  69  * Even if one does not trust the security of this PRNG (and, without a good
  70  * source of entropy to seed it, one should not), ISAAC is an excellent source
  71  * of high-quality random numbers for Monte Carlo simulations, etc.
  72  *
  73  * It is the fastest 32-bit generator among all of those that pass the
  74  * statistical tests in the recent survey
  75  * http://www.iro.umontreal.ca/~simardr/testu01/tu01.html, with the exception
  76  * of Marsa-LFIB4, and it is quite competitive on 64-bit archtectures.
  77  *
  78  * Unlike Marsa-LFIB4 (and all other LFib generators), there are no linear
  79  * dependencies between successive values, and unlike many generators found in
  80  * libc implementations, there are no small periods in the least significant
  81  * bits, or seeds which lead to very small periods in general.
  82  *
  83  * Example:
  84  *  #include <stdio.h>
  85  *  #include <time.h>
  86  *  #include <ccan/isaac/isaac.h>
  87  *
  88  *  int main(void){
  89  *    static const char *CHEESE[3]={"Cheddar","Provolone","Camembert"};
  90  *    isaac_ctx     isaac;
  91  *    unsigned char seed[8];
  92  *    time_t        now;
  93  *    int           i;
  94  *    //N.B.: time() is not a good source of entropy.
  95  *    //Do not use it for cryptogrpahic purposes.
  96  *    time(&now);
  97  *    //Print it out so we can reproduce problems if needed.
  98  *    printf("Seed: 0x%016llX\n",(long long)now);
  99  *    //And convert the time to a byte array so that we can reproduce the same
 100  *    // seed on platforms with different endianesses.
 101  *    for(i=0;i<8;i++){
 102  *      seed[i]=(unsigned char)(now&0xFF);
 103  *      now>>=8;
 104  *    }
 105  *    isaac_init(&isaac,seed,8);
 106  *    printf("0x%08lX\n",(long)isaac_next_uint32(&isaac));
 107  *    printf("%s\n",CHEESE[isaac_next_uint(&isaac,3)]);
 108  *    printf("%0.8G\n",isaac_next_float(&isaac));
 109  *    printf("%0.8G\n",isaac_next_signed_float(&isaac));
 110  *    printf("%0.18G\n",isaac_next_double(&isaac));
 111  *    printf("%0.18G\n",isaac_next_signed_double(&isaac));
 112  *    return 0;
 113  *  }
 114  *
 115  * License: CC0 (Public domain)
 116  * Ccanlint:
 117  *      // We actually depend on the LGPL ilog routines, so not PD :(
 118  *      license_depends_compat FAIL
 119  */
 120 #include "config.h"
 121 #include <string.h>
 122 #include <stdio.h>
 123
 124 int main(int _argc,const char *_argv[]){
 125   /*Expect exactly one argument.*/
 126   if(_argc!=2)return 1;
 127   if(strcmp(_argv[1],"depends")==0){
 128     printf("ccan/ilog\n");
 129     return 0;
 130   }
 131   return 1;
 132 }