linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "Reshetova, Elena" <elena.reshetova@intel.com>
To: Kees Cook <keescook@chromium.org>, Ingo Molnar <mingo@kernel.org>,
	"Andy Lutomirski" <luto@kernel.org>
Cc: David Laight <David.Laight@aculab.com>,
	Theodore Ts'o <tytso@mit.edu>, Eric Biggers <ebiggers3@gmail.com>,
	"ebiggers@google.com" <ebiggers@google.com>,
	"herbert@gondor.apana.org.au" <herbert@gondor.apana.org.au>,
	Peter Zijlstra <peterz@infradead.org>,
	"Daniel Borkmann" <daniel@iogearbox.net>,
	"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
	"jpoimboe@redhat.com" <jpoimboe@redhat.com>,
	"jannh@google.com" <jannh@google.com>,
	"Perla, Enrico" <enrico.perla@intel.com>,
	"mingo@redhat.com" <mingo@redhat.com>,
	"bp@alien8.de" <bp@alien8.de>,
	"tglx@linutronix.de" <tglx@linutronix.de>,
	"gregkh@linuxfoundation.org" <gregkh@linuxfoundation.org>,
	"Edgecombe, Rick P" <rick.p.edgecombe@intel.com>,
	Linus Torvalds <torvalds@linux-foundation.org>,
	Peter Zijlstra <a.p.zijlstra@chello.nl>
Subject: RE: [PATCH] x86/entry/64: randomize kernel stack offset upon syscall
Date: Tue, 28 May 2019 12:28:53 +0000	[thread overview]
Message-ID: <2236FBA76BA1254E88B949DDB74E612BA4CA8DBF@IRSMSX102.ger.corp.intel.com> (raw)
In-Reply-To: <201905120705.4F27DF3244@keescook>

> > With 5 bits there's a ~96.9% chance of crashing the system in an attempt,
> > the exploit cannot be used for a range of attacks, including spear
> > attacks and fast-spreading worms, right? A crashed and inaccessible
> > system also increases the odds of leaving around unfinished attack code
> > and leaking a zero-day attack.
> 
> Yup, which is why I'd like to have _something_ here without us getting
> lost in the "perfect entropy" weeds. :)

I really start to believe that we cannot make good randomness sources behave
fast enough for per-syscall usage if our target is 1-2% overhead under worst possible
(and potentially unrealistic ) scenario (stress test of some simple syscall like getpid()).
The only thing that would fit the margin is indeed rdtsc().

I profiled the path in use with get_random_bytes() and results look like this 
(arch_get_random_long in not inline for measurement purpose here):

> >
> >                |          |          |           --9.44%--random_get_byte
> >                |          |          |                     |
> >                |          |          |                      --8.08%--get_random_bytes
> >                |          |          |                                |
> >                |          |          |                                 --7.80%--_extract_crng.constprop.45
> >                |          |          |                                           |
> >                |          |          |                                           |--4.95%--arch_get_random_long
> >                |          |          |                                           |
> >                |          |          |                                            --2.39%--chacha_block


And here is the proof that under such usage _extract_crng bottlenecks on rdrand: 

PerfTop:    5877 irqs/sec  kernel:78.6%  exact: 100.0% [4000Hz cycles:ppp],  (all, 8 CPUs)
------------------------------------------------------------------------------------------------------------------------------------
Showing cycles:ppp for _extract_crng.constprop.46
  Events  Pcnt (>=5%)
 Percent | Source code & Disassembly of kcore for cycles:ppp (2104 samples, percent: local period)
-------------------------------------------------------------------------------------------------------
    0.00 :   ffffffff9abd1a62:       mov    $0xa,%edx
   97.94 :   ffffffff9abd1a67:       rdrand %rax

And then of course there is chacha permutation itself. So, I think Andy's proposal to rewrite 
"get_random_bytes" for speed is not so easy to implement. 

So, given that all we want is to raise the bar for attackers to predict the stack location
on subsequent syscall, is it really worth to try to come up with more complex solutions than
just using lower bits of rdtsc() by default? 

