Wednesday, July 19, 2023

Fuzzing Farm #4: Hunting and Exploiting 0-day [CVE-2022-24834]

Authors: Dronex, ptr-yudai

Introduction

 This article is part 4 of the Fuzzing Farm series. You can check the previous article at "Fuzzing Farm #3: Patch Analysis and PoC Development."

 The Fuzzing Farm team is not only working on 1-day exploits, but also developing 0-day exploits. In the final chapter of the Fuzzing Farm series, we will explain the 0-day vulnerability discovered by our engineers and the process for developing the exploit.

 Over a year ago in April 2022, we discovered a vulnerability in Redis related to the Lua interpreter and developed an RCE (Remote Code Execution) exploit for it. The fixes have now been completed, and the vendor has announced the information, so we decided to post this article.

CVE-2022-24834

 CVE-2022-24834 is a vulnerability in the Lua interpreter of Redis. It was discovered and reported by Dronex and ptr-yudai in the Fuzzing Farm team. Redis is an open-source software used worldwide as a datastore for databases, caches, and more.

 We reported this vulnerability in April 2022, and a fix patch was released on July 10, 2023.

 

Background to Vulnerability Discovery

 The Fuzzing Farm team selected Redis as its target among many open-source software options after considering factors such as the number of users, the size of the software, and its impact levels.

 Since Redis has many functions, it is more efficient to narrow down the targets for vulnerability searches. Redis is not just a simple data store, but it also supports Lua, which enables complicated processing. In the past, some researchers discovered several vulnerabilities in the Lua interpreter, such as CVE-2015-8080 and CVE-2018-11218. Therefore, we focused on investigating the Lua function in Redis.

 Although we found multiple vulnerabilities and issues in Redis other than Lua, we decided to explain CVE-2022-24834 in this blog post because it is exploitable and technically interesting.

Root Cause Analysis

  CVE-2022-24834 is caused by an issue with the JSON encoder in the Lua interpreter in Redis. Specifically, the issue is related to the json_append_string function.

/* json_append_string args:
 * - lua_State
 * - JSON strbuf
 * - String (Lua stack index)
 *
 * Returns nothing. Doesn't remove string from Lua stack */
static void json_append_string(lua_State *l, strbuf_t *json, int lindex)
{
    const char *escstr;
    int i;
    const char *str;
    size_t len;

    str = lua_tolstring(l, lindex, &len);

    /* Worst case is len * 6 (all unicode escapes).
     * This buffer is reused constantly for small strings
     * If there are any excess pages, they won't be hit anyway.
     * This gains ~5% speedup. */
    strbuf_ensure_empty_length(json, len * 6 + 2);    // [1]

    strbuf_append_char_unsafe(json, '\"');
    for (i = 0; i < len; i++) {
        escstr = char2escape[(unsigned char)str[i]];
        if (escstr)
            strbuf_append_string(json, escstr);
        else
            strbuf_append_char_unsafe(json, str[i]);
    }
    strbuf_append_char_unsafe(json, '\"');
}

 This function encodes Lua string objects into JSON string literals. For example, the string Hello, 世界 is encoded as "Hello, \u4e16\u754c".

 The buffer for the encoded string is allocated on line [1]. As shown in the previous example, a single character can be represented by a maximum of a 6-byte Unicode escape sequence. Therefore, the buffer is allocated with the size len * 6 + 2. Care must be taken to avoid integer overflow during this size calculation. In this case, the variable len is of type size_t, which is defined as a 64-bit integer. To cause an overflow, we would need to encode a string that is (2^64 - 2) / 6 bytes in size, which is not practical.

 The definition of strbuf_ensure_empty_length, however, is as follows:

static inline void strbuf_ensure_empty_length(strbuf_t *s, int len)
{
    if (len > strbuf_empty_length(s))    // [2]
        strbuf_resize(s, s->length + len);
}

 The length argument is defined as an int type, so there is a possibility of an integer overflow if len * 6 + 1 is cast to an int. For example:

  • 0x200000000 * 6 + 2 = 0xc00000021073741822
  • 0x300000000 * 6 + 2 = 0x120000002536870914 (truncated upper 32 bits)

 If integer overflow occurs, the buffer cannot be allocated with the intended size. Moreover, if the result of the integer overflow is a negative value, the expression on line [2] always evaluates to false, and the buffer is not resized. Additionally, strbuf_append_char_unsafe adds characters to the buffer without checking the buffer size. As a result, a heap buffer overflow occurs.

 To trigger the buffer overflow, a string of length (0x80000000 - 2) / 6 = 0x15555555 bytes is required. This is approximately 341 MiB and is a practical size for 64-bit systems.

