Predicting Struts CSRF Token (CVE-2014-7809)

A week has passed since the official release of Struts 2.3.20. I would like to now explain how CSRF tokens could be "easily" predicted by taking advantage of the vulnerability S2-023.

This article will be all about practical exploitation of a LCG pseudo random generator. Buckle up for code review, some math analysis and tons of hex fun!

True random number generator in action [Image Credit]

Diving in code review

The class 'TokenHelper' is use to generate CSRF token in the web framework Struts 2. The security of those tokens is crucial. It is expected that those would be immune to brute force attempt and to prediction. Take a minute to review the following class and maybe you will also find the vulnerability.

TokenHelper.java (Struts 2.3.17)

import java.math.BigInteger;
import java.util.Map;
import java.util.Random;
[...]

public class TokenHelper {

    /**
     * The default namespace for storing token session values
     */
    public static final String TOKEN_NAMESPACE = "struts.tokens";

    /**
     * The default name to map the token value
     */
    public static final String DEFAULT_TOKEN_NAME = "token";

    /**
     * The name of the field which will hold the token name
     */
    public static final String TOKEN_NAME_FIELD = "struts.token.name";
    private static final Logger LOG = LoggerFactory.getLogger(TokenHelper.class);
    private static final Random RANDOM = new Random();

[...]

    /**
     * Sets a transaction token into the session based on the provided token name.
     *
     * @param tokenName the token name based on which a generated token value is stored into session; for actual session
     *                  store, this name will be prefixed by a namespace.
     *
     * @return the token string
     */
    public static String setToken( String tokenName ) {
        String token = generateGUID();
        setSessionToken(tokenName, token);
        return token;
    }

[...]

    public static String generateGUID() {
        return new BigInteger(165, RANDOM).toString(36).toUpperCase();
    }

}

Got it ? Or giving up ? .. You can now pass to the next section.

Identifying the weak point

In order to be able to analyse the previous code, two classes need to be introduce.

java.security.SecureRandom

SecureRandom is a random generator that is recognized to be "cryptographically" secure. Its implementation will depend on the system hosting the JVM. With sufficient entropy, the values generated should be unpredictable. It is also important to note that each value generated is not base on the previous value or sequential.

java.util.Random

Random is a Linear Congruential Generator (LCG). What does it means? The generator is based on the evolving state of a value that is multiply by a huge number and reduce to its less significant bits (Those operations will be explain later). It is important to understand that the goal of such generator is mainly efficiency and uniform bit distribution.

Let's focus on the generation of the GUID (method generateGUID from the previous sample).

TokenHelper.java (Struts 2.3.17)

private static final Random RANDOM = new Random();

public static String generateGUID() {
    return new BigInteger(165, RANDOM).toString(36).toUpperCase();
}

The seed and random state

First, at the line 1, the Random class use a implicit seed that is the timestamp in nanoseconds of the time where this class is loaded (System.nanoTime()). This could be predict if the attacker have some insight about the load time of the Random class.

The weakest point is simply the usage of the java.util.Random instead of java.security.SecureRandom. The random values are generated based on a LCG which is not design to unpredictable. That's it! We have a vulnerability.

Vulnerable in theory, but is it exploitable?

Theory is one thing. Can we realistically predict tokens by collecting multiple tokens (or maybe just one)? To exploit this vulnerability we will have to dig into the implementation of the class Random. What happen when a number is generated...

java.util.Random

There are few details we need to know to attack the random generator.

Generator lifecycle

Life cycle of a Linear Congruential Generator (LCG)

1. The seed is multiply with a constant value (mutiplier).
2. An constant value (addend) is added to the previous result.
3. A mask of 48 bits is then applied to the previous result (less significant).
4. A mask of 32 bits is then applied to the previous result (most significant) but will not affect the seed for the next value.

The exact implementation of java.util.Random number generation is:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

What's next() ?

The previous algorithm describe the generation int (32 bits). What about long (64 bits) and byte array (multiple of 8 bits)? The two types are build upon the generation of one or multiple ints.

Byte order for the various nextX() methods.

Why does this details matter? In the case of Struts, the nextBytes method is called implicitly by the BigInteger class. In order to predict the state of the seed, we will need to reverse the order of the bytes to match the original int values.

java.util.Random usage in Struts (TokenHelper.java)

Now how does Struts interact with java.util.Random? The important calls are as follow.

-TokenHelper.generateGUID()
  -new Random()
  -new BigInteger()
    -Random.nextBytes()

As said previously, the nextBytes() method is used. Nonetheless, a sequence of int is still generated.

Exploit

To exploit this algorithm, a bridge need to be made between two successive generated values. The only obstacle is the loss of 16 bits information of the seed. It is really easy to retrieve the seed by brute-forcing the missing 16 bits. Once the seed is found, we can generate all the following values. This is made possible because the Random instance is reuse globally (see the static keyword).

Brute force operation

The proof of concept code has some additional details that are not that interesting. If you need to produce a working exploit, take a look at this proof of concept : struts-csrf-cracker.


Execution preview:

== Initial token
H6P3Y3GHIC2865ASZVQ913NR93QZO7BR
== Initial token in hex (easier evaluation)
14b08fcbf6523eecd7dd7d3e89cf97d6f478db5617

Guessing part..
== bytes representation (reconstructed byte array)
14b08fcb
f6523eec
d7dd7d3e
89cf97d6
f478db56
Seed found: 259752424024079
== following int .. (should match the initial token last part) 
d7dd7d3e
89cf97d6
f478db56
175a6e1c
== (prediction) Next token 
1590c1573a30295e6d87082bf2c389f575f5fcfa3890b8ac

== (actual) Next token
HWVVZO2VGBZOYD0QFWE8GU3BW4DCRVW8
== (actual) Next token in hex (easier evaluation)
1590c1573a30295e6d87082bf2c389f575f5fcfa38

Conclusion

If you see java.util.Random being used to generate secret value, the code is most likely vulnerable.

You can scan your code and the libraries you are using with Find Security Bugs. It will find vulnerabilities including predictable Pseudo Random Generator.

References

Struts 2 Advisory S2-023 : Official Struts advisory
Cracking Random Number Generators by James Roper : 3 parts articles series explaining PRNG in Java.
Black-Box Assessment of Pseudorandom Algorithms by Derek Soeder, Christopher Abad and Gabriel Acevedo : Excellent paper presented at BlackHat USA 2013. The tool presented "Prangster" is probably your best bet when source code is not available (Detailed paper).