One idea that I got suggested last week is to create a pool of good randomness and
 then during syscall select a random number from the pool using smth rdtsc()%POOL_SIZE.
Pool would need to be refilled periodically, outside of syscall path to maintain diversity. 
I can try this approach, if people believe that it would address the security concerns around
rdtsc() (my personal feeling is that one can still time attack this if we assume that rdtsc
can be attacked and complexity of the whole thing increases considerably). 

If we decide that this is too much trouble for just 5 bits of randomness we need per syscall, I would 
still propose we reconsider original rdtsc() approach since it is still better than nothing. 
We can have the whole thing on three levels:

CONFIG_RANDOMIZE_KSTACK_OFFSET - off - no randomization, like now
CONFIG_RANDOMIZE_KSTACK_OFFSET on with rdtsc(), fast, better than nothing, but prone to 
timing attacks
CONFIG_RANDOMIZE_KSTACK_OFFSET based on get_random_bytes() with better security guarantees. 

Performance numbers for  will approx. look like

No randomization: 			Simple syscall: 0.0534 microseconds
With rdtsc():				Simple syscall: 0.0539 microseconds
Wih get_random_bytes(4096 buffer): 	Simple syscall: 0.0597 microseconds

Pure rdrand option with calling rdrand_long every 10th syscall is considerably slower

With rdrand (every 10th syscall):		Simple syscall: 0.0719 microseconds

And I guess we should once again remember that these are *not* the numbers that real
users will see in practice since I doubt we have the real loads issuing millions of *very
lightweight* syscalls in a loop, so this is really more "theoretical, worst case ever" numbers. 

If someone could actually propose a reasonable *practical* workload to measure with, 
then we can see what is the overhead on that both for rdtsc and get_random_bytes(). 

Best Regards,
Elena.



  reply	other threads:[~2019-05-28 12:29 UTC|newest]