Writing an RCE Exploit

Challenges in Exploit

 Although it is possible to cause a heap buffer overflow, there are several constraints that make the situation challenging in this case.

[Challenge 1] Large amount of overflows

 If we write 0x15555557 bytes to the buffer, which is the size of the overflow before resizing, the heap area will be heavily destroyed. Therefore, we must be careful not to destroy the data necessary for Redis to run. Also, since the size of the overflow is significantly larger than the size of the normal heap area, writing to an unmapped area will eventually cause a crash.

[Challenge 2] ASLR and PIE are enabled

 Redis is compiled with PIE, like most modern applications, and of course, ASLR is enabled on the system. We need to somehow leak the address.

[Challenge 3] Data is Unicode-escaped

 The data is encoded as a JSON string literal overflow. This means that many characters, including NULL bytes, are Unicode-escaped. Therefore, it is not possible to simply overflow arbitrary byte sequences.

[Challenge 4] A double quote is added

 The written byte sequence always ends with a " (closing quotation mark of the string literal). We need to take it into account.

 To resolve Challenge 1, we can allocate a large amount of data in advance to expand the heap and avoid a crash. As Lua uses GC (Garbage Collector), releasing somewhat large string data will free up space when the GC runs. Even if the data is released, its memory remains mapped, so overflowing a heap buffer with a large amount of data will not cause a crash.

 It is also important to manipulate the heap appropriately in advance to prevent the destruction of important structures.

 While Challenge 2 can be easily solved, we will describe this later.

 The most critical issues related to exploitability are Challenges 3 and 4. Although a heap overflow may be possible, there are significant constraints on the data that can overflow. Writing a stable exploit under these constraints can be quite challenging.

Variables in Lua

 Let's investigate how Lua manages variables in memory.

 Lua uses the mark-and-sweep garbage collector for memory management. You can force garbage collection using the built-in collectgarbage function, so you don't need to worry about it too much.

 Every Lua object is managed by a tagged structure called TValue, which handles variables.

typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;

#define TValuefields	Value value; int tt

typedef struct lua_TValue {
  TValuefields;
} TValue;

 The member variable tt represents the type, which can take one of the following values.

#define LUA_TNONE		(-1)

#define LUA_TNIL		0
#define LUA_TBOOLEAN		1
#define LUA_TLIGHTUSERDATA	2
#define LUA_TNUMBER		3
#define LUA_TSTRING		4
#define LUA_TTABLE		5
#define LUA_TFUNCTION		6
#define LUA_TUSERDATA		7
#define LUA_TTHREAD		8

Here are some important types:

  • LUA_TNUMBER
    • Indicates the numeric type. It is internally represented as a simple double type.
  • LUA_TSTRING
    • Indicates the string type. The string body is located immediately after the header in memory. Lua strings are immutable and cannot be modified.
    • The hash value for the allocated string is calculated and managed by Lua. This prevents the same string from being allocated multiple times for efficiency.
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

  • LUA_TTABLE
    • Indicates the table type. A table is an object that can have either an array or an associative array.
    • When used as an array, a pointer to the TValue array (array) and its size (sizearray) are used.
typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  int readonly;
  lu_byte lsizenode;  /* log2 of size of `node' array */
  struct Table *metatable;
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  GCObject *gclist;
  int sizearray;  /* size of `array' array */
} Table;

  • LUA_TFUNCTION
    • Indicates the closure type. It is used for a closure to a function defined in Lua (LClosure), or a closure to a C-defined built-in function (CClosure).
typedef struct CClosure {
  ClosureHeader;
  lua_CFunction f;
  TValue upvalue[1];
} CClosure;

typedef struct LClosure {
  ClosureHeader;
  struct Proto *p;
  UpVal *upvals[1];
} LClosure;

