KernelSnitch: Side Channel-Attacks on Kernel Data Structures

KernelSnitch: Side Channel-Attacks on Kernel Data Structures

Speakers: Lukas Maar

Conference: NDSS Symposium

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

Overview

"KernelSnitch" presents a groundbreaking investigation into a novel operating system side channel that leverages subtle timing differences when accessing kernel data structures. Presented by Lukas Maar, with collaboration from Yolas, this research exposes a critical vulnerability in the fundamental isolation mechanisms of modern operating systems, particularly the Linux kernel. The talk highlights how untrusted user-space processes can deduce security-critical information by observing the latency of system calls that interact with kernel data structures.

The significance of KernelSnitch lies in its ability to amplify these minute timing discrepancies into exploitable information leakages, even from isolated and untrusted user contexts. The research not only theorizes these vulnerabilities but concretely demonstrates their impact through three distinct and potent attacks: a high-bandwidth cover channel, an effective website fingerprinting attack, and, most notably, the first-ever documented kernel heap pointer leak achieved purely through a side channel in under 65 seconds. This work underscores a significant gap in current operating system security paradigms, challenging the efficacy of existing mitigations like Kernel Address Space Layout Randomization (KASLR) for heap pointers.

Background

▶ Watch: Introduction to KernelSnitch and its key attacks (0:00)

The landscape of side channel attacks has historically focused on two primary domains: the hardware level and the application level. On the hardware front, components like CPUs, RAM, and disks have long been recognized as susceptible to timing, power, and electromagnetic leakages, leading to vulnerabilities like Spectre and Meltdown. Similarly, at the application level, cryptographic algorithms and data conversion routines have been shown to leak sensitive information through their execution characteristics. Despite extensive research and mitigation efforts in these areas, a significant blind spot has persisted: the operating system level. Research into side channels originating from the OS itself, particularly from its core data structures, has been remarkably sparse.

KernelSnitch addresses this critical gap by meticulously analyzing one of the most fundamental entities within an operating system: the linked list. The researchers observed a direct correlation between the occupancy level of a linked list and the time required to access it. For instance, an empty linked list is accessed very quickly, a list with two elements takes a medium amount of time, and a list with five elements exhibits a noticeably slower access time. This fundamental timing difference forms the bedrock of the KernelSnitch side channel.

The primary target system for their attacks is the Linux kernel, specifically its implementation of hash tables. In the Linux kernel, hash tables are often composed of an array of hash buckets, where each bucket is essentially a linked list. The kernel employs a hash function that takes a key (often derived from a kernel address and a user identifier) and maps it to a specific hash bucket index. The KernelSnitch mechanism hinges on this architecture: when a user-space process initiates a system call (syscall) that internally accesses a kernel data structure (like a hash bucket), the access time varies based on the bucket's current occupancy. An initially fast syscall (due to an empty bucket) can become significantly slower if another process concurrently appends elements to that same hash bucket. KernelSnitch is designed to deduce security-critical information from these observable timing differences.

To exploit this, KernelSnitch relies on two types of primitives: access primitives and append/remove primitives.

Access primitives are syscalls that internally read or query kernel data structures, thereby exposing their occupancy level through timing. An example provided is obtaining the time from a POSIX timer. This operation typically involves three stages: first, calculating a hash using a kernel address and a user identifier; second, obtaining a reference to the corresponding hash bucket; and third, revealing the occupancy level of that hash bucket through the measured timing of the syscall.

Append and remove primitives, conversely, are syscalls that internally modify kernel data structures by adding or deleting elements. An example is creating a new POSIX timer. Similar to access primitives, this involves calculating a hash, obtaining a hash bucket reference, and then appending a new element to that bucket. The researchers emphasize that these primitives are highly generic and pervasive throughout the Linux kernel, making the attack surface substantial.

Empirical validation of these timing differences was conducted by performing 4,960 random accesses to hash buckets containing between zero and five timers. The results were stark: accessing a hash bucket with zero timers took approximately 178 clock cycles, while accessing one with three timers took about 205 clock cycles. This clear distinction in timing, observable from user space, provides the necessary signal for KernelSnitch to operate effectively.

