Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

There are some pseudo-random-number generators in PHP: rand(), srand(), mt_rand(), mt_srand(). You can look at their code here.

I understand those functions are insecure, but how insecure are they?

For example, if those functions are used for generation of anti-CSRF tokens, tokens in file download links how easy will it be for attacker to guess those of other user? How he can do it?

Update: The paper I Forgot Your Password: Randomness Attacks Against PHP Applications seems to be a canonical reading on the subject and contains detailed response to this question. However, it's quiet long and complicated so I'd want to see a more short excerpt that will point or show existence of exploit algorithm using which those functions can be broken.

share|improve this question
2  
4  
@Polynomial Not a duplicate. D.W. specifically said in comments that that question is too broad and more specific questions should be asked about other functions. I ask about weaknesses in those exact functions. –  Andrey Botalov Aug 2 '12 at 10:11
    
Fair enough. I'll provide an answer. –  Polynomial Aug 2 '12 at 10:13
    
If you want more details on the attacks, I updated my answer with additional links that explain some of these attacks. But do understand that some of the attacks do involve some mathematics. That's just how it goes, sometimes. –  D.W. Aug 3 '12 at 18:04
    
"I want to see a more short excerpt that will point or show existence of exploit algorithm using which those functions can be broken" - The references already show a working attack algorithm, but it's not something you can fit in a fortune cookie. Sometimes attacks are complicated; that's just the way it is. (By the way, given the number of independent sources that state that these PRNGs are broken and insecure, and explain why, I think it would be wise to believe them.) –  D.W. Aug 3 '12 at 18:44

3 Answers 3

PHP's rand() generator is a based on the system implementation, which is usually a weak LCG or LFSR (see Andrey's comment below). For more info on why these types of generators are bad, take a look at How insecure are non-cryptographic random number generators?

The mt_rand() function uses Mersenne Twister, which isn't much better. You can determine the internal state and all future values after observing just 624 values.

Don't use either in any situation where you require cryptographic-strength randomness, including CSRF / password-equivilent tokens. A better alternative is the openssl_random_pseudo_bytes function, or reading from /dev/urandom. You could also look into implementing Blum Blum Shub, which is a strong (albeit slow) PRNG.

share|improve this answer
1  
PHP's rand() uses internal system implementation. At Linux it's LFSR, not LCG. See section 5.4 in this paper for more details –  Andrey Botalov Aug 2 '12 at 12:02
    
Whoops, I misunderstood then. I'll update. –  Polynomial Aug 2 '12 at 12:03
    
Bruteforce attack that you outlined in your answer to linked question will be impractical because of state of glibc is 31 word of 32 bits each. Again, see section 5.4 in this paper –  Andrey Botalov Aug 2 '12 at 12:27
    
@AndreyBotalov The bruteforce attack was only meant to be feasible for RNGs whose state is entirely determined from an initial seed. If an LFSR draws entropy from other sources, the bruteforce will be impossible. –  Polynomial Aug 2 '12 at 12:31
1  
Don't use Blum-Blum-Shub. It is totally irrelevant here. Recommending Blum-Blum-Shub is like recommending that the person use Diffie-Hellman: it doesn't solve the problem, and is misleading. –  D.W. Aug 3 '12 at 16:57

Those are all insecure. None of them are suitable for use in a CSRF token, or any other application requiring cryptographic strength. If you want more details why you should not use these methods, see the following resources:

As Polynomial suggests, you should instead use /dev/urandom or openssl_random_pseudo_bytes().

See also Better Random Numbers in PHP using /dev/urandom.

share|improve this answer

All of the PRNGs you listed are insecure. Anything dealing with security (sessions, tokens, secrets) requires a CSPRNG. Here are a list of suitable alternatives:

  • mcrypt_create_iv() - Uses /dev/urandom on *NIX and the built-in crypto platform on Windows. Requires the 'mcrypt' extension.
  • /dev/urandom - Requires a *NIX host.
  • openssl_random_pseudo_bytes() - Requires the 'openssl' extension.
  • http://barebonescms.com/documentation/csprng/ - A cross-platform solution that uses whatever is available plus a number of trusted remote web hosts that generate true random data.

As to your question regarding the paper, whatever algorithm you might come up with to generate a random string has probably been done before and the source code is likely available somewhere. If a PRNG is seeded with the current system clock in microsecond resolution, the search space is drastically reduced requiring only a few hundred thousand attempts. Combine that with maybe a few hundred common algorithms and you're looking at potentially mere seconds of CPU to reverse-engineer a token and synchronize with a remote system clock. After that, the application's security is hosed.

I guess the question is, will anyone care to hack your website at that level? Finding a SQL injection opportunity is generally a much easier route than trying to reverse-engineer a token scheme. Low-hanging fruit is more desirable to a hacker.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.