typedef union Closure {
  CClosure c;
  LClosure l;
} Closure;

Creating the Addrof Primitive

 We need to solve Challenge 2 despite ASLR and PIE being enabled. However, this problem can be easily resolved. According to the Lua specification, when a Lua table or built-in function is stringified with tostring, the address of the object allocated on the heap is returned as a string. This means that the addrof primitive that obtains the object's address is available without the vulnerability.

 

 The ASLR problem can be solved if we have the heap address.

Creating a Fake Object

 It's not possible to write a valid address in the heap buffer overflow because there are limitations on the characters that can be written. In such cases, there are mainly two exploitation techniques:

  1. Metadata Corruption

    Even if there are limitations on the data, rewriting metadata such as size information might work. Let's check if it's possible under the current condition.

    First, it's not possible to write characters to a string variable even if the size information is corrupted since the string is immutable in Lua. Also, the size information is located after the pointer to the array. It's not possible to rewrite only the size information without destroying the pointer. Therefore, it seems difficult to rewrite metadata in this condition.

  2. Partial Overwrite

    We can make a pointer point to an invalid address by partially rewriting it. For example, if you rewrite the least significant byte of the array pointer to point to a fake array, it might be useful. This is the approach we took to develop the exploit this time.

 As mentioned in Challenge 4, the data that overflows always ends with " (0x22). By overwriting the least significant byte of the pointer to the array with this value, an incorrect memory address is recognized as a pointer to the array.

 A normal table (array) has a structure as shown in Figure 1. There is a table object, and its array points to the array entity of TValue type. If the TValue is a type with a pointer, such as a table or string, there is also a pointer to the object entity.

 

Figure 1. Typical table object in Lua

 

 We will overwrite the least significant byte of the pointer array with ", which has a hexadecimal value of 0x22. Next, we will prepare a fake array using a string at an address slightly lower than the regular array entity. As shown in Figure 2, the pointer array will then point to the fake array, allowing us to obtain an arbitrary fake object. Fortunately, even if the pointer metatable has a random value, the program will not crash as long as the metatable of the variable is not modified.

 

Figure 2. Table object with the least significant byte of the array pointer corrupted

 

 The issue is that you must allocate a table object at the precise position where the last byte (0x22) overwrites the least significant byte of the pointer array. One way to stabilize it is through heap spraying to consume freed chunks.

 With the addrof primitive, we can determine the exact address of the fake object, which enables us to create a fakeobj while avoiding Challenges 3 and 4. Unfortunately, this fakeobj is still not a useful primitive because it can only be used once.

Creating AAR/AAW Primitive

 Let's create more powerful primitives such as arbitrary address read (AAR) and arbitrary address write (AAW).

 It is possible to create a fake table structure as we can obtain a fake object. The base address of this fake array should be set to as low an address as possible, and the size should be made as large as possible. As a result, this fake array becomes a table that can reference a wide area of the heap.

 

Figure 3. Creating a fake table object
 

 If we set the type of the array to number, we can write relatively arbitrary values to the specified address. However, due to the nature of TValue, simple read and write operations are not possible. TValue is a 16-byte structure that holds the value entity (or pointer) and type information. In the case of number type, the following restrictions apply:

  • Write: A double type value is written to value. Additionally, the type information is overwritten with LUA_TNUMBER.
  • Read: A double type value is read from value. However, an assertion error will occur if the type information is not LUA_TNUMBER.

 Note that LUA_TNUMBER is written along with the value during writing as shown in Figure 4.

 

Figure 4. Write to arbitrary address

 

 When using the read function in Lua, it is important to write LUA_TNUMBER 8 bytes after the address to be loaded beforehand to ensure the correct type information is provided. Note that this method cannot be used to load a value from read-only memory. Refer to Figure 5 for an example illustration.

 

Figure 5. Read from arbitrary address

 Since TValue is 0x10 bytes in size, you can only write to addresses that are multiples of 0x10 from the base address pointed to by the array of the fake table. Therefore, as shown in Figure 6, we created another fake table that points to a base address 8 bytes lower. We can overwrite the address and size of the table shown on the right with a relative write from the fake table on the left, as the offsets from array to sizearray happen to be multiples of 0x10.


