Re: PointGuard: It's not the Size of the Buffer, it's the Address

[Florian Weimer]

Crispin Cowan <crispin@immunix.com> writes:

> Thanks to Snax and the Shmoo for a better tag line: It's not the Size
> of the Buffer, it's the Address of the Pointer

This is not true. There are buffer overflow exploits which do not
modify pointers, but other objects. The most prominent example is
probably the "c c c c c..." exploit for the Solaris /bin/login
vulnerability.

[Crispin Cowan]

Florian Weimer wrote:

>Crispin Cowan <crispin@immunix.com> writes:
>
>
>>Thanks to Snax and the Shmoo for a better tag line: It's not the Size
>>of the Buffer, it's the Address of the Pointer
>>
>>
>This is not true. There are buffer overflow exploits which do not
>modify pointers, but other objects. The most prominent example is
>probably the "c c c c c..." exploit for the Solaris /bin/login
>vulnerability.
>
Please address technical commentary to the paper (which addresses this
point) and not to the cute tag line.

WRT this point: correct, PointGuard does not stop all buffer overflows.
IMHO it *nearly* stops all shell code. To bypass PointGuard, you have to
corrupt the logic of the program itself to get its own code to do what
you want; you can't readily generate a jump to arbitrary code.

Caveat: I can't prove the above, and someone may generate a bypass. But
I don't know of one.

Crispin

--
Crispin Cowan, Ph.D. http://immunix.com/~crispin/
Chief Scientist, Immunix http://immunix.com
http://www.immunix.com/shop/

[Crispin Cowan]

Nicholas Weaver wrote:

>The most likely bypass will be when a program also has a "print a
>pointer" bug/feature.
>
That's true, but unintended "print a pointer" bugs become much more
scarce when composed with FormatGuard <http://immunix.org/formatguard.html>.

Crispin

--
Crispin Cowan, Ph.D. http://immunix.com/~crispin/
Chief Scientist, Immunix http://immunix.com
http://www.immunix.com/shop/

[pageexec@freemail.hu]

Subject: Re: PointGuard: It's not the Size of the Buffer, it's the Address
From: Crispin Cowan <crispin () immunix ! com>
Date: 2003-08-15 18:00:04

> Please address technical commentary to the paper (which addresses this
> point) and not to the cute tag line.

Here we go then (all quotes are from your paper).

1. "This key is then never shared with any entity outside the process's
address space. To obtain the key, the attacker would either have to
already have permission to manipulate the process with debugging
tools (e.g. ptrace) or would have to have already successfully
perpetrated a buffer overflow attack against the process."

"However, PointGuard never gives the attacker a look at the
ciphertext."

"Nor can the key be extracted by looking at ciphertext, because the
ciphertext is never actually shared with anyone. To obtain a sample
of ciphertext, the attacker would have to coerce the victim program
into exposing internal pointer values to the attacker. Attackers
seeking the privileges of the victim process normally do not have
read access to the processes address space. Programs do not normally
dump data structures containing pointers outside of their address
space, because such pointers lose any meaning outside of the address
space."

"Thus we cannot identify any feasible means by which the attacker can
obtain the PointGuard key."

You are wrong (and even self-contradicting) here, in any case, so-called
information leaking can happen without having to corrupt pointers ([1],
[2]). Also, section 3.4.3 sublates the above.


2. In section 3.3.1 you talk about various implementation strategies.
Earlier in section 3.2 you declare that:

"PointGuard seeks to provide integrity for pointers, so that pointers
cannot be modified in ways the programmer did not intend."

However in the implementation part you talk about only those pointers
that are visible at the C language level whereas we know all too well
that there is more than that (ELF GOT/PLT, saved program counter and
frame pointer, etc). Because of this omission it appears that PG does
not protect these pointers at all even if they have been the primary
targets of address space corruption bugs in the past. Is this really
the case or is the paper missing something?

What really piqued my interest is that the PLT/GOT are not generated
by the compiler hence the implementation you describe cannot possibly
handle them without changes to the dynamic linker - something you do
not mention at all. It would also be interesting to know how you can
handle the saved program counter and frame pointer just after the AST
level where as far as i know these entities do not even exist (and
hence cannot be manipulated/controlled there).


3. In section 3.4.1 you say about statically initialized data that:

"[...] we modify the initialization code emitted by the compiler
(stuff that runs before main()) to re-initialize statically
initialized pointers with values encrypted with the current
process's key."

Can you clarify what initialization code the compiler emits before
main()? As far as i know, on entry only the dynamic linker, library
initialization and some statically linked-in object code (various
crt*.o stuff and what they call) gets to run before main() - none
of this is emitted by the compiler, at least not for each executable
as you made it sound to be.

If your initializer code gets to run after the dynamic linker's entry
point then there will or might be pointers in static data that are used
before your code gets to run - they are obviously not covered by your
protection (i.e., PG does not provide 100% coverage).


4. As mentioned above, section 3.4.3 admits that there are still ways to
modify non-encrypted pointers in the current implementation (beyond
the information leaking attacks i mentioned). To me it also means that
not all pointer stores/loads are protected but only those visible at
the C language level (refer to the problematic pointers pointed out in
2). It also begs the question of what kind of performance impact PG
will have once all these omissions are rectified (more on your
performance evaluation below).


