AMD Bulldozer Linux ASLR weakness: Reducing entropy by 87.5%

Authors:Hector Marco & Ismael Ripoll
CVE:To be assigned
BUG:AMD Bulldozer Linux ASLR mmapped files weakness
Dates:24 March 2015 - Public disclosure


Description

Non-affected bulldozer ;-)
(Photo by: MathKnight)

A security issue in Linux ASLR implementation which affects some AMD processors has been found. The issue affects to all Linux process even if they are not using shared libraries (statically compiled).

The problem appears because some mmapped objects (VDSO, libraries, etc.) are poorly randomized in an attempt to avoid cache aliasing penalties for AMD Bulldozer (Family 15h) processors.

Affected systems have reduced the mmapped files entropy by eight.

After we found (and fixed) this weakness, we found a detailed white paper about this issue (Shared Level 1 instruction cache performance on AMD family 15h CPUs). Several workarounds were proposed, but none of them solved the problem in the way our proposal does.

Our solution (see below) is not a workaround, but a solution that effectively avoids cache conflicts and does not jeopardizes ASLR entropy. The complexity, both in the number of lines of code and the timing overhead, of our proposed solution is negligible; that is, it does not have trade-offs AFAWK.

This vulnerability is similar to:

1) Linux ASLR mmap weakness: Reducing entropy by half published on January 17, 2015.

2) CVE-2015-1593 - Linux ASLR integer overflow: Reducing stack entropy by four published on January 7, 2015.

The following output is the run on an AMD Opteron 62xx class CPU processor under x86_64 Linux 4.0.0:

$ for i in `seq 1 10`; do cat /proc/self/maps | grep "r-xp.*libc" ; done
7fbcdb388000-7fbcdb545000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f4c88a18000-7f4c88bd5000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f8d7e7b8000-7f8d7e975000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f6c314d8000-7f6c31695000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7fccad6b0000-7fccad86d000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f53bcc50000-7f53bce0d000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f0c3c838000-7f0c3c9f5000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7ffecb3c8000-7ffecb585000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f87d7500000-7f87d76bd000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6
7f1a725a0000-7f1a7275d000 r-xp 00000000 00:01 1387            /lib/x86_64-linux-gnu/libc.so.6

Grsecurity/PaX is also affected. To check it, we have patched the Linux kernel 3.14.27 with Grsecurity/PaX. Some kernel configurations selected are:

Note: Due to a problem in the configuration of the Grsecurity kernel, the PaX options were not properly enabled, and so the following run is not a PaX run. See discussion below.

The following output is the run on AMD the same processor (Opteron 62xx class CPU) under a i386 Linux 3.14.27 patched with PaX 3.1. (Therefore, this run is on a native i386 Linux 3.14.27) The result is:

$ for i in `seq 1 10`; do cat /proc/self/maps | grep "r-xp.*libc" ; done
b7588000-b7736000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b7570000-b771e000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b75d0000-b777e000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b75b0000-b775e000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b7578000-b7726000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b7598000-b7746000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b7528000-b76d6000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b75b0000-b775e000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b7560000-b770e000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6
b75d0000-b777e000 r-xp 00000000 00:01 4924       /lib/i386-linux-gnu/libc.so.6

As shown in the previous outputs, both the non-patched PaX and the patched one have the bits 12, 13 and 14 are always 0. In order to have more confidence about this hypothesis, we can run additional tests:

Test 1

Non-PaX Kernel:
$ for i in `seq 1 1000`; do cat /proc/self/maps |grep vvar |grep "[^08]000-"; done |wc -l
0
Grsecurity/PaX Kernel:
$ for i in `seq 1 1000`; do cat /proc/self/maps |grep "r-xp.*libc" |grep "[^08]000-"; done |wc -l
0

In both cases the result is 0, which indicates that after 1000 executions the bits 12, 13 and 14 are always 0.

Test 2

Non-PaX Kernel:
$ for i in `seq 1 1000`; do cat /proc/self/maps |grep vvar |grep "[08]000-"; done |wc -l
1000
Grsecurity/PaX Kernel:
$ for i in `seq 1 1000`; do cat /proc/self/maps |grep "r-xp.*libc" |grep "[08]000-"; done |wc -l
1000

At this point, we are pretty sure that our system is vulnerable.

Impact

The total entropy for the VVAR/VDSO, mmapped files and libraries of a processes are reduced by eight. The number of possible locations where the mapped areas can be placed are reduced by 87.5%.

Only 5 random bits on i386.
On 32-bit systems, for example, the entropy for libraries is reduced from 28 to 25, which means that libraries only have 32 different places where they can be loaded. Under this scenario, advanced techniques used by PaX to thwart brute force attacks (for example, force a delay on the process creation when a crash occurs) are no longer effective. The attackers need on average only 16 trials.

32-bit applications running on 64-bit systems (x86_32) are also affected. The entropy is approximately the same or a littler bit higher depending on the personality flags. Actually, these applications are at a similar risk than when running on 32-bit systems (i386).

On 64-bit systems, the entropy for libraries is reduced from 228 to 225. The different places where the libraries can be mapped are reduced approximately form 33554432 to of 268435456. The number of possible locations where the objects can be mapped on average is reduced from 268 to 16 millions.

The number of potential vulnerable users could be high because both, standard and Grsecurity/PaX Linux are affected.

The bug

The bug is caused by a hack to improve performance by avoiding cache aliasing penalties in the Family 15h of AMD Bulldozer processors. The hack which affects mmapped files is in the file arch/x86/kernel/sys_x86_64.c. Here, the arch_get_unmapped_area_topdown() function is defined and later it calls to vm_unmapped_area() with a pointer to a struct vm_unmapped_area_info as a parameter. This struct, among other fields, contains a mask used to align the returned address which will be used as a base address to map the file. Following is a snippet of the affected code:

arch_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
                          const unsigned long len, const unsigned long pgoff,
                          const unsigned long flags)
{
        struct vm_area_struct *vma;
        struct mm_struct *mm = current->mm;
        unsigned long addr = addr0;
        ...

        info.flags = VM_UNMAPPED_AREA_TOPDOWN;
        info.length = len;
        info.low_limit = PAGE_SIZE;
        info.high_limit = mm->mmap_base;
        info.align_mask = filp ? get_align_mask() : 0;
        info.align_offset = pgoff << PAGE_SHIFT;
        addr = vm_unmapped_area(&info);
        ...
}

The info.align_mask value is calculated by calling to get_align_mask() only if the filp is not null. In other words, if the process is mapping a file then the info.align_mask depends on the return value of get_align_mask(). This function is:

/*
 * Align a virtual address to avoid aliasing in the I$ on AMD F15h.
 */
static unsigned long get_align_mask(void)
{
        /* handle 32- and 64-bit case with a single conditional */
        if (va_align.flags < 0 || !(va_align.flags & (2 - mmap_is_ia32())))
                return 0;

        if (!(current->flags & PF_RANDOMIZE))
                return 0;

        return va_align.mask;
}

The previous code returns a unsigned long mask which was initialized when the kernel booted and depends on the family processor. When the processor is an AMD F15h this value is 0x7000. Therefore, ASLR depends on the specific processor.

Reading the log comments it seems that kernel developers were aware of this issue (the reduction on the ASLR entropy):

This patch provides performance tuning for the "Bulldozer" CPU. With its shared instruction cache there is a chance of generating an excessive number of cache cross-invalidates when running specific workloads on the cores of a compute module.

This excessive amount of cross-invalidations can be observed if cache lines backed by shared physical memory alias in bits [14:12] of their virtual addresses, as those bits are used for the index generation.

Maybe three bits less of entropy was not considered significant on 64bit systems. Unfortunately, on 32 bit systems, where the implementation of the ASLR is limited to 8 random bits it has a disastrous effect.

Affected Systems

The first affected Linux kernel version was 3.0.0, released on August 5, 2011. The following table summarizes the affected systems as well as the objects which are poorly randomized.


Object 32-bit apps. 64-bit apps.
Standard Linux kernel
Libraries and files 28  →   25 228  →   225
VVAR/VDSO 28  →   25 218  →  215
Grsecurity/PaX Linux kernel
Libraries and files 2825  /   216213 229  →   226
VVAR/VDSO 28   /   216 229
Table: Effective entropy for (affected → non-affected) systems

Exploit

It is not necessary to do anything to exploit this issue. Every launched application in the system using the ASLR will be affected by this issue.

Any attempt to guess where the VVAR/VDSO, library or any mmapped user file, by using brute force or trial and test attacks, requires eight times less attempts.

Workaround

Fortunately, the kernel provides a command line boot option to disable this behaviour. By setting the align_va_addr=off, the alignment is disabled and then the objects are loaded without losing entropy.

If you have a 64bit system and you consider that 225 is a fairly large number (which depends on your threats and attack vectors), then you may set align_va_addr=64, which forces the page alignment only when running 64bits applications, and lets 32bit apps unaffected.


Fix

It is possible to have both: performance and security at once. Rather than resetting the conflicting bits [12..14], those bits can be set to a random value for all shared pages. At boot time, a random value in the range 0 to 7 is computed and stored. Then, all the bits [12..14] of all shared pages are set to that computed value.

Since all the shared pages have the same value at the bits [12..14], there is no cache aliasing problems (which is supposed to be the cause of performance loss). On the other hand, since the value is not known by a potential remote attacker, the ASLR preserves its effectiveness.

This type of ASLR model is known as per-boot randomization, which is pretty close to the way the ASLR is implemented in Windows(r) and Mac OS(r).

With this fix, the affected addresses will have a mix of ASLR types: "per-process" ASLR for all bits but [12..14], and "per-boot" ASLR in [12..14] bits.

Patch: [ 0001-mm-x86-AMD-Bulldozer-ASLR-fix.patch ]

Patching Linux:
$ cd linux.git
$ wget http://hmarco.org/bugs/patches/0001-mm-x86-AMD-Bulldozer-ASLR-fix.patch
$ git apply 0001-mm-x86-AMD-Bulldozer-ASLR-fix.patch

Discussion

Although it could be argued that this loss of entropy is justified in order to avoid some performance penalties, we should consider the following:

We recommend to apply the proposed fix to the kernel source or to disable the virtual address alignment (align_va_addr=off) on any Internet server equipped with an AMD Bulldozer CPU.

PaX issues

PaX solution has actually 16 random bits for mmap objects in 32bit systems. Unfortunately, depending on the PaX Kernel configuration sequence, some features may not be enabled. There are sequences of PaX configuration which does not give the expected result.

The configuration sequence that results in a miss-configured system is:
  1. Starting from a clean Linux tree with PaX patch applied.

  2. Enabled the "Grsecurity" option (which sets "Security Method" to "Custom") and compile&test:
    Observed mmap entropy: 25 (as expected).

  3. Then set "Security Method" to "Automatic" (which sets "Required Priorities" to "Performance") and compile&test:
    Observed mmap entropy: 25.

  4. Last test: select "Security" on the "Required Priorities" option and compile&test:
    Observed mmap entropy: 25.

  5. At this point, it seems that the "Required Priorities" option has no effect, that is, switching from "Performance" to "Security" or the other way around (as may times as desired) does not enable/disable the expected features, including the mmap randomization.

If steps 2 and 3, or 2 and 4 are configured at once (without exiting from the menuconfig), then the system gets properly configured.



Hector Marco - http://hmarco.org