KernelSnitch Side-Channel Attacks on Kernel Data Structures

Paper Summary | NDSS 2025 | Generated by Hermes Agent

---

Executive Summary: KernelSnitch presents a new class of software-induced timing side-channel attacks targeting Linux kernel data container structures (hash tables, radix trees, red-black trees). By measuring syscall time variances caused by occupancy-level differences in shared kernel structures, an unprivileged, isolated attacker can leak sensitive information. Two amplification methods (cache thrashing and element inflation) make even single-element differences distinguishable. Three case studies demonstrate: a covert channel at up to 580 kbit/s, a kernel heap pointer leak (mm_struct address) in under 65 s, and a website fingerprinting attack with 89.5% F1 score — all from a sandboxed user-space process with no hardware side channels required. Disclosed to the Linux kernel security team; mitigations remain challenging.

---

1. High-Level Overview

This paper, from the Graz University of Technology security group (Gruss, Mangard et al.), identifies a generic timing side channel in the Linux kernel that exists regardless of whether hardware side channels (caches, ports) are eliminated. The core insight: kernel data container structures (hash tables, trees) have variable occupancy levels, and syscalls that iterate through these structures take proportionally longer with more elements. An unprivileged process can measure these timing differences to infer secrets from other processes or from the kernel itself.

Key novelty: Prior software side channels targeted specific kernel components (slab allocator, page cache); KernelSnitch is the first to show that any shared kernel data structure that varies in size creates a timing side channel observable from user space.

2. Threat Model

• Unprivileged, isolated attacker — runs code on the same machine as the victim, but is strictly sandboxed (no shared memory, no network, no kernel privileges)
• No microarchitectural side channels assumed (no caches, no ports)
• Only requires standard Linux syscalls available to any user-space process
• Three distinct scenarios: covert channel (two co-located processes), kernel heap pointer leak (kernel as oracle), website fingerprinting (browser activity observation)

3. Vulnerable Data Structures

KernelSnitch exploits four types of kernel data container structures:

Structure	Instance	Leak Mechanism	Syscall Used
Fixed-size hash table	futex_hash_table (futex queues)	Bucket linked-list iteration	sys_futex_wait / sys_futex_wake
Fixed-size hash table	posix_timers_hashtable (POSIX timers)	Bucket linked-list iteration	sys_timer_create / sys_clock_gettime
Dynamically resizable hash table	ipc_ids.key_ht (IPC objects)	Bucket linked-list iteration	sys_msgcreate / sys_msgget
Radix tree	ipc_ids.ipcs_idr.root_rt (IPC IDs)	Tree level depth on lookup	sys_msgcreate / sys_msgstat
Red-black tree	hrtimer_bases.clock_base.active (high-res timers)	Logarithmic enqueue time vs occupancy	sys_timerfd_create / sys_timerfd_settime

4. Leakage Amplification (Two Methods)

A critical challenge: the timing difference between occupancy levels can be as few as 8 extra instructions (e.g., POSIX timer hash table). Two amplification methods make the difference measurable:

Structure-Agnostic Amplification (Cache Thrashing)

• Evict the Last Level Cache (LLC) by accessing a large array, causing memory loads in kernel syscalls to miss cache
• Each extra load then takes hundreds of cycles instead of a few cycles
• Aggravates timing differences for any data structure

Hardware-Agnostic Amplification (Element Inflation)

• Append extra elements to the target data structure before probing
• For hash tables: call sys_futex_wait with the same uaddr/mm to fill the same bucket
• For radix trees: fill all 64 first-level slots, then alternate insert/remove of a key that forces a second tree level
• Works without any hardware-specific knowledge

Results: Without amplification: 1.8% FPR / 10.0% FNR. With both amplifications: 0% FPR and FNR on idle systems, >98.5% accuracy under 3/4 CPU load.

5. Case Study 1: Covert Channel

• Two co-located processes use the occupancy level of a shared kernel structure as a communication medium
• Sender modulates bit ‘1’ by appending elements, bit ‘0’ by removing elements
• Receiver probes occupancy level in fixed time slices
• Results (true capacity / bit-error rate):
  • Fixed-size hash table (futex): 580 kbit/s @ 2.8% BER
  • Resizable hash table (IPC): 528 kbit/s
  • Radix tree: 483 kbit/s
  • Red-black tree: 35 kbit/s
