Consequences of Incorrect Random Number Generation

My earlier post discussed a few interesting examples of security flaws in the NIST Juliet 1.1 suite for Java.  Analysis of their test cases for CWE 330, Use of Insufficiently Random Values, provides additional food for thought.  The HP Fortify taxonomy identifies these issues as as Insecure Randomness.  Static analysis results in this category are reported as low priority, however some mistakes in random number generation can lead to more dangerous exploits and should not be dismissed.  Random numbers are used in cryptography to generate public-private key pairs, initial vectors for block ciphers, and in Diffie-Hellman key exchange. Outside of crypto, randomness is used in generating temporary passwords, user and session IDs, creating CAPTCHAs, and filenames for uploaded/temporary files.  A poor implementation of a generator can result in DNS spoofing and DoS attacks.

 

A pseudo-random number generator (PRNG) is an algorithm that starts with an initial state, called the seed, and produces an output sequence of integers that may appear to be truly random but are in fact predictable.  Such a generator must cycle eventually back to the initial state of the seed, and the length of a cycle is called the period.  A PRNG looks random to humans, but the values are predictable if the inputs are known.
 

        // Example 1, declare and initialize PRNG

        java.util.Random r = new java.util.Random();

        // insecure: integer literal

        r.setSeed(123L);

 

        // Example 2, integer t is from a taint source

        String s = request.getParameter("webinput");

        long t = Long.parseLong(s);

        // insecure: attacker might know the generated values of r

        r.setSeed(t);

 

Using a fixed or tainted integer to initialize a PRNG will result in generation of predictable values.  The reason is that the program typically generates values, usually of integral type, with a sequence of calls to

 

        int n = r.nextInt();      // also nextLong(), etc

 

or fills a byte array:

 

        // fill b[] at random

        byte[] b = new byte[8];

        r.nextBytes(b);

 

Once the seed is assigned to a PRNG, the values produced are predictable; this is a known limitation of the PRNG inside java.util.Random.  The following code samples represent other subtle kinds of vulnerabilities.

 

        // PRNG case 1, Initialize Random more than once with the same seed

        java.util.Random r = new Random();

        final long s = 123L;

        r.setSeed(s);

        // ... and later in the program

        r.setSeed(s);

 

        // PRNG case 2, Initialize different Random objects with the same seed

        r1.setSeed(s);

        // ... and anywhere else in the program

        r2.setSeed(s);

 

In the first case, r generates the same data twice, and in the second, r1 and r2 generate the same data.  Both cases are examples of poor initialization.  The right way to initialize a PRNG is by the timeclock using Random.setSeed(System.nanoTime()).  Even when called more than once, this leads to a proper sequence of pseudo-random numbers as it should.  It's risky to depart from established libraries, but if you must extend java.util.Random to your own class ExtendedRandom and override setSeed() on your own, ensure that the following three properties hold.

 

        (1) ExtendedRandom.setSeed(long s) must generate the same sequence when seeded twice with the same seed.
        (2) ExtendedRandom.setSeed(long s) must generate different sequences for different seeds.
        (3) The PRNG must not have a short cycle.

 

If property (1) is not met, the PRNG may fail statistical tests for randomness that PRNGs are generally designed to meet.   If property (2) is not met, then a specific random sequence can be generated from two different starting points, which is obviously a security flaw.

 

Properties (1) and (2) are fairly easy to test, but checking property (3) requires identifying common sequences, a topic which lies outside our scope.  I myself have tested PRNGs in development which lacked each property.  One PRNG in particular lacked all of them, and cycled with period under a hundred thousand – far too short.  If property (3) is not met, then the PRNG is flawed, which leads to the kinds of vulnerabilities mentioned earlier: key pair generation with repeats, easily-guessed initial vectors, repeated use of filenames, duplicate temporary passwords, and so on.

Leave a Comment

We encourage you to share your comments on this post. Comments are moderated and will be reviewed
and posted as promptly as possible during regular business hours

To ensure your comment is published, be sure to follow the Community Guidelines.

Be sure to enter a unique name. You can't reuse a name that's already in use.
Be sure to enter a unique email address. You can't reuse an email address that's already in use.
Type the characters you see in the picture above.Type the words you hear.
Search
About the Author


Follow Us
The opinions expressed above are the personal opinions of the authors, not of HP. By using this site, you accept the Terms of Use and Rules of Participation