Key Findings

▶ Watch: High-level overview of KernelSnitch mechanism (3:40)

The research presented in KernelSnitch unveils a novel and potent operating system side channel. Its core contribution is the demonstration that timing differences in accessing kernel data structures, specifically linked lists within hash buckets, can be reliably observed and exploited from untrusted user-space processes. This capability challenges fundamental assumptions about isolation within operating systems.

A crucial aspect of KernelSnitch's efficacy is the introduction of information leakage amplifications. These techniques are designed to magnify the subtle timing discrepancies, making them distinctly measurable and exploitable by isolated and untrusted users, thereby bridging the gap between low-level kernel operations and high-level information inference.

The talk demonstrated the practical implications of KernelSnitch through three distinct and impactful attacks:

1. High-Bandwidth Cover Channel: The researchers successfully implemented a cover channel capable of transmitting information between two user-space processes. By encoding messages into the occupancy level of a shared kernel hash bucket, they achieved a true capacity of up to 580 kilobits per second. This showcases the significant data transfer potential of this side channel.
2. Website Fingerprinting Attack: KernelSnitch was leveraged to perform website fingerprinting. By continuously probing kernel hash buckets, a spying process could infer which websites a browser was accessing. Using a convolutional neural network (CNN), the attack achieved an impressive F1 score of 89.3% when identifying websites from the top 100 most visited list.
3. Novel Kernel Pointer Leak: Perhaps the most critical finding is the successful leakage of a kernel heap pointer in under 65 seconds. This is a significant breakthrough, as it marks the first time a kernel pointer has been leaked using a side channel. This attack directly undermines the effectiveness of Kernel Address Space Layout Randomization (KASLR) for heap objects, a cornerstone of modern kernel security.

The research conclusively establishes that KernelSnitch is a software-induced side channel, meaning it does not rely on specific hardware vulnerabilities, and is largely hardware agnostic. Furthermore, the disclosure of KernelSnitch to the Linux security team and the subsequent reaction from prominent kernel developers, including Linus Torvalds, highlighted the severity of the issue, particularly the rejection of a proposed patch, leaving KernelSnitch exploitable to this day.

Technical Deep Dive

▶ Watch: Distinguishing hash bucket occupancy levels by timing (6:00)

The technical foundation of KernelSnitch relies on the predictable timing behavior of linked lists and hash tables within the Linux kernel. As established, the time taken to traverse a linked list (which forms a hash bucket) is directly proportional to its number of elements. KernelSnitch exploits this by having an attacker (or receiver) continuously measure the latency of specific syscalls that access these kernel data structures. Meanwhile, a cooperating attacker (or sender) or even an unsuspecting target application (like a web browser) can manipulate the occupancy of these structures using other syscalls.

The core mechanism for observation and manipulation involves the aforementioned access primitives and append/remove primitives. These syscalls, while seemingly innocuous, provide the necessary side channel. For instance, a syscall to get the time from a POSIX timer acts as an access primitive. Internally, this syscall performs a hash calculation using a combination of a kernel address and a user identifier. The result of this hash determines which specific hash bucket is accessed. By measuring the timing of this syscall, an attacker can infer the occupancy level of that particular hash bucket. Conversely, creating a new POSIX timer acts as an append primitive, adding an element to a hash bucket and thereby increasing its access latency for subsequent probes.

The most technically sophisticated and impactful attack presented is the kernel pointer leak. This attack targets the syscall's internal hash function: hash(kernel_address, user_identifier) -> hash_bucket_index. The attacker knows the specific hash function (as it's open source in the Linux kernel) and can control the user identifier (which is an input to the syscall). However, the critical unknown is the kernel address – the very piece of information KASLR is designed to protect.

The exploitation strategy for leaking kernel pointers is ingenious:

