SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields

SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields

Speakers: Jean Paul Degabriele; Jan Gilcher; Jérôme Govinden; Kenneth G. Paterson

Conference: IEEE S&P

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

Overview

This talk, presented by Jérôme Govinden and Jan Gilcher, delves into a comprehensive Systematization of Knowledge (SoK) regarding the design and implementation of polynomial hash functions over prime fields. The core objective of their research is to systematically explore the vast design space for these cryptographic primitives, aiming to create new, more efficient, and secure alternatives to established functions like Poly1305. The work highlights the apparent disconnect between existing designs, often optimized for older hardware paradigms, and the capabilities of modern computing architectures.

The speakers meticulously detail how current polynomial hash functions, despite their widespread adoption, suffer from limitations that compromise their security and performance on contemporary systems. By dissecting the various design and implementation choices, the team has not only organized existing knowledge but also developed a modular benchmarking framework to empirically test new constructions. This systematic approach has led to the proposal of five novel polynomial hash functions that offer superior security-performance tradeoffs, specifically targeting modern 64-bit architectures while maintaining simplicity and compatibility with various optimization strategies.

The significance of this research cannot be overstated. Polynomial hash functions are fundamental building blocks in modern cryptography, underpinning the security of message authentication codes (MACs), authenticated encryption with associated data (AEAD) schemes, and various network protocols. As such, improving their efficiency and security has direct implications for the robustness and speed of secure communication across a multitude of applications, from TLS to WireGuard and even the Bitcoin Lightning Network. This talk provides a critical analysis of current practices and a clear roadmap for the next generation of these essential cryptographic tools.

Background

▶ Watch: Introduction to efficient polynomial hash functions SoK (0:00)

The talk begins by establishing the foundational role of polynomial hash functions, particularly Poly1305, in modern cryptography. Poly1305 satisfies the security notion of Delta universality, meaning it is computationally hard to find two distinct messages, m and m', such that the difference between their hash evaluations H(m) - H(m') equals a given value Z. This property makes it highly suitable for applications such as data structures, message authentication codes (MACs), and authenticated encryption schemes. Notably, ChaCha20-Poly1305 is a widely adopted AEAD scheme, with Poly1305 serving as its MAC component.

Poly1305's journey to prominence is remarkable: designed independently by Bernstein, it was combined into an IETF draft in 2013, quickly adopted by Chrome and OpenSSH, finalized in RFC 7539 in 2015, and selected for TLS and as a default in OpenSSH and WireGuard by 2016. Its success stems from its conservative and simple design, prioritizing performance across architectures without requiring specific hardware support like AES-NI or carry-less multiplication. It also serves as a crucial fallback algorithm in scenarios where vulnerabilities might be discovered in other popular schemes like AES-GCM.

Despite its widespread adoption and perceived robustness, Poly1305 exhibits several limitations in the context of modern hardware and security requirements. Firstly, its design incorporated clamping, a procedure where 22 bits of the 128-bit key R are set to zero. This was originally intended to facilitate fast implementations using floating-point units (FPUs). However, most contemporary implementations utilize integer arithmetic instructions, rendering the FPU optimization irrelevant and resulting in a reduction of the effective security from 128 bits to 103 bits. Secondly, Poly1305 was primarily tailored for 32-bit architectures, making its performance on modern 64-bit systems suboptimal. Lastly, an analysis by Jean Paul Degabriele revealed that Poly1305 possesses limited multi-user security, a critical concern in environments where a single hash function instance might be used across multiple distinct communication channels.

These limitations underscore a growing disconnect between Poly1305's design and modern hardware capabilities. This realization prompted the authors to systematically revisit the entire design space for polynomial hash functions. They identified that knowledge regarding optimal design and implementation choices was scattered across various sources, creating a need for a Systematization of Knowledge (SoK). This SoK classifies design choices (fixed during specification) and implementation choices (left to implementers), highlighting their complex interplay. The goal was to clarify how design decisions constrain implementation options and how implementers' feedback should inform future design specifications, ultimately striving to answer whether the same design would emerge if conceived today.

Key Findings

▶ Watch: Critical limitations and drawbacks of the Poly1305 design (2:59)