• Previous best software covert channel (mutex-based) achieved only 13.1 kbit/s

6. Case Study 2: Kernel Heap Pointer Leak

• The Linux futex hash table uses jhash2(m_struct, uaddr) for indexing — combining a kernel secret (mm_struct address) with a user-controlled (uaddr) value
• By detecting hash collisions from user space, the attacker can enumerate possible kernel addresses offline and match the collision pattern
• Search space reduced to ≈2^35.5 using alignment constraints (page allocator + slab allocator)
• Results: mm_struct address leaked in 3.7–63.6 seconds across 10 runs
• Cross-cache reuse technique then places msg_msg objects at the leaked address, revealing additional kernel heap pointers
• First demonstration of a kernel heap pointer leak via side channel (not just KASLR break)
• Works on x86_64, AArch64, and RISC-V

7. Case Study 3: Website Fingerprinting

• Firefox uses futexes for user-space locking during network I/O; accessing different websites creates unique occupancy fingerprints in the futex hash table
• Attacker probes all futex hash table buckets 20 times/second during 15 s website loading window
• Two-dimensional traces (bucket × time) fed into a CNN with 9 convolutional layers
• Results: 89.3% F1 score across Ahrefs Top 100 websites (5-fold cross-validation), up to 89.5% in best fold

8. Mitigations Discussed

Approach	Feasibility	Limitation
Remove precise timing	Hard	Breaking change; attackers find alternatives
Separate privileged/unprivileged info in hash keys	Partial	Only prevents heap leaks, not covert channels or fingerprinting
Watermark constant-time	Moderate	Bounded overhead; watermark adjustment needed
Isolate container structures per namespace	Very hard	Major kernel redesign; extreme memory/performance overhead

The paper highlights a fundamental trade-off between resource isolation and resource sharing: kernel data structures must be shared for efficiency, but sharing creates side channels. The authors suggest quantification research (“How much leakage is tolerable?”) as a future direction.

9. Key Findings and Significance

1. Side channels exist even without hardware leakage — pure software timing differences from kernel data structures are exploitable
2. The attack is universal — exploits the inherent design of hash tables, radix trees, and red-black trees, not implementation bugs
3. Hardware-independent — verified across Intel i7-1260P, Xeon Gold 6530, AMD EPYC 7443, and Raspberry Pi 4 (AArch64)
4. Practical leakage rates — 580 kbit/s covert channel exceeds prior software-only channels by 40×
5. No sandbox can prevent this — the kernel itself is the shared resource; all sandboxed processes on the same kernel are potentially vulnerable
6. Disclosed to Linux kernel security team — no patches available at publication

10. Limitations

• Covert channel on IPC and red-black tree structures restricted to same IPC namespace (container/browser sandboxes may prevent this)
• Radix tree amplification requires filling 64 first-level slots first (high setup overhead)
• Website fingerprinting CNN may degrade under heavy system load (frequency scaling noise)
• Cross-cache reuse timing highly variable (0.85–0.90 s per reuse step)
• Red-black tree covert channel limited to 35 kbit/s due to slow append/probe operations

TL;DR

KernelSnitch exploits kernel data structure occupancy as a timing side channel observable from user space. With cache-thrashing and element-inflation amplification, an unprivileged attacker achieves 580 kbit/s covert channels, kernel heap pointer leaks in <65 s, and 89.5% website fingerprinting accuracy. The attack is hardware-agnostic and cannot be prevented by user-space constant-time code — it represents a fundamental software-level side channel in the operating system’s shared data structures.

---

Sources

1. NDSS 2025 Paper (DOI): https://dx.doi.org/10.14722/ndss.2025.240223
2. NDSS Paper Page: https://www.ndss-symposium.org/ndss-paper/kernelsnitch-side-channel-attacks-on-kernel-data-structures/
3. Open-source Code (Zenodo): https://doi.org/10.5281/zenodo.14249716
4. Authors: Lukas Maar, Jonas Juffinger, Thomas Steinbauer, Daniel Gruss, Stefan Mangard — Graz University of Technology