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.

Question: Is there a way to detect the use of a PRNG strictly from observing the output provided by an application?

Background: During an audit of a key generating algorithm that I knew was based on the LCG I noticed that Burp's sequencer rated the entropy of the keys as strong, which is false as they are predictable. I then fed the same test with raw integers generated by Python's Mersenne Twister based random module to see entropy rated as high again.

The failure of this tool got me to wonder wether there are tools/approaches available for actually detecting PRNG use from output.

share|improve this question

1 Answer 1

up vote 8 down vote accepted

If the PRNG is cryptographically strong, then, by definition, its output cannot be distinguished from random bytes. That's the thought experiment by which a PRNG is supposed to be tested: two black boxes are given to the attacker, one implementing the PRNG, the other producing really random bytes (that one contains a gnome who throws dice real quick). The attacker goals is to find which box contains the PRNG, with a better success rate than pure luck (i.e. 50%).

PRNG which are NOT cryptographically strong, such as Mersenne Twister, can be recognized as such by an attacker targeting them specifically. But not necessarily by a generic statistical analysis tool.

To take an analogy, there are PRNG which are strong against armies of cryptographers who know the complete source code of the PRNG, and have access to a thousand big computers. There also are PRNG which can be declared non-random by a woodchuck wielding an abacus. And there are PRNG which are in between: generic simple tools won't catch them, but it does not mean that they can't be caught, only that it takes some more effort.

(Mathematically, it is not known whether cryptographically strong PRNG can really exist -- this is all the difference between an algorithm that cannot be broken, and an algorithm that we do not know how to break. A corollary is that we do not know whether there can exist an implementable analysis tool which would reliably recognize all non-strong PRNG. Right now, we have PRNG which are cryptographically weak, but statistically very good, so that analysis tools such as Burp's sequencer will find nothing non-random in them.)

share|improve this answer
    
"woodchuck wielding an abacus"... pure gold. –  Terry Chia Jan 9 '13 at 3:19
    
Lost it at the gnome. –  0x90 Jan 9 '13 at 6:15

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.