KernelSnitch: Leaking Kernel Heap Pointers by Exploiting Software-Induced Side-Channel Leakage

KernelSnitch: Leaking Kernel Heap Pointers by Exploiting Software-Induced Side-Channel Leakage

Speakers: Lucas Ma, PhD Candidate, Graz University of Technology; Jonas, PhD Candidate, Graz University of Technology

Conference: Black Hat Asia

YouTube: https://www.youtube.com/watch?v=jfgpIv5cbeY

Overview

This presentation introduces KernelSnitch, a novel operating system side channel attack that leverages timing differences in kernel hash table accesses to leak security-critical kernel heap pointers. Presented by Lucas Ma and Jonas, both PhD candidates at Graz University of Technology, the talk demonstrates a practical, unprivileged user-space attack capable of leaking the address of the mm_struct—a crucial kernel data structure—in under one minute. This research highlights a largely unexplored area of operating system security, proving that even in a world free of hardware and application-level side channels, the operating system itself can introduce exploitable leakage.

The significance of KernelSnitch lies in its ability to bypass the initial, often unstable, memory corruption phase of traditional kernel exploitation. By providing a reliable method to obtain kernel heap addresses without triggering vulnerabilities or putting the system into an undefined state, KernelSnitch fundamentally enhances the reliability and stability of subsequent kernel exploits. This breakthrough represents the first successful kernel heap pointer leak achieved purely through a side channel, demonstrating a powerful new primitive for attackers and a critical blind spot for defenders.

Background

▶ Watch: Introduction to KernelSnitch: Novel OS side channel (0:00)

The pervasive nature of side channels is a well-established concern in computing. From cache and timing side channels in CPUs and DRAM to electromagnetic radiation and even acoustic leakage from hard drives, hardware components are inherently susceptible. Similarly, user-space applications, including encryption algorithms, compression routines, and neural networks, frequently exhibit exploitable side channels. However, a critical gap in security research has been the focus on the operating system itself. While hardware and application layers receive considerable attention, the operating system, acting as the intermediary between them, has been comparatively underexplored for its potential side-channel leakage. KernelSnitch directly addresses this gap.

The foundation of KernelSnitch relies on a fundamental understanding of data structures within the Linux kernel, specifically linked lists and hash tables. A linked list is a simple data structure where elements are connected sequentially. Accessing an element in a linked list requires iterating through preceding elements, meaning the time taken for access is directly proportional to the number of elements before the target. An empty linked list is accessed almost instantly, while a long one takes significantly more time.

To mitigate the performance bottleneck of long linked lists, the Linux kernel extensively uses hash tables. Instead of a single, potentially lengthy linked list, a hash table distributes elements across multiple linked lists, known as buckets. When an object needs to be added or retrieved, a hash function takes a key and computes an index, directing the operation to a specific bucket. This design aims to keep individual buckets short, thus reducing access times. However, if multiple keys hash to the same bucket, that bucket can grow, reintroducing the performance variability that KernelSnitch exploits. This inherent design choice, while optimizing for speed, inadvertently creates a measurable timing difference based on bucket occupancy, which forms the core of the KernelSnitch side channel.

Key Findings

▶ Watch: Linux kernel hash table implementation explained (3:20)

KernelSnitch delivers several groundbreaking contributions to the field of system security:

