1

I use PHP to write a software that generates random combinations of characters. For this I need arbitrary length integers random generation. So I use GMP extension and especially gmp_random_range(). But I need to prove with a link for example that it is cryptographically secure. Or at least it is enough random.

GMP random functions use seed (gmp_random_seed ), and if I don't set a seed everything looks random enough. So, I suppose when I don't set the seed explicitly it takes it from some reliable random source. I could not find something clearly stating such thing.

Peter O.
  • 32,158
  • 14
  • 82
  • 96
lameretc
  • 13
  • 2
  • 1
    No, gmp has no intention of being cryptographically secure. Use [random_int](https://www.php.net/manual/en/function.random-int.php) or [random_bytes](https://www.php.net/manual/en/function.random-bytes.php), for instance. In general, unless something is explicitly documented to be suitable for cryptographic use it isn't. – Peter May 30 '19 at 11:43
  • Also, being able to seed an RNG is almost always a sign of not being cryptographically secure. CSPRNGs are usually seeded automatically from a good source provided by the OS. – Peter May 30 '19 at 11:47

1 Answers1

1

As shown in "Random State Initialization", in the GMP documentation, the only random generator algorithms included in GMP are—

  • A Mersenne Twister algorithm,
  • linear congruential generators of various sizes, and
  • a "default algorithm" for "applications with no special requirements", including security requirements.

Curiously, the GMP documentation says in "Random State Seeding" that the "method for choosing a seed is critical if the generated numbers are to be used for important applications, such as generating cryptographic keys", even though none of the algorithms included in GMP are appropriate for cryptographic use.

As it appears, you can use random_bytes or random_int in PHP to generate cryptographic random numbers. The only thing left is to transform the numbers they deliver into arbitrary-precision numbers.* In that sense, GMP appears not to allow custom RNGs (besides the ones it provides) for the gmp_random_range and similar functions. Thus, you will have to transform those random numbers "manually", with the help of GMP's arithmetic functions. I have an article that discusses how to transform random numbers into a variety of distributions. To generate uniform random integers in a given range, the algorithm you need is called RNDINT or RNDINTEXC in that article.

* Where information security is involved, using random numbers as the seed for a noncryptographic RNG is not appropriate since an attacker, given enough random numbers, can then work backwards to derive the seed, even if the seed was generated in a cryptographically secure way.

If your goal is merely to generate a cryptographically random string of characters, you don't even need to go the GMP route. Just build the string one character at a time by calling random_int for each character you want to generate:

  • Build a list of characters allowed to appear in the random string.
  • For each character in the string, call random_int with a max of the list's size (a size which will almost certainly be within the range of integers PHP can handle), then append the character found at the given random index in the list (starting at 0).
Peter O.
  • 32,158
  • 14
  • 82
  • 96
  • Thank you very much for your answer. I will accept it although I don't mind others to comment this topic too. I wanted to comment more, but I am limited to 600 characters. I will include the last part. To generalize it: as an author of my software I should be able to answer the question whether the generated combinations are cryptographically secure. What I could say for now is: "No, they aren't. But the randomization is good (may be)". Excuse me if I said some stupid things here. (And I didn't mention - I use PHP 7.2 on Linux) – lameretc May 31 '19 at 10:07
  • Sorry for continuing to coment but have an idea how to use gmp_random_range in CS way. I can seed the GMP RNG with output from random_bytes, which is CS for sure. I just have to calculate how many bytes to ask. This depends on the number of numbers I need from gmp_random_range. I already got some formula, it uses logarithm and PHP GMP doesn't have such function but I found some solutions about this in SO. I think to seed before every use so every result to be completely random. I plan to begin implementation the next week. For now it's just an idea. – lameretc Jun 01 '19 at 12:54
  • The danger in using noncryptographic RNGs is that an attacker, given enough random numbers, can work backwards to derive the seed, even if the seed was generated in a cryptographically secure way. For your purposes, especially if you're implementing a security-sensitive algorithm, you might be better off using the numbers given by `random_bytes` or `random_int` directly, rather than using them to seed a noncryptographic RNG such as found in GMP. – Peter O. Jun 01 '19 at 15:26
  • Thank you! But what I meant is to use different seed for every call of gmp_random_range. So I would use random_bytes for randomness and the gmp function for its range usefulness (and of course no int type limitations). I mean - one seed - one number. An attacker would not have enough numbers, I think. One is the maximum. – lameretc Jun 03 '19 at 09:55
  • In that sense, are you aware that PHP's `random_int` _already_ generates cryptographic random numbers within a given range of integers? Also, I have an [article](https://peteroupc.github.io/randomfunc.html) that discusses how to transform random numbers into a variety of distributions. – Peter O. Jun 03 '19 at 12:38
  • Of course I know about random_int. I have to say a little about what I am doing. I perceive combinations of symbols as numbers in a bijective number system with a different base. When I have the char set, the num of symbols required, I can determine the min and max values and after that take a random number between them. All're very big-so GMP. I wrote my own class which has methods for str<->num (GMP). For that moment I don't get how to use random_int to produce a GMP number in a GMP range. If you tell me that this is what you have in mind - I will have to dig in your article deeply enough. – lameretc Jun 04 '19 at 15:26
  • Finally I implemented gmp random number generation using random_bytes and my version of [this](https://stackoverflow.com/questions/1846202/php-how-to-generate-a-random-unique-alphanumeric-string/13733588#13733588) . – lameretc Jun 14 '19 at 08:08