PHP Seeded, Deterministic, Cryptographically Secure PRNG (PseudoRandom Number Generator). Is it possible?

Question

I'm required to create a provably-fair (deterministic & seeded) cryptographically secure (CS) random number generator in PHP. We are running PHP 5 and PHP 7 isn't really an option right now. However, I found a polyfill for PHP 7's new CS functions so I've implemented that solution (https://github.com/paragonie/random_compat).

I thought that srand() could be used to seed random_int(), but now I'm not certain if that is the case. Can a CSPRNG even be seeded? If it can be seeded, will the output be deterministic (same random result, given same seed)?

Here is my code:

require_once($_SERVER['DOCUMENT_ROOT']."/lib/assets/random_compat/lib/random.php");

$seed_a = 8138707157292429635;
$seed_b = 'JuxJ1XLnBKk7gPASR80hJfq5Ey8QWEIc8Bt';

class CSPRNG{
    private static $RNGseed = 0;

    public function generate_seed_a(){
        return random_int(0, PHP_INT_MAX);
    }

    public function generate_seed_b($length = 35){
        $characters = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
        $randomString = '';
        for($i = 0; $i < $length; $i++){
            $randomString .= $characters[random_int(0, strlen($characters) - 1)];
        }
        return $randomString;
    }

    public function seed($s = 0) {
        if($s == 0){
            $this->RNGseed = $this->generate_seed_a();
        }else{
            $this->RNGseed = $s;
        }
        srand($this->RNGseed);
    }

    public function generate_random_integer($min=0, $max=PHP_INT_MAX, $pad_zeros = true){
        if($this->RNGseed == 0){
            $this->seed();
        }
        $rnd_num = random_int($min, $max);
        if($pad_zeros == true){
            $num_digits = strlen((string)$max);
            $format_str = "%0".$num_digits."d";
            return sprintf($format_str, $rnd_num);
        }else{
            return $rnd_num;
        }
    }

    public function drawing_numbers($seed_a, $num_of_balls = 6){
        $this->seed($seed_a);
        $draw_numbers = array();
        for($i = 0; $i < $num_of_balls; $i++) {
            $number = ($this->generate_random_integer(1, 49));
            if(in_array($number, $draw_numbers)){
                $i = $i-1;
            }else{
                array_push($draw_numbers, $number);
            }
        }
        sort($draw_numbers);
        return $draw_numbers;
    }
}

$CSPRNG= new CSPRNG();

echo '<p>Seed A: '.$seed_a.'</p>';
echo '<p>Seed B: '.$seed_b.'</p>';
$hash = hash('sha1', $seed_a.$seed_b);
echo '<p>Hash: '.$hash.'</p>';

$drawNumbers = $CSPRNG->drawing_numbers($seed_a);
$draw_str = implode("-", $drawNumbers);
echo "<br>Drawing: $draw_str<br>";

When this code is run, the Drawing ($draw_str) should be the same on each run, but it is not.

To prove that the drawing is fair, a seed (Seed A) is chosen before the winning number is picked and shown. Another random number is generated as well (Seed B). Seed B is used as a salt and combined with Seed A and the result is hashed. This hash is shown to the user prior to the drawing. They would also be provided with the source code so that when the winning number is picked, both seeds are revealed. They can verify that the hash matches and everything was done fairly.

Answer 1

Duskwuff asks:

How do you intend to prove that the seed was chosen fairly? A suspicious user can easily claim that you picked a seed that would result in a favorable outcome for specific users, or that you revealed the seed to specific users ahead of time.

Before you investigate solutions, what exactly is the problem you are trying to solve? What is your threat model?

---

It sounds like you want SeedSpring (version 0.3.0 supports PHP 5.6).

$prng = new \ParagonIE\SeedSpring\SeedSpring('JuxJ1XLnBKk7gPAS');
$byte = $prng->getBytes(16);
\var_dump(bin2hex($byte));

This should always return:

string(32) "76482c186f7c5d1cb3f895e044e3c649"

The numbers should be unbiased, but since it's based off a pre-shared seed, it is not, by strict definition, cryptographically secure.

Keep in mind that SeedSpring was created as a toy implementation/proof of concept rather than an official Paragon Initiative Enterprises open source security solution, so feel free to fork it and tweak it to suit your purposes. (I doubt our branch will ever reach a "stable 1.0.0 release").

(Also, if you're going to accept/award the bounty to any of these answers, Aaron Toponce's answer is more correct. Encrypting the nonce with ECB mode is more performant than encrypting a long stream of NUL bytes with AES-CTR, for approximately the same security benefit. This is one of the extremely rare occasions that ECB mode is okay.)

Answer 2

First, you shouldn't be implementing your own userspace CSPRNG. The operating system you have PHP 5 installed on already ships a CSPRNG, and you should be using that for all your randomness, unless you know you can use it, or performance is a concern. You should be using random_int(), random_bytes(), or openssl_random_pseudo_bytes().

However, if you must implement a userspace CSPRNG, then this can be done by simply using an AES library (E.G.: libsodium), and encrypting a counter. Psuedocode would be:

Uint-128 n = 0;
while true:
    output = AES-ECB(key, n);
    n++;

They AES key, in this case, needs sufficient entropy to withstand a sophisticated attack, or the security of your userspace CSPRNG falls apart, of course. The key could be the bcrypt() of a user-supplied password.

Provided your counter represented as a 128-bit unsigned integer is always unique, you will always get a unique output every time the generator is "seeded" with a new counter. If it's seeded with a previously used counter, but a different key, then the output will also be different. The best case scenario, would be a changing key and a changing counter every time the generator is called.

You may be tempted to use high precision timestamp, such as using microsecond accuracy, in your counter. This is fine, except you run the risk of someone or something manipulating the system clock. As such, if the clock can be manipulated, then the CSPRNG generator can be compromised. You're best off providing a new key every time you call the generator, and start encrypting with a 128-bit zero.

Also, notice that we're using ECB mode with AES. Don't freak out. ECB has problems with maintaining structure in the ciphertext that the plaintext provides. In general terms, you should not use ECB mode. However, with 128-bits of data, you will only be encrypting a single ECB block, so there will be no leak of structured data. ECB is preferred over CTR for a userspace CSPRNG, as you don't have to keep track of a key, a counter object, and the data to be encrypted. Only a key and the data are needed. Just make sure you are never encrypting more than 128-bits of data, and you'll never need more than 1 block.

Can a CSPRNG even be seeded?

Yes, and it should always be seeded. If you look at your GNU/Linux operating system, you'll likely notice a file in /var/lib/urandom/random-seed. When the operating system shuts down, it creates that file from the CSPRNG. On next boot, this file is used to seed the kernelspace CSPRNG to prevent reusing previous state of the generator. On every shutdown, that file should change.

If it can be seeded, will the output be deterministic (same random result, given same seed)?

Yes. Provided the same seed, key, etc., the output is deterministic, so the output will be the same. If one of your variables changes, then the output will be different. This is why on each call of the generator should be rekeyed.