5. In section 3.4.4 you talk about mixed-mode code (PG vs. non-PG). You
seem to be focused on marking function parameters for use by PG or
non-PG code but you do not mention what happens with pointers stored
in data structures which are used by both kinds of code. Do/can you
mark such structure members with __std_ptr_mode_on__? Also what happens
with functions that take format strings and hence accept arguments of
variable types (i.e., pointers and non-pointers), do you parse such
format strings and convert the pointer arguments accordingly or do
you turn off PG altogether for such code? What happens with system
calls that take pointers? You mention in the paper that you have not
created a PG version of glibc, so are all pointers passed to system
calls unprotected? What happens to system calls that do not go through
glibc (there are applications that do this)?

In the same section you all of a sudden introduce the notion of
'hashed pointers' without explaining what they are and how PG uses
them. Can you elaborate on this?

Finally i am wondering how you plan to implement pointer mode tracking
in the compiler, or more precisely, why you have to do it in the compiler
only and not at runtime (in the latter case you would have to extend the
pointer representation and open a whole can of worms).


6. In section 5 you admit that you do not indeed have a PG protected
glibc and hence heap pointers are not protected at all, this calls
into question the seriousness of your security and performance
testing (especially since you compare your results to mature
solutions which cannot be said of PG yet).


7. In section 5 you also say that

"Unfortunately, it is not possible to use testing and
experimentation to show non-bypassability: testing can
only show bypassability. Non-bypassability must be
established by inspection. Our argument is that:"

This is a welcome change in your opinion as you finally realized that
your claims about StackGuard's experimentally 'proven' non-bypassability
are also bogus (more on this later). So let's take a look at your
arguments about PG's non-bypassability:

"2. Usefully corrupting a pointer requires pointing it at a
specific location."

This is false, the hijacked pointer may very well point to a set of
specific values (e.g. any GOT entry that is used later, any member of
a linked list, etc).

"3. Under PointGuard protection, a pointer cannot be corrupted
to point to a specific location without knowing the secret key."

This is correct provided the implementation is bug-free - something
that cannot be verified until you actually release PG.

"4. Learning the secret key requires either obtaining the secret
key directly, or cryptanalysis against a sample pointer value."

These methods are called information leaking as discussed above. The
term 'cryptanalysis' is a bogus term here, as it makes it sound like
an expensive operation whereas all it takes is knowing the valid
pointer value (something an attacker can observe on a test system)
and xor'ing it against the leaked one.

"5. Obtaining the secret key directly would require corrupting a
pointer precisely, which begs the question (see Section 3.4.2)."

It depends, if the page holding the key follows another (i.e., no
non-mapped gaps surround it), and there is a buffer in the previous
page(s) that can be leaked, it may/will leak the key as well - did
you take countermeasures against this (you did not say anything about
it in the paper)?

"6. Obtaining a sample of ciphertext (an encrypted pointer) would
require either corrupting a pointer precisely (which begs the
question) or a program that leaks pointer values (which is highly
unusual)."

The latter claim ("highly unusual") is unsubstantiated, what is the
basis for it? At least neither your paper nor anything you referenced
present research data on this. Also there have been papers published
recently on this very topic ([1] and [2]), so it seems we are just
beginning to see the real nature of information leaking (this has
also been pointed out in the PaX ASLR paper [3]).


8. In section 6 you present performance evaluation data. The fundamental
problem with it is of course that PG has apparently not been finished
yet (something you do not make clear there), therefore any claims about
its impact are to be taken with a grain of salt.

There are more problems here however. First, you use the very latest
member of the Intel CPU family (P4-M) which is known to have special
microarchitecture changes to provide better performance at the same
clock speeds than its predecessors. It would have been more interesting
to see performance data on a variety of CPU families (P5, P2, P3, and
the various AMD cores). If you do not have the necessary hardware at
your disposal, i can offer you to do some testing on P3 myself, just
make your test binaries available.

Second, gcc is known to not produce the best code for P4 and therefore
your negative performance impact highlights the shortcomings of gcc
rather than provide any meaningful data on PG's performance. These
tests should be repeated once gcc has matured or you should have run
the tests on older families where gcc is known to generate reasonably
good code (and therefore you would be more likely measuring PG's real
impact and not compiler/CPU artifacts).

Third, there is related work ([4] and [5], all of which predates PG
by years and you failed to reference) that appears to show more real
performance impact of function pointer encryption (something PG does
not seem to do yet universally).


9. In section 7.1 you say that:

"A developer can port an application to these safer dialects in a few
hours or days, where as PointGuard was designed to allow a developer
to compile & protect millions of lines of code in a few hours or day."

whereas you admit before that PG requires programmer intervention (as it
is not possible to have a pure PG system right now), i doubt a programmer
can compile (port) millions of lines of code in a day.


10. In section 7.2 you claim that:

"The main limitation is that this defense can be bypassed, because
suitable attack payload code (effectively "exec(sh)")) is almost
always resident in victim program address spaces, and so pointer
corruption is all that is necessary for the determined attacker
to succeed."

Where is this "exec(sh)" supposed to be 'almost always'? Can you substantiate
this claim? Also, it is not always enough to execute a shell (i would even
say 'rarely'), you often have to change UIDs, break chroot, etc - code
that is even less likely to be present in a given program's address space.

Next you make certain claims about PaX [6] (please observe the proper
capitalization) without providing any reference to our project - why?
What is worse however is that your claims are false and/or misleading.

