x86/entry/64: randomize kernel stack offset upon syscall
Subsystems (3)
RFC PATCH 1/1 x86/entry/64: randomize kernel stack offset upon syscall
If CONFIG_RANDOMIZE_KSTACK_OFFSET is selected, the kernel stack offset is randomized upon each entry to a system call after fixed location of pt_regs struct.
This feature is based on the original idea from the PaX's RANDKSTACK feature:
https://pax.grsecurity.net/docs/randkstack.txt
All the credits for the original idea goes to the PaX team. However, the design and implementation of RANDOMIZE_KSTACK_OFFSET differs greatly from the RANDKSTACK feature (see below).
Reasoning for the feature:
This feature aims to make considerably harder various stack-based attacks that rely on deterministic stack structure.
We have had many of such attacks in past [1],[2],[3] (just to name few), and as Linux kernel stack protections have been constantly improving (vmap-based stack allocation with guard pages, removal of thread_info, STACKLEAK), attackers have to find new ways for their exploits to work.
It is important to note that we currently cannot show a concrete attack that would be stopped by this new feature (given that other existing stack protections are enabled), so this is an attempt to be on a proactive side vs. catching up with existing successful exploits.
The main idea is that since the stack offset is randomized upon each system call, it is very hard for attacker to reliably land in any particular place on the thread stack when attack is performed. Also, since randomization is performed *after* pt_regs, the ptrace-based approach to discover randomization offset during a long-running syscall should not be possible.
[1] jon.oberheide.org/files/infiltrate12-thestackisback.pdf
[2] jon.oberheide.org/files/stackjacking-infiltrate11.pdf
[3] googleprojectzero.blogspot.com/2016/06/exploiting- recursion-in-linux-kernel_20.html
Design description:
During most of the kernel's execution, it runs on the "thread stack", which is allocated at fork.c/dup_task_struct() and stored in a per-task variable (tsk->stack). Since stack is growing downward, the stack top can be always calculated using task_top_of_stack(tsk) function, which essentially returns an address of tsk->stack + stack size. When VMAP_STACK is enabled, the thread stack is allocated from vmalloc space.
Thread stack is pretty deterministic on its structure - fixed in size, and upon every entry from a userspace to kernel on a
syscall the thread stack is started to be constructed from an address fetched from a per-cpu cpu_current_top_of_stack variable. The first element to be pushed to the thread stack is the pt_regs struct that stores all required CPU registers and sys call parameters.
The goal of RANDOMIZE_KSTACK_OFFSET feature is to add a random offset after the pt_regs has been pushed to the stack and the rest of thread stack (used during the syscall processing) every time a process issues a syscall. The source of randomness can be taken either from rdtsc or rdrand with performance implications listed below. The value of random offset is stored in a callee-saved register (r15 currently) and the maximum size of random offset is defined by __MAX_STACK_RANDOM_OFFSET value, which currently equals to 0xFF0.
As a result this patch introduces 8 bits of randomness
(bits 4 - 11 are randomized, bits 0-3 must be zero due to stack alignment) after pt_regs location on the thread stack.
The amount of randomness can be adjusted based on how much of the stack space we wish/can trade for security.
The main issue with this approach is that it slightly breaks the processing of last frame in the unwinder, so I have made a simple fix to the frame pointer unwinder (I guess others should be fixed similarly) and stack dump functionality to "jump" over the random hole at the end. My way of solving this is probably far from ideal, so I would really appreciate feedback on how to improve it.
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset (rdtsc): Simple syscall: 0.1803 microseconds
random_offset (rdrand): Simple syscall: 0.3702 microseconds
2) Andy's tests, misc-tests: ./timing_test_64 10M sys_enosys
base: 10000000 loops in 1.62224s = 162.22 nsec / loop
random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop
random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopComparison to grsecurity RANDKSTACK feature:
RANDKSTACK feature randomizes the location of the stack start (cpu_current_top_of_stack), i.e. location of pt_regs structure itself on the stack. Initially this patch followed the same approach, but during the recent discussions [4], it has been determined to be of a little value since, if ptrace functionality is available for an attacker, he can use PTRACE_PEEKUSR/PTRACE_POKEUSR api to read/write different offsets in the pt_regs struct, observe the cache behavior of the pt_regs accesses, and figure out the random stack offset.
Another big difference is that randomization is done upon syscall entry and not the exit, as with RANDKSTACK.
Also, as a result of the above two differences, the implementation of RANDKSTACK and RANDOMIZE_KSTACK_OFFSET has nothing in common.
[4] https://www.openwall.com/lists/kernel-hardening/2019/02/08/6
--- arch/Kconfig | 15 +++++++++++++++ arch/x86/Kconfig | 1 + arch/x86/entry/calling.h | 14 ++++++++++++++ arch/x86/entry/entry_64.S | 6 ++++++ arch/x86/include/asm/frame.h | 3 +++ arch/x86/kernel/dumpstack.c | 10 +++++++++- arch/x86/kernel/unwind_frame.c | 9 ++++++++- 7 files changed, 56 insertions(+), 2 deletions(-)
arch/Kconfig +15 -0
@@ -808,6 +808,21 @@ config VMAP_STACK the stack to map directly to the KASAN shadow map using a formula that is incorrect if the stack is in vmalloc space. +config HAVE_ARCH_RANDOMIZE_KSTACK_OFFSET + def_bool n + help + An arch should select this symbol if it can support kernel stack + offset randomization. + +config RANDOMIZE_KSTACK_OFFSET + default n + bool "Randomize kernel stack offset on syscall entry" + depends on HAVE_ARCH_RANDOMIZE_KSTACK_OFFSET + help + Enable this if you want the randomize kernel stack offset upon + each syscall entry. This causes kernel stack (after pt_regs) to + have a randomized offset upon executing each system call. + config ARCH_OPTIONAL_KERNEL_RWX def_bool n
arch/x86/Kconfig +1 -0
@@ -131,6 +131,7 @@ config X86 select HAVE_ARCH_TRANSPARENT_HUGEPAGE select HAVE_ARCH_TRANSPARENT_HUGEPAGE_PUD if X86_64 select HAVE_ARCH_VMAP_STACK if X86_64 + select HAVE_ARCH_RANDOMIZE_KSTACK_OFFSET if X86_64 select HAVE_ARCH_WITHIN_STACK_FRAMES select HAVE_CMPXCHG_DOUBLE select HAVE_CMPXCHG_LOCAL
arch/x86/entry/calling.h +14 -0
@@ -345,6 +345,20 @@ For 32-bit we have the following conventions - kernel is built with#endif .endm +.macro RANDOMIZE_KSTACK +#ifdef CONFIG_RANDOMIZE_KSTACK_OFFSET +/* prepare a random offset in rax */ + pushq %rax + xorq %rax, %rax + ALTERNATIVE "rdtsc", "rdrand %rax", X86_FEATURE_RDRAND + andq $__MAX_STACK_RANDOM_OFFSET, %rax + +/* store offset in r15 */ + movq %rax, %r15 + popq %rax +#endif +.endm +/* * This does 'call enter_from_user_mode' unless we can avoid it based on * kernel config or using the static jump infrastructure.
arch/x86/entry/entry_64.S +6 -0
@@ -167,13 +167,19 @@ GLOBAL(entry_SYSCALL_64_after_hwframe) PUSH_AND_CLEAR_REGS rax=$-ENOSYS + RANDOMIZE_KSTACK /* stores randomized offset in r15 */ + TRACE_IRQS_OFF /* IRQs are off. */ movq %rax, %rdi movq %rsp, %rsi + sub %r15, %rsp /* substitute random offset from rsp */ call do_syscall_64 /* returns with IRQs disabled */ + /* need to restore the gap */ + add %r15, %rsp /* add random offset back to rsp */ + TRACE_IRQS_IRETQ /* we're about to change IF */ /*
arch/x86/include/asm/frame.h +3 -0
@@ -4,6 +4,9 @@#include <asm/asm.h> +#ifdef CONFIG_RANDOMIZE_KSTACK_OFFSET +#define __MAX_STACK_RANDOM_OFFSET 0xFF0 +#endif /* * These are stack frame creation macros. They should be used by every * callable non-leaf asm function to make kernel stack traces more reliable.
arch/x86/kernel/dumpstack.c +9 -1
@@ -192,7 +192,6 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs,*/ for ( ; stack; stack =PTR_ALIGN (stack_info.next_sp,sizeof (long ))) {const char *stack_name; -if (get_stack_info (stack, task, &stack_info, &visit_mask)) {/* * We weren't on a valid stack. It's possible that
@@ -224,6 +223,9 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs,*/ for (; stack < stack_info.end; stack++) {unsigned long real_addr; +#ifdef CONFIG_RANDOMIZE_KSTACK_OFFSET +unsigned long left_gap; +#endif int reliable =0 ;unsigned long addr =READ_ONCE_NOCHECK (*stack); unsigned long *ret_addr_p =
@@ -272,6 +274,12 @@ void show_trace_log_lvl(struct task_struct *task, struct pt_regs *regs, regs =unwind_get_entry_regs (&state, &partial);if (regs)show_regs_if_on_stack (&stack_info, regs, partial); +#ifdef CONFIG_RANDOMIZE_KSTACK_OFFSET + left_gap = (unsigned long )regs - (unsigned long )stack; +/* if we reached last frame, jump over the random gap*/ +if (left_gap < __MAX_STACK_RANDOM_OFFSET) + stack = (unsigned long *)regs--; +#endif }if (stack_name)
arch/x86/kernel/unwind_frame.c +8 -1
@@ -98,7 +98,14 @@ static inline unsigned long *last_frame(struct unwind_state *state)static bool is_last_frame (struct unwind_state *state) { -return state->bp ==last_frame (state); +if (state->bp ==last_frame (state)) +return true; +#ifdef CONFIG_RANDOMIZE_KSTACK_OFFSET +if ((last_frame (state) - state->bp) < __MAX_STACK_RANDOM_OFFSET) +return true; +#endif +return false; + }#ifdef CONFIG_X86_32
Signature · 1 line
2.17.1
Andy Lutomirski
maintainerQuoted 72 lines · Elena Reshetova
If
CONFIG_RANDOMIZE_KSTACK_OFFSETis selected, the kernel stack offset is randomized upon each entry to a system call after fixed location ofpt_regsstruct.This feature is based on the original idea from the PaX's RANDKSTACK feature:
https://pax.grsecurity.net/docs/randkstack.txt
All the credits for the original idea goes to the PaX team. However, the design and implementation ofRANDOMIZE_KSTACK_OFFSETdiffers greatly from the RANDKSTACK feature (see below).Reasoning for the feature:
This feature aims to make considerably harder various stack-based attacks that rely on deterministic stack structure.
We have had many of such attacks in past [1],[2],[3] (just to name few), and as Linux kernel stack protections have been constantly improving (vmap-based stack allocation with guard pages, removal ofthread_info, STACKLEAK), attackers have to find new ways for their exploits to work.It is important to note that we currently cannot show a concrete attack that would be stopped by this new feature (given that other existing stack protections are enabled), so this is an attempt to be on a proactive side vs. catching up with existing successful exploits.
The main idea is that since the stack offset is randomized upon each system call, it is very hard for attacker to reliably land in any particular place on the thread stack when attack is performed. Also, since randomization is performed *after*
pt_regs, the ptrace-based approach to discover randomization offset during a long-running syscall should not be possible.[1] jon.oberheide.org/files/infiltrate12-thestackisback.pdf
[2] jon.oberheide.org/files/stackjacking-infiltrate11.pdf
[3] googleprojectzero.blogspot.com/2016/06/exploiting- recursion-in-linux-kernel_20.htmlDesign description:
During most of the kernel's execution, it runs on the "thread stack", which is allocated at fork.c/dup_task_struct() and stored in a per-task variable (
tsk->stack). Since stack is growing downward, the stack top can be always calculated usingtask_top_of_stack(tsk)function, which essentially returns an address oftsk->stack+ stack size. WhenVMAP_STACKis enabled, the thread stack is allocated from vmalloc space.Thread stack is pretty deterministic on its structure - fixed in size, and upon every entry from a userspace to kernel on a
syscall the thread stack is started to be constructed from an address fetched from a per-cpucpu_current_top_of_stackvariable. The first element to be pushed to the thread stack is thept_regsstruct that stores all required CPU registers and sys call parameters.The goal of
RANDOMIZE_KSTACK_OFFSETfeature is to add a random offset after thept_regshas been pushed to the stack and the rest of thread stack (used during the syscall processing) every time a process issues a syscall. The source of randomness can be taken either from rdtsc or rdrand with performance implications listed below. The value of random offset is stored in a callee-saved register (r15 currently) and the maximum size of random offset is defined by__MAX_STACK_RANDOM_OFFSETvalue, which currently equals to0xFF0.
Quoted 5 lines
As a result this patch introduces 8 bits of randomness
(bits 4 - 11 are randomized, bits 0-3 must be zero due to stack alignment) afterpt_regslocation on the thread stack.
The amount of randomness can be adjusted based on how much of the stack space we wish/can trade for security.
Why do you need four zero bits at the bottom? x86_64 Linux only maintains 8 byte stack alignment.
Quoted 7 lines
The main issue with this approach is that it slightly breaks the processing of last frame in the unwinder, so I have made a simple fix to the frame pointer unwinder (I guess others should be fixed similarly) and stack dump functionality to "jump" over the random hole at the end. My way of solving this is probably far from ideal, so I would really appreciate feedback on how to improve it.
That's probably a question for Josh :)
Another way to do the dirty work would be to do:
char *ptr = alloca(offset);
asm volatile ("" :: "m" (*ptr));in do_syscall_64() and adjust compiler flags as needed to avoid warnings. Hmm.
Quoted 8 lines
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microseconds
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosysbase: 10000000 loops in 1.62224s = 162.22 nsec / loop random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loop
Egads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
Quoted 13 lines
/*
* This does 'callenter_from_user_mode' unless we can avoid it based on
* kernel config or using the static jump infrastructure.arch/x86/entry/entry_64.S +2
-0@@ -167,13 +167,19 @@ GLOBAL(entry_SYSCALL_64_after_hwframe) PUSH_AND_CLEAR_REGS rax=$-ENOSYS + RANDOMIZE_KSTACK /* stores randomized offset in r15 */ +
arch/x86/entry/entry_64.S GLOBAL(entry_SYSCALL_64_after_hwframe) · line 181
Quoted 10 lines
arch/x86/entry/entry_64.S +3
-0TRACE_IRQS_OFF /* IRQs are off. */ movq %rax, %rdi movq %rsp, %rsi + sub %r15, %rsp /* substitute random offset from rsp */ call do_syscall_64 /* returns with IRQs disabled */ + /* need to restore the gap */ + add %r15, %rsp /* add random offset back to rsp */
Off the top of my head, the nicer way to approach this would be to change this such that mov %rbp, %rsp; popq %rbp or something like that will do the trick. Then the unwinder could just see it as a regular frame. Maybe Josh will have a better idea.
Quoted 9 lines · Andy Lutomirski
Quoted 7 lines · Elena Reshetova
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microseconds
Quoted 8 lines
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosysbase: 10000000 loops in 1.62224s = 162.22 nsec / loop random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopEgads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
RDRAND can also fail.
Quoted 3 lines
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
I'd like to avoid saving the _exact_ details of where the next offset will be, but if nothing else works, this should be okay. We can use 8 bits at a time and call prandom_u32() every 4th call. Something like prandom_bytes(), but where it doesn't throw away the unused bytes.
Signature · 1 line
Kees Cook
Quoted 21 lines · Andy Lutomirski
Quoted 9 lines
Quoted 7 lines · Elena Reshetova
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microsecondsQuoted 8 lines
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosysbase: 10000000 loops in 1.62224s = 162.22 nsec / loop random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopEgads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
RDRAND can also fail.
Quoted 8 lines
Quoted 3 lines
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
I'd like to avoid saving the _exact_ details of where the next offset will be, but if nothing else works, this should be okay. We can use 8 bits at a time and call
prandom_u32()every 4th call. Something likeprandom_bytes(), but where it doesn't throw away the unused bytes.
Actually I think this would make the end result even worse security-wise than simply using rdtsc() on every syscall. Saving the randomness in percpu buffer, which is probably easily accessible and can be probed if needed, would supply attacker with much more knowledge about the next 3-4 random offsets that what he would get if we use "weak" rdtsc. Given that for a successful exploit, an attacker would need to have stack aligned once only, having a knowledge of 3-4 next offsets sounds like a present to an exploit writer... Additionally it creates complexity around the code that I have issues justifying with "security" argument because of above...
I have the patch now with alloca() and rdtsc() working, I can post it (albeit it is very simple), but I am really hesitating on adding the percpu buffer randomness storage to it...
Best Regards,
Elena.
Andy Lutomirski
maintainerQuoted 41 lines · Elena
Quoted 22 lines · Andy Lutomirski
Quoted 9 lines
Quoted 7 lines · Elena Reshetova
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microsecondsQuoted 8 lines
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosysbase: 10000000 loops in 1.62224s = 162.22 nsec / loop random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopEgads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
RDRAND can also fail.
Quoted 8 lines
Quoted 3 lines
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
I'd like to avoid saving the _exact_ details of where the next offset will be, but if nothing else works, this should be okay. We can use 8 bits at a time and call
prandom_u32()every 4th call. Something likeprandom_bytes(), but where it doesn't throw away the unused bytes.Actually I think this would make the end result even worse security-wise than simply using
rdtsc()on every syscall. Saving the randomness in percpu buffer, which is probably easily accessible and can be probed if needed, would supply attacker with much more knowledge about the next 3-4 random offsets that what he would get if we use "weak" rdtsc. Given that for a successful exploit, an attacker would need to have stack aligned once only, having a knowledge of 3-4 next offsets sounds like a present to an exploit writer... Additionally it creates complexity around the code that I have issues justifying with "security" argument because of above...
Quoted 4 lines
I have the patch now with
alloca()andrdtsc()working, I can post it (albeit it is very simple), but I am really hesitating on adding the percpu buffer randomness storage to it...
Hmm. I guess it depends on what types of attack you care about. I bet that, if you do a bunch of iterations of mfence;rdtsc;syscall, you'll discover that the offset between the user rdtsc and the syscall's rdtsc has several values that occur with high probability.
--Andy
Quoted 34 lines · Andy Lutomirski
Quoted 31 lines · Elena
Quoted 30 lines · Andy Lutomirski
Quoted 9 lines
Quoted 7 lines · Elena Reshetova
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microsecondsQuoted 8 lines
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosysbase: 10000000 loops in 1.62224s = 162.22 nsec / loop random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopEgads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
RDRAND can also fail.
Quoted 3 lines
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
I'd like to avoid saving the _exact_ details of where the next offset will be, but if nothing else works, this should be okay. We can use 8 bits at a time and call
prandom_u32()every 4th call. Something likeprandom_bytes(), but where it doesn't throw away the unused bytes.
Quoted 9 lines
Quoted 9 lines
Actually I think this would make the end result even worse security-wise than simply using
rdtsc()on every syscall. Saving the randomness in percpu buffer, which is probably easily accessible and can be probed if needed, would supply attacker with much more knowledge about the next 3-4 random offsets that what he would get if we use "weak" rdtsc. Given that for a successful exploit, an attacker would need to have stack aligned once only, having a knowledge of 3-4 next offsets sounds like a present to an exploit writer... Additionally it creates complexity around the code that I have issues justifying with "security" argument because of above...
That certainly solidifies my concern against saving randomness. :)
Quoted 9 lines
Quoted 4 lines
I have the patch now with
alloca()andrdtsc()working, I can post it (albeit it is very simple), but I am really hesitating on adding the percpu buffer randomness storage to it...Hmm. I guess it depends on what types of attack you care about. I bet that, if you do a bunch of iterations of mfence;rdtsc;syscall, you'll discover that the offset between the user rdtsc and the syscall's rdtsc has several values that occur with high probability.
How about rdtsc xor with the middle word of the stack canary? (to avoid the 0-byte) Something like:
rdtsc
xorl [%gs:...canary....], %rax
andq $__MAX_STACK_RANDOM_OFFSET, %rax
I need to look at the right way to reference the canary during that code. Andy might know off the top of his head. :)
-Kees
Signature · 1 line
Kees Cook
Quoted 64 lines · Kees Cook
Quoted 36 lines · Andy Lutomirski
Quoted 31 lines · Elena
Quoted 30 lines
Quoted 11 lines · Andy Lutomirski
Quoted 7 lines · Elena Reshetova
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microsecondsQuoted 8 lines
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosys
base: 10000000 loops in 1.62224s = 162.22 nsec / loop
random_offset(rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop
random_offset(rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopEgads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
RDRAND can also fail.
Quoted 3 lines
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
I'd like to avoid saving the _exact_ details of where the next offset will be, but if nothing else works, this should be okay. We can use 8 bits at a time and call
prandom_u32()every 4th call. Something likeprandom_bytes(), but where it doesn't throw away the unused bytes.Quoted 9 lines
Quoted 9 lines
Actually I think this would make the end result even worse security-wise than simply using
rdtsc()on every syscall. Saving the randomness in percpu buffer, which is probably easily accessible and can be probed if needed, would supply attacker with much more knowledge about the next 3-4 random offsets that what he would get if we use "weak" rdtsc. Given that for a successful exploit, an attacker would need to have stack aligned once only, having a knowledge of 3-4 next offsets sounds like a present to an exploit writer... Additionally it creates complexity around the code that I have issues justifying with "security" argument because of above...That certainly solidifies my concern against saving randomness. :)
Quoted 9 lines
Quoted 4 lines
I have the patch now with
alloca()andrdtsc()working, I can post it (albeit it is very simple), but I am really hesitating on adding the percpu buffer randomness storage to it...Hmm. I guess it depends on what types of attack you care about. I bet that, if you do a bunch of iterations of mfence;rdtsc;syscall, you'll discover that the offset between the user rdtsc and the syscall's rdtsc has several values that occur with high probability.
How about rdtsc xor with the middle word of the stack canary? (to avoid the 0-byte) Something like:
Quoted 7 lines
rdtsc
xorl [%gs:...canary....], %rax
andq $__MAX_STACK_RANDOM_OFFSET, %raxI need to look at the right way to reference the canary during that code. Andy might know off the top of his head. :)
Doesn’t this just leak some of the canary to user code through side channels?
Quoted 1 line · Andy Lutomirski
Doesn’t this just leak some of the canary to user code through side channels?
Erf, yes, good point. Let's just use prandom and be done with it.
Signature · 1 line
Kees Cook
Quoted 4 lines · Andy Lutomirski
Quoted 1 line
Doesn’t this just leak some of the canary to user code through side channels?
Erf, yes, good point. Let's just use prandom and be done with it.
And here I have some numbers on this. Actually prandom turned out to be pretty fast, even when called every syscall. See the numbers below:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset (prandom_u32() every syscall): Simple syscall: 0.1822 microseconds
random_offset (prandom_u32() every 4th syscall): Simple syscall: 0.1844 microseconds
2) Andy's tests, misc-tests: ./timing_test_64 10M sys_enosys
base: 10000000 loops in 1.62224s = 162.22 nsec / loop
random_offset (prandom_u32() every syscall): 10000000 loops in 1.64660s = 166.26 nsec / loop
random_offset (prandom_u32() every 4th syscall): 10000000 loops in 3.51315s = 169.30 nsec / loopThe second case is when prandom is called only once in 4 syscalls and unused random
bits are preserved in a per-cpu buffer. As you can see it is actually slower (modulo my maybe not
so optimized code in prandom, see below) vs. calling it every time, so I would vote for actually calling it every time and saving on the hassle and also avoid additional code in prandom.
And below is what I was calling instead of prandom_u32() to preserve random bits (net_rand_state_buffer is a new per-cpu buffer I added to save random bits):
And I didn't include the check for bytes >= sizeof(u32) since this was just poc to test the base speed, but for generic case it would be needed.
+void prandom_bytes_preserve(void *buf, size_t bytes) +{
+ u32 *buffer = &get_cpu_var(net_rand_state_buffer);
+ u8 *ptr = buf;
+
+ if (!(*buffer)) {
+ struct rnd_state *state = &get_cpu_var(net_rand_state);
+ if (bytes > 0) {
+ *buffer = prandom_u32_state(state);
+ do {
+ *ptr++ = (u8) *buffer;
+ bytes--;
+ *buffer >>= BITS_PER_BYTE;
+ } while (bytes > 0);
+ }
+ put_cpu_var(net_rand_state);
+ put_cpu_var(net_rand_state_buffer);
+ } else {
+ if (bytes > 0) {
+ do {
+ *ptr++ = (u8) *buffer;
+ bytes--;
+ *buffer >>= BITS_PER_BYTE;+ } while (bytes > 0);
+ }
+ put_cpu_var(net_rand_state_buffer);
+ }
+}
I will send the first version of patch (calling prandom_u32() every time) shortly if anyone wants to double check performance implications.
Best Regards,
Elena.
Quoted 43 lines · Andy Lutomirski
Quoted 41 lines · Elena Reshetova
If
CONFIG_RANDOMIZE_KSTACK_OFFSETis selected, the kernel stack offset is randomized upon each entry to a system call after fixed location ofpt_regsstruct.This feature is based on the original idea from the PaX's RANDKSTACK feature:
https://pax.grsecurity.net/docs/randkstack.txt
All the credits for the original idea goes to the PaX team. However, the design and implementation ofRANDOMIZE_KSTACK_OFFSETdiffers greatly from the RANDKSTACK feature (see below).Reasoning for the feature:
This feature aims to make considerably harder various stack-based attacks that rely on deterministic stack structure.
We have had many of such attacks in past [1],[2],[3] (just to name few), and as Linux kernel stack protections have been constantly improving (vmap-based stack allocation with guard pages, removal ofthread_info, STACKLEAK), attackers have to find new ways for their exploits to work.It is important to note that we currently cannot show a concrete attack that would be stopped by this new feature (given that other existing stack protections are enabled), so this is an attempt to be on a proactive side vs. catching up with existing successful exploits.
The main idea is that since the stack offset is randomized upon each system call, it is very hard for attacker to reliably land in any particular place on the thread stack when attack is performed. Also, since randomization is performed *after*
pt_regs, the ptrace-based approach to discover randomization offset during a long-running syscall should not be possible.
Quoted 4 lines
Quoted 4 lines
[1] jon.oberheide.org/files/infiltrate12-thestackisback.pdf
[2] jon.oberheide.org/files/stackjacking-infiltrate11.pdf
[3] googleprojectzero.blogspot.com/2016/06/exploiting- recursion-in-linux-kernel_20.html
Now that thread_info is off the stack, and vmap stack guard pages exist, it's not clear to me what the benefit is.
Quoted 7 lines
Quoted 6 lines
The main issue with this approach is that it slightly breaks the processing of last frame in the unwinder, so I have made a simple fix to the frame pointer unwinder (I guess others should be fixed similarly) and stack dump functionality to "jump" over the random hole at the end. My way of solving this is probably far from ideal, so I would really appreciate feedback on how to improve it.
Quoted 8 lines
That's probably a question for Josh :)
Another way to do the dirty work would be to do:
char *ptr = alloca(offset); asm volatile ("" :: "m" (*ptr));in
do_syscall_64()and adjust compiler flags as needed to avoid warnings. Hmm.
I like the alloca() idea a lot. If you do the stack adjustment in C, then everything should just work, with no custom hacks in entry code or the unwinders.
Quoted 21 lines
Quoted 21 lines
/*
* This does 'callenter_from_user_mode' unless we can avoid it based on
* kernel config or using the static jump infrastructure.arch/x86/entry/entry_64.S +3
-0@@ -167,13 +167,19 @@ GLOBAL(entry_SYSCALL_64_after_hwframe) PUSH_AND_CLEAR_REGS rax=$-ENOSYS + RANDOMIZE_KSTACK /* stores randomized offset in r15 */ + TRACE_IRQS_OFF /* IRQs are off. */ movq %rax, %rdi movq %rsp, %rsi + sub %r15, %rsp /* substitute random offset from rsp */ call do_syscall_64 /* returns with IRQs disabled */
Quoted 7 lines
arch/x86/entry/entry_64.S GLOBAL(entry_SYSCALL_64_after_hwframe) · line 181
Quoted 2 lines
arch/x86/entry/entry_64.S +2
-0+ /* need to restore the gap */ + add %r15, %rsp /* add random offset back to rsp */Off the top of my head, the nicer way to approach this would be to change this such that mov %rbp, %rsp; popq %rbp or something like that will do the trick. Then the unwinder could just see it as a regular frame. Maybe Josh will have a better idea.
Yes, we could probably do something like that. Though I think I'd much rather do the alloca() thing.
Signature · 1 line
Josh
Quoted 44 lines · Andy Lutomirski
Quoted 43 lines
Quoted 41 lines · Elena Reshetova
If
CONFIG_RANDOMIZE_KSTACK_OFFSETis selected, the kernel stack offset is randomized upon each entry to a system call after fixed location ofpt_regsstruct.This feature is based on the original idea from the PaX's RANDKSTACK feature:
https://pax.grsecurity.net/docs/randkstack.txt
All the credits for the original idea goes to the PaX team. However, the design and implementation ofRANDOMIZE_KSTACK_OFFSETdiffers greatly from the RANDKSTACK feature (see below).Reasoning for the feature:
This feature aims to make considerably harder various stack-based attacks that rely on deterministic stack structure.
We have had many of such attacks in past [1],[2],[3] (just to name few), and as Linux kernel stack protections have been constantly improving (vmap-based stack allocation with guard pages, removal ofthread_info, STACKLEAK), attackers have to find new ways for their exploits to work.It is important to note that we currently cannot show a concrete attack that would be stopped by this new feature (given that other existing stack protections are enabled), so this is an attempt to be on a proactive side vs. catching up with existing successful exploits.
The main idea is that since the stack offset is randomized upon each system call, it is very hard for attacker to reliably land in any particular place on the thread stack when attack is performed. Also, since randomization is performed *after*
pt_regs, the ptrace-based approach to discover randomization offset during a long-running syscall should not be possible.
Quoted 7 lines
Quoted 4 lines
Quoted 4 lines
[1] jon.oberheide.org/files/infiltrate12-thestackisback.pdf
[2] jon.oberheide.org/files/stackjacking-infiltrate11.pdf
[3] googleprojectzero.blogspot.com/2016/06/exploiting- recursion-in-linux-kernel_20.htmlNow that
thread_infois off the stack, and vmap stack guard pages exist, it's not clear to me what the benefit is.
Yes, as it says above, this is an attempt to be proactive vs. reactive. We cannot show concrete attack now that would succeed with vmap stack enabled, thread_info removed and other protections enabled. However, the fact that kernel thread stack is still very deterministic remains, and this feature of it has been utilized many times in attacks. We don't know where creative attackers would go next and what they can use to mount next kernel stack-based attack, but I think this is just a question of time. I don't believe we can claim that currently Linux kernel thread stack is immune from attacks.
So, if we can add a protection that is not invasive, both on code and performance, and which might make the attacker's life considerably harder, why not making it?
Quoted 12 lines
Quoted 12 lines
Quoted 7 lines
The main issue with this approach is that it slightly breaks the processing of last frame in the unwinder, so I have made a simple fix to the frame pointer unwinder (I guess others should be fixed similarly) and stack dump functionality to "jump" over the random hole at the end. My way of solving this is probably far from ideal, so I would really appreciate feedback on how to improve it.
That's probably a question for Josh :)
Another way to do the dirty work would be to do:
Quoted 8 lines
Quoted 4 lines
char *ptr = alloca(offset); asm volatile ("" :: "m" (*ptr));in
do_syscall_64()and adjust compiler flags as needed to avoid warnings. Hmm.I like the
alloca()idea a lot. If you do the stack adjustment in C, then everything should just work, with no custom hacks in entry code or the unwinders.
Ok, so maybe this is what I am going to try next then.
Best Regards,
Elena.
From: Andy Lutomirski
Quoted 1 line
Sent: 18 March 2019 20:16
...
Quoted 8 lines
Quoted 5 lines
As a result this patch introduces 8 bits of randomness
(bits 4 - 11 are randomized, bits 0-3 must be zero due to stack alignment) afterpt_regslocation on the thread stack.
The amount of randomness can be adjusted based on how much of the stack space we wish/can trade for security.Why do you need four zero bits at the bottom?
x86_64Linux only maintains 8 byte stack alignment.
ISTR that the gcc developers arbitrarily changed the alignment a few years ago.
If the stack is only 8 byte aligned and you allocate a variable that requires 16 byte alignment you need gcc to generate the extra stack frame to align the stack.
I don't remember seeing the relevant gcc options on the linux gcc command lines.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Quoted 15 lines · David Laight
From: Andy Lutomirski
Quoted 1 line
Sent: 18 March 2019 20:16
...
Quoted 8 lines
Quoted 5 lines
As a result this patch introduces 8 bits of randomness
(bits 4 - 11 are randomized, bits 0-3 must be zero due to stack alignment) afterpt_regslocation on the thread stack.
The amount of randomness can be adjusted based on how much of the stack space we wish/can trade for security.Why do you need four zero bits at the bottom?
x86_64Linux only maintains 8 byte stack alignment.
Quoted 8 lines
ISTR that the gcc developers arbitrarily changed the alignment a few years ago.
If the stack is only 8 byte aligned and you allocate a variable that requires 16 byte alignment you need gcc to generate the extra stack frame to align the stack.
I don't remember seeing the relevant gcc options on the linux gcc command lines.
On older gcc, you *can’t* set the relevant command line options because gcc was daft. So we just crossed out fingers and hope led for the best. On newer gcc, we set the options. Fortunately, 32-byte stack variable alignment works regardless.
AFAIK x86_64 Linux has never aligned the stack to 16 bytes.
Smth is really weird with my intel mail: it only now delivered
me all messages in one go and I was thinking that I don't get any feedback...
Quoted 71 lines
Quoted 71 lines
If
CONFIG_RANDOMIZE_KSTACK_OFFSETis selected, the kernel stack offset is randomized upon each entry to a system call after fixed location ofpt_regsstruct.This feature is based on the original idea from the PaX's RANDKSTACK feature:
https://pax.grsecurity.net/docs/randkstack.txt
All the credits for the original idea goes to the PaX team. However, the design and implementation ofRANDOMIZE_KSTACK_OFFSETdiffers greatly from the RANDKSTACK feature (see below).Reasoning for the feature:
This feature aims to make considerably harder various stack-based attacks that rely on deterministic stack structure.
We have had many of such attacks in past [1],[2],[3] (just to name few), and as Linux kernel stack protections have been constantly improving (vmap-based stack allocation with guard pages, removal ofthread_info, STACKLEAK), attackers have to find new ways for their exploits to work.It is important to note that we currently cannot show a concrete attack that would be stopped by this new feature (given that other existing stack protections are enabled), so this is an attempt to be on a proactive side vs. catching up with existing successful exploits.
The main idea is that since the stack offset is randomized upon each system call, it is very hard for attacker to reliably land in any particular place on the thread stack when attack is performed. Also, since randomization is performed *after*
pt_regs, the ptrace-based approach to discover randomization offset during a long-running syscall should not be possible.[1] jon.oberheide.org/files/infiltrate12-thestackisback.pdf
[2] jon.oberheide.org/files/stackjacking-infiltrate11.pdf
[3] googleprojectzero.blogspot.com/2016/06/exploiting- recursion-in-linux-kernel_20.htmlDesign description:
During most of the kernel's execution, it runs on the "thread stack", which is allocated at fork.c/dup_task_struct() and stored in a per-task variable (
tsk->stack). Since stack is growing downward, the stack top can be always calculated usingtask_top_of_stack(tsk)function, which essentially returns an address oftsk->stack+ stack size. WhenVMAP_STACKis enabled, the thread stack is allocated from vmalloc space.Thread stack is pretty deterministic on its structure - fixed in size, and upon every entry from a userspace to kernel on a
syscall the thread stack is started to be constructed from an address fetched from a per-cpucpu_current_top_of_stackvariable. The first element to be pushed to the thread stack is thept_regsstruct that stores all required CPU registers and sys call parameters.The goal of
RANDOMIZE_KSTACK_OFFSETfeature is to add a random offset after thept_regshas been pushed to the stack and the rest of thread stack (used during the syscall processing) every time a process issues a syscall. The source of randomness can be taken either from rdtsc or rdrand with performance implications listed below. The value of random offset is stored in a callee-saved register (r15 currently) and the maximum size of random offset is defined by__MAX_STACK_RANDOM_OFFSETvalue, which currently equals to0xFF0.
Quoted 8 lines
Quoted 5 lines
As a result this patch introduces 8 bits of randomness
(bits 4 - 11 are randomized, bits 0-3 must be zero due to stack alignment) afterpt_regslocation on the thread stack.
The amount of randomness can be adjusted based on how much of the stack space we wish/can trade for security.Why do you need four zero bits at the bottom?
x86_64Linux only maintains 8 byte stack alignment.
I have to check this: it did look to me that this is needed to avoid alignment issues, but maybe it is my mistake.
Quoted 8 lines
Quoted 7 lines
The main issue with this approach is that it slightly breaks the processing of last frame in the unwinder, so I have made a simple fix to the frame pointer unwinder (I guess others should be fixed similarly) and stack dump functionality to "jump" over the random hole at the end. My way of solving this is probably far from ideal, so I would really appreciate feedback on how to improve it.
Quoted 8 lines
That's probably a question for Josh :)
Another way to do the dirty work would be to do:
char *ptr = alloca(offset); asm volatile ("" :: "m" (*ptr));in
do_syscall_64()and adjust compiler flags as needed to avoid warnings. Hmm.
I was hoping to go away with assembly-only and minimal changes, but if this approach seems better for you and Josh, then I guess I can do it this way.
Quoted 9 lines
Quoted 9 lines
Performance:
1) lmbench: ./lat_syscall -N 1000000 null
base: Simple syscall: 0.1774 microseconds
random_offset(rdtsc): Simple syscall: 0.1803 microseconds
random_offset(rdrand): Simple syscall: 0.3702 microseconds
Quoted 8 lines
Quoted 5 lines
2) Andy's tests, misc-tests: ./timing_test_64 10M
sys_enosysbase: 10000000 loops in 1.62224s = 162.22 nsec / loop random_offset (rdtsc): 10000000 loops in 1.64660s = 164.66 nsec / loop random_offset (rdrand): 10000000 loops in 3.51315s = 351.32 nsec / loopEgads! RDTSC is nice and fast but probably fairly easy to defeat. RDRAND is awful. I had hoped for better.
Yes, it is very very slow, I actually didn't believe my measurements first thinking that it cannot be so much slower just because of one instruction difference, but it looks like it can...
Quoted 4 lines
So perhaps we need a little percpu buffer that collects 64 bits of randomness at a time, shifts out the needed bits, and refills the buffer when we run out.
Hm... We might have to refill pretty often on a syscall-hungry workloads. If we need 8 bits for each sys call, then we will refill every 8 syscalls, which is of course better than each one, but is it an acceptable penalty? And then there is also a storage issue of our offset bits as Kees mentioned.
Quoted 22 lines
Quoted 22 lines
/*
* This does 'callenter_from_user_mode' unless we can avoid it based on
* kernel config or using the static jump infrastructure.arch/x86/entry/entry_64.S +3
-0@@ -167,13 +167,19 @@ GLOBAL(entry_SYSCALL_64_after_hwframe) PUSH_AND_CLEAR_REGS rax=$-ENOSYS + RANDOMIZE_KSTACK /* stores randomized offset in r15 */ + TRACE_IRQS_OFF /* IRQs are off. */ movq %rax, %rdi movq %rsp, %rsi + sub %r15, %rsp /* substitute random offset from rsp */ call do_syscall_64 /* returns with IRQs disabled */
Quoted 7 lines
arch/x86/entry/entry_64.S GLOBAL(entry_SYSCALL_64_after_hwframe) · line 181
Quoted 2 lines
arch/x86/entry/entry_64.S +2
-0+ /* need to restore the gap */ + add %r15, %rsp /* add random offset back to rsp */Off the top of my head, the nicer way to approach this would be to change this such that mov %rbp, %rsp; popq %rbp or something like that will do the trick. Then the unwinder could just see it as a regular frame. Maybe Josh will have a better idea.
I tried it with rbp, but I could not get it working as with other callee saved registers. But since alloca method seems to be more preferable, maybe it is not worth investigating this further.
Best Regards,
Elena.