Efficient and Generic Microarchitectural Hash-Function Recovery

Efficient and Generic Microarchitectural Hash-Function Recovery

Speakers: Lukas Gerlach; Simon Schwarz; Nicolas Faraß; Michael Schwarz

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=sHWj44C-ohA

Overview

In the realm of modern computing, microarchitectural details often remain opaque, treated as proprietary intellectual property by hardware manufacturers. This talk, "Efficient and Generic Microarchitectural Hash-Function Recovery," presented by Lukas Gerlach, Simon Schwarz, Nicolas Faraß, and Michael Schwarz at IEEE S&P, delves into the critical challenge of reverse engineering these hidden components, specifically focusing on microarchitectural hash functions. These functions are fundamental to the efficient operation of contemporary processors, responsible for load balancing across various hardware elements such as cache slices, DRAM addressing, and cache way predictors.

The speakers unveil a novel, automated approach that significantly streamlines the recovery of these complex functions. Their research highlights the increasing prevalence of non-linear hash functions in modern heterogeneous CPUs, a shift that complicates traditional reverse engineering efforts. By combining a new measurement framework with an innovative logic minimization technique, the team demonstrates how to efficiently uncover these functions, which were previously considered intractable or required months of manual effort. The implications of this work are far-reaching, impacting both offensive security research, enabling more precise side-channel attacks, and defensive strategies, potentially allowing for better cache utilization and attack prevention.

Background

▶ Watch: Introduction to caching using a container ship analogy (0:00)

Modern processors rely heavily on caching to bridge the vast speed gap between the CPU and main memory (DRAM). Caches are organized into multiple sub-partitions, often called slices or ways, to distribute memory accesses and improve performance. When the CPU requests data, its physical address is fed into a microarchitectural hash function (also referred to as a slice mapping function or index function) to determine which cache slice, DRAM bank, or other microarchitectural element will store or provide the data. These functions are crucial for efficient load balancing, ensuring that memory requests are spread evenly across the available hardware resources.

Historically, simpler processors often employed linear hash functions, typically involving XOR operations on address bits, especially when the number of slices was a power of two. This design provided uniform distribution for randomly distributed inputs. However, as CPUs have evolved, incorporating heterogeneous cores (e.g., performance and efficiency cores) and non-power-of-two slice counts, the underlying hash functions have become increasingly complex and non-linear. This complexity is necessary to maintain effective load balancing under more varied workload conditions and hardware configurations.

The problem, however, is that these microarchitectural hash functions are rarely documented by manufacturers, treated as highly proprietary intellectual property. This lack of transparency creates significant hurdles for security researchers and software developers alike. Attackers need to understand these functions to precisely target specific cache slices for side-channel attacks, thereby increasing their efficacy. Defenders and optimizers, on the other hand, could leverage this knowledge to improve cache utilization, write more performant software, or even design memory allocation strategies that actively prevent cache-based side-channel attacks by ensuring victims and attackers do not share the same microarchitectural resources. Prior work has attempted to reverse engineer these functions, but largely struggled with the complexity of non-linear functions and the computational overhead of existing minimization techniques.

Key Findings

▶ Watch: Why understanding microarchitectural hash functions is critical (4:00)

The talk presents several key findings that collectively enable the efficient and generic recovery of microarchitectural hash functions:

1. Novel Measurement Framework: The researchers developed a new framework capable of measuring which address maps to which microarchitectural element (e.g., cache slice). This framework supports two primary measurement techniques:

• Performance Counters: On systems with available performance counters that expose slice mapping information, these can be directly leveraged.
• Timing Measurements: For systems without direct counter access, a more general approach using timing side channels is employed. By observing varying latencies to different slices from different cores, the framework can infer slice assignments.

This framework utilizes a divide-and-conquer approach, assuming output bits of the function are independent and measuring each bit individually, significantly reducing measurement complexity compared to prior holistic methods.