Figure 6. AAR/AAW primitive


 This allows us to create a relative AAR/AAW primitive that can freely read and write data on the heap, with the constraint that LUA_TNUMBER is written beforehand.

Creating Addrof/Fakeobj primitive

 The addrof primitive currently we have only works with certain objects, such as tables and functions, as it uses tostring. Additionally, fakeobj can only be used once at the beginning, limiting its utility.

 However, with the AAR/AAW primitives, we can now create addrof and fakeobj primitives. With full control over the heap, it is easy to create fake objects of any type. As shown in Figure 7, we can first overwrite the address and type information of an array element, and then create fake objects with the desired type.

 

Figure 7. Creating fakeobj primitive
 

 Similarly, as shown in Figure 8, we can store the object that you want to leak in an array and overwrite the type information to LUA_TNUMBER. This causes it to be recognized as a number when the array element is read, allowing us to obtain the address of the object.

 

Figure 8. Creating addrof primitive

 Controlling the RIP, or instruction pointer, is simple. A CClosure-type function calls a function written in C, meaning they have function pointers. By creating a fake built-in function with fakeob, we can make the program jump to any address we want.

 However, we cannot control the arguments. Redis uses execve somewhere, and it has the PLT (Procedure Linkage Table) for the function. We can use the PLT to call execve. However, to execute arbitrary commands, we need to pass three arguments to execve appropriately. In this situation, controlling the arguments with Call Oriented Programming is useful.

 When building a call chain, the first step is to identify where the function pointer comes from. Let's look at the assembly of luaD_precall, which calls the function pointer. As shown below, the function pointer is located at rax+0x20.

 

 

 In essence, RAX currently refers to a controllable fake function object. As a result, we can create a call chain using certain gadgets that ends with instructions such as call qword ptr [rax+XXX]. (The function pointer itself is located at offset 0x20; therefore, we use other locations to build the chain.)

 In the call chain, we only need to perform the following three operations:

  • Set RDX (envp) to 0.
  • Set RSI (argv) to argv.
  • Set RDI (pathname) to argv[0].

 One gadget that might prove useful for setting RDX to 0 is the following:

0x000abb6a:
xor edx, edx;
xor esi, esi;
mov rdi, rbp;
call qword ptr [rax+0x38];

 Next, we need to assign specific addresses to RDI and RSI registers. As the data pointed to by RAX is controllable, we should search for a "mov" gadget. For instance, you may find the following one:

0x001554c8:
mov rdi, [rax];
call qword ptr [rax+0x18];

 There are gadgets that can input values into the RSI register, as shown below. However, they have the same source memory as the RDI register in the previous gadget, and they destroy the RDX register. Additionally, the source memory of the last call instruction overlaps with the first gadget, rendering it useless.

0x000d1f3e:
mov rsi, [rax];            // conflict!
mov rdx, rbp;              // overwrite!
call qword ptr [rax+0x38]; // conflict!

 We used the following gadget instead.

0x0012718b:
mov rsi, [rdi+8];
mov rdi, [rdi];
call qword ptr [rax+0x10];

 This gadget can set values for both RDI and RSI. The source memory for the values is RDI, but this is not a problem as RDI is controllable with the second gadget. The entire chain can be seen in Figure 9.

 

Figure 9. Call chain
 

  The address of the gadget depends on the version of Redis. However, the gadget used in this call chain is a generic gadget that can be found in both the version at the time we discovered the vulnerability and the version at the time we published this article.

Exploit

 You can find the final exploit on the following GitHub repository. We tested it in the commit right before the patch is applied.

CVE-2022-24823 - RICSecLab/exploit-poc-public

 The following is the PoC video for this vulnerability.

 


5 comments:

  1. nice job! - Freak

    ReplyDelete
  2. I enjoy this kinds of own post. It Like this knowledgeable blog here.

    ReplyDelete
  3. You put very helpful information on this website. Keep it up. Keep blogging.

    ReplyDelete
  4. Looking forward to read your next update, Thanks Nice article you have!

    ReplyDelete
  5. Hi there, You have done an excellent job. Lot will be benefited in this web site.

    ReplyDelete