CVE-2014-7284: Lack of randomness in Linux kernel network secrets

CVE-2014-7284 (NGRO Bug): Lack of randomness in Linux kernel network secrets

Published October 1, 2014; updated October 2, 2014 with CVE number.

In the late 1990s and early 2000s, many operating systems were found to have flawed TCP/IP sequence number generators, and this was identified as a serious security vulnerability (see, for example, Strange Attractors and TCP/IP Sequence Number Analysis - One Year Later ). Since that time, generators have been improved, it has been assumed that the problem was dealt with, and most people stopped thinking about these kinds of vulnerabilities.

However, we have identified a problem with Linux kernel, the result of which was that secret random seed values (e.g., net_secret , syncookie_secret , inet_ehash_secret , etc.) were never initialized on some systems. This would mean that values such as IP IDs, TCP sequence numbers, and ephemeral port numbers become far more easily predictable than they should be. Affected systems would be vulnerable to a number of attacks. For example, as noted by CERT in their 2001 Vulnerability Note Multiple TCP/IP implementations may use statistically predictable initial sequence numbers : "If the ISN [TCP initial sequence number] of an existing connection can be determined within some practical range, a malicious agent may be able to close or hijack the connection. If the ISNs of future connections are targeted, an agent may be able to 'complete' a TCP three-way handshake and spoof TCP packets delivered to a victim."

Affected Systems

This isssue affected Linux kernel versions 3.13 and 3.14, x86_64 or x86. This shipped, for example, with Ubuntu 14.04 and as an update for Fedora 19 and 20. It was fixed in 3.15, and the fix was applied to some older kernels (e.g., Ubuntu trusty kernels 3.13.0-31 and greater have it). Until now, however, the security implications of the bug seem to have gone completely unrecognized. We don't know if it was a deliberate decision to obscure the bug's impact, or if no one working on it realized what the impact was.

If a system is running an x86_64 (64-bit) kernel with the bug, it will be affected if the CPU is one of the newer Intel processors (Ivy Bridge — family 6, model > 48 according to /proc/cpuinfo ). These are relatively common, and getting more so. If a system is running an x86 (32-bit) kernel with the bug, it may be affected if the CPU is one of certain older Intel processors (see below for details). We believe these to be relatively uncommon.

How We Found The Bug

We found this problem while working on our Linux security product,Second Look. Second Look is a memory forensics and integrity verification tool used for incident response and intrusion detection. We were testing with an Ubuntu 14.04 64-bit target on some new hardware when Second Look reported unexpected mismatches between the kernel code in memory and the "reference kernel" (i.e., the kernel of matching version supplied by the distribution vendor).

In normal usage, alerts such as these are often indications of a rootkit that has hooked itself into the kernel. When testing on a new kernel version, however, they can instead indicate some new variation on dynamic code modification, which is used fairly extensively in the Linux kernel (alternative instructions, paravirtualization operations, SMP lock removal, etc.).

With Second Look, our comparison of the in-memory kernel and the reference kernel attempts to take into account these fix-ups, so our first instinct was to try to determine what new fix-ups we may need to apply. However, as we delved into the code, and compared memory dumps from various systems running 3.13 kernels, some of which exhibited these alerts and some of which did not, we began to suspect something was "not right". Particularly when we realized the random seeds mentioned above weren't getting initialized on the affected systems. There didn't seem to be any reason for these mismatches, based on our understanding of how this aspect of the kernel was supposed to operate. Yet clearly on some systems the "slow path" which performs initialization of the random seeds was never being executed.

We observed that if a host was affected, so would be a VM running on the host, but if a host was unaffected, the same VM running on it would also be unaffected. This led us to believe that CPU type or features were a trigger for the behavior. We noticed that all the affected systems had newer CPUs. Finally, reading again each line of code responsible for the boot-time net_get_random_once call site code patching, with these observations in mind, we realized what the bug was (as explained below).

Explanation Of The Bug

In 3.13, an optimization for net_get_random_once was introduced, making use of the kernel's "static key" and "jump label" functionality. The commit dates from October 2013. You can read more about static keys in general in Documentation/static-keys.txt in the kernel tree.

The author of the patch acknowledged that "[t]he usage of static_keys for net_get_random_once is a bit uncommon so it needs some further explanation why this actually works", which he provided in the commit message. Part of the explanation for why the implementation should work is: "because we initialize ___done_key with (enabled != (entries & 1)) this call-site will get patched up at boot". But actually, it is not always true that this patching occurs as expected. On affected systems, the slow path (where initialization of random seeds occurs) is never taken.

Here's why:

  • Call sites are initially nops — the "default nop" is written by the compiler (see arch_static_branch in arch/x86/include/asm/jump_label.h ).
  • At boot time, call sites are normally patched with an "ideal nop" (see jump_label_init in kernel/jump_label.c ).
  • This commit introduced a situation that static keys had not previously been used for anywhere in the kernel: the slow path is taken initially. Therefore a jump needs to be patched in at boot time, rather than a nop. (Code called in the slow path will replace the jump with a nop so that the slow path ends up only ever being followed once.)
  • The jump_label_init function calls arch_jump_label_transform_static with type JUMP_LABEL_ENABLE to patch in the jump for the net_get_random_once call sites... but on some hardware arch_jump_label_transform_static fails to write jumps (leaving the default nop in place).

In arch/x86/kernel/jump_label.c :

