includes/MWCryptRand.php

   1 <?php
   2 /**
   3  * A cryptographic random generator class used for generating secret keys
   4  *
   5  * This is based in part on Drupal code as well as what we used in our own code
   6  * prior to introduction of this class.
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with this program; if not, write to the Free Software Foundation, Inc.,
  20  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  21  * http://www.gnu.org/copyleft/gpl.html
  22  *
  23  * @author Daniel Friesen
  24  * @file
  25  */
  26
  27 class MWCryptRand {
  28
  29         /**
  30          * Minimum number of iterations we want to make in our drift calculations.
  31          */
  32         const MIN_ITERATIONS = 1000;
  33
  34         /**
  35          * Number of milliseconds we want to spend generating each separate byte
  36          * of the final generated bytes.
  37          * This is used in combination with the hash length to determine the duration
  38          * we should spend doing drift calculations.
  39          */
  40         const MSEC_PER_BYTE = 0.5;
  41
  42         /**
  43          * Singleton instance for public use
  44          */
  45         protected static $singleton = null;
  46
  47         /**
  48          * The hash algorithm being used
  49          */
  50         protected $algo = null;
  51
  52         /**
  53          * The number of bytes outputted by the hash algorithm
  54          */
  55         protected $hashLength = null;
  56
  57         /**
  58          * A boolean indicating whether the previous random generation was done using
  59          * cryptographically strong random number generator or not.
  60          */
  61         protected $strong = null;
  62
  63         /**
  64          * Initialize an initial random state based off of whatever we can find
  65          */
  66         protected function initialRandomState() {
  67                 // $_SERVER contains a variety of unstable user and system specific information
  68                 // It'll vary a little with each page, and vary even more with separate users
  69                 // It'll also vary slightly across different machines
  70                 $state = serialize( $_SERVER );
  71
  72                 // To try vary the system information of the state a bit more
  73                 // by including the system's hostname into the state
  74                 $state .= wfHostname();
  75
  76                 // Try to gather a little entropy from the different php rand sources
  77                 $state .= rand() . uniqid( mt_rand(), true );
  78
  79                 // Include some information about the filesystem's current state in the random state
  80                 $files = array();
  81
  82                 // We know this file is here so grab some info about ourselves
  83                 $files[] = __FILE__;
  84
  85                 // We must also have a parent folder, and with the usual file structure, a grandparent
  86                 $files[] = __DIR__;
  87                 $files[] = dirname( __DIR__ );
  88
  89                 // The config file is likely the most often edited file we know should be around
  90                 // so include its stat info into the state.
  91                 // The constant with its location will almost always be defined, as WebStart.php defines
  92                 // MW_CONFIG_FILE to $IP/LocalSettings.php unless being configured with MW_CONFIG_CALLBACK (eg. the installer)
  93                 if ( defined( 'MW_CONFIG_FILE' ) ) {
  94                         $files[] = MW_CONFIG_FILE;
  95                 }
  96
  97                 foreach ( $files as $file ) {
  98                         wfSuppressWarnings();
  99                         $stat = stat( $file );
 100                         wfRestoreWarnings();
 101                         if ( $stat ) {
 102                                 // stat() duplicates data into numeric and string keys so kill off all the numeric ones
 103                                 foreach ( $stat as $k => $v ) {
 104                                         if ( is_numeric( $k ) ) {
 105                                                 unset( $k );
 106                                         }
 107                                 }
 108                                 // The absolute filename itself will differ from install to install so don't leave it out
 109                                 if ( ( $path = realpath( $file ) ) !== false ) {
 110                                         $state .= $path;
 111                                 } else {
 112                                         $state .= $file;
 113                                 }
 114                                 $state .= implode( '', $stat );
 115                         } else {
 116                                 // The fact that the file isn't there is worth at least a
 117                                 // minuscule amount of entropy.
 118                                 $state .= '0';
 119                         }
 120                 }
 121
 122                 // Try and make this a little more unstable by including the varying process
 123                 // id of the php process we are running inside of if we are able to access it
 124                 if ( function_exists( 'getmypid' ) ) {
 125                         $state .= getmypid();
 126                 }
 127
 128                 // If available try to increase the instability of the data by throwing in
 129                 // the precise amount of memory that we happen to be using at the moment.
 130                 if ( function_exists( 'memory_get_usage' ) ) {
 131                         $state .= memory_get_usage( true );
 132                 }
 133
 134                 // It's mostly worthless but throw the wiki's id into the data for a little more variance
 135                 $state .= wfWikiID();
 136
 137                 // If we have a secret key or proxy key set then throw it into the state as well
 138                 global $wgSecretKey, $wgProxyKey;
 139                 if ( $wgSecretKey ) {
 140                         $state .= $wgSecretKey;
 141                 } elseif ( $wgProxyKey ) {
 142                         $state .= $wgProxyKey;
 143                 }
 144
 145                 return $state;
 146         }
 147
 148         /**
 149          * Randomly hash data while mixing in clock drift data for randomness
 150          *
 151          * @param string $data The data to randomly hash.
 152          * @return String The hashed bytes
 153          * @author Tim Starling
 154          */
 155         protected function driftHash( $data ) {
 156                 // Minimum number of iterations (to avoid slow operations causing the loop to gather little entropy)
 157                 $minIterations = self::MIN_ITERATIONS;
 158                 // Duration of time to spend doing calculations (in seconds)
 159                 $duration = ( self::MSEC_PER_BYTE / 1000 ) * $this->hashLength();
 160                 // Create a buffer to use to trigger memory operations
 161                 $bufLength = 10000000;
 162                 $buffer = str_repeat( ' ', $bufLength );
 163                 $bufPos = 0;
 164
 165                 // Iterate for $duration seconds or at least $minIterations number of iterations
 166                 $iterations = 0;
 167                 $startTime = microtime( true );
 168                 $currentTime = $startTime;
 169                 while ( $iterations < $minIterations || $currentTime - $startTime < $duration ) {
 170                         // Trigger some memory writing to trigger some bus activity
 171                         // This may create variance in the time between iterations
 172                         $bufPos = ( $bufPos + 13 ) % $bufLength;
 173                         $buffer[$bufPos] = ' ';
 174                         // Add the drift between this iteration and the last in as entropy
 175                         $nextTime = microtime( true );
 176                         $delta = (int)( ( $nextTime - $currentTime ) * 1000000 );
 177                         $data .= $delta;
 178                         // Every 100 iterations hash the data and entropy
 179                         if ( $iterations % 100 === 0 ) {
 180                                 $data = sha1( $data );
 181                         }
 182                         $currentTime = $nextTime;
 183                         $iterations++;
 184                 }
 185                 $timeTaken = $currentTime - $startTime;
 186                 $data = $this->hash( $data );
 187
 188                 wfDebug( __METHOD__ . ": Clock drift calculation " .
 189                         "(time-taken=" . ( $timeTaken * 1000 ) . "ms, " .
 190                         "iterations=$iterations, " .
 191                         "time-per-iteration=" . ( $timeTaken / $iterations * 1e6 ) . "us)\n" );
 192                 return $data;
 193         }
 194
 195         /**
 196          * Return a rolling random state initially build using data from unstable sources
 197          * @return string A new weak random state
 198          */
 199         protected function randomState() {
 200                 static $state = null;
 201                 if ( is_null( $state ) ) {
 202                         // Initialize the state with whatever unstable data we can find
 203                         // It's important that this data is hashed right afterwards to prevent
 204                         // it from being leaked into the output stream
 205                         $state = $this->hash( $this->initialRandomState() );
 206                 }
 207                 // Generate a new random state based on the initial random state or previous
 208                 // random state by combining it with clock drift
 209                 $state = $this->driftHash( $state );
 210                 return $state;
 211         }
 212
 213         /**
 214          * Decide on the best acceptable hash algorithm we have available for hash()
 215          * @throws MWException
 216          * @return String A hash algorithm
 217          */
 218         protected function hashAlgo() {
 219                 if ( !is_null( $this->algo ) ) {
 220                         return $this->algo;
 221                 }
 222
 223                 $algos = hash_algos();
 224                 $preference = array( 'whirlpool', 'sha256', 'sha1', 'md5' );
 225
 226                 foreach ( $preference as $algorithm ) {
 227                         if ( in_array( $algorithm, $algos ) ) {
 228                                 $this->algo = $algorithm;
 229                                 wfDebug( __METHOD__ . ": Using the {$this->algo} hash algorithm.\n" );
 230                                 return $this->algo;
 231                         }
 232                 }
 233
 234                 // We only reach here if no acceptable hash is found in the list, this should
 235                 // be a technical impossibility since most of php's hash list is fixed and
 236                 // some of the ones we list are available as their own native functions
 237                 // But since we already require at least 5.2 and hash() was default in
 238                 // 5.1.2 we don't bother falling back to methods like sha1 and md5.
 239                 throw new MWException( "Could not find an acceptable hashing function in hash_algos()" );
 240         }
 241
 242         /**
 243          * Return the byte-length output of the hash algorithm we are
 244          * using in self::hash and self::hmac.
 245          *
 246          * @return int Number of bytes the hash outputs
 247          */
 248         protected function hashLength() {
 249                 if ( is_null( $this->hashLength ) ) {
 250                         $this->hashLength = strlen( $this->hash( '' ) );
 251                 }
 252                 return $this->hashLength;
 253         }
 254
 255         /**
 256          * Generate an acceptably unstable one-way-hash of some text
 257          * making use of the best hash algorithm that we have available.
 258          *
 259          * @param $data string
 260          * @return String A raw hash of the data
 261          */
 262         protected function hash( $data ) {
 263                 return hash( $this->hashAlgo(), $data, true );
 264         }
 265
 266         /**
 267          * Generate an acceptably unstable one-way-hmac of some text
 268          * making use of the best hash algorithm that we have available.
 269          *
 270          * @param $data string
 271          * @param $key string
 272          * @return String A raw hash of the data
 273          */
 274         protected function hmac( $data, $key ) {
 275                 return hash_hmac( $this->hashAlgo(), $data, $key, true );
 276         }
 277
 278         /**
 279          * @see self::wasStrong()
 280          */
 281         public function realWasStrong() {
 282                 if ( is_null( $this->strong ) ) {
 283                         throw new MWException( __METHOD__ . ' called before generation of random data' );
 284                 }
 285                 return $this->strong;
 286         }
 287
 288         /**
 289          * @see self::generate()
 290          */
 291         public function realGenerate( $bytes, $forceStrong = false ) {
 292                 wfProfileIn( __METHOD__ );
 293
 294                 wfDebug( __METHOD__ . ": Generating cryptographic random bytes for " . wfGetAllCallers( 5 ) . "\n" );
 295
 296                 $bytes = floor( $bytes );
 297                 static $buffer = '';
 298                 if ( is_null( $this->strong ) ) {
 299                         // Set strength to false initially until we know what source data is coming from
 300                         $this->strong = true;
 301                 }
 302
 303                 if ( strlen( $buffer ) < $bytes ) {
 304                         // If available make use of mcrypt_create_iv URANDOM source to generate randomness
 305                         // On unix-like systems this reads from /dev/urandom but does it without any buffering
 306                         // and bypasses openbasedir restrictions, so it's preferable to reading directly
 307                         // On Windows starting in PHP 5.3.0 Windows' native CryptGenRandom is used to generate
 308                         // entropy so this is also preferable to just trying to read urandom because it may work
 309                         // on Windows systems as well.
 310                         if ( function_exists( 'mcrypt_create_iv' ) ) {
 311                                 wfProfileIn( __METHOD__ . '-mcrypt' );
 312                                 $rem = $bytes - strlen( $buffer );
 313                                 $iv = mcrypt_create_iv( $rem, MCRYPT_DEV_URANDOM );
 314                                 if ( $iv === false ) {
 315                                         wfDebug( __METHOD__ . ": mcrypt_create_iv returned false.\n" );
 316                                 } else {
 317                                         $buffer .= $iv;
 318                                         wfDebug( __METHOD__ . ": mcrypt_create_iv generated " . strlen( $iv ) . " bytes of randomness.\n" );
 319                                 }
 320                                 wfProfileOut( __METHOD__ . '-mcrypt' );
 321                         }
 322                 }
 323
 324                 if ( strlen( $buffer ) < $bytes ) {
 325                         // If available make use of openssl's random_pseudo_bytes method to attempt to generate randomness.
 326                         // However don't do this on Windows with PHP < 5.3.4 due to a bug:
 327                         // http://stackoverflow.com/questions/1940168/openssl-random-pseudo-bytes-is-slow-php
 328                         // http://git.php.net/?p=php-src.git;a=commitdiff;h=cd62a70863c261b07f6dadedad9464f7e213cad5
 329                         if ( function_exists( 'openssl_random_pseudo_bytes' )
 330                                 && ( !wfIsWindows() || version_compare( PHP_VERSION, '5.3.4', '>=' ) )
 331                         ) {
 332                                 wfProfileIn( __METHOD__ . '-openssl' );
 333                                 $rem = $bytes - strlen( $buffer );
 334                                 $openssl_bytes = openssl_random_pseudo_bytes( $rem, $openssl_strong );
 335                                 if ( $openssl_bytes === false ) {
 336                                         wfDebug( __METHOD__ . ": openssl_random_pseudo_bytes returned false.\n" );
 337                                 } else {
 338                                         $buffer .= $openssl_bytes;
 339                                         wfDebug( __METHOD__ . ": openssl_random_pseudo_bytes generated " . strlen( $openssl_bytes ) . " bytes of " . ( $openssl_strong ? "strong" : "weak" ) . " randomness.\n" );
 340                                 }
 341                                 if ( strlen( $buffer ) >= $bytes ) {
 342                                         // openssl tells us if the random source was strong, if some of our data was generated
 343                                         // using it use it's say on whether the randomness is strong
 344                                         $this->strong = !!$openssl_strong;
 345                                 }
 346                                 wfProfileOut( __METHOD__ . '-openssl' );
 347                         }
 348                 }
 349
 350                 // Only read from urandom if we can control the buffer size or were passed forceStrong
 351                 if ( strlen( $buffer ) < $bytes && ( function_exists( 'stream_set_read_buffer' ) || $forceStrong ) ) {
 352                         wfProfileIn( __METHOD__ . '-fopen-urandom' );
 353                         $rem = $bytes - strlen( $buffer );
 354                         if ( !function_exists( 'stream_set_read_buffer' ) && $forceStrong ) {
 355                                 wfDebug( __METHOD__ . ": Was forced to read from /dev/urandom without control over the buffer size.\n" );
 356                         }
 357                         // /dev/urandom is generally considered the best possible commonly
 358                         // available random source, and is available on most *nix systems.
 359                         wfSuppressWarnings();
 360                         $urandom = fopen( "/dev/urandom", "rb" );
 361                         wfRestoreWarnings();
 362
 363                         // Attempt to read all our random data from urandom
 364                         // php's fread always does buffered reads based on the stream's chunk_size
 365                         // so in reality it will usually read more than the amount of data we're
 366                         // asked for and not storing that risks depleting the system's random pool.
 367                         // If stream_set_read_buffer is available set the chunk_size to the amount
 368                         // of data we need. Otherwise read 8k, php's default chunk_size.
 369                         if ( $urandom ) {
 370                                 // php's default chunk_size is 8k
 371                                 $chunk_size = 1024 * 8;
 372                                 if ( function_exists( 'stream_set_read_buffer' ) ) {
 373                                         // If possible set the chunk_size to the amount of data we need
 374                                         stream_set_read_buffer( $urandom, $rem );
 375                                         $chunk_size = $rem;
 376                                 }
 377                                 $random_bytes = fread( $urandom, max( $chunk_size, $rem ) );
 378                                 $buffer .= $random_bytes;
 379                                 fclose( $urandom );
 380                                 wfDebug( __METHOD__ . ": /dev/urandom generated " . strlen( $random_bytes ) . " bytes of randomness.\n" );
 381                                 if ( strlen( $buffer ) >= $bytes ) {
 382                                         // urandom is always strong, set to true if all our data was generated using it
 383                                         $this->strong = true;
 384                                 }
 385                         } else {
 386                                 wfDebug( __METHOD__ . ": /dev/urandom could not be opened.\n" );
 387                         }
 388                         wfProfileOut( __METHOD__ . '-fopen-urandom' );
 389                 }
 390
 391                 // If we cannot use or generate enough data from a secure source
 392                 // use this loop to generate a good set of pseudo random data.
 393                 // This works by initializing a random state using a pile of unstable data
 394                 // and continually shoving it through a hash along with a variable salt.
 395                 // We hash the random state with more salt to avoid the state from leaking
 396                 // out and being used to predict the /randomness/ that follows.
 397                 if ( strlen( $buffer ) < $bytes ) {
 398                         wfDebug( __METHOD__ . ": Falling back to using a pseudo random state to generate randomness.\n" );
 399                 }
 400                 while ( strlen( $buffer ) < $bytes ) {
 401                         wfProfileIn( __METHOD__ . '-fallback' );
 402                         $buffer .= $this->hmac( $this->randomState(), mt_rand() );
 403                         // This code is never really cryptographically strong, if we use it
 404                         // at all, then set strong to false.
 405                         $this->strong = false;
 406                         wfProfileOut( __METHOD__ . '-fallback' );
 407                 }
 408
 409                 // Once the buffer has been filled up with enough random data to fulfill
 410                 // the request shift off enough data to handle the request and leave the
 411                 // unused portion left inside the buffer for the next request for random data
 412                 $generated = substr( $buffer, 0, $bytes );
 413                 $buffer = substr( $buffer, $bytes );
 414
 415                 wfDebug( __METHOD__ . ": " . strlen( $buffer ) . " bytes of randomness leftover in the buffer.\n" );
 416
 417                 wfProfileOut( __METHOD__ );
 418                 return $generated;
 419         }
 420
 421         /**
 422          * @see self::generateHex()
 423          */
 424         public function realGenerateHex( $chars, $forceStrong = false ) {
 425                 // hex strings are 2x the length of raw binary so we divide the length in half
 426                 // odd numbers will result in a .5 that leads the generate() being 1 character
 427                 // short, so we use ceil() to ensure that we always have enough bytes
 428                 $bytes = ceil( $chars / 2 );
 429                 // Generate the data and then convert it to a hex string
 430                 $hex = bin2hex( $this->generate( $bytes, $forceStrong ) );
 431                 // A bit of paranoia here, the caller asked for a specific length of string
 432                 // here, and it's possible (eg when given an odd number) that we may actually
 433                 // have at least 1 char more than they asked for. Just in case they made this
 434                 // call intending to insert it into a database that does truncation we don't
 435                 // want to give them too much and end up with their database and their live
 436                 // code having two different values because part of what we gave them is truncated
 437                 // hence, we strip out any run of characters longer than what we were asked for.
 438                 return substr( $hex, 0, $chars );
 439         }
 440
 441         /** Publicly exposed static methods **/
 442
 443         /**
 444          * Return a singleton instance of MWCryptRand
 445          * @return MWCryptRand
 446          */
 447         protected static function singleton() {
 448                 if ( is_null( self::$singleton ) ) {
 449                         self::$singleton = new self;
 450                 }
 451                 return self::$singleton;
 452         }
 453
 454         /**
 455          * Return a boolean indicating whether or not the source used for cryptographic
 456          * random bytes generation in the previously run generate* call
 457          * was cryptographically strong.
 458          *
 459          * @return bool Returns true if the source was strong, false if not.
 460          */
 461         public static function wasStrong() {
 462                 return self::singleton()->realWasStrong();
 463         }
 464
 465         /**
 466          * Generate a run of (ideally) cryptographically random data and return
 467          * it in raw binary form.
 468          * You can use MWCryptRand::wasStrong() if you wish to know if the source used
 469          * was cryptographically strong.
 470          *
 471          * @param int $bytes the number of bytes of random data to generate
 472          * @param bool $forceStrong Pass true if you want generate to prefer cryptographically
 473          *                          strong sources of entropy even if reading from them may steal
 474          *                          more entropy from the system than optimal.
 475          * @return String Raw binary random data
 476          */
 477         public static function generate( $bytes, $forceStrong = false ) {
 478                 return self::singleton()->realGenerate( $bytes, $forceStrong );
 479         }
 480
 481         /**
 482          * Generate a run of (ideally) cryptographically random data and return
 483          * it in hexadecimal string format.
 484          * You can use MWCryptRand::wasStrong() if you wish to know if the source used
 485          * was cryptographically strong.
 486          *
 487          * @param int $chars the number of hex chars of random data to generate
 488          * @param bool $forceStrong Pass true if you want generate to prefer cryptographically
 489          *                          strong sources of entropy even if reading from them may steal
 490          *                          more entropy from the system than optimal.
 491          * @return String Hexadecimal random data
 492          */
 493         public static function generateHex( $chars, $forceStrong = false ) {
 494                 return self::singleton()->realGenerateHex( $chars, $forceStrong );
 495         }
 496
 497 }