1. Novel Operating System Side Channel: It introduces a new class of software-induced side channels that exploit the timing variations of kernel hash table accesses. Unlike microarchitectural attacks that target specific hardware features, KernelSnitch's core leakage originates purely from the software implementation of kernel data structures.
2. Information Leakage Amplification: The research demonstrates effective techniques to amplify the subtle timing differences caused by varying hash bucket occupancies. These amplification methods make the leakage robust and reliably measurable from unprivileged and untrusted user space, overcoming the inherent noise and variability of typical system operations.
3. Kernel Heap Pointer Leak in Under One Minute: KernelSnitch achieves the first-ever successful kernel heap pointer leak using a side channel. The demonstration specifically targets and leaks the address of the mm_struct, a critical data structure containing vital process memory management information, with remarkable speed—achieving the leak in approximately 30 seconds on a modern system.
4. Enhanced Reliability for Kernel Exploitation: By providing a stable and non-crashing method to obtain crucial kernel addresses, KernelSnitch significantly increases the reliability and stability of subsequent kernel exploitation efforts. This shifts the paradigm from relying solely on unstable memory corruption vulnerabilities for information leakage to a more robust side-channel approach.
5. Unaddressed Vulnerability in Upstream Kernel: Despite disclosure to the Linux security team and a proposed patch, the core vulnerability remains unmitigated in the upstream Linux kernel, highlighting a potential blind spot in kernel security posture.

Technical Deep Dive

▶ Watch: High-level overview of KernelSnitch attack (4:15)

The technical underpinnings of KernelSnitch are rooted in the observable timing differences when accessing hash table buckets with varying numbers of elements. The attack operates in two main phases: an online phase to gather timing fingerprints and an offline phase to brute-force and identify the target kernel address.

At a high level, the attack involves a malicious user-space process (Process 1) and potentially another process (also controlled by the attacker) that can modify kernel data structures (Process 2).

1. Process 1 makes a syscall that internally accesses a specific hash bucket in the kernel. Initially, this bucket might be empty, resulting in a notably fast access time.
2. Process 2 then makes another syscall that modifies the same kernel hash table, specifically appending several elements to the previously accessed bucket.
3. Process 1 repeats its syscall, accessing the now-populated hash bucket. This access will be notably slower due to the increased number of elements it must iterate over.
4. KernelSnitch deduces security-critical information from this measurable timing difference.

To achieve this, KernelSnitch relies on two types of primitives:

1. Access Primitive

An access primitive is a syscall that, when invoked, causes the kernel to iterate over elements within a hash bucket without modifying its contents. A key characteristic is that the syscall's execution time must be dependent on the number of elements in the targeted bucket.

The talk uses clock_gettime as an example. This syscall takes an identifier for a POSIX timer. Internally:

• It takes the user-provided ID and a known kernel address (e.g., of a signal_struct).
• A hash function is applied to these inputs to compute a hash value.
• This hash value determines the bucket index within a kernel hash table.
• The kernel then iterates over all elements in that specific hash bucket, searching for a match.

Crucially, if an invalid ID is provided (one that does not match any element in the bucket), the kernel must iterate over the entire linked list within that bucket. This full iteration leaks the occupancy level of the hash bucket through its timing.

2. Append and Remove Primitive

An append and remove primitive is a syscall that allows an unprivileged user-space process to modify the occupancy of a kernel hash bucket.

• For the POSIX timer example, the timer_create syscall serves this purpose.
• Similar to clock_gettime, it calculates a hash based on the provided ID and a kernel address.
• It then selects the corresponding hash bucket and adds a new timer object to its linked list.

By repeatedly calling timer_create, an attacker can increase the number of elements in a specific hash bucket.

Initial Measurement and Challenges

An initial experiment involved performing 1,500 measurements, each consisting of 512 accesses, on a real system. The 8 fastest measurements were averaged to reduce noise. When comparing an empty bucket to a bucket with a single timer, a timing difference of approximately 165 timestamps was observed, suggesting a successful side channel.

However, this initial approach suffered from false positives and false negatives, making the side channel unreliable for precise kernel heap pointer leakage. To overcome this, information leakage amplification techniques were developed.

Information Leakage Amplification

Two primary methods were employed to amplify the timing differences and achieve perfect distinguishability:

1. Making the List Bigger: The timing difference between zero and one element in a hash bucket is subtle. However, the difference between zero and five (or more) elements is significantly larger and much easier to measure reliably. By appending a substantial number of elements to a target bucket, the timing discrepancy becomes pronounced.

