CVE-XXX-XXXX - Linux ASLR mmap weakness: Reducing entropy by half

Authors:Hector Marco & Ismael Ripoll
CVE:To be assigned
BUG:Linux mmap ASLR improper randomization
Dates:17 January 2015 - Public disclosure


Description

A bug in Linux ASLR implementation has been found. The issue is that the mmap base address for processes is not properly randomized on some architectures due to an improper bit-mask manipulation. Affected systems have reduced the mmap area entropy of the processes by half.

This vulnerability is similar to the CVE-2015-1593 - Linux ASLR integer overflow: Reducing stack entropy by four published 10 days ago.

The following output is the run on ARM64 under Linux 3.17.0 to check if it is affected:

$ for i in `seq 1 10`; do cat /proc/self/maps | grep vdso ; done
7fa4b50000-7fa4b51000 r-xp 00000000 00:00 0                              [vdso]
7f927ba000-7f927bb000 r-xp 00000000 00:00 0                              [vdso]
7f8d3b6000-7f8d3b7000 r-xp 00000000 00:00 0                              [vdso]
7fb4d12000-7fb4d13000 r-xp 00000000 00:00 0                              [vdso]
7fb4bd2000-7fb4bd3000 r-xp 00000000 00:00 0                              [vdso]
7fb5f9c000-7fb5f9d000 r-xp 00000000 00:00 0                              [vdso]
7f7b668000-7f7b669000 r-xp 00000000 00:00 0                              [vdso]
7fa8a40000-7fa8a41000 r-xp 00000000 00:00 0                              [vdso]
7f7cb2e000-7f7cb2f000 r-xp 00000000 00:00 0                              [vdso]
7f9068a000-7f9068b000 r-xp 00000000 00:00 0                              [vdso]

As shown in the previous output, the 13th bit is fixed to 1. In order to have more confidence about this hypothesis, we can run additional tests:

Test 1:
$ for i in `seq 1 1000`; do cat /proc/self/maps | grep vdso | grep "[02468ace]000 r"; done |wc -l
0

We obtained 0 as a result, which indicate us that the 13th bit after 1000 executions never is 1. To be more confident about this, we can run the complementary test (test 2). That is, run 1000 executions keeping only those samples that have the 13th bit set to 1. Since it seems that our system is vulnerable the expected number will be 1000.

Test 2:
$ for i in `seq 1 1000`; do cat /proc/self/maps | grep vdso | grep "[13579bdf]000 r"; done |wc -l
1000

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

Impact

The total entropy for the mmap area of the processes is reduced by half. The number of possible locations are reduced by 50%, which for example will reduce the cost of brute force attacks.

PowerPC, Sparc64 and ARM have 18 bits of entropy. Non-vulnerable systems have 262144 (218) different places to locate the mmap area. On vulnerable systems, this value is reduced to 131072 (217).

The bug

The bug appears because as an attempt to avoid to use the same random number while creating a new process. The old implementation of get_random_int() returned the same value within a 1 jiffy window, which produced in some cases the same random value both to calculate the stack and the mmap area. This undesired behaviour was solved with following hack:

static unsigned long mmap_rnd(void)
{
   unsigned long rnd = 0;

   if (current->flags & PF_RANDOMIZE)
      rnd = (long)get_random_int() & (STACK_RND_MASK >> 1)

   return rnd << (PAGE_SHIFT + 1);
}

The previous code belongs to ARM64 but the similar code is used by Sparc64 and PowerPC, which tries to shift the randomness by 1 bit.

Unfortunately, they shifted the mask instead of the random value. The STACK_RND_MASK (which is 0x3FFFF on ARM64, 18 bits) mask is shifted 1 bit to the right, resulting in 0x1FFFF, 17 bits. After that, this resulting mask is used to obtain the "rnd" by performing an "&" operation obtaining a random value of 17 bits. This "rnd" value is shifted to left (PAGE_SHIFT + 1), which is 13 for ARM64, setting the 13th to 0.

In our tests, we saw that the 13th bit is always 0 and not 1. This is because how the mmap_base is calculated for the ARM64:

static unsigned long mmap_base(void)
{
    unsigned long gap = rlimit(RLIMIT_STACK);

    if (gap < MIN_GAP)
        gap = MIN_GAP;
    else if (gap > MAX_GAP)
        gap = MAX_GAP;

    return PAGE_ALIGN(STACK_TOP - gap - mmap_rnd());
}

The mmap_base value is calculated by doing some subtractions. The STACK_TOP is a constant value and the gap depends on the stack limit, but by default (and in most cases) it is a constant value (and it is always a known value).

For the ARM64 architecture, these values are: 0x8000000000 for the STACK_TOP and 0x47FFF001 for the gap. Doing the subtractions and aligning the result to PAGE_SIZE we got that the 13th bit is always set to 1.


Affected Systems

Several Linux architectures are affected. The following picture sketches the most important commits and the time when the vulnerability was introduced for each architecture.

In May 2009, the get_random_int() kernel function was improved. From this date, the hack introduced to avoid to use the same random number was not longer necessary.


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 stack is mapped, for example by using brute force or trial and test attacks, requires half attempts.

FIX

This weakness is already fixed in the Kernel. Hence, update to a non-vulnerable Kernel will prevent abuse of this security issue. Unfortunately this is not always an option for some devices like NAS or other embedded systems fairly common on PowerPC, Sparc64 or ARM64.

Discussion

Although only one bit is dropped, note that from 218 to 217 the range of mmap base area is reduced by half. In short, an attacker will need to perform 2 times less work to guess where the libraries (and other mmap areas) are placed. The range of the mmap area is approximately 131072 (217) instead of 262144 (218).



Hector Marco - http://hmarco.org