1. Prevalence of Non-Linear Functions: The research empirically confirms that modern processors increasingly utilize non-linear Boolean functions for microarchitectural hashing. This shift is driven by the advent of heterogeneous core designs (e.g., Intel's P-cores and E-cores) and the need to support non-power-of-two numbers of cache slices or other microarchitectural resources. Linear XOR-based functions, while simple, fail to provide adequate load balancing in these complex scenarios.

1. Limitations of Standard Logic Minimization: The speakers identify a critical bottleneck in existing logic minimization algorithms, such as the widely used Espresso algorithm. While Espresso is a de-facto standard for heuristic minimization of Boolean functions in Disjunctive Normal Form (DNF), it performs poorly when functions contain many XOR operations or nested linear components. Unfolding such functions into DNF leads to an exponential blow-up in representation size, making efficient minimization practically impossible.

1. Novel Logic Minimization Technique: The most significant contribution is a new, hybrid logic minimization approach specifically tailored for the class of microarchitectural hash functions. This method combines:

• Initial DNF minimization using Espresso.
• Conversion of the DNF representation into a polynomial representation over GF(2) (Galois Field with two elements).
• Computation of a Gröbner basis for this polynomial representation. The Gröbner basis, while not guaranteed to be minimal in all cases, empirically yields significantly smaller and more manageable representations for the target function class.
• Unfolding the Gröbner basis back into a minimal Boolean formula.

This approach drastically reduces the time required for minimization, transforming tasks that previously took "multiple months" into processes completable "in a single day."

1. Practical Attack Demonstrations: The recovered functions were successfully applied to mount highly effective Prime+Probe side-channel attacks against vulnerable AES table implementations. These attacks achieved between 97% and 99% correct key recovery with a brute-force effort of less than one second, demonstrating the critical impact of precise knowledge of these microarchitectural details.

Technical Deep Dive

▶ Watch: The problem: Undocumented microarchitectural hash functions (5:00)

The core of this research lies in tackling the dual challenges of accurately measuring microarchitectural hash functions and then efficiently minimizing their Boolean representations.

The measurement framework is designed for generality, accommodating different hardware environments. For systems where processor vendors expose performance counters that directly indicate which cache slice an access mapped to, the process is relatively straightforward. The researchers employ a divide-and-conquer strategy: instead of attempting to infer the entire multi-bit output function at once, they focus on determining each output bit independently. To do this, they use the clflush instruction to invalidate specific cache lines, forcing data to be re-fetched. By accessing carefully chosen addresses and observing the activation of performance counters associated with different slices, they can deduce the mapping for individual bits.

In the more common scenario where direct performance counters are unavailable, the framework leverages timing measurements as a side channel. The key insight here is that different CPU cores might have varying physical distances or interconnect paths to different cache slices. Consequently, accessing a specific cache slice from different cores will exhibit slightly different latencies. The process involves:

1. Activating a specific cache slice by accessing a target address and using clflush to ensure it's in a known state.
2. Recording the access timing from one core.
3. "Hopping" to other cores and repeating the timing measurement for the same cache slice.
4. The slice that shows the lowest access time from a particular core is inferred to be the one physically closest or most efficiently accessible by that core. By systematically mapping addresses to their corresponding timing profiles across cores, the framework can build a dataset of address-to-slice mappings.

Once the address-to-slice mappings are collected, the output is a truth table representing the Boolean function. The next, and arguably more complex, challenge is logic minimization. As mentioned, modern CPUs often use non-linear functions because linear functions (simple XOR chains) fail to provide uniform load balancing when the number of slices is not a power of two or when heterogeneous cores introduce asymmetric access patterns. For example, performance cores might be allocated more cache slices than efficiency cores, necessitating a more intricate mapping.

The problem with minimizing arbitrary Boolean functions is that it is provably hard (NP-hard in general). Traditional algorithms like Espresso are designed to minimize functions represented in Disjunctive Normal Form (DNF). A DNF formula is a sum of products (e.g., (A AND B) OR (C AND D)). However, microarchitectural hash functions often contain numerous XOR operations. Converting an XOR-heavy function into DNF leads to an exponential blow-up in the number of terms and literals. For instance, X1 XOR X2 XOR X3 in DNF becomes (X1 AND NOT X2 AND NOT X3) OR (NOT X1 AND X2 AND NOT X3) OR (NOT X1 AND NOT X2 AND X3) OR (X1 AND X2 AND X3). This expansion makes Espresso's heuristic minimization inefficient and impractical for functions of even moderate complexity.

To overcome this, the speakers propose a novel, multi-stage minimization pipeline:

1. Initial DNF Minimization (Espresso): The raw truth table from measurements is initially converted into a DNF formula and subjected to a quick minimization pass using Espresso. This provides a baseline, albeit potentially still inefficient, representation.
2. Conversion to Polynomial Representation: The DNF formula is then converted into a polynomial representation over GF(2). In this field, AND operations become multiplication, and XOR operations become addition. For example, A AND B is A*B, and A XOR B is A + B. While OR operations can also be represented (A OR B = A + B + A*B), the target functions typically have few ORs, so this conversion is efficient for XOR-heavy functions.
3. Gröbner Basis Computation: This is the pivotal step. The polynomial representation is then used to compute a Gröbner basis. A Gröbner basis is a special kind of generating set for a polynomial ideal, which allows for systematic simplification and reduction of polynomials. For the class of low-depth, XOR-heavy Boolean functions found in microarchitectural hashing, computing a Gröbner basis empirically yields a significantly smaller and more canonical representation of the equivalent polynomial. This is computationally feasible for the input sizes typically encountered (e.g., 64 address bits mapping to a few output bits).
4. Unfolding to Minimal Formula: Finally, the simplified Gröbner basis representation is unfolded back into a minimal Boolean formula, which is ready for use.

This hybrid approach, by strategically switching between DNF and polynomial representations and leveraging Gröbner bases, provides an efficient and effective solution for minimizing the specific class of Boolean functions found in microarchitectural hash functions, reducing the time from months to a single day.

Demo / Proof of Concept

▶ Watch: Divide and conquer measurement example with performance counters (7:00)

While the talk did not feature a live, interactive "demo" in the traditional sense, the practical utility and validation of their research were demonstrated through its application to Prime+Probe side-channel attacks. The ability to accurately reverse engineer microarchitectural hash functions (specifically cache slice functions) directly translates into a significantly enhanced capability for attackers to mount precise and effective side-channel attacks.

The researchers applied their recovered functions to target AES table implementations. AES, a widely used symmetric encryption algorithm, often relies on lookup tables (e.g., T-tables) which are stored in the cache. In a Prime+Probe attack, an attacker "primes" the cache by filling it with their own data, then allows a victim process to execute, and finally "probes" the cache to see which lines were accessed by the victim. By observing cache hits and misses, the attacker can infer which parts of the victim's data (e.g., AES T-tables) were accessed, thereby leaking information about the secret key.

The precision offered by the reverse-engineered hash functions is paramount here. Instead of relying on statistical inference or brute-forcing potential slice mappings, an attacker equipped with the exact slice mapping function can:

1. Precisely control cache eviction: The attacker can craft addresses that are guaranteed to map to the same cache slice as the victim's target data, ensuring that priming operations effectively evict the victim's data.
2. Accurately identify victim accesses: During the probe phase, the attacker knows exactly which cache slices to monitor to detect accesses to specific AES T-table entries.

The results were compelling: using their recovered functions, the researchers achieved an accuracy of between 97% and 99% for correct key recovery when attacking vulnerable AES table implementations. Furthermore, the brute-force effort required for an attacker to recover the key was reduced to under one second. This highlights the practical and immediate security implications of their work, demonstrating that precise knowledge of these undocumented microarchitectural details can transform a theoretical attack into a highly potent and practical threat. This successful application serves as a strong proof of concept for the efficiency and accuracy of their hash function recovery methodology.

Defensive Implications

▶ Watch: Generalizing measurements using timing when counters are unavailable (8:00)

The detailed understanding and efficient recovery of microarchitectural hash functions presented in this talk offer several crucial defensive implications for system architects, software developers, and security practitioners.

Firstly, the most direct implication relates to side-channel attack mitigation. Current defenses against cache-based side-channel attacks often rely on coarse-grained techniques or heuristics due to the opaque nature of cache slice mappings. With the ability to precisely determine these functions, defenders can implement more robust and targeted countermeasures. For instance, memory allocators could be designed to be "slice-aware," ensuring that sensitive data belonging to different security domains (e.g., an attacker and a victim process) are never allocated to memory regions that map to the same cache slice. This could effectively prevent many cache-based side-channel attacks by eliminating the shared resource contention that these attacks exploit. Similarly, operating systems could gain better control over cache resource isolation.

Secondly, the insights into the shift towards non-linear hash functions in modern, heterogeneous CPUs are vital. Defenders need to understand that the complexity of these functions is increasing, making them harder to reason about and secure against without specific knowledge. Relying on assumptions about simple, linear mappings is no longer sufficient. This necessitates a proactive approach to understanding hardware microarchitecture, even if it remains proprietary.

Thirdly, beyond security, knowledge of these functions can lead to performance optimizations. Software, particularly high-performance computing applications, could be written to have better cache utilization. By understanding how data maps to cache slices, developers could arrange data structures in memory to minimize cache conflicts, improve spatial locality, and optimize cache line utilization, leading to faster execution times.

Finally, the talk implicitly calls for greater transparency from hardware vendors regarding these critical microarchitectural details, or at least the provision of tools or interfaces that allow for secure and efficient interaction with these features. In the absence of such transparency, the methodology presented here provides a powerful tool for researchers and defenders to gain the necessary insights to build more secure and efficient systems.

Key Takeaways

• Microarchitectural hash functions are critical for load balancing in CPUs but are largely undocumented intellectual property.
• Modern CPUs increasingly use non-linear Boolean functions for hashing, driven by heterogeneous core designs and non-power-of-two slice counts, making reverse engineering harder.
• A new measurement framework using divide-and-conquer, supporting both performance counters and timing measurements, efficiently collects address-to-slice mappings.
• A novel logic minimization approach combines Espresso with Gröbner basis computation on polynomial representations to efficiently minimize complex, XOR-heavy Boolean functions, reducing processing time from months to days.
• The recovered functions enable highly effective Prime+Probe side-channel attacks on AES, achieving 97-99% key recovery with sub-second brute-force effort.
• Defenders can leverage this knowledge for slice-aware memory allocation to prevent cache attacks and for optimizing software for better cache utilization.

About the Speaker(s)

The talk "Efficient and Generic Microarchitectural Hash-Function Recovery" was a collaborative effort by Lukas Gerlach, Simon Schwarz, Nicolas Faraß, and Michael Schwarz. Based on the presentation, the team's expertise lies in microarchitectural security and reverse engineering. Lukas Gerlach, Simon Schwarz, Nicolas Faraß, and Michael Schwarz are affiliated with institutions such as Zand University (likely a reference to TU Graz or a similar academic institution given Michael Schwarz's known affiliations) and CISPA Helmholtz Center for Information Security. Michael Schwarz is a well-known researcher in the field of microarchitectural attacks and side channels. Their collective work demonstrates deep understanding and practical experience in analyzing complex hardware behaviors and developing innovative techniques to overcome the challenges of undocumented processor internals.