PaX does not provide a mere non-executable heap as you state, it provides
proper separation between writable and executable pages (it is called the
NOEXEC feature, [7]). Contrary to your claim, this feature is not bypassable,
you cannot introduce new executable code into the target's address space
(the special case mentioned in [8] is trivial to handle with ACL systems
or grsecurity's safe chroot() in a read-only directory). If you still
believe that there is a way to bypass NOEXEC then please let me know
because it must be a bug i want to correct. Your claim about StackGuard's
non-bypassability stands in stark contrast to several papers about its
failing ([9], [10]) and even your own advisories for ImmunixOS ([11]).

You also fail to substantiate your claims about the performance of PaX.
My best guess is that you are probably referring to a very old and long
outdated paper, not the current implementation. For your information,
NOEXEC has no performance impact on alpha, i386 (when SEGMEXEC is used,
which is the default, [12]), parisc, sparc and sparc64 and has a small
impact on ppc. I am curious to learn why you cited this information
when you have already been made aware of the current situation ([13]).


11. In section 7.3 you claim that:

"PAX also incorporates ASLR (Address Space Layout Randomization) which
can be viewed as the dual of PointGuard: rather than randomizing
pointers, ASLR randomizes the location of key memory objects."

This is a false claim, ASLR does the exact same thing to pointers as PG.
Think about it, if you randomize all memory regions, then all pointers
to these regions will necessarily be randomized as well. There is a
difference in the amount of randomization, the number of differently
randomized regions and the classes of randomized pointers - on the first
PG is better (at least at the first sight, if you examine real life
exploit situations you will realize that an attacker will likely need
to guess pointers from more than one region at once, hence the total
randomness to be guessed is at least 32 bits, more likely 40 or more),
on the latter two PaX is. You further claim that:

"[...] there is residual risk of attackers exploiting adjacency and
approximate memory location."

Why would PG be immune to these kinds of attacks? My understanding is that
this class of exploit techniques does not need to know memory addresses,
hence it will work against both ASLR and PG. You also claim that:

"Sekar et al [3] have a new implementation of this concept that
randomizes more elements of the address spacelayout, which may
make it harder to bypass than PAX/ASLR."

This is misleading because Address Obfuscation is vulnerable to the exact
same information leaking problem as ASLR or PG, otherwise an attacker has
to guess addresses (if he needs any, that is), there is no (determinisctic)
way around that.

The extra measures AO takes are meaningless because they introduce so little
randomization and/or can be bypassed by simply sending multiple copies of
the attack payload. You also failed point out that AO does not fully
randomize the address space, it leaves the main executable and the dynamic
linker at a fixed address and makes them a nice target for return-to-libc
style attacks (this is an inherent flaw of their technique as they try to
do everything in userland whereas these two files are mapped by the kernel
itself and without changes to the dynamic linker, they cannot be
randomized from userland).


12. Table 6 in section 7 has some bogus information:

- as discussed above, the performance impact of NOEXEC is 0%, not
the 10-30% as you quote it.

- you state that ASLR is 'probably' bypassable without explaining what
it is supposed to mean, especially in contrast to AO and PG which
you say 'maybe' bypassable - as i pointed out above, every randomization
based method is vulnerable to information leaking, and in fact PG is
the worse in this regard as a leak of any pointer will reveal the
randomness, whereas in PaX and AO you would need leaks of pointers
to different regions to learn all.

- StackGuard is bypassable as has been shown numerous times in the past
([9], [10]).

- the PG performance claim is meaningless because of issues discussed
above.


In conclusion, i have to ask how your paper managed to go through the
USENIX peer-review process with so many misleading, unsubstantiated
or false claims, omissions.


References:

[1] http://marc.theaimsgroup.com/?l=bugtraq&m=105941103709264&w=2
[2] http://phrack.org/show.php?p=61&a=6 section 4.4
[3] http://pageexec.virtualave.net/docs/aslr.txt
[4] http://www.eng.iastate.edu/abstracts/facultymenu.asp?PI=tyagi
(Encoded Program Counter: Self-Protection from Buffer Overflow
Attacks)
[5] http://link.springer.de/link/service/series/0558/bibs/2513/25130025.htm
[6] http://pageexec.virtualave.net/
[7] http://pageexec.virtualave.net/docs/noexec.txt
[8] http://pageexec.virtualave.net/docs/pax.txt
[9] http://www.phrack.org/show.php?p=56&a=5
[10] http://www1.corest.com/common/showdoc.php?idx=242&idxseccion=11
[11] http://marc.theaimsgroup.com/?l=stackguard&m=106042055816779&w=2
[12] http://pageexec.virtualave.net/docs/segmexec.txt
[13] http://marc.theaimsgroup.com/?l=stackguard&m=104812282808922&w=2

[pageexec@freemail.hu]

> >You are wrong (and even self-contradicting) here, in any case, so-called
> >information leaking can happen without having to corrupt pointers ([1],
> >[2]). Also, section 3.4.3 sublates the above.
> >
> It is true that PointGuard raises new issues with regard to information
> leakage: before PointGuard, there was not much significance to leaking
> pointer values from a running process, and so this now becomes a new
> threat that needs study.

You are wrong, PG is not the one that raised the issue of information
leaking as it has been known for quite some time now [1] (i would say
ever since randomization schemes were implemented, although apparently
not everyone knew of them).

> Yes, PointGuard only protects pointer values generated by code compiled
> with PointGuard.

In other words, does this mean that PG as you described it in your paper
is vulnerable to the most basic form of exploit techniques - shellcode
injection and execution?

> We are modifying the dynamic linker for Immunix. But that kind of
> hacking isn't worthy of a paper, so we omitted it.

I did not expect a full paper about ld.so hacking but you should have
at least mentioned the very fact that you did need to do it - after all
it is part of the PG system. Also i would like to point out that at least
on i386 the PLT is generated by the normal linker (ld in binutils), so
you will have to modify it as well.

> > It would also be interesting to know how you can
> >handle the saved program counter and frame pointer just after the AST
> >level where as far as i know these entities do not even exist (and
> >hence cannot be manipulated/controlled there).
> >
> As the paper said, we are going to tag the AST expressions so that
> spills are PG-encrypted, but this is not yet implemented.

I was not asking about register spills (which hold local variables
described at the C language level), i meant the CPU specific registers
that are used for addressing local variables (frame pointer, EBP on
i386) and control flow (instruction pointer or program counter, EIP on
i386). As far as i know, these registers are not visible at the AST
level, they are not (directly) controlled by any C language level
construct therefore encrypting/decrypting them requires special
changes - what shall they be?

> > 2). It also begs the question of what kind of performance impact PG
> > will have once all these omissions are rectified (more on your
> > performance evaluation below).
> >
> The only pointer load/stores that are not encrypted right now are
> register spills. That is a rare case, so it will not affect performance
> much.