1. Collision Detection Phase: The attacker repeatedly calls the chosen access primitive syscall with a fixed, but unknown, kernel address (the target pointer they wish to leak) but with a wide range of different user identifiers. Due to the inherent properties of hash functions, even with the same kernel address, different user identifiers will inevitably lead to hash collisions – meaning multiple distinct (kernel_address, user_identifier) pairs will map to the same hash bucket. The attacker uses KernelSnitch to detect these collisions by observing the timing. If two different user identifiers consistently result in syscalls that exhibit similar, slower timings, it suggests they are hitting the same, occupied hash bucket. This creates a set of (user_identifier, timing_profile) pairs that indicate collisions.
2. Offline Brute Force Phase: With the collision information gathered, the attacker moves to an offline brute-force phase. They systematically test all possible candidate kernel addresses. For each candidate kernel address, they re-calculate the hash for the same set of user identifiers used in the collision detection phase. The goal is to find a candidate kernel address that, when combined with the previously determined user identifiers, perfectly reproduces the observed hash collisions and their corresponding timing profiles. The unique pattern of collisions effectively acts as a "fingerprint" for the unknown kernel address.

The researchers successfully demonstrated this attack on the futex hash table. In this specific context, the user identifier is a user address, and the kernel address is the mm_struct (memory management structure) pointer. By considering the typical alignment of mm_struct by the page allocator and slab allocator, the search space for the mm_struct pointer was narrowed down to approximately 2^35 different kernel addresses. Despite this seemingly large space, the attack successfully identified the correct mm_struct pointer in less than 65 seconds, a remarkably short time for a KASLR bypass. This technical feat highlights the severity of the KernelSnitch vulnerability, proving that a low-level timing side channel can directly compromise high-level security mechanisms.

Demo / Proof of Concept

▶ Watch: Website fingerprinting attack with high F1 score (7:55)

The KernelSnitch research was underpinned by three concrete demonstrations, showcasing the versatility and impact of this novel side channel.

The first proof of concept was a cover channel, designed to demonstrate the bidirectional communication capabilities through kernel data structure manipulation. In this setup, a sender process encodes binary messages (0s and 1s) by either appending elements to a specific kernel hash bucket (for a '1') or removing them (for a '0'). Simultaneously, a receiver process continuously probes the occupancy level of that same hash bucket by measuring the timing of its access primitive syscalls. A fast timing is interpreted as a '0', while a slow timing signifies a '1'. The researchers meticulously validated this by reducing the time slice per bit from 1 second down to 1 microsecond. This experiment successfully established a true capacity of 580 kilobits per second, illustrating the potential for high-bandwidth covert communication between isolated processes.

The second demonstration involved a website fingerprinting attack, which is a more realistic threat scenario where the attacker ("spy process") does not control the target ("browser process"). In this case, the browser's normal operation of accessing various websites inherently appends and removes elements from numerous kernel hash buckets as it performs various syscalls. The spy process continuously probes all accessible hash buckets, collecting a rich stream of timing data. Each website, due to its unique interaction pattern with the kernel, generates a distinct "fingerprint" in the aggregated timing data. The researchers analyzed the top 100 websites and, with the assistance of Yolas, developed a convolutional neural network (CNN) to process the collected timing profiles. This CNN was able to identify which website was being accessed with an impressive F1 score of 89.3%. The data collection for each website involved approximately 15 seconds of browsing, repeated 50 to 100 times to build robust fingerprints.

The third and arguably most critical demonstration was the kernel pointer leak. This was a direct proof of concept for bypassing KASLR for heap objects. As detailed in the technical deep dive, the attack focused on the futex hash table and aimed to leak the address of the mm_struct pointer. The attacker executed the syscall access primitive with different user identifiers while observing the resulting timing profiles to detect hash collisions. This data, representing a unique collision pattern, was then used in an offline brute-force phase against a search space of 2^35 potential mm_struct addresses. The success of this demonstration was profound: the correct mm_struct pointer was identified and leaked in less than 65 seconds. This concrete proof of concept unequivocally validated the ability of KernelSnitch to compromise a fundamental security mitigation in modern operating systems.