Thread overview: 81+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-04-15  6:09 [PATCH] x86/entry/64: randomize kernel stack offset upon syscall Elena Reshetova
2019-04-15  7:25 ` Ingo Molnar
2019-04-15  8:44   ` Reshetova, Elena
2019-04-16  7:34     ` Ingo Molnar
2019-04-16 11:10       ` Reshetova, Elena
2019-04-16 12:08         ` Peter Zijlstra
2019-04-16 12:45           ` David Laight
2019-04-16 15:43             ` Theodore Ts'o
2019-04-16 16:07               ` Peter Zijlstra
2019-04-16 16:47               ` Reshetova, Elena
2019-04-17  9:28                 ` David Laight
2019-04-17 15:15                   ` Theodore Ts'o
2019-04-17 15:40                     ` Kees Cook
2019-04-17 15:53                     ` David Laight
2019-04-24 11:42                       ` Reshetova, Elena
2019-04-24 13:33                         ` David Laight
2019-04-25 11:23                           ` Reshetova, Elena
2019-04-26 11:33                         ` Reshetova, Elena
2019-04-26 14:01                           ` Theodore Ts'o
2019-04-26 17:44                             ` Eric Biggers
2019-04-26 18:02                               ` Theodore Ts'o
2019-04-27 13:59                                 ` Andy Lutomirski
2019-04-29  8:04                               ` Reshetova, Elena
2019-04-26 18:34                             ` Andy Lutomirski
2019-04-29  7:46                               ` Reshetova, Elena
2019-04-29 16:08                                 ` Andy Lutomirski
2019-04-30 17:51                                   ` Reshetova, Elena
2019-04-30 18:01                                     ` Kees Cook
2019-05-01  8:23                                     ` David Laight
2019-05-02  8:07                                       ` Reshetova, Elena
2019-05-01  8:41                                     ` David Laight
2019-05-01 23:33                                       ` Andy Lutomirski
2019-05-02  8:15                                       ` Reshetova, Elena
2019-05-02  9:23                                         ` David Laight
2019-05-02 14:47                                           ` Andy Lutomirski
2019-05-02 15:08                                             ` Ingo Molnar
2019-05-02 16:32                                               ` Andy Lutomirski
2019-05-02 16:43                                                 ` Ingo Molnar
2019-05-03 16:40                                                   ` Andy Lutomirski
2019-05-02 16:34                                               ` David Laight
2019-05-02 16:45                                                 ` Ingo Molnar
2019-05-03 16:17                                                   ` Reshetova, Elena
2019-05-03 16:40                                                     ` David Laight
2019-05-03 19:10                                                       ` Linus Torvalds
2019-05-06  6:47                                                         ` Reshetova, Elena
2019-05-06  7:01                                                       ` Reshetova, Elena
2019-05-08 11:18                                                       ` Reshetova, Elena
2019-05-08 11:32                                                         ` Ingo Molnar
2019-05-08 13:22                                                           ` Reshetova, Elena
2019-05-09  5:59                                                             ` Ingo Molnar
2019-05-09  7:01                                                               ` Reshetova, Elena
2019-05-09  8:43                                                                 ` Ingo Molnar
2019-05-11 22:45                                                                   ` Andy Lutomirski
2019-05-12  0:12                                                                     ` Kees Cook
2019-05-12  8:02                                                                       ` Ingo Molnar
2019-05-12 14:33                                                                         ` Kees Cook
2019-05-28 12:28                                                                           ` Reshetova, Elena [this message]
2019-05-28 13:33                                                                             ` Theodore Ts'o
2019-05-29 10:13                                                                               ` Reshetova, Elena
2019-05-29 10:51                                                                                 ` David Laight
2019-05-29 18:35                                                                                 ` Kees Cook
2019-05-29 18:37                                                                                 ` Kees Cook
2019-07-29 11:41                                                                                   ` Reshetova, Elena
2019-07-30 18:07                                                                                     ` Kees Cook
2019-08-01  6:35                                                                                     ` Reshetova, Elena
2019-05-09  7:03                                                               ` Reshetova, Elena
2019-05-06  7:32                                               ` Reshetova, Elena
2019-04-29  7:49                             ` Reshetova, Elena
2019-04-26 17:37                           ` Edgecombe, Rick P
2019-04-17  6:24               ` Ingo Molnar
2019-04-16 18:19           ` Reshetova, Elena
     [not found] <20190408061358.21288-1-elena.reshetova@intel.com>
2019-04-08 12:49 ` Josh Poimboeuf
2019-04-08 13:30   ` Reshetova, Elena
2019-04-08 16:21     ` Kees Cook
2019-04-10  8:26   ` Ingo Molnar
2019-04-10  9:00     ` Reshetova, Elena
2019-04-10 10:17       ` Ingo Molnar
2019-04-10 10:24       ` Reshetova, Elena
2019-04-10 14:52         ` Andy Lutomirski
2019-04-12  5:36           ` Reshetova, Elena
2019-04-12 21:16             ` Andy Lutomirski

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=2236FBA76BA1254E88B949DDB74E612BA4CA8DBF@IRSMSX102.ger.corp.intel.com \
    --to=elena.reshetova@intel.com \
    --cc=David.Laight@aculab.com \
    --cc=a.p.zijlstra@chello.nl \
    --cc=bp@alien8.de \
    --cc=daniel@iogearbox.net \
    --cc=ebiggers3@gmail.com \
    --cc=ebiggers@google.com \
    --cc=enrico.perla@intel.com \
    --cc=gregkh@linuxfoundation.org \
    --cc=herbert@gondor.apana.org.au \
    --cc=jannh@google.com \
    --cc=jpoimboe@redhat.com \
    --cc=keescook@chromium.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luto@kernel.org \
    --cc=mingo@kernel.org \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=rick.p.edgecombe@intel.com \
    --cc=tglx@linutronix.de \
    --cc=torvalds@linux-foundation.org \
    --cc=tytso@mit.edu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).