If it is true that PG does not protect the saved instruction and frame
pointers then indeed the performance impact of the above changes will
be irrelevant - all an attacker has to do is simply use the good old
way of shellcode injection/execution without having to worry about PG
encrypted pointers. If you are going to encrypt these then i am not
convinced that the resulting impact will be so little (see [2]).

> > Also what happens
> > with functions that take format strings and hence accept arguments of
> > variable types (i.e., pointers and non-pointers), do you parse such
> > format strings and convert the pointer arguments accordingly or do
> > you turn off PG altogether for such code?
> >
> There is special case handling for varargs.

I understood that, i was asking about its technical details. Consider the
following code:

union bar {
char * y; /* char @ y; */
long z;
};

void foo(int x, const char * f, union bar * s, int y) {
if (x)
printf(f, s->y[0]);
else
printf(f, s->z);
}

Here foo() is PG protected so 'f' and 's' are encrypted. The question
is: what happens to s->y ? Is it supposed to be marked with '@' (maybe
along with s itself) and hence be used unencrypted throughout the code
(and leave it vulnerable to overflows)? If not, when will it be
decrypted? The problem with this is that the compiler cannot know in
advance whether the format string 'f' will contain a %c or a %ld
specifier, so neither blind decryption (of s->y) nor leaving it
(s->z) untouched will produce the expected result (which is defined
to be the result of non-PG compiled code).

> That is correct: unencrypted pointers are passed into the kernel.

This means that such pointers (passed as arguments on the stack) do
leak on the stack (beyond the register spills you mentioned).

> or to have the kernel know the key value of all processes and do
> the mapping for you (which is feasible, but more intrusive than
> just hacking glibc).

Did you consider building the kernel itself with PG? In that case
sharing the (per task) encryption key between the kernel and userland
could be automatic.

> > Finally i am wondering how you plan to implement pointer mode tracking
> > in the compiler, or more precisely, why you have to do it in the compiler
> > only and not at runtime (in the latter case you would have to extend the
> > pointer representation and open a whole can of worms).
> >
> I have no idea what you are talking about.

Refer to my small example above and imagine that you encrypt varargs
pointer arguments as well. As i pointed it out above, you cannot decide
at compile time whether to do the decryption or not hence you would
have to carry the pointer's mode into the runtime which means you will
have to augment the internal pointer type which increases its size.

> >6. In section 5 you admit that you do not indeed have a PG protected
> > glibc and hence heap pointers are not protected at all, this calls
> > into question the seriousness of your security and performance
> > testing (especially since you compare your results to mature
> > solutions which cannot be said of PG yet).
> >
> All of the code used in our performance testing was statically linked
> and compiled with PointGuard to work around the absence of a PG version
> of glibc, so the performance figures are valid.

I think i am not following you here. Why does statically linking
in glibc change the fact that glibc is not protected with PG (and
neither are heap pointers as a consequence)? By the way, can you
please make your 'straw man' vulnerable binary (the one shown in
figure 12 in your paper) available, i would like to take a look
at it.

> > "2. Usefully corrupting a pointer requires pointing it at a
> > specific location."
> >
> >This is false, the hijacked pointer may very well point to a set of
> >specific values (e.g. any GOT entry that is used later, any member of
> >a linked list, etc).
> >
> Bull: you just specified a specific location that happens to be a range.

Sorry, i am not a native speaker and have misunderstood your use of
'specific location' as 'fixed/known address'. However this does not
change the fact that such a pointer can still be successfully attacked
without knowing the full encryption key, see below.

> A very small range in the size of an address space. Unlike PaX/ASLR
> (which can only jiggle objects a little within a range)

What is your definition of 'little' here? ASLR randomizes the main
executable, the brk() heap, the libraries (mmap()) and the stack in
separate 256 MB ranges (the main executable and the brk() regions
do overlap somewhat). The randomness within these ranges is roughly
16/24/16/24 bits (all this on 32 bit architectures, and more on
64 bit ones).

> PointGuard has complete freedom to randomize all 32 bits of the
> pointer, so the fact that you can craft an exploit that can only
> approximately hit a target does not affect PointGuard.

Even if PG randomizes all 32 bits it is vulnerable to partial pointer
overwrites as described in [3].

> * PointGuard provides better randomization than ASLR, because the
> randomization ranges are much greater.

