Message-ID: <1470011071.890.132.camel@gmail.com>
Date:	Sun, 31 Jul 2016 20:24:31 -0400
From:	Daniel Micay <danielmicay@...il.com>
To:	kernel-hardening@...ts.openwall.com
Cc:	Nick Kralevich <nnk@...gle.com>,
	"Roberts, William C" <william.c.roberts@...el.com>,
	"linux-mm@...ck.org" <linux-mm@...ck.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"akpm@...ux-foundation.org" <akpm@...ux-foundation.org>,
	"keescook@...omium.org" <keescook@...omium.org>,
	"gregkh@...uxfoundation.org" <gregkh@...uxfoundation.org>,
	"jeffv@...gle.com" <jeffv@...gle.com>,
	"salyzyn@...roid.com" <salyzyn@...roid.com>,
	"dcashman@...roid.com" <dcashman@...roid.com>
Subject: Re: [kernel-hardening] Re: [PATCH] [RFC] Introduce mmap
 randomization

> > It's very hard to quantify the benefits of fine-grained
> > randomization,
> 
> ?  N = # of possible addresses.  The bigger N is, the more chances the
> attacker will trip up before finding what they were looking for.

If the attacker is forcing the creation of many objects with a function
pointer and then trying to hit one, the only thing that would help is if
the heap is very sparse with random bases within it. They don't need to
hit a specific object for an exploit to work.

The details of how the randomization is done and the guarantees that are
provided certainly matter. Individual random gaps are low entropy and
they won't add up to much higher entropy randomization even for two
objects that are far apart. The entropy has no chance to build up since
the sizes will average out.

I'm not saying it doesn't make sense to do this (it's a feature that I
really want), but there are a lot of ways to approach fine-grained mmap
randomization and the design decisions should be justified and their
impact analyzed/measured.

> > but there are other useful guarantees you could provide. It would be
> > quite helpful for the kernel to expose the option to force a
> > PROT_NONE
> > mapping after every allocation. The gaps should actually be
> > enforced.
> > 
> > So perhaps 3 things, simply exposed as off-by-default sysctl options
> > (no need for special treatment on 32-bit):
> 
> I'm certainly not an mm-developer, but this looks to me like we're
> pushing the work of creating efficient, random mappings out to
> userspace.  :-/

Exposing configuration doesn't push work to userspace. I can't see any
way that this would be done by default even on 64-bit due to the extra
VMAs, so it really needs configuration.

> > a) configurable minimum gap size in pages (for protection against
> > linear and small {under,over}flows) b) configurable minimum gap size
> > based on a ratio to allocation size (for making the heap sparse to
> > mitigate heap sprays, especially when mixed with fine-grained
> > randomization - for example 2x would add a 2M gap after a 1M
> > mapping)
> 
> mmm, this looks like an information leak.  Best to set a range of
> pages
> and pick a random number within that range for each call.

A minimum gap size provides guarantees not offered by randomization
alone. It might not make sense to approach making the heap sparse by
forcing it separately from randomization, but doing it isn't leaking
information.

Obviously the random gap would be chosen by picking a maximum size (n)
and choosing a size between [0, n], which was the next potential
variable, separate from these non-randomization-related guarantees.

> > c) configurable maximum random gap size (the random gap would be in
> > addition to the enforced minimums)
> > 
> > The randomization could just be considered an extra with minor
> > benefits rather than the whole feature. A full fine-grained
> > randomization implementation would need a higher-level form of
> > randomization than gaps in the kernel along with cooperation from
> > userspace allocators. This would make sense as one part of it
> > though.
> 
> Ok, so here's an idea.  This idea could be used in conjunction with
> random gaps, or on it's own.  It would be enhanced by userspace random
> load order.
> 
> The benefit is that with 32bit address space, and no random gapping,
> it's still not wasting much space.
> 
> Given a memory space, break it up into X bands such that there are 2*X
> possible addresses.
> 
>   |A     B|C     D|E     F|G     H| ... |2*X-2  2*X-1|
>   |--> <--|--> <--|--> <--|--> <--| ... |-->      <--|
> min                                                  max
> 
> For each call to mmap, we randomly pick a value within [0 - 2*X).
> Assuming A=0 in the diagram above, even values grow up, odd values
> grow
> down.  Gradually consuming the single gap in the middle of each band.
> 
> How many bands to use would depend on:
>   * 32/64bit
>   * Average number of mmap calls
>   * largest single mmap call usually seen
>   * if using random gaps and range used
> 
> If the free gap in a chosen band is too small for the request, pick
> again among the other bands.
> 
> Again, I'm not an mm dev, so I might be totally smoking crack on this
> one...
> 
> thx,
> 
> Jason.

Address space fragmentation matters a lot, not only wasted space due to
memory that's explicitly reserved for random gaps. The randomization
guarantees under situations like memory exhaustion also matter.

I do think fine-grained randomization would be useful, but I think it's
unclear what a good approach would be, along with what the security
benefits would be. The malloc implementation is also very relevant.

OpenBSD has fine-grained mmap randomization with a fair bit of thought
put into how it works, but I don't think there has been much analysis of
it. The security properties really aren't clear.
Download attachment "signature.asc" of type "application/pgp-signature" (852 bytes)

Powered by blists - more mailing lists