How to automatically detect and exploit format strings
 - j00n1x
======================================================


"How could you possibly think typing 'import skynet' was a good idea?"
	- Xkcd comic

From the Terminator 2 movie:

	"The Skynet funding bill is passed.  The system
	goes on-line August 4th, 1997.  Human decisions
	are removed from strategic defense.  Skynet
	begins to learn, at a geometric rate.  It becomes
	self-aware at 2:14 a.m. eastern time, August 29.
	In a panic, they try to pull the plug."


Necessary Conditions
--------------------

The idea is simple. Format string exploits require the following 
conditions to be true:

	1. There is only one or more parameters to the *printf() function.

	2. The first parameter is not a constant string. i.e. allocated in BSS,
	heap, or stack, but NOT data.

These are necessary, but not sufficient conditions for format strings to be
exploitable.

Now, imagine if you will, that the following is done by a "process which ptraces
other processes". For now, let's call this an "automated debugger". 


Scan for CALL *printf
---------------------

The idea then, in this case is to create an opcode scanner which searches for
the following opcodes:

	CALL <addr> 

where <addr> is an address of the *printf() functions in the GOT (Global Offset
Table). 

Once such an instruction is found, it needs to scan back to see if either one
of those conditions above have been met -- it can be satisfied by seeing the 
amount of pushes onto the stack before the call, or it can be calculated by
the amount of bytes "added" back to the stack after the call (stack cleanup).

It will also need to check the addresses of the pushed parameters, in
particular, the first parameter, to check to see if it satisfies condition #2.

Once these conditions have been found, there needs to be a way to see if the
stack contains data which may be exploitable, and whether the (non-constant)
string can be modified externally.


Determining string accessibility
--------------------------------

The way to determine if the format string can be modified or not is by:

	1. Determining the address of the string -- if it is within BSS/heap 
	or is inside the stack, then it is ok. Data area is the only area which
	is NOT ok.
	
	2. If the string itself is ever accessed by calls which modify it, such
	as strcpy/strcat, or from a user input. Ideally you're looking for code
	which contains a "MOV" opcode to this address. 

	3. A "watch" on this address is another way to find out when it 
	is modified during run-time. 

	4. Alternatively, the page of the address could be memory protected so 
	that SIGSEGV is caught and handled by the debugger when the string is
	accessed.


Throwing in the shoe - tracing string accessibility
---------------------------------------------------

Under UNIX systems, there is only one way for a program to grab user input,
and that is from file descriptors (stdin is also a file descriptor).

During the string accessibility trace, one of the file descriptors must have
been used to provide information for the string, so eventually it can
be determined which file descriptor supplied/supplies the information
that is required.

After all, the format string in question has already been determined to be
a non-constant, user defined string, which is passed as the FIRST parameter
to a *printf function. 

And if it's non-constant, it must have been derived from somewhere.

This is the "format string exploit" entry point.


Finding corruptible pointers on the stack
---------------------------------------------------------------

Finally, to find out what pointers are corruptible on the stack, a breakpoint
is enabled on the code just before "call *printf" and the stack is walked. 

Any pointers to GOT is good. DTOR is also good. See other documents on 
exploiting format strings. 


Shared Automation
-----------------

Again, imagine if you will, that this code was a "rogue process" that had 
gained superuser access on a machine with some remote (to local user) and 
local (to superuser) exploit.

This leads to the idea that after exploiting a machine, the "rogue process"
can now search for other exploitable daemons on the machine. 

So for each daemon, search for format string bug. Auto-detect and exploit.

The "rogue process" stores this technique and uses it again. It has "learnt"
a new way to enter the same machine. It uses this technique on other remote
machines.

Also it connects to other "rogue processes" and shares this new technique.
Other "rogue processes" will not require to learn this technique to use
this technique. And so on.


Conclusion
----------

A little mantra, to motivate authors to writing intelligent programs:

"What you can do (and repeat), AI can do better."