Attacking ASLR means that one needs to know addresses from more than one
(differently) randomized region (e.g., a code address and a stack/heap
address because one is forced to do a return to libc style attack), this
quickly adds up (e.g., up to 40 bits in the mentioned case) as generally
one cannot brute force these values independently.

> > "3. Under PointGuard protection, a pointer cannot be corrupted
> > to point to a specific location without knowing the secret key."
> >
> >This is correct provided the implementation is bug-free - something
> >that cannot be verified until you actually release PG.
> >
> I have no idea what you are talking about. If the pointer is hashed, you
> *cannot* usefully corrupt it without knowing the secret key.

I can, it is called partial pointer overwrite and can be useful if your
'specific location' you want to aim at is a range. Imagine that in the
future PG will encrypt the saved program counter as well and you have
a large enough overflowable stack buffer - overwriting the least
significant byte of the saved program counter will transfer control
within a 256 byte range of the original return place (or a 64k range
for a 2 byte overwrite). If there is any byte sequence there that does
something like 'jmp register' and the register happens to hold a value
pointing back to the buffer (it can happen since you do not reload all
registers on function return therefore a plaintext pointer can leak
back to the caller) you will execute shellcode. Even a non-executable
stack is just a workaround here, you may very well have a plaintext
heap pointer in the register (which in fact you do since PG does not
handle them yet) and return there if you can ensure that there is a
copy of the shellcode there.

> Speculating that any piece of software has bugs without foundation
> boarders on FUD,

It is not FUD, it is a simple reminder that unless your work is made
public, it cannot be evaluated let alone trusted for its correctness.
I will remind you that in [4] you stated that:

"We describe StackGuard: a simple compiler technique
that virtually eliminates buffer overflow vulnerabilities
with only modest performance penalties."

As we know this did not prove to be true, StackGuard was found to be
circumventable ([5], [6]). I personally believe that the more eyes
can scrutinize a system, the lower its error rate will be. It is in
your best interest to make your work available and wait for judgement
until others have looked over it - you did not prove to be infallible
in the past, why would you have created a bug-free system this time
(especially considering how much more complex it is to hack the AST
than function prologue/epilogue generation)? For now i would even
appreciate just taking a look at PG compiled binaries at the
assembly level, that would tell me what is exactly randomized
and how vulnerable PG is.

> but in this case it isn't even possible: an encrypted pointer cannot be
> modified by a plaintext overflow. A bug that accidentally laid a
> plaintext pointer would result in a crash when the value is decrypted,
> and vice versa: the design specifically resists this problem.

Three words: partial pointer overwrite.

> Speculate away as to what PointGuard will do when we're done integrating
> it. On second thought, don't: you've done more than enough flaming
> speculation today :)

It seems to be that my only mistake was an unfortunate consequence
of my language skills (or lack thereof), otherwise you have only
confirmed my 'speculations'. In any case, i look forward for trying
out PG once it is available (or at least your test binaries).

> > Third, there is related work ([4] and [5], all of which predates PG
> > by years and you failed to reference) that appears to show more real
> > performance impact of function pointer encryption (something PG does
> > not seem to do yet universally).
> >
> That work is in fact based directly on PointGuard, having resulted from
> this post http://lwn.net/1999/1111/a/stackguard.html

Which of the two works are you referring to here?

> And you're on crack if you think their performance results are more
> realistic: the only "pointer" they encrypt is the activation return
> address. *None* of the hard work of weaving pointer encryption into the
> compiler's type system was done. They published first because we chose
> deliberately to not publish an empty idea with no implementation.

Assuming you are talking about [5] above, i am at a loss to interpret
your words ;-). Their performance results indicate much bigger (yes,
positive, i.e., slowdown) impact than what you have reported in your
PG paper. Now, if you think they encrypt even less than PG (so far you
seem to confirm that PG does *not* in fact encrypt the program counter),
then one would expect that your numbers would be even worse than theirs
(i.e., even more slowdown and definitely no speed-up). Since you imply
that their numbers are less realistic than yours (i hope you did not
seriously expect a speed-up from them), you can draw the consequence
that your numbers are even less realistic than theirs. Which is what
i have been saying myself. Also do you realize that the 'only' pointer
they encrypt happens to be the most vulnerable for execution flow
redirection style attacks as well?

> >9. In section 7.1 you say that:
> >whereas you admit before that PG requires programmer intervention (as it
> >is not possible to have a pure PG system right now), i doubt a programmer
> >can compile (port) millions of lines of code in a day.
> >
> You are entitled to your opinion on the numbers and magnitudes, but it
> is inescapable that "porting" to PointGuard is far less work than
> porting from C to Cyclone or CCured. So what's your point?

The point is that augmenting existing code for PG use consumes time
(since you do not have a full PG system) and you have shown no data
that would back up your claim. When PG becomes able to recompile the
entire userland without any intervention then you can claim your
'millions of lines of code in a day'.

> >Where is this "exec(sh)" supposed to be 'almost always'? Can you
> > substantiate this claim?
> >
> It is in glibc, and most programs link to glibc. This is very well
> known, and I didn't think it needed to be justified.

Last time i checked, glibc did not contain any exec(sh) code. What it
does contain is system() which will invoke 'sh -c' and exit if you
fail to pass a proper argument and the various wrappers around the
execve() system call that will also fail if you do not pass the proper
arguments. The point i am making here is that despite a handy execve()
in glibc you also have to be able to provide arguments (pointers) before
you can (ab)use it in an exploit. Therefore randomization (ASLR in PaX)
prevents this kind of exploiting in a probabilistic sense (minus
information leaking) and you should have pointed out that composing
various techniques (such as those in PaX) provides more protection
than using them standalone - it is an important part of the PaX
philosophy, you will see it once you read the documentation.

