CVE-2015-1593 - Linux ASLR integer overflow: Reducing stack entropy by four

A bug in Linux ASLR implementation for versions prior to 3.19-rc3 has been found. The issue is that the stack for processes is not properly randomized on some 64 bit architectures due to an integer overflow.

Affected systems have reduced the stack entropy of the processes by four. To check if your Linux is vulnerable simply execute the following:

$ for i in `seq 1 10`; do cat /proc/self/maps | grep stack; done
7fff612ab000-7fff612cc000 rw-p 00000000 00:00 0                          [stack]
7fff7df8d000-7fff7dfae000 rw-p 00000000 00:00 0                          [stack]
7fff9b738000-7fff9b759000 rw-p 00000000 00:00 0                          [stack]
7fff915db000-7fff915fc000 rw-p 00000000 00:00 0                          [stack]
7fffa4111000-7fffa4132000 rw-p 00000000 00:00 0                          [stack]
7fff1f272000-7fff1f293000 rw-p 00000000 00:00 0                          [stack]
7fffa5831000-7fffa5852000 rw-p 00000000 00:00 0                          [stack]
7fff10ac5000-7fff10ae6000 rw-p 00000000 00:00 0                          [stack]
7fffeb039000-7fffeb05a000 rw-p 00000000 00:00 0                          [stack]
7fff807b6000-7fff807d7000 rw-p 00000000 00:00 0                          [stack]

If you see in your system the sequence 7FFF then your system is not patched and your ASLR is slightly weaker. The previous example shows that this x86_64 architecture is vulnerable.

For completeness: The total amount of stack entropy is not shown by printing the memory map because most Linux architectures implement an intra-page randomization which increases the stack entropy by one more byte. Therefore, the real stack entropy is given by 7FFF???????0, which is 2^28 in affected systems.

A system not affected by this weakness shall have a total stack entropy of 2³⁰, that is four times more entropy.

$ for i in `seq 1 10`; do cat /proc/self/maps | grep stack; done
7ffeda566000-7ffeda587000 rw-p 00000000 00:00 0                          [stack]
7fff5a332000-7fff5a353000 rw-p 00000000 00:00 0                          [stack]
7ffcdb7a1000-7ffcdb7c2000 rw-p 00000000 00:00 0                          [stack]
7ffd5e2c4000-7ffd5e2e5000 rw-p 00000000 00:00 0                          [stack]
7ffdb59f6000-7ffdb5a17000 rw-p 00000000 00:00 0                          [stack]
7ffcc20d4000-7ffcc20f5000 rw-p 00000000 00:00 0                          [stack]
7fff3d799000-7fff3d7ba000 rw-p 00000000 00:00 0                          [stack]
7ffe9ddf9000-7ffe9de1a000 rw-p 00000000 00:00 0                          [stack]
7ffeda006000-7ffeda027000 rw-p 00000000 00:00 0                          [stack]
7ffeef21f000-7ffeef240000 rw-p 00000000 00:00 0                          [stack]

The upper two bytes in non-affected systems should cover the range from 7FFC to 7FFD.

Impact

The total stack entropy of the processes is reduced by four: from 2³⁰ to 2²⁸ (One fourth of expected entropy). The possible locations are significantly reduced from around one billion to two hundred millions. The problem seems to affect only to the x86_64 architecture.

Affected Linux versions

