arch/x86/boot/compressed/kaslr.c

   1 /*
   2  * kaslr.c
   3  *
   4  * This contains the routines needed to generate a reasonable level of
   5  * entropy to choose a randomized kernel base address offset in support
   6  * of Kernel Address Space Layout Randomization (KASLR). Additionally
   7  * handles walking the physical memory maps (and tracking memory regions
   8  * to avoid) in order to select a physical memory location that can
   9  * contain the entire properly aligned running kernel image.
  10  *
  11  */
  12 #include "misc.h"
  13
  14 #include <asm/msr.h>
  15 #include <asm/archrandom.h>
  16 #include <asm/e820.h>
  17
  18 #include <generated/compile.h>
  19 #include <linux/module.h>
  20 #include <linux/uts.h>
  21 #include <linux/utsname.h>
  22 #include <generated/utsrelease.h>
  23
  24 /* Simplified build-specific string for starting entropy. */
  25 static const char build_str[] = UTS_RELEASE " (" LINUX_COMPILE_BY "@"
  26                 LINUX_COMPILE_HOST ") (" LINUX_COMPILER ") " UTS_VERSION;
  27
  28 #define I8254_PORT_CONTROL      0x43
  29 #define I8254_PORT_COUNTER0     0x40
  30 #define I8254_CMD_READBACK      0xC0
  31 #define I8254_SELECT_COUNTER0   0x02
  32 #define I8254_STATUS_NOTREADY   0x40
  33 static inline u16 i8254(void)
  34 {
  35         u16 status, timer;
  36
  37         do {
  38                 outb(I8254_PORT_CONTROL,
  39                      I8254_CMD_READBACK | I8254_SELECT_COUNTER0);
  40                 status = inb(I8254_PORT_COUNTER0);
  41                 timer  = inb(I8254_PORT_COUNTER0);
  42                 timer |= inb(I8254_PORT_COUNTER0) << 8;
  43         } while (status & I8254_STATUS_NOTREADY);
  44
  45         return timer;
  46 }
  47
  48 static unsigned long rotate_xor(unsigned long hash, const void *area,
  49                                 size_t size)
  50 {
  51         size_t i;
  52         unsigned long *ptr = (unsigned long *)area;
  53
  54         for (i = 0; i < size / sizeof(hash); i++) {
  55                 /* Rotate by odd number of bits and XOR. */
  56                 hash = (hash << ((sizeof(hash) * 8) - 7)) | (hash >> 7);
  57                 hash ^= ptr[i];
  58         }
  59
  60         return hash;
  61 }
  62
  63 /* Attempt to create a simple but unpredictable starting entropy. */
  64 static unsigned long get_random_boot(void)
  65 {
  66         unsigned long hash = 0;
  67
  68         hash = rotate_xor(hash, build_str, sizeof(build_str));
  69         hash = rotate_xor(hash, boot_params, sizeof(*boot_params));
  70
  71         return hash;
  72 }
  73
  74 static unsigned long get_random_long(void)
  75 {
  76 #ifdef CONFIG_X86_64
  77         const unsigned long mix_const = 0x5d6008cbf3848dd3UL;
  78 #else
  79         const unsigned long mix_const = 0x3f39e593UL;
  80 #endif
  81         unsigned long raw, random = get_random_boot();
  82         bool use_i8254 = true;
  83
  84         debug_putstr("KASLR using");
  85
  86         if (has_cpuflag(X86_FEATURE_RDRAND)) {
  87                 debug_putstr(" RDRAND");
  88                 if (rdrand_long(&raw)) {
  89                         random ^= raw;
  90                         use_i8254 = false;
  91                 }
  92         }
  93
  94         if (has_cpuflag(X86_FEATURE_TSC)) {
  95                 debug_putstr(" RDTSC");
  96                 raw = rdtsc();
  97
  98                 random ^= raw;
  99                 use_i8254 = false;
 100         }
 101
 102         if (use_i8254) {
 103                 debug_putstr(" i8254");
 104                 random ^= i8254();
 105         }
 106
 107         /* Circular multiply for better bit diffusion */
 108         asm("mul %3"
 109             : "=a" (random), "=d" (raw)
 110             : "a" (random), "rm" (mix_const));
 111         random += raw;
 112
 113         debug_putstr("...\n");
 114
 115         return random;
 116 }
 117
 118 struct mem_vector {
 119         unsigned long start;
 120         unsigned long size;
 121 };
 122
 123 #define MEM_AVOID_MAX 5
 124 static struct mem_vector mem_avoid[MEM_AVOID_MAX];
 125
 126 static bool mem_contains(struct mem_vector *region, struct mem_vector *item)
 127 {
 128         /* Item at least partially before region. */
 129         if (item->start < region->start)
 130                 return false;
 131         /* Item at least partially after region. */
 132         if (item->start + item->size > region->start + region->size)
 133                 return false;
 134         return true;
 135 }
 136
 137 static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
 138 {
 139         /* Item one is entirely before item two. */
 140         if (one->start + one->size <= two->start)
 141                 return false;
 142         /* Item one is entirely after item two. */
 143         if (one->start >= two->start + two->size)
 144                 return false;
 145         return true;
 146 }
 147
 148 static void mem_avoid_init(unsigned long input, unsigned long input_size,
 149                            unsigned long output, unsigned long output_size)
 150 {
 151         u64 initrd_start, initrd_size;
 152         u64 cmd_line, cmd_line_size;
 153         unsigned long unsafe, unsafe_len;
 154         char *ptr;
 155
 156         /*
 157          * Avoid the region that is unsafe to overlap during
 158          * decompression (see calculations in ../header.S).
 159          */
 160         unsafe_len = (output_size >> 12) + 32768 + 18;
 161         unsafe = (unsigned long)input + input_size - unsafe_len;
 162         mem_avoid[0].start = unsafe;
 163         mem_avoid[0].size = unsafe_len;
 164
 165         /* Avoid initrd. */
 166         initrd_start  = (u64)boot_params->ext_ramdisk_image << 32;
 167         initrd_start |= boot_params->hdr.ramdisk_image;
 168         initrd_size  = (u64)boot_params->ext_ramdisk_size << 32;
 169         initrd_size |= boot_params->hdr.ramdisk_size;
 170         mem_avoid[1].start = initrd_start;
 171         mem_avoid[1].size = initrd_size;
 172
 173         /* Avoid kernel command line. */
 174         cmd_line  = (u64)boot_params->ext_cmd_line_ptr << 32;
 175         cmd_line |= boot_params->hdr.cmd_line_ptr;
 176         /* Calculate size of cmd_line. */
 177         ptr = (char *)(unsigned long)cmd_line;
 178         for (cmd_line_size = 0; ptr[cmd_line_size++]; )
 179                 ;
 180         mem_avoid[2].start = cmd_line;
 181         mem_avoid[2].size = cmd_line_size;
 182
 183         /* Avoid heap memory. */
 184         mem_avoid[3].start = (unsigned long)free_mem_ptr;
 185         mem_avoid[3].size = BOOT_HEAP_SIZE;
 186
 187         /* Avoid stack memory. */
 188         mem_avoid[4].start = (unsigned long)free_mem_end_ptr;
 189         mem_avoid[4].size = BOOT_STACK_SIZE;
 190 }
 191
 192 /* Does this memory vector overlap a known avoided area? */
 193 static bool mem_avoid_overlap(struct mem_vector *img)
 194 {
 195         int i;
 196         struct setup_data *ptr;
 197
 198         for (i = 0; i < MEM_AVOID_MAX; i++) {
 199                 if (mem_overlaps(img, &mem_avoid[i]))
 200                         return true;
 201         }
 202
 203         /* Avoid all entries in the setup_data linked list. */
 204         ptr = (struct setup_data *)(unsigned long)boot_params->hdr.setup_data;
 205         while (ptr) {
 206                 struct mem_vector avoid;
 207
 208                 avoid.start = (unsigned long)ptr;
 209                 avoid.size = sizeof(*ptr) + ptr->len;
 210
 211                 if (mem_overlaps(img, &avoid))
 212                         return true;
 213
 214                 ptr = (struct setup_data *)(unsigned long)ptr->next;
 215         }
 216
 217         return false;
 218 }
 219
 220 static unsigned long slots[KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN];
 221 static unsigned long slot_max;
 222
 223 static void slots_append(unsigned long addr)
 224 {
 225         /* Overflowing the slots list should be impossible. */
 226         if (slot_max >= KERNEL_IMAGE_SIZE / CONFIG_PHYSICAL_ALIGN)
 227                 return;
 228
 229         slots[slot_max++] = addr;
 230 }
 231
 232 static unsigned long slots_fetch_random(void)
 233 {
 234         /* Handle case of no slots stored. */
 235         if (slot_max == 0)
 236                 return 0;
 237
 238         return slots[get_random_long() % slot_max];
 239 }
 240
 241 static void process_e820_entry(struct e820entry *entry,
 242                                unsigned long minimum,
 243                                unsigned long image_size)
 244 {
 245         struct mem_vector region, img;
 246
 247         /* Skip non-RAM entries. */
 248         if (entry->type != E820_RAM)
 249                 return;
 250
 251         /* Ignore entries entirely above our maximum. */
 252         if (entry->addr >= KERNEL_IMAGE_SIZE)
 253                 return;
 254
 255         /* Ignore entries entirely below our minimum. */
 256         if (entry->addr + entry->size < minimum)
 257                 return;
 258
 259         region.start = entry->addr;
 260         region.size = entry->size;
 261
 262         /* Potentially raise address to minimum location. */
 263         if (region.start < minimum)
 264                 region.start = minimum;
 265
 266         /* Potentially raise address to meet alignment requirements. */
 267         region.start = ALIGN(region.start, CONFIG_PHYSICAL_ALIGN);
 268
 269         /* Did we raise the address above the bounds of this e820 region? */
 270         if (region.start > entry->addr + entry->size)
 271                 return;
 272
 273         /* Reduce size by any delta from the original address. */
 274         region.size -= region.start - entry->addr;
 275
 276         /* Reduce maximum size to fit end of image within maximum limit. */
 277         if (region.start + region.size > KERNEL_IMAGE_SIZE)
 278                 region.size = KERNEL_IMAGE_SIZE - region.start;
 279
 280         /* Walk each aligned slot and check for avoided areas. */
 281         for (img.start = region.start, img.size = image_size ;
 282              mem_contains(&region, &img) ;
 283              img.start += CONFIG_PHYSICAL_ALIGN) {
 284                 if (mem_avoid_overlap(&img))
 285                         continue;
 286                 slots_append(img.start);
 287         }
 288 }
 289
 290 static unsigned long find_random_addr(unsigned long minimum,
 291                                       unsigned long size)
 292 {
 293         int i;
 294         unsigned long addr;
 295
 296         /* Make sure minimum is aligned. */
 297         minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);
 298
 299         /* Verify potential e820 positions, appending to slots list. */
 300         for (i = 0; i < boot_params->e820_entries; i++) {
 301                 process_e820_entry(&boot_params->e820_map[i], minimum, size);
 302         }
 303
 304         return slots_fetch_random();
 305 }
 306
 307 unsigned char *choose_random_location(unsigned char *input,
 308                                       unsigned long input_size,
 309                                       unsigned char *output,
 310                                       unsigned long output_size)
 311 {
 312         unsigned long choice = (unsigned long)output;
 313         unsigned long random_addr;
 314
 315 #ifdef CONFIG_HIBERNATION
 316         if (!cmdline_find_option_bool("kaslr")) {
 317                 warn("KASLR disabled: 'kaslr' not on cmdline (hibernation selected).");
 318                 goto out;
 319         }
 320 #else
 321         if (cmdline_find_option_bool("nokaslr")) {
 322                 warn("KASLR disabled: 'nokaslr' on cmdline.");
 323                 goto out;
 324         }
 325 #endif
 326
 327         boot_params->hdr.loadflags |= KASLR_FLAG;
 328
 329         /* Record the various known unsafe memory ranges. */
 330         mem_avoid_init((unsigned long)input, input_size,
 331                        (unsigned long)output, output_size);
 332
 333         /* Walk e820 and find a random address. */
 334         random_addr = find_random_addr(choice, output_size);
 335         if (!random_addr) {
 336                 warn("KASLR disabled: could not find suitable E820 region!");
 337                 goto out;
 338         }
 339
 340         /* Always enforce the minimum. */
 341         if (random_addr < choice)
 342                 goto out;
 343
 344         choice = random_addr;
 345 out:
 346         return (unsigned char *)choice;
 347 }