The central finding of this research is the critical need for a systematic, modular, and empirically driven approach to designing and implementing polynomial hash functions. Given the vast and complex design space, coupled with the varied performance characteristics across different hardware architectures, theoretical predictions alone are insufficient. This necessitates a framework that allows for the modular configuration and automated generation of hash function implementations, followed by rigorous benchmarking.

The authors established clear goals for their new designs:

1. Efficiency: Achieve a better runtime-security tradeoff than Poly1305.
2. Simplicity and Familiarity: Ensure designs are easy for developers to understand and adopt.
3. Optimization Flexibility: Allow for diverse optimization strategies without tailoring to a specific implementation (e.g., avoiding FPU-specific designs like Poly1305's clamping).
4. Hardware Agnosticism: Design for general performance without being locked into specific hardware features or instruction sets.

To meet these goals, the new designs incorporate several key characteristics:

• No Clamping: Eliminating the security loss associated with FPU-driven clamping.
• Classical Polynomials over Prime Fields (FP): Sticking to a well-understood and secure polynomial structure.
• Full Limb Packing: Maximizing the utilization of machine words (limbs) to enhance efficiency.
• Support for Advanced Optimization Strategies: Specifically allowing for delayed reduction and two-level polynomial evaluation strategies, which enable implementers to exploit CPU parallelism effectively.

Based on these principles, the research introduces five new polynomial hash functions: Poly1163, Poly1223, Poly1503, Poly1743, and Poly2663. These designs are categorized into three security/performance levels:

• High Performance at Poly1305 Security Level: Poly1163 and Poly1223 (with Poly1163 being suitable for both 32-bit and 64-bit architectures, and Poly1223 for 64-bit only).
• Higher Security at Poly1305 Performance Level: Poly1503 and Poly1743 (with Poly1503 being suitable for both 32-bit and 64-bit architectures, and Poly1743 for 64-bit only). These offer 30-50 bits higher security than Poly1305.
• Very High Security Level (Sacrificing Performance): Poly2663 (targeting 64-bit architectures only), which more than doubles Poly1305's security.

Benchmarking results demonstrate that, without any specific vectorization or hand-optimization, the generated implementations of these new designs perform remarkably well. Specifically, Poly1163 shows performance competitive with, and in some cases superior to, OpenSSL's AVX2-vectorized Poly1305 for messages up to 7KB. On older CPUs lacking AVX support, Poly1163 massively outperforms OpenSSL's integer fallback. The authors project that with vectorization, Poly1163 would significantly outperform Poly1305, and Poly1503 could achieve similar performance to Poly1305 while offering an additional 34 bits of security, making it an excellent drop-in replacement.

Technical Deep Dive

▶ Watch: Overview of the polynomial hash function design space (5:00)

The technical foundation of this work rests on a thorough understanding of polynomial hashing and its underlying arithmetic. Poly1305, as a key-dependent hash function, takes a key R and a message M. The message M is first split into fixed-size blocks, c_i, each padded with a single bit to form a coefficient. The 128-bit key R undergoes clamping, where 22 of its bits are set to zero. The core operation is the evaluation of a polynomial P(X) = c_n X^n + ... + c_1 X + c_0 at the point X=R, with the result reduced modulo 2^130 - 5. A final reduction modulo 2^128 produces the tag.

The research systematically explores the vast design space, categorizing choices into specification-level design choices and implementation-level choices.

• Encoding: The initial step involves encoding bit strings (key and message) into field elements. This requires decisions on block sizes, ensuring memory-aligned data for fast access, maintaining security, and compatibility with the chosen finite field.
• Polynomial Structure: The classical polynomial form, where message blocks are multiplied by powers of the key, is a common choice, as seen in Poly1305.
• Evaluation Strategies: Once the polynomial is defined, various evaluation strategies exist, such as Horner's rule and its optimized variants, which dictate how the polynomial is computed efficiently.
• Output Encoding: Finally, the resulting field element (the tag T) must be securely and efficiently encoded back into a bit stream.

A critical aspect highlighted is field multiplication, which is central to polynomial evaluation. In a machine, field elements are stored across multiple words, or limbs, depending on the architecture's word size W.

• Saturated Representation: In this approach, all limbs are filled to their maximum capacity, except potentially the last one. The problem with saturated representation arises during schoolbook multiplication (the standard long multiplication algorithm). When summing intermediate products, terms in the same column can become saturated, making it impossible to sum them without first performing a limb alignment operation, which is costly. Poly1305's key clamping was an attempt to mitigate this by setting high bits of each limb in the key to zero, preventing saturation. However, this reduces security and is not exploitable by all polynomial evaluation algorithms.
• Unsaturated Representation: This is the more generally adopted approach, where the data of each field element is distributed as equally as possible among the limbs, ensuring there's always enough "headroom" in each limb to accommodate carries from additions without immediate overflow, thus avoiding the limb alignment problem.

To navigate this complex design space, the authors developed a sophisticated benchmarking framework. This framework takes modular configuration files as input, which define the parameters of a specific polynomial hash function. These configurations are then fed into an arithmetic generator that automatically produces optimized field arithmetic routines. This generated arithmetic is combined with high-level C implementations for polynomial evaluation, encoding/decoding, and a general hash function interface. A benchmarking harness is integrated, and the entire system is compiled using a standard C compiler to produce a hash function library and a benchmark executable. This automated generation and empirical testing pipeline allow for rapid exploration and validation of numerous design combinations.

The new designs specifically embrace an unsaturated representation and avoid clamping, ensuring full security and better leverage of 64-bit arithmetic. They are engineered to facilitate delayed reduction strategies, where intermediate results are allowed to grow larger than the prime modulus before being reduced, potentially enabling more operations to be batched and executed in parallel. Similarly, two-level polynomial evaluation techniques are supported, which can further exploit parallelism within modern CPUs. The selection of suitable primes for each of the five new hash functions was carefully considered to allow for efficient limb packing and to meet specific security targets, from slightly above Poly1305's 103 bits to over 200 bits for Poly2663.

Demo / Proof of Concept

▶ Watch: Deep dive into field multiplication and clamping challenges (5:58)

The "Demo / Proof of Concept" in this research takes the form of extensive benchmarking results generated by their custom framework, showcasing the performance of the newly designed polynomial hash functions against Poly1305. The authors compared their five new designs (Poly1163, Poly1223, Poly1503, Poly1743, and Poly2663) against two reference implementations of Poly1305: one generated by their own framework and another, highly optimized version from OpenSSL that utilizes AVX2 vectorization.

The initial performance graphs revealed that, with the exception of Poly2663 (which is designed for extremely high security at the cost of performance), all new designs fit neatly in the performance spectrum between their own generated Poly1305 and the OpenSSL AVX2-vectorized Poly1305. This is a significant achievement, as their generated implementations currently do not employ any specific vectorization (like AVX2) or hand-optimized assembly.

A standout performer is Poly1163. The benchmarks demonstrated that Poly1163 achieves remarkably high performance, coming very close to the vectorized OpenSSL Poly1305. For smaller messages, specifically those around 7 kilobytes or less, Poly1163 actually outperforms OpenSSL's AVX2-vectorized Poly1305. This highlights its efficiency even without specialized vector instructions.

Further analysis across different CPU architectures provided more compelling evidence:

• On an older CPU like the Intel Core i7 940, which does not support AVX instructions, OpenSSL Poly1305 falls back to a generic integer implementation. In this scenario, the generated Poly1305 was competitive with OpenSSL's fallback, while Poly1503 slightly outperformed it. Crucially, Poly1163 massively outperformed OpenSSL's Poly1305 on this architecture, showcasing its inherent efficiency on systems without advanced vector extensions.
• On a modern server CPU, the AMD Epyc, Poly1163 continued its impressive performance, outperforming vectorized OpenSSL Poly1305 for messages up to 16 kilobytes.

The speakers concluded by outlining their expectations for future optimizations. They anticipate that once vectorization (e.g., AVX2) is applied to their new designs, Poly1163 will achieve significant performance boosts, massively outperforming Poly1305 at the same security level. Similarly, Poly1503 is expected to reach performance levels comparable to Poly1305 while providing a substantial additional 34 bits of security, solidifying its position as a highly attractive replacement for Poly1305. These empirical results effectively serve as a proof of concept for the viability and superiority of their systematically designed polynomial hash functions.

Defensive Implications

▶ Watch: Solution: Modular framework for designing and benchmarking (7:59)

The research presented has profound implications for defenders and cryptographic implementers. The identified limitations of Poly1305—namely the security reduction due to clamping, its 32-bit architecture bias, and its constrained multi-user security—represent vulnerabilities or inefficiencies that modern systems should ideally avoid. The new polynomial hash functions proposed in this work directly address these shortcomings, offering a clear path to more robust and performant cryptographic primitives.

For developers and protocol designers, the key defensive implication is the availability of well-analyzed, systematically designed alternatives to Poly1305.

• Enhanced Security without Performance Sacrifices: Designs like Poly1503 offer a significant security upgrade (an additional 34 bits of security) while maintaining performance levels comparable to Poly1305. This means that systems relying on polynomial hashing can achieve a higher security margin against future attacks without incurring a performance penalty.
• Improved Performance on Modern Hardware: Poly1163 demonstrates superior performance, even outperforming vectorized Poly1305 in certain scenarios, especially on 64-bit architectures. This allows for faster message authentication, which can lead to reduced latency in network protocols and improved throughput in high-volume data processing.
• Elimination of Architectural Biases: By designing without FPU-specific clamping and explicitly considering 64-bit architectures, the new functions are inherently more suited to modern systems, ensuring consistent and optimal performance across a broader range of hardware.
• Guidance for Future Designs: The Systematization of Knowledge (SoK) provides a valuable framework for understanding the complex interplay between design and implementation choices. This can guide future cryptographic primitive development, ensuring that new designs are informed by empirical data and are resilient to evolving hardware landscapes.
• Drop-in Replacement Potential: The performance characteristics of Poly1163, especially on certain CPUs (e.g., AMD Epyc, or older CPUs lacking AVX), make it a strong candidate for a direct "drop-in replacement" for Poly1305. This simplifies migration for existing applications, allowing them to benefit from the improvements with minimal changes to their codebase.
• Proactive Vulnerability Mitigation: By adopting these newer, more conservatively designed hash functions, organizations can proactively mitigate risks associated with Poly1305's known limitations, such as its limited multi-user security, thereby strengthening the overall security posture of their applications and infrastructure.

In essence, this research empowers defenders with the knowledge and tools to select or implement polynomial hash functions that are better aligned with contemporary security requirements and hardware capabilities, moving beyond the legacy constraints of Poly1305.

Key Takeaways

• Poly1305's Limitations: Despite its widespread adoption, Poly1305 suffers from critical limitations, including a reduced security level (103 bits instead of 128) due to FPU-driven key clamping, suboptimal performance on modern 64-bit architectures, and limited multi-user security.
• Systematic Design is Crucial: The complex and vast design space for polynomial hash functions necessitates a "Systematization of Knowledge" approach, systematically classifying design and implementation choices to inform the creation of new, improved primitives.
• Novel, Optimized Designs: The research introduces five new polynomial hash functions (Poly1163, Poly1223, Poly1503, Poly1743, Poly2663) that address Poly1305's shortcomings by eliminating clamping, prioritizing 64-bit architectures, and supporting advanced optimization strategies like delayed reduction and two-level evaluation.
• Empirical Validation via Benchmarking Framework: A modular benchmarking framework was developed to automatically generate and empirically test these designs, providing concrete performance data that highlights their efficiency without relying on specific hardware optimizations like vectorization.
• Superior Performance and Security Tradeoffs: Poly1163, in particular, demonstrates performance competitive with, and often exceeding, OpenSSL's AVX2-vectorized Poly1305 for various message sizes, even without vectorization. Other designs offer significantly higher security (e.g., Poly1503 with 34 extra bits) at comparable performance levels.
• Path to Modern Replacements: These new polynomial hash functions offer compelling drop-in replacements for Poly1305, enabling developers to enhance the security and performance of cryptographic applications on modern hardware while simplifying future protocol design choices.

About the Speaker(s)

The talk was presented by Jérôme Govinden and Jan Gilcher. They are co-authors of the Systematization of Knowledge (SoK) paper "Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields," alongside Jean Paul Degabriele and Kenneth G. Paterson. Their work focuses on the systematic exploration and empirical evaluation of cryptographic primitives, specifically polynomial hash functions, to advance their design and implementation for modern computing environments.