Re: Protecting against Pointer Subterfuge (Redux)

[pageexec () freemail hu]

On 6 Oct 2006 at 11:50, Ben Nagy wrote:

> > > Steven Alexander:
> > > The variable rotation does increase security because it 
> > > decreases the predictability with which an attacker can
> > > manipulate a program.
>
> From here, pagexec unless marked otherwise:
> > the variable rotation in the presented form *cannot* possibly increase
> > security:
>
> I disagree. There may be some rotations, for example, where nothing
> interesting is reachable because of the 8 bits that you can manipulate.
> That is both possible and would increase security.

"i disagree. there may be rotations, for example, where something
interesting is reachable because of the 8 bits that you can manipulate.
that is both possible and would decrease security."

does it sound familiar? contradicting? or just plain naive? ;-)

both statements rely on one assumption: that the non-rotating case
produces more good or bad addresses, respectively. you can't in
general assume that without rotation we'll get more good addresses
than bad ones (which would make your statement correct) or without
rotation we'll always get more bad addresses than good ones (which
would make my paraphrased statement correct).

if you want to quantify then you'll have to produce real life test
cases and see what you get. till then i rely on math and continue
to state that knowing the rotation amount because it is derived
from the cookie cannot possibly increase security (and i said, it
doesn't matter in the end, a work factor of 32 only).

> If you look at the scheme without rotation, you will have access to 256
> addresses, but they will all be nearby the original pointer - and that
> pointer is very likely to be somewhere nice.

very likely? and how likely is it that there's no nice insn there?
and how likely is it that with added rotation you turn that useless
address into a useful one? see, your argument cuts both ways ;-).

> It could, in fact, be like a cabbage patch in the middle of the desert.
> Would you rather get a location in the cabbage patch or a random
> location anywhere in the desert? 

if my cabbage patch happens to be full of int3 paddings then no,
i think i'll take the random location any day.

> > so you're saying that on one hand, variable rotation 
> > increases security
> > but on the other hand it gives the attacker more flexibility, 
> > how's that
> > for a contradiction? ;-)
>
> I don't see it as a contradiction. If I had a choice between, say,
> overwriting 4 bytes at a random stack location or 4 bytes at a totally
> random location I know which I'd pick.

on a non-exec stack as well? ;-)

> > > Michael Howard said:
> > as i alluded to at the beginning, there's a lesson here. in security,
> > what i call 'naive common sense' reasoning often falls on its face,
> > which is the case here. the naivety here is the assumption that 8 bits
> > of input (for a single byte partial overwrite) provided by 
> > the attacker
> > will affect 8 bits of output in the plaintext pointer.
>
> Uh... that seems like a fair assumption to me. Each 8 bit overwrite _will_
> affect exactly 8 bits in the plaintext pointer. 

for a given address/cookie pair certainly. but in brute force we're not
dealing with a given address/cookie pair, but many and that's where the
attack surface explosion occurs. whether you get the address/cookie pairs
on one machine or many has no bearing on the fact that the rotation
increases the number of reachable addresses.

> [...]
> > this in turn means that when an attacker brute forces the 32 bits of
> > randomness in the XOR cookie, he'll also get to influence more than
> > the 8 bits he directly overwrote - the 'attack surface' explodes.
>
> This is assuming you get a new cookie each time. With the
> EncodeSystemPointer you need a reboot, which is going to make it
> impractical.

against one specific machine probably, against an internet wide population
i'm not so sure.

> With EncodePointer I believe that it's stored in the PIB, so
> you would need to restart the process. Since most of the attacks where you
> can have many, many tries are going to be killing threads not processes, I
> don't see how you will get access to any more than 256 possible locations in
> many scenarios.

have you run the code at all? it's not 256 locations but a whole lot more.
if you picked 256 because that's somehow a magical limit on how many times
a process or machine can be restarted, then i'd like to know what that
limit is ;-).

> > to
> > quantify this explosion i wrote a simple proof-of-concept enumerator
> > (http://grsecurity.net/~paxguy1/howard-xorrot.c). the result 
> > will speak for itself
>
> Yes, it says that each time the cookie changes you get access to another set
> of 256 overwrite locations. Your 2600 number confuses me, though... Given
> that there are 32 rotations and 256 possible XOR values for each rotation I
> guess the total number of reachable addresses should be 8192, no?

no, it's not, there're combinations that produce the same value. just
run the code and you'll see. as an exercise, also check out 2 byte
overwrites, the number of reachable addresses is well beyond 64k.

_______________________________________________
Dailydave mailing list
Dailydave () lists immunitysec com
http://lists.immunitysec.com/mailman/listinfo/dailydave