PHP: rfc:improve_predictable_prng_random

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== PHP RFC: Improve predictable PRNG random and RNG API======
  * Version: 0.9
  * Date: 2017-02-01
  * Author: Yasuo Ohgaki <yohgaki@ohgaki.net>
  * Status: Under Discussion
  * First Published at: http://wiki.php.net/rfc/improve_predictable_prng_random


===== Introduction =====
Current predictable PRNG, i.e. mt_rand() and rand(), produces very weak random values even produces non random values. 

==== Non random value ====

<code php>
// We need the same random numbers here
srand(1234); 
for ($i=0; $i < 10; $i++) {
   // Use my PRNG state
   $my_rand[] = rand(); 
}

// Somewhere later in code AND/OR even other requests

// We need somewhat random numbers for non CS purpose
for ($i=0; $i < 10; $i++) {
   // following mt_rand() is NOT RANDOM at all
   $my_other_rand[] = mt_rand(); 
}
</code>

**Above code worked as it should. PHP 7.1 broke this code.** Similarly, shuffle()/etc are broken by PHP 7.1.

<code php>
// We need the same random numbers here
mt_srand(1234); 
for ($i=0; $i < 10; $i++) {
   // Use my PRNG state
   $my_rand[] = mt_rand(); 
}

// Somewhere later in code AND/OR even other requests

// We need to shuffle randomly
shuffle($my_random_array); // This is NOT RANDOM at all
</code>

**These behaviors are not limited to specific request that calls mt_srand($some_value)/srand($some_value), but applies to consecutive requests.**

PHP should have system and user PRNG state to resolve this behavior.

==== Weak seeding = Weak random ====

MT rand has 2^19937−1 cycle. This makes MT rand much stronger than older predictable PRNG. However, PHP initializes MT rand by 32 bit int value for both system and user seed, thus only 2^32 initial states. As a result, PHP's MT rand cannot not use more than 99% of MT rand cycle. This behavior is extremely weaker than MT rand could be.

To resolve this issue, PHP should initialize MT rand with more seed value and have API allows large seed value.


==== Rack of Reseeding ====

Reseeding is important for PRNG to mitigate guessed random value. Since MT rand is predictable PRNG, using the same PRNG state allows to guess next random value easily. Current PHP only supports very weak initialization and keeps using the same PRNG state once it is initialized. This behavior makes trivial to guess  MT rand generated random numbers.

To resolve this issue, PHP should reseed MT rand when state is used certain number of times.

===== Proposal =====

==== Return PRNG random object (RandomMT) from mt_srand()/srand() ====

<code php>
  RandomMT mt_srand([int|string $seed]);
  RandomMT srand([int|string $seed]);
</code>

mt_srand()/srand() returns RandomeMT object, that implements RandomInterface, is used with PRNG functions. Unless PRNG state object is specified, functions that use MT rand uses internal system PRNG state. When $seed is string, all bits are used for PRNG state initialization upto MT rand state buffer max. Internal PRNG state uses php_random_bytes() and randomize state.

Note: srand() is alias of mt_rand(). Python initializes MT rand state by string data like this proposal.

Example
<code php>
  $state = mt_srand(random_bytes(2000));
  $rand = mt_rand($state); // User PRNG state is used
  
  $rand = mt_rand(); // System PRNG state is used
</code>

==== Add optional PRNG object parameter for functions ====

<code php>
  int mt_rand([RandomMT $seed_object])
  int mt_rand(int $min, int $max [, RandomMT $seed_object])
  int rand([Random $seed_object])
  int rand(int $min, int $max [, Random $seed_object])
  bool shuffle(array &$arr [, Random $seed_object]);
</code>

When user initialized PRNG state object is specified, specified state is used to generate random values.

==== Random object and function ====

Create RandomeInterface, then implement RNG specific Random objects.

<code php>

interface RandomInterface {
    public function getInt(int $min = NULL, int $max = NULL); // Int random
    public function getBytes(int $length); // Raw bytes
    public function getString(int $length, int $bits = 6); // String [0-9a-zA-Z,-]+
    public function seed($seed = NULL); // No use with CS RNG, raise exception.
    public function getState(); // Return string representation PRNG state. No use with CS RNG, raise exception.
    public function setState(string $state); // Set PRNG state. No use with CS RNG, raise exception.
    public function getCount(); // No use with CS RNG, raise exception.
    public function getReseedCycle(); // No use with CS RNG, raise exception.
    public function setReseedCycle(int $count); // No use with CS RNG, raise exception.
}

class RandamCS implements RandomIterface {
   // random_*() functions OO API
   // Description omitted, see RandomMT
}

// Implement True RNG which may block process when TRNG abstraction function is implemented 
class RandamTRNG implements RandomIterface {
   // Description omitted, see RandomMT
}