All Linux versions prior to 3.19-rc3 are affected. As far as we know this bug is already present in the first commit (1da177e) on the current repository (https://github.com/torvalds/linux), April 2005.

The bug

The bug appears because the presence of a integer overflow in the function which randomizes the stack:randomize_stack_top() in file "fs/binfmt_elf.c" (the line containing the error is highlighted in red):

static unsigned long randomize_stack_top(unsigned long stack_top)
{
        unsigned int random_variable = 0;

        if ((current->flags & PF_RANDOMIZE) &&
                !(current->personality & ADDR_NO_RANDOMIZE)) {
                random_variable = get_random_int() & STACK_RND_MASK;
                random_variable <<= PAGE_SHIFT;
        }
#ifdef CONFIG_STACK_GROWSUP
        return PAGE_ALIGN(stack_top) + random_variable;
#else
        return PAGE_ALIGN(stack_top) - random_variable;
#endif
}

The "random_variable" variable is declared as "unsigned int". Since the result of the shifting operation between STACK_RND_MASK (which is 0x3FFFFF on x86_64, 22 bits) and PAGE_SHIFT (which is 12 on x86_64), then the two leftmost bits are dropped when storing the result in the "random_variable". This variable shall be at least 34 bits long to hold the (22+12) result.

The previous integer overflow could cause intermittent crashed due to an incorrect stack GAP calculation. But a second bug on the stack_maxrandom_size() function, which also suffers an integer overflow, the value calculated on the former function (although it is wrong) matches with the real max stack value. The second affected function is in file "arch/x86/mm/mmap.c":

static unsigned int stack_maxrandom_size(void)
{
   unsigned int max = 0;
   if ((current->flags & PF_RANDOMIZE) &&
      !(current->personality & ADDR_NO_RANDOMIZE)) {
      max = ((-1U) & STACK_RND_MASK) << PAGE_SHIFT;
   }

   return max;
}

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 four time less trials (i.e. are faster).

FIX

We have created a patch which restores back the entropy by correcting the types involved in the operations in the functions randomize_stack_top() and stack_maxrandom_size().

diff --git a/arch/x86/mm/mmap.c b/arch/x86/mm/mmap.c
index 919b912..df4552b 100644
--- a/arch/x86/mm/mmap.c
+++ b/arch/x86/mm/mmap.c
@@ -35,12 +35,12 @@ struct va_alignment __read_mostly va_align = {
        .flags = -1,
 };

-static unsigned int stack_maxrandom_size(void)
+static unsigned long stack_maxrandom_size(void)
 {
-       unsigned int max = 0;
+       unsigned long max = 0;
        if ((current->flags & PF_RANDOMIZE) &&
                !(current->personality & ADDR_NO_RANDOMIZE)) {
-               max = ((-1U) & STACK_RND_MASK) << PAGE_SHIFT;
+               max = ((-1UL) & STACK_RND_MASK) << PAGE_SHIFT;
        }

        return max;
diff --git a/fs/binfmt_elf.c b/fs/binfmt_elf.c
index d8fc060..ee668b4 100644
--- a/fs/binfmt_elf.c
+++ b/fs/binfmt_elf.c
@@ -554,11 +554,11 @@ out:

 static unsigned long randomize_stack_top(unsigned long stack_top)
 {
-       unsigned int random_variable = 0;
+       unsigned long random_variable = 0;

        if ((current->flags & PF_RANDOMIZE) &&
                !(current->personality & ADDR_NO_RANDOMIZE)) {
-               random_variable = get_random_int() & STACK_RND_MASK;
+               random_variable = (unsigned long) get_random_int() & STACK_RND_MASK;
                random_variable <<= PAGE_SHIFT;
        }
 #ifdef CONFIG_STACK_GROWSUP

[ fix_randomize_stack_top_properly_linux_3-17.1.patch ] 

Patching Linux:

$ wget http://hmarco.org/bugs/patches/fix_randomize_stack_top_properly_linux_3-17.1.patch
$ cd linux-source
$ patch -p1 < ../fix_randomize_stack_top_properly_linux_3-17.1.patch
patching file arch/x86/mm/mmap.c
patching file fs/binfmt_elf.c

Discussion

Although only two bits are dropped due to an integer overflow, note that from 2³⁹ to 2²⁸ the stack entropy is reduced by four. In short, an attacker will need to perform 4 times less work to guess where the stack is placed. The number of possible places to allocate the stack due to integer overflow is approximately 268 millions instead of 1 billion. Maybe for this reason this bug has remained hidden for so long.