> I have been *trying* to properly cite PaX in various papers for at least
> a year, but you don't make it easy. A web URL is not normally considered
> a suitable citation.

Is it not? Then how do you explain that you provided web URLs for projects
like Solar Designer's kernel patch?

> research community is unaware of PaX. I dare say that the PointGuard
> paper will do more to raise PaX visibility in the research community
> than anything before. That was deliberate, because IMHO PaX is
> under-exposed: it's good work, and few have heard of it.

Shall i also thank google then for helping out all the lost souls who
otherwise would not be able to find the PaX webpage because for some
yet to be explained reason you had failed to provide it yourself?

> >I am curious to learn why you cited this information
> >when you have already been made aware of the current situation ([13]).
> >
> It was hearsay. Publish something, and I'll cite it. Please.

Is hearsay what can be published in a paper accepted at a 'strong
refereed conference' then? How about you test it out yourself? You
have the source code at your disposal after all. I also doubt that
you would cite anything i write considering how you failed to do so
in the past, even after you have been made aware of the documentation
(and which you had apparently failed to read). In any case, a separate
documentation about PaX performance is not out of question, but i
would rather do it when all architectures can be properly evaluated
(right now due to some crappy userland code RISC architectures need
special emulation that i will get rid of eventually).

> Go look up the word "dual": it is a mathematical term. What you're
> saying is exactly the same as what I am saying.

Ok, i did and according to [7]:

"Every field of mathematics has a different meaning of dual."

Oops.

"Loosely, where there is some binary symmetry of a theory, the image
of what you look at normally under this symmetry is referred to as
the dual of your normal things."

I cannot really say that i got what you really meant by 'dual' but
let's assume we were really meaning the same thing ;-).

> >This is misleading because Address Obfuscation is vulnerable to the exact
> >same information leaking problem as ASLR or PG, otherwise an attacker has
> >to guess addresses (if he needs any, that is), there is no (determinisctic)
> >way around that.
> >
> It is *your job*, not mine, to go write a paper explaining how PaX/ASLR
> is better than Sekar et al.

Actually, it is not my job (more below), i was merely pointing out that
your comparison table has more flaws beyond PaX.

> In the absence of such a paper, I'm having to guess at the differences,
> in a very small portion of my paper.

Why do you have to guess at the differences and why did i not have to?
I can assure you that we have access to the exact same information:
the AO paper and the PaX source code and documentation (and i am sure
that you could have asked questions from either party should you have
needed it).

> I vigorously encourage you to go write a real paper and
> submit it to a strong refereed conference such as USENIX Security.

Thank you but i have other ideas about a 'strong refereed conference'.
Besides, i am not into academia, my interests lie elsewhere.

> Had you done this two years ago, you would not be having this silly
> flame war over W^X with Theo.

Thanks for the advice but i already saw in this very thread ([8])
where publishing papers in this area leads to, i do not think i
need any more of it.

[1] http://www.phrack.org/show.php?p=58&a=4
[2] http://link.springer.de/link/service/series/0558/bibs/2513/25130025.htm
[3] http://www.phrack.org/show.php?p=59&a=9
[4] http://immunix.org/StackGuard/usenixsc98.pdf
[5] http://www.phrack.org/show.php?p=56&a=5
[6] http://www1.corest.com/common/showdoc.php?idx=242&idxseccion=11
[7] http://dictionary.reference.com/search?q=dual
[8] http://marc.theaimsgroup.com/?l=bugtraq&m=106124676623652&w=2

[Crispin Cowan]

Sorry for the length, but its a long post, and I feel the need to rebut
most of this.
pageexec@freemail.hu wrote:

>Here we go then (all quotes are from your paper).
>
>1. "This key is then never shared with any entity outside the process's
> address space....
> "Thus we cannot identify any feasible means by which the attacker can
> obtain the PointGuard key."
>
>You are wrong (and even self-contradicting) here, in any case, so-called
>information leaking can happen without having to corrupt pointers ([1],
>[2]). Also, section 3.4.3 sublates the above.
>
It is true that PointGuard raises new issues with regard to information
leakage: before PointGuard, there was not much significance to leaking
pointer values from a running process, and so this now becomes a new
threat that needs study. At the USENIX conference, it was pointed out
that format string bugs can be used to obtain pointer values, which we
had not thought of. However, composing PointGuard with FormatGuard
somewhat mitigates this problem.

>However in the implementation part you talk about only those pointers
>that are visible at the C language level whereas we know all too well
>that there is more than that (ELF GOT/PLT, saved program counter and
>frame pointer, etc). Because of this omission it appears that PG does
>not protect these pointers at all even if they have been the primary
>targets of address space corruption bugs in the past. Is this really
>the case or is the paper missing something?
>
Yes, PointGuard only protects pointer values generated by code compiled
with PointGuard.

>What really piqued my interest is that the PLT/GOT are not generated
>by the compiler hence the implementation you describe cannot possibly
>handle them without changes to the dynamic linker - something you do
>not mention at all.
>
We are modifying the dynamic linker for Immunix. But that kind of
hacking isn't worthy of a paper, so we omitted it.

> It would also be interesting to know how you can
>handle the saved program counter and frame pointer just after the AST
>level where as far as i know these entities do not even exist (and
>hence cannot be manipulated/controlled there).
>
As the paper said, we are going to tag the AST expressions so that
spills are PG-encrypted, but this is not yet implemented.

