Linux ASLR mmap weakness: Reducing entropy by half
XXXX-XXXX - Linux ASLR mmap wekaness: Reducing entropy by half

      
      
      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