115 static enum {
116         JL_STATE_START,
117         JL_STATE_NO_UPDATE,
118         JL_STATE_UPDATE,
119 } jlstate __initdata_or_module = JL_STATE_START;
121 __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry,
122                                       enum jump_label_type type)
123 {
124         /*
125          * This function is called at boot up and when modules are
126          * first loaded. Check if the default nop, the one that is
127          * inserted at compile time, is the ideal nop. If it is, then
128          * we do not need to update the nop, and we can leave it as is.
129          * If it is not, then we need to update the nop to the ideal nop.
130          */
131         if (jlstate == JL_STATE_START) {
132                 const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
133                 const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
135                 if (memcmp(ideal_nop, default_nop, 5) != 0)
136                         jlstate = JL_STATE_UPDATE;
137                 else
138                         jlstate = JL_STATE_NO_UPDATE;
139         }
140         if (jlstate == JL_STATE_UPDATE)
141                 __jump_label_transform(entry, type, text_poke_early, 1);
142 }

If default_nop is the same as ideal_nop the memcmp on line 135 returns 0, putting us in the else branch of the innermost if statement. jlstate is set to NO_UPDATE (line 138). This means __jump_label_transform will never be called. This makes sense if this function is only ever used to patch in nops, but for patching in jumps, as we want to do now with the net_get_random_once use case, the patching should happen regardless of whether default_nop and ideal_nop are the same or not.

So, when will the ideal_nop be the same as the default? First of all, what's the default? In arch/x86/include/asm/jump_label.h we have:

#ifdef CONFIG_X86_64

P6_NOP5_ATOMIC comes from p6_nops . GENERIC_NOP5_ATOMIC comes from intel_nops .

Next, what's the ideal? See function arch_init_ideal_nops in arch/x86/kernel/alternative.c , and compare with Intel Architecture and Processor Identification With CPUID Model and Family Numbers .

Our reading is that these will be the affected systems: with x86_64 kernels, it seems that p6_nops are selected as ideal on Intel CPUs manufactured with the Ivy Bridge process (model > 48); with x86 kernels, intel_nops seem to be selected as ideal if family < 6 (i.e., pre-Pentium 2 CPUs), or if family == 6 and model matches one of three specific values (0x1c, 0x26, 0x27) — if those models don't have the nopl instruction. It's not clear to us exactly which CPUs might fall into the latter category.

Fixing The Bug

It seems the fix could simply have been to add an or-clause to to the final if-statement (line 140 above): ... || type == JUMP_LABEL_ENABLE . However, instead the author of this optimization decided to reimplement it in a different (more straightforward) manner — to use the static key functionality of the kernel in the usual way, rather than (in his words) "abusing" it. The commit was made in May 2014. It was applied to the Ubuntu trusty kernel tree in June 2014. There was no mention of the security implications of the bug in the commit message, or elsewhere, so far as we can tell. It seems that initial discovery of the bug was related to issues it caused with ephemeral port numbering that impacted the LTSP project. See, for example, Launchpad Bug #133067: LTSP boot fails... and this LTSP-discuss mailing list thread .

Checking For The Bug

A bit of "proof" that a system is affected is to compile and load a kernel module that prints the value of one of the secret random seeds. For example, the accompanyingnsprintmodule prints the value of the kernel's net_secret variable. Results can be viewed with the dmesg command. Some results:

  • An example *affected* system
    OS: Ubuntu 14.04 / kernel version (uname -rvm): 3.13.0-24-generic #46-Ubuntu SMP Thu Apr 10 19:11:08 UTC 2014 x86_64
    CPU: Intel(R) Xeon(R) CPU E5-2670 v2 (family 6, model 62)
    ~/nsprint$ sudo insmod nsprint.ko
    ~/nsprint$ dmesg | tail -1
    [xxxxxx.yyyyyy] 000000000000000000000000000000000000000000000000000000000000000...
  • An example *unaffected* system (same hardware, different kernel)
    OS: Ubuntu 12.04.4 / kernel version (uname -rvm): 3.11.0-19-generic #33~precise1-Ubuntu SMP Wed Mar 12 21:16:27 UTC 2014 x86_64
    CPU: Intel(R) Xeon(R) CPU E5-2670 v2 (family 6, model 62)
    ~/nsprint$ sudo insmod nsprint.ko
    ~/nsprint$ dmesg | tail -1
    [xxxxxxx.yyyyyy] 18c8b127324835317963570b05f233dcac3c48d577ed3af66668b6d0937d2b...
  • Another example *unaffected* system (same kernel, different hardware)
    OS: Ubuntu 14.04 / kernel version (uname -rvm): 3.13.0-24-generic #46-Ubuntu SMP Thu Apr 10 19:11:08 UTC 2014 x86_64
    CPU: Intel(R) Xeon(R) CPU E5-2620 (family 6, model 45)
    ~/nsprint$ sudo insmod nsprint.ko
    ~/nsprint$ dmesg | tail -1
    [xxxxx.yyyyyy] d37832c21e9daf443e6a3e9396ff740446fb48914aad3626fed609ae33df96e3...

NB: As mentioned above, net_secret isn't the only random seed value that is affected. There are a number of others that are initialized with net_get_random_once . This is just one example to demonstrate the problem.

Remote Detection Of Affected Systems

Probably the simplest way to determine whether remote systems are affected is to look at the ID field in the IP header of packets they send you. For example, you could do an nmap scan, capture traffic with tcpdump, and look at the IP IDs. The accompanying program,calcipid.c, calculates the value you would see from an affected system, given your IP address. Note, however, that some middleboxes may scrub IP IDs, as permitted by RFC 6864. For example, we set up an Ubuntu 14.04 64-bit EC2 c3.large instance, confirmed it was affected locally, but observed 0 in the IP ID field of remotely received packets.