xorl %eax, %eax

CVE-2009-3238: Linux kernel get_random_int() Predictable Numbers

leave a comment »

This bug was fixed in 2.6.30 release of the Linux kernel as we can read from its ChangeLog file. The issue was discovered by Linus Torvalds and here is some code from 2.6.29’s drivers/char/random.c code.

/*
 * Get a random word for internal kernel use only. Similar to urandom but
 * with the goal of minimal entropy pool depletion. As a result, the random
 * value is not cryptographically secure but for several uses the cost of
 * depleting entropy is too high
 */
unsigned int get_random_int(void)
{
        /*
         * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
         * every second, from the entropy pool (and thus creates a limited
         * drain on it), and uses halfMD4Transform within the second. We
         * also mix it with jiffies and the PID:
         */
        return secure_ip_id((__force __be32)(current->pid + jiffies));
}

So, it just uses the current process’ ID along with ‘jiffies’ value. The called function can be found in the same source code file like this:

/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
 *  All blames to Andrey V. Savochkin <saw@msu.ru>.
 */
__u32 secure_ip_id(__be32 daddr)
{
        struct keydata *keyptr;
        __u32 hash[4];

        keyptr = get_keyptr();

        /*
         *  Pick a unique starting offset for each IP destination.
         *  The dest ip address is placed in the starting vector,
         *  which is then hashed with random data.
         */
        hash[0] = (__force __u32)daddr;
        hash[1] = keyptr->secret[9];
        hash[2] = keyptr->secret[10];
        hash[3] = keyptr->secret[11];

        return half_md4_transform(hash, keyptr->secret);
}

It retrieves the key pointer using get_keyptr() and stores it in ‘keyptr’ variable. Then the ‘hash[]’ array is initialized with the passed argument as its first value and the rest three are taken from ‘keyptr->secret[]’ array. Finally, a cut-down version of MD4 hash algorithm is used to return a 32-bit unsigned integer given the 4 integers long hash array along with the 12 integers long secret one. The secret array is initialized using the kernel’s entropy pool.
L. Torvalds noticed that ‘hash’ array was always in a specific area that could allow an attacker to predict/bruteforce the number passed to MD4 algorithm since he could repeatedly call that routine and always start from the same seed.
His patch was this:

 unsigned int get_random_int(void)
 {
-       /*
-        * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
-        * every second, from the entropy pool (and thus creates a limited
-        * drain on it), and uses halfMD4Transform within the second. We
-        * also mix it with jiffies and the PID:
-        */
-       return secure_ip_id((__force __be32)(current->pid + jiffies));
+       struct keydata *keyptr;
+       __u32 *hash = get_cpu_var(get_random_int_hash);
+       int ret;
+
+       keyptr = get_keyptr();
+       hash[0] += current->pid + jiffies + get_cycles() + (int)(long)&ret;
+
+       ret = half_md4_transform(hash, keyptr->secret);
+       put_cpu_var(get_random_int_hash);
+
+       return ret;
 }

He used code similar to secure_ip_id() instead of calling it directly. Specifically, he uses a pointer as hashing area which is initialized using get_cpu_var() passing a random hash to it as an argument. C macro get_cpu_var() is a wrapper around __get_cpu_var() which can be found at include/asm-generic/percpu.h like this:

#define __get_cpu_var(var) \
        (*SHIFT_PERCPU_PTR(&per_cpu_var(var), my_cpu_offset))

Macro SHIFT_PERCPU_PTR() is used to add the passed offset (its second argument) to the pointer (first argument). And per_cpu_var() which contains the random hash is defined in include/linux/percpu-defs.h like this:

/*
 * Determine the real variable name from the name visible in the
 * kernel sources.
 */
#define per_cpu_var(var) per_cpu__##var

L. Torvalds stated that he did this for this:

I made that hash be a per-cpu data just to avoid cache-line ping-pong:
having multiple CPU's write to the same data would be fine for randomness,
and add yet another layer of chaos to it, but since get_random_int() is
supposed to be a fast interface I did it that way instead. I considered
using "__raw_get_cpu_var()" to avoid any preemption overhead while still
getting the hash be _mostly_ ping-pong free, but in the end good taste won
out.

The next change was the initialization of ‘hash[0]’ value which apart from the current process’ ID and ‘jiffies’ value, it uses the address of local variable ‘ret’ and the return value of get_cycles() which is just a wrapper around rdtsc instruction. At last, put_cpu_var() is used to enable to execute preempt_enable() on preemptive kernels.

Written by xorl

October 26, 2009 at 21:37

Posted in bugs, linux

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s