>3. In section 3.4.1 you say about statically initialized data that:
>
> "[...] we modify the initialization code emitted by the compiler
> (stuff that runs before main()) to re-initialize statically
> initialized pointers with values encrypted with the current
> process's key."
>
>Can you clarify what initialization code the compiler emits before
>main()? As far as i know, on entry only the dynamic linker, library
>initialization and some statically linked-in object code (various
>crt*.o stuff and what they call) gets to run before main() - none
>of this is emitted by the compiler, at least not for each executable
>as you made it sound to be.
>
Yes, the static data initialization is hacked into that code. I don't
recall whether it is crt0.o or something else, but it doesn't really matter.

>4. As mentioned above, section 3.4.3 admits that there are still ways to
> modify non-encrypted pointers in the current implementation (beyond
> the information leaking attacks i mentioned). To me it also means that
> not all pointer stores/loads are protected but only those visible at
> the C language level (refer to the problematic pointers pointed out in
> 2). It also begs the question of what kind of performance impact PG
> will have once all these omissions are rectified (more on your
> performance evaluation below).
>
The only pointer load/stores that are not encrypted right now are
register spills. That is a rare case, so it will not affect performance
much.

>5. In section 3.4.4 you talk about mixed-mode code (PG vs. non-PG). You
> seem to be focused on marking function parameters for use by PG or
> non-PG code but you do not mention what happens with pointers stored
> in data structures which are used by both kinds of code. Do/can you
> mark such structure members with __std_ptr_mode_on__?
>
Yes.

> Also what happens
> with functions that take format strings and hence accept arguments of
> variable types (i.e., pointers and non-pointers), do you parse such
> format strings and convert the pointer arguments accordingly or do
> you turn off PG altogether for such code?
>
There is special case handling for varargs.

> What happens with system
> calls that take pointers? You mention in the paper that you have not
> created a PG version of glibc, so are all pointers passed to system
> calls unprotected?
>
That is correct: unencrypted pointers are passed into the kernel. It has
to be this way, because the alternatives would be to either have a
system-wide single key value (which would persist far too long for such
a small key, and be too easy to obtain) or to have the kernel know the
key value of all processes and do the mapping for you (which is
feasible, but more intrusive than just hacking glibc).

> What happens to system calls that do not go through
> glibc (there are applications that do this)?
>
You would have to modify the source to mark those arguments as cleartext.

> In the same section you all of a sudden introduce the notion of
> 'hashed pointers' without explaining what they are and how PG uses
> them. Can you elaborate on this?
>
It's just a synonym for PG-encrypted pointers.

> Finally i am wondering how you plan to implement pointer mode tracking
> in the compiler, or more precisely, why you have to do it in the compiler
> only and not at runtime (in the latter case you would have to extend the
> pointer representation and open a whole can of worms).
>
I have no idea what you are talking about.

>6. In section 5 you admit that you do not indeed have a PG protected
> glibc and hence heap pointers are not protected at all, this calls
> into question the seriousness of your security and performance
> testing (especially since you compare your results to mature
> solutions which cannot be said of PG yet).
>
All of the code used in our performance testing was statically linked
and compiled with PointGuard to work around the absence of a PG version
of glibc, so the performance figures are valid.

> "2. Usefully corrupting a pointer requires pointing it at a
> specific location."
>
>This is false, the hijacked pointer may very well point to a set of
>specific values (e.g. any GOT entry that is used later, any member of
>a linked list, etc).
>
Bull: you just specified a specific location that happens to be a range.
A very small range in the size of an address space. Unlike PaX/ASLR
(which can only jiggle objects a little within a range) PointGuard has
complete freedom to randomize all 32 bits of the pointer, so the fact
that you can craft an exploit that can only approximately hit a target
does not affect PointGuard.

Thanks for bringing up this point, as it highlights something important:
PointGuard and address space randomization techniques (PaX/ASLR, the
Sekar paper that immediately followed PointGuard at USENIX, and several
other re-implementations of PaX/ASLR) are complementary.

* ASLR techniques defend binaries (good for convenience) and as a
consequence defend objects that are hard to protect with PointGuard.
* PointGuard provides better randomization than ASLR, because the
randomization ranges are much greater.
* These two techniques compose: you are better off using both PG and
ASLR. Similar to the way in which you are better off using both
StackGuard and non-executable stacks (Immunix ships with both
StackGuarded binaries and a non-executable stack kernel).


> "3. Under PointGuard protection, a pointer cannot be corrupted
> to point to a specific location without knowing the secret key."
>
>This is correct provided the implementation is bug-free - something
>that cannot be verified until you actually release PG.
>
I have no idea what you are talking about. If the pointer is hashed, you
*cannot* usefully corrupt it without knowing the secret key. Speculating
that any piece of software has bugs without foundation boarders on FUD,
but in this case it isn't even possible: an encrypted pointer cannot be
modified by a plaintext overflow. A bug that accidentally laid a
plaintext pointer would result in a crash when the value is decrypted,
and vice versa: the design specifically resists this problem.

> "4. Learning the secret key requires either obtaining the secret
> key directly, or cryptanalysis against a sample pointer value."
>
>These methods are called information leaking as discussed above. The
>term 'cryptanalysis' is a bogus term here, as it makes it sound like
>an expensive operation whereas all it takes is knowing the valid
>pointer value (something an attacker can observe on a test system)
>and xor'ing it against the leaked one.
>
It is none the less cryptanalysis. The paper itself points out that the
crypto is weak: the security depends on not leaking ciphertext.

