PHP Seeded, Deterministic, Cryptographically Secure PRNG (PseudoRandom Number Generator). Is it possible?
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)?
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;
output = AES-ECB(key, 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 n
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?
$prng = new \ParagonIE\SeedSpring\SeedSpring('JuxJ1XLnBKk7gPAS');
$byte = $prng->getBytes(16);
This should always return:
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.)
Asked in February 2016Viewed 3,322 timesVoted 8Answered 2 times