1. Enforcing CPU Cache Misses: When the kernel iterates over elements in a linked list, these elements are typically spread across memory. On the first access, they might be uncached, leading to slower access. Subsequent accesses, however, will find these elements in the CPU cache, making iteration much faster and diminishing the timing difference.

To counteract this, KernelSnitch employs a cache flushing technique. Before each syscall that accesses the target hash table, the attacker rapidly accesses a large array in user space. This large array is designed to be significantly larger than the CPU's caches (L1, L2, L3), effectively evicting relevant kernel data from the cache lines. By forcing a cache miss on every iteration, the timing difference between an empty and a populated bucket becomes dramatically larger and more consistent. This method is noted for its universality, working effectively across various CPU architectures like x86, ARM, and RISC-V, without requiring specific knowledge of cache replacement policies.

With these amplification techniques, a refined experiment (1,400 measurements, 512 accesses each, average of 8 fastest) showed a "huge" difference between zero and five timers, with "basically no false negatives, no false positives." This transformed the unreliable side channel into a robust and precise measurement primitive.

Demo / Proof of Concept

▶ Watch: Access and modify primitives for KernelSnitch (6:05)

The live demonstration showcased the leakage of the mm_struct kernel heap pointer on the laptop used for the presentation. The target was the futex hash table, which stores data for fast user-space mutexes. In this specific scenario:

• The user ID supplied to the syscall was a user-space virtual memory address.
• The kernel address to be leaked was the address of the mm_struct, a critical structure detailing a process's virtual memory layout.
• The exploit targeted an x86-64 system, but the principles apply to ARM and RISC-V due to the software-induced nature of the side channel. The entire process completed in under a minute.

The demonstration followed a two-phase exploitation strategy:

Online Phase: Fingerprinting Hash Collisions

The goal of the online phase is to identify a set of user-space addresses (IDs) that, when hashed with the target kernel address, all map to the same hash bucket. This set of colliding IDs forms a unique "fingerprint."

1. Setup: A large user-space array is prepared to store potential user identifiers. Another array stores the identifiers that will eventually form the fingerprint.
2. Threshold Calculation:

• The CPU caches are flushed by accessing a large array.
• The timing of a futex_wait syscall with an invalid user address (to ensure full bucket iteration) is measured when the target hash bucket is known to be empty.
• This "empty bucket timing" is multiplied by 10 to establish a threshold. If a subsequent syscall's timing exceeds this threshold, it indicates a significantly populated bucket.

1. Population: An append primitive is used to populate a specific hash bucket with a large number of elements. In the demo, 4,069 futexes were appended to one hash bucket.
2. Collision Detection:

• For a range of different user-space addresses, the CPU caches are flushed, and the futex_wait syscall timing is measured.
• If the measured timing is greater than the pre-calculated threshold, it signifies a hash collision with the bucket containing the 4,069 futexes.
• The process continues until 15 such colliding IDs are found. These 15 IDs constitute the unique fingerprint.

Offline Phase: Brute-Forcing Kernel Addresses

With the fingerprint (the 15 colliding user addresses) obtained, the offline phase attempts to find the kernel address that, when hashed with these user addresses using the kernel's known hash function, produces the same set of collisions.

1. Kernel Hash Function Simulation: The attacker, knowing the Linux kernel's open-source hash function, implements it in user space.
2. Iterative Matching: The program iterates through a reduced search space of possible kernel addresses. For each candidate kernel address, it:

• Computes the hash for each of the 15 fingerprint IDs, combined with the candidate kernel address.
• Checks if all 15 hashes resolve to the same bucket index (i.e., produce the same collision pattern as observed in the online phase).

1. Search Space Reduction: Brute-forcing all 2^64 or even 2^46 possible kernel addresses is impractical. The exploit leverages specific knowledge about kernel memory layout to drastically reduce the search space:

• Direct Physical Map: Kernel heap pointers are always located within the direct physical map, which is gigabyte-page aligned.
• mm_struct_slab: mm_struct objects are allocated within a dedicated kernel slab allocator cache called mm_struct_slab.
• Slab Page Order: For the target Ubuntu Linux kernel 6.8.0-52 generic version, the mm_struct_slab has a page order of 3, meaning it spans 2^3 = 8 pages.
• Objects per Slab: Within one mm_struct_slab, there are 23 possible locations where an mm_struct object could reside.
• By combining these facts (page alignment, slab location, slab size, and objects per slab), the initial 2^46 search space for a 64-bit kernel address is reduced to a manageable 2^35.3.

This reduced search space makes the brute-force feasible. The demo showed the "Find collisions" phase completing in 1 second, followed by a "Brute force phase" using 16 threads, which successfully identified the correct mm_struct address in approximately 30 seconds. A custom kernel module was used solely for verification, confirming that the leaked address matched the actual mm_struct address.

Defensive Implications

▶ Watch: User space code for timing measurements (8:05)

Upon discovering KernelSnitch, the researchers followed responsible disclosure practices, informing the Linux security team. The response, however, highlighted a significant philosophical divide regarding local KASLR (Kernel Address Space Layout Randomization) bypasses.

Initially, the Linux team's stance was that KASLR is inherently broken for local access anyway, implying that there was no practical way to fully protect the kernel against such local information leaks, and thus, no mitigation would be implemented.

However, Kees Cook, a prominent Linux kernel security developer, pushed back on this notion, emphasizing that heap KASLR (which KernelSnitch targets) is much harder to expose locally than code KASLR. Recognizing the severity, Kees Cook proposed a patch. The proposed patch aimed to introduce additional randomization into the futex hash function:

• It involved swapping the most significant bytes with the least significant bytes of the futex hash table key.
• It then XORed this modified key with the code base address.
• Finally, it XORed the result with the original key before returning it.

The intent was to add more randomness to the hash calculation, significantly increasing the complexity and time required for the brute-forcing phase of the KernelSnitch attack.

Despite Kees Cook's efforts, the proposed patch was ultimately rejected by Linus Torvalds, who famously dismissed it as "what voodoo programming is," indicating a lack of clear understanding or acceptance of the proposed obfuscation technique. As a result, the vulnerability exploited by KernelSnitch remains unmitigated in the upstream Linux kernel to this day, leaving systems susceptible to this powerful local side-channel attack.

Key Takeaways

• Novel OS Side Channel: KernelSnitch introduces a new class of software-induced timing side channels that exploit the inherent timing variations in kernel hash table accesses, opening up a previously underexplored field of operating system security research.
• Reliable User-Space Exploitation: Through robust leakage amplification techniques (making lists larger and enforcing CPU cache misses), KernelSnitch achieves perfect distinguishability of timing differences, making the side channel reliably exploitable from unprivileged user space.
• First Heap Pointer Leak via Side Channel: This research marks the first successful kernel heap pointer leak achieved purely through a side channel, demonstrating the ability to obtain critical kernel addresses like the mm_struct in under one minute.
• Enhanced Kernel Exploitation Reliability: While not an end-to-end privilege escalation exploit on its own, KernelSnitch provides a stable and non-crashing method to obtain essential kernel addresses, significantly increasing the reliability and stability of subsequent kernel exploits when combined with a separate write primitive.
• Unaddressed Vulnerability: Despite disclosure and a proposed patch, the core vulnerability remains unmitigated in the upstream Linux kernel, highlighting an ongoing security risk for Linux users.

About the Speaker(s)

Lucas Ma is a PhD candidate at Graz University of Technology, specializing in system security, with a particular focus on kernel and side channel security. His research contributes to understanding and mitigating advanced threats in operating system environments.

Jonas is also a PhD candidate at Graz University of Technology. His research interests lie in side channel security, with a deeper dive into low-level microarchitectural attacks, including topics like Rowhammer. He is nearing completion of his PhD and actively seeking new opportunities in the field.