class RandomMT implements RandomInterface {
    private int $count = 0; // Number of this state is used to generate random value
    private int $reseed = 100; // Max number of count to reseed automatically
    private string $state; // Binary PRNG state
    
    public function __construct($seed = NULL) {
      $this->seed($seed);
    }

    private reseed() {
      $this->count++;
      if ($this->reseed && !($this->count % $this->reseed)) {
        $this->seed();
        $this->count = 1;
      }
    }
    
    public function getInt($min = NULL, $max = NULL) {
      assert($min <= $max);
      $this->reseed();
      if ($min && $max) {
        return mt_rand($min, $max);
      }
      if ($min && $min > 0) {
        // Return array of random values
        while ($min--) {
          $ret[] = mt_rand();
        }
        return $ret;
      }
      trigger_error('Invalid params');
      return FALSE;
    }
    
    public function getBytes(int $length) {
      // Return raw random bytes. 3 out of 4 bytes are used not to disclose full PRNG state
    }
    
    public function getString(int $length, int $bits) {
      // Return random string as in bin_to_readable() in ext/session.c
      // Only 4 to 6 bits out of a byte is used to avoid disclosing raw PRNG state and simplicity.
    }    
    
    public function seed($seed = NULL) {
      // This method code is pseudo code. New mt_srand() will return new state object for user.
      // C written code updates $this->state instead.
      if ($seed) {
        // Update state by user seed
        mt_srand($seed);
        $this->reseed = 0;
      } else {
        // Seed by system generated random value
        mt_srand(random_bytes(2500));
      }
      return TRUE;
    }
    
    public function getCount() {
      return $this->count;
    }
    
    // Set/Get reseed cycle
    public function getReseedCycle() {
      return $this->reseed;
   }

    // Set reseed cycle
    public function setReseedCycle(int $count) {
      if (!is_int($count)) {
        return FALSE;
      }
      $this->reseed = $count;
      return TRUE;
   }
}
</code>

Random object has getBytes() and getString(). Implement function also.

<code php>
string mt_rand_bytes(int $length [, RandomMT $rand])
string mt_rand_string(int $length [, RandomMT $rand])
string rand_bytes(int $length [, Random $rand] ) // Alias of mt_rand_raw() now, but signature differs from MT rand to allow better PRNG in the future.
string rand_string(int $length [,int $bits [, Random $rand]]) // Alias of mt_rand_string()
string random_string(int $length [,int $bits])
</code>

==== Add automatic reseeding for system PRNG state ====

Add BG(mt_rand_reseed) global default to 100.

<code php>
   ini_set('mt_rand_reseed', 10); // Change system reseed cycle to 10
   ini_get('mt_rand_reseed'); // Get system reseed cycle
</code>

uint32_t BG(mt_rand_is_seeded) is used for already seeded flag and counter. MSB is used for seeded flag, the rest bits are used for counters. Therefore, max reseed count is 2^31.


===== Backward Incompatible Changes =====

Basically, none if user wants random values.
mt_srand()/srand() returned nothing previously.

If users want static random values, they have to use Random object to get certain random sequence. i.e. Call mt_srand()/srand() for Random object, then use it with functions, rand()/mt_rand()/shuffle()/etc. Use of mt_srand()/srand() would be rare in general.

===== Proposed PHP Version(s) =====

Next PHP 7.x

===== RFC Impact =====
==== To SAPIs ====
None.

==== To Existing Extensions ====
Modules uses MT rand RPNG.

==== To Opcache ====
None.

==== New Constants ====
None.

==== php.ini Defaults ====

New
  * mt_rand_reseed = 100 for compiled/php.ini-*.


===== Open Issues =====

Research internal MT rand usage and adjust them.

===== Unaffected PHP Functionality =====

Patch uses CSPRNG, php_random_bytes(), which could raise exception in case of CSPRNG failure. However, raised exception is not a matter that PHP should took care of.

  - php_random_bytes() abstracts access to CSPRNG. PHP cannot compile without CSPRNG now.
  - modern/usable system should provide CSPRNG as system service. 
  - CSPRNG is system service and error is very unlikely unless serious hardware and/or OS error.
  - CSPRNG access error is system error that PHP should not try to recover or workaround. 

CSPRNG exception should be raised when it is necessary, but it is not a real BC issue. 

===== Future Scope =====

Add Random objects as it required

===== Proposed Voting Choices =====


===== Patches and Tests =====

TBD

===== Implementation =====
After the project is implemented, this section should contain 
  - the version(s) it was merged to
  - a link to the git commit(s)
  - a link to the PHP manual entry for the feature
  - a link to the language specification section (if any)

===== References =====
Links to external references, discussions or RFCs

===== Rejected Features =====
Keep this updated with features that were discussed on the mail lists.
Page Tools