Defensive Implications

▶ Watch: Leaking kernel pointers using side-channel techniques (8:40)

The discovery of KernelSnitch presents significant defensive implications for operating system security. The fundamental problem it exposes is the leakage of sensitive kernel state information (specifically, the occupancy levels of kernel data structures) through observable timing variations from user space. This directly undermines the principle of isolation between user processes and the kernel, as well as between different user processes sharing the same kernel resources.

One of the most critical defensive implications is the compromise of Kernel Address Space Layout Randomization (KASLR). While KASLR is designed to randomize the memory locations of kernel code and data to hinder exploitation, KernelSnitch demonstrates that for kernel heap pointers (such as the mm_struct pointer), KASLR can be effectively bypassed. The ability to leak a kernel heap pointer in under 65 seconds provides an attacker with the necessary information to craft more sophisticated exploits, such as ROP (Return-Oriented Programming) chains, by knowing the exact memory layout of critical kernel objects.

The response from the Linux security team to the KernelSnitch disclosure further highlights the challenge. While the vulnerability was acknowledged, a proposed patch by Keith Cook aimed at introducing a randomized value into hash calculations to mitigate the side channel was rejected by Linus Torvalds. Torvalds' rationale was that KASLR is already considered "broken for local excesses" for kernel code pointers, and he dismissed the proposed fix as "voodoo programming." However, the critical distinction, as noted by Keith Cook, is that KernelSnitch leaks a kernel heap pointer, for which KASLR was still assumed to provide protection. The rejection of the patch means that KernelSnitch remains exploitable in the Linux kernel to this day.

Defenders need to reconsider how kernel data structures are accessed and managed in light of these findings. Potential mitigation strategies, though not explicitly detailed as proposed by the researchers in the talk, would generally involve:

1. Constant-Time Operations: Modifying kernel code to ensure that access times to critical data structures are constant, regardless of their occupancy level. This could involve padding, introducing dummy elements, or always traversing a fixed number of elements.
2. Noise and Randomization: Injecting artificial noise or random delays into syscall timings to obscure the true occupancy-dependent variations. However, this often comes with a performance overhead.
3. Hash Function Hardening: Redesigning kernel hash functions to be less susceptible to collision-based timing attacks, perhaps by incorporating truly unpredictable, user-uncontrolled entropy that varies per syscall or process.
4. Resource Isolation: Stricter isolation of kernel resources, preventing untrusted user processes from influencing the state of hash buckets accessed by other processes or the kernel itself in a measurable way.

Ultimately, KernelSnitch serves as a stark reminder that even seemingly minor timing variations in core operating system components can have profound security implications, requiring a re-evaluation of fundamental design principles to ensure robust isolation and confidentiality.

Key Takeaways

• KernelSnitch is a novel operating system side channel that exploits timing differences in accessing kernel data structures, specifically linked lists within hash buckets.
• It enables information leakage amplifications, allowing untrusted user-space processes to deduce security-critical information by observing syscall latency.
• The research demonstrated a high-bandwidth cover channel with a true capacity of up to 580 kilobits per second and an effective website fingerprinting attack achieving an F1 score of 89.3% using a convolutional neural network.
• Crucially, KernelSnitch achieved the first-ever kernel heap pointer leak via a side channel, compromising the mm_struct address in less than 65 seconds and effectively bypassing KASLR for heap objects.
• The attack is software-induced and largely hardware agnostic, making it a pervasive threat across various system configurations.
• Despite disclosure, a proposed mitigation patch was rejected by Linus Torvalds, leaving the Linux kernel vulnerable to KernelSnitch attacks to this day.

About the Speaker(s)

Lukas Maar is the presenter of the KernelSnitch research, which explores side-channel attacks on kernel data structures. He collaborated with Yolas on aspects of the work, particularly the website fingerprinting attack. The presentation at the NDSS Symposium highlights his expertise in operating system security and side-channel analysis. Beyond his name and affiliation with a research group, no further specific titles or companies were mentioned in the provided transcript.