> "6. Obtaining a sample of ciphertext (an encrypted pointer) would
> require either corrupting a pointer precisely (which begs the
> question) or a program that leaks pointer values (which is highly
> unusual)."
>
>The latter claim ("highly unusual") is unsubstantiated, what is the
>basis for it? At least neither your paper nor anything you referenced
>present research data on this. Also there have been papers published
>recently on this very topic ([1] and [2]), so it seems we are just
>beginning to see the real nature of information leaking (this has
>also been pointed out in the PaX ASLR paper [3]).
>
As I said above, it's a new area, and needs study. Thanks for the citations.

>8. In section 6 you present performance evaluation data. The fundamental
> problem with it is of course that PG has apparently not been finished
> yet (something you do not make clear there), therefore any claims about
> its impact are to be taken with a grain of salt.
>
PointGuard is at almost exactly the same stage of maturity as StackGuard
was when the paper first appeared in January 1998. A whole bunch of
system engineering has yet to be done. In the case of StackGuard,
overall performance *improved* vs. the results claimed in the paper.
Speculate away as to what PointGuard will do when we're done integrating
it. On second thought, don't: you've done more than enough flaming
speculation today :)

> Third, there is related work ([4] and [5], all of which predates PG
> by years and you failed to reference) that appears to show more real
> performance impact of function pointer encryption (something PG does
> not seem to do yet universally).
>
That work is in fact based directly on PointGuard, having resulted from
this post http://lwn.net/1999/1111/a/stackguard.html

And you're on crack if you think their performance results are more
realistic: the only "pointer" they encrypt is the activation return
address. *None* of the hard work of weaving pointer encryption into the
compiler's type system was done. They published first because we chose
deliberately to not publish an empty idea with no implementation.

>9. In section 7.1 you say that:
>
> "A developer can port an application to these safer dialects in a few
> hours or days, where as PointGuard was designed to allow a developer
> to compile & protect millions of lines of code in a few hours or day."
>
>whereas you admit before that PG requires programmer intervention (as it
>is not possible to have a pure PG system right now), i doubt a programmer
>can compile (port) millions of lines of code in a day.
>
You are entitled to your opinion on the numbers and magnitudes, but it
is inescapable that "porting" to PointGuard is far less work than
porting from C to Cyclone or CCured. So what's your point?

>10. In section 7.2 you claim that:
>
> "The main limitation is that this defense can be bypassed, because
> suitable attack payload code (effectively "exec(sh)")) is almost
> always resident in victim program address spaces, and so pointer
> corruption is all that is necessary for the determined attacker
> to succeed."
>
>Where is this "exec(sh)" supposed to be 'almost always'? Can you substantiate
>this claim?
>
It is in glibc, and most programs link to glibc. This is very well
known, and I didn't think it needed to be justified.

>Next you make certain claims about PaX [6] (please observe the proper
>capitalization) without providing any reference to our project - why?
>
I have been *trying* to properly cite PaX in various papers for at least
a year, but you don't make it easy. A web URL is not normally considered
a suitable citation. At least publish a Phrack article or something so I
can actually cite you. FWIW, I have been repeatedly pointing out PaX to
various people who are re-inventing ALSR in various forms, because the
research community is unaware of PaX. I dare say that the PointGuard
paper will do more to raise PaX visibility in the research community
than anything before. That was deliberate, because IMHO PaX is
under-exposed: it's good work, and few have heard of it.

>You also fail to substantiate your claims about the performance of PaX.
>My best guess is that you are probably referring to a very old and long
>outdated paper, not the current implementation. For your information,
>NOEXEC has no performance impact on alpha, i386 (when SEGMEXEC is used,
>which is the default, [12]), parisc, sparc and sparc64 and has a small
>impact on ppc. I am curious to learn why you cited this information
>when you have already been made aware of the current situation ([13]).
>
It was hearsay. Publish something, and I'll cite it. Please.

>11. In section 7.3 you claim that:
>
> "PaX also incorporates ASLR (Address Space Layout Randomization) which
> can be viewed as the dual of PointGuard: rather than randomizing
> pointers, ASLR randomizes the location of key memory objects."
>
>This is a false claim, ASLR does the exact same thing to pointers as PG.
>Think about it, if you randomize all memory regions, then all pointers
>to these regions will necessarily be randomized as well.
>
Go look up the word "dual": it is a mathematical term. What you're
saying is exactly the same as what I am saying.

> "Sekar et al [3] have a new implementation of this concept that
> randomizes more elements of the address spacelayout, which may
> make it harder to bypass than PaX/ASLR."
>
>This is misleading because Address Obfuscation is vulnerable to the exact
>same information leaking problem as ASLR or PG, otherwise an attacker has
>to guess addresses (if he needs any, that is), there is no (determinisctic)
>way around that.
>
It is *your job*, not mine, to go write a paper explaining how PaX/ASLR
is better than Sekar et al. Be sure to point out that PaX/ASLR came
first, as that is a strong point in your favor. In the absence of such a
paper, I'm having to guess at the differences, in a very small portion
of my paper. I vigorously encourage you to go write a real paper and
submit it to a strong refereed conference such as USENIX Security.
Really, please, go write a real paper, I would love to read it, and
would cite it as often as I could. Had you done this two years ago, you
would not be having this silly flame war over W^X with Theo.

Crispin

--
Crispin Cowan, Ph.D. http://immunix.com/~crispin/
Chief Scientist, Immunix http://immunix.com
http://www.immunix.com/shop/