Smashing the stack

[zblaxell () tenchi myrus com (Zygo Blaxell)]

Please correct me everywhere where this is wrong:

On iX86-based Unix systems the general method for buffer overrun attacks
is to create a string consisting of three parts:

        1.  garbage or code here; specific length required
        2.  fake stack frame pointing to #1 or #3 as a return address
            for the currently executing function
        3.  garbage or code here; may have a length limit

For this to work, we have to know the exact address of #2 (so we can
rewrite it) and the exact address of #1 (so we can point to it in #2).
If we know where #2 is, we can add or subtract to find where #1 and
#3 are.

"Exact" is perhaps too strong; as I wrote the previous paragraph I
realized that if we can guess the mis-alignment of the buffer (usually 0)
and we can guess to within a few hundred or few thousand bytes the
location of #1, then we just have to have relocation code at the beginning
of #1 followed by several versions of #2 for different addresses of #1.
Whichever version of #2 is correct will be pulled off the stack, and
it will point to the correct location of #1.

As a further limitation on #1 and #3, we usually cannot have a 0 (null)
character in the text of #1 or #3 (or for that matter #2).  That's no
problem, because we can write a decoder in X86 machine code that
uudecodes a interesting program, using a fairly restrictive set of
characters.

Another problem is finding interesting system calls to execute.  Under
X86 Unix there's usually a specific instruction sequence for the kernel
interface, but under Windoze you actually have to be able to do dynamic
linkage to access DLLs (why?).  Apparently this isn't much of a problem,
and someone has already solved it by a combination of guessing and
pattern matching.

On the X86 memory can be read-only, read-write, or unmapped.  This means
that it's not possible to mark memory as readable but not executable.
On every other major architecture I've heard of (except maybe the 68000),
it is at least theoretically possible to mark which addresses can be
used to fetch machine instructions and which ones can't, even if the
operating system doesn't usually actually do that (as in the recently
discussed case of the Alpha and OSF's Unix flavor, where the stack is
no-execute but the heap isn't).

Depending on the architecture it may be possible to fake enough machine
state to do this kind of attack even without execute permission, if you
can somehow manage to get a pointer to a string like "cp /bin/sh /tmp &&
chmod 4555 /tmp/sh" in a register, then specify the address of the system()
library routine as the "return address" as in #2 above.  Some architectures
have bits in the stack frame that indicate what registers are on the
stack, which helps a lot for this kind of attack.

There are other variations that only pose trivial obstacles to buffer
overrun attacks:  using the Alpha again, the return address of a stack
frame could be placed at a lower address than automatic variables; in
this case the fake stack frame (#2 above) clobbers the stack frame of
the return address of the caller of the current function.

Some architectures grow the stack "upwards" in memory instead of
"downwards"; this means that buffer overrun doesn't overwrite existing
stack frames at all.  Is there a solution for this kind of architecture?
For that matter, can anyone offhand name such a machine?  I've heard
rumours about Crays...

Small architectures pose problems of their own.  A 16-bit architecture has
a really small address space compared to the potential size of a buffer
overrun; it could not only overrun an automatic variable and clobber a
stack frame, but it could proceed on from there and overwrite the code
that is copying the buffer, or the heap, or anything else in that tiny
address space.

The 286 has an interesting twist; it uses 16-bit registers with segment
registers to boost its address range, and no memory protection worth
speaking of.  A 65536-byte buffer overrun could rewrite the *entire*
stack.

A good way to stamp out most of these attacks would be to allocate
automatic variables somewhere on the heap or at least somewhere that
isn't the stack.  This may cause a performance penalty on CPUs that
have special optimizations for data at short offsets from a particular
"stack" register.  This solution may be unreasonable on most real-world
systems, but if you're designing a system from the ground up this is
something to think of early on if it genuinely makes no difference in
terms of performance.

Of course, all of this just deals with automatic variable overruns that
clobber the stack; in general a buffer overrun could occur anywhere, even
in the heap and in dynamically allocated memory.  This requires some
effort to exploit, but it could be helped if the program is pushing around
a lot of pointers to functions in struct's with buffers in them for
some reason.  It's difficult even to contrive a case where this might
happen, but I'm sure we'll all recognize it when we actually see it...

--
Zygo Blaxell. Unix/soft/hardware/firewall/security guru. 10th place, ACM Intl
Prog Contest, 1995. Admin Linux+Solaris for food, Tshirts, anime. Pager: 1613
7608572. "I gave up $1000 to avoid working on windoze... *sigh*"-Amy Fong. "smb
is a microsoft toy, like a "child" protocol that never matured"-S Boisjoli.