Multipath-ROP: Tools available?

[halfdog <me () halfdog net>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Out of personal interest, I am currently trying to exploit a
buffer-overflow in apache using ROP. The exploit allows to send %eip to
any location, but ASLR is challenging. To improve my odds agains ASLR I
thought to create code, that allows multiple ROP-pathes in parallel.
Does someone known, if this method is already publicly known and if yes,
are there tools for library, e.g. for /lib/i386-linux-gnu/libc-2.13.so,
analysis available?

The idea:

Let's assume, all states of a program are nodes, an instruction is a
vertex from one node to another. A program is deterministic and with a
given input just follows only one path.

ASLR: The start-node is different since the libraries can be mapped at
different locations. The instructions executed following the path are
the same, but the path itself is different (containing other nodes).

ROP: The exploit modifies a memory location when the processor is
executing a given instruction. Due to ASLR, this may occur at many nodes
representing the different address space states. With standard ROP one
would choose just one node, hence doing a guess on memory layout, and
try to build the ROP-exploit on that guess. The program will fail if the
guess does not hold true.

Multipath-ROP: Try to find different ROP-instruction blocks that are
separated by the ASLR memory randomization unit size, e.g. 1 page on
linux. Without the knownledge of ASLR state, this will represent
different ROP-programs. The idea is to find a set of input data set that
corresponds to a set of instruction pathes, that all lead to the same
result, e.g. the jump to one de-ASLRed memory address. Hence using this
technique, it is possible to do multiple memory guesses in one program
run, increasing the odds against ASLR (decreasing the entropy of ASLR).

Simple two-path example:

lib-offset 0x1000: ret
lib-offset 0x2000: pop eax; ret

lib-offset 0x6666: where I really want to go (de-ASLRed address)

Let's assume, lib is mapped to 0x1000000 + n*0x1000 and jump to
0x1002000. If n=0, this will run "pop eax; ret", hence ret will use 2nd
address from stack. If n=1, only "ret" is executed. With a stack
containing 0x1007666 0x1006666, this will reliable jump to offset
0x6666, independent of n. Of course, this could be extended to n>1.


Does someone know about this method? If there are no tools available for
that, I would like to create one, that uses markov-chains for library
analysis and that should support multiple CPU-archs.

- -- 
http://www.halfdog.net/
PGP: 156A AE98 B91F 0114 FE88  2BD8 C459 9386 feed a bee
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFOJ9H/xFmThv7tq+4RAhw1AJ9zBhdtCGb8MsKaYVOfNnXn5M8SggCfVw1l
ZX2MvaE2khuWPvY3wyxwxVw=
=AWE+
-----END PGP SIGNATURE-----

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/