Efficient Design Strategies Based on the AES Round Function

Jérémy Jean, Ivica Nikolic

TL;DR

This paper presents new, highly efficient cryptographic building blocks based on the AES round function, leveraging modern CPU instructions (AES-NI) to achieve unprecedented speeds. The authors demonstrate designs that are up to five times faster than AES-128, pushing the boundaries of secure and fast symmetric-key primitives.

What Problem Does This Paper Address?

The Advanced Encryption Standard (AES) is a cornerstone of modern cryptography, valued for its security and efficiency. Many cryptographic schemes, such as Message Authentication Codes (MACs) and Authenticated Encryption (AE) schemes, build upon AES. While AES itself is well-understood, there's a continuous drive to optimize these derivative schemes for performance, especially on modern hardware. Specifically, the advent of dedicated AES instructions (AES-NI) on Intel processors offers a significant speedup potential. The challenge is to design new primitives that can fully exploit these instructions without compromising security, which often involves using fewer AES rounds or novel ways of combining them. Existing designs that utilize round-reduced AES or parallel processing show promise, but there's room to push efficiency further, particularly by understanding the interplay between hardware capabilities and cryptographic design principles.

Methods

The authors explore two main design strategies for creating AES-based building blocks:

  1. Strategy 1 (Wide-Trail Based): This approach applies AES rounds in a way that mimics keyless AES rounds. It benefits from the AES's "wide-trail strategy," which provides strong security guarantees and simplifies security proofs. However, this strategy has limited efficiency potential.
  2. Strategy 2 (Message/State XORing): This more efficient strategy involves XORing message and state words between AES calls. This allows for greater parallelism and higher speeds but makes security analysis more complex, requiring techniques like Mixed Integer Linear Programming (MILP) to find optimal differential characteristics and establish security bounds.

The core of their implementation relies on the aesenc instruction from the AES-NI set, which executes a single AES round. They analyze the latency and throughput of this instruction on various Intel processors to inform their design choices. Security is primarily assessed by the ability to find internal collisions, which is reduced to finding high-probability differential characteristics. They use MILP to search for these characteristics and determine the minimum number of active S-boxes, a key metric for security.

Datasets

Not discussed in the paper. The paper focuses on theoretical design and performance benchmarking on specific hardware, rather than training on or evaluating against predefined datasets.

Key Insights and Ideas

  • AES-NI is a Game Changer: The dedicated AES-NI instructions on modern CPUs offer a massive performance boost, enabling speeds far beyond traditional software implementations.
  • Efficiency vs. Security Trade-off: The paper highlights that achieving higher efficiency often requires more complex security analysis. The second strategy, while faster, demands advanced techniques like MILP to prove security.
  • Rate is Crucial, but Not Everything: A lower "rate" (fewer AES rounds per message block) generally leads to higher efficiency. However, parallelization and the efficient use of AES-NI instructions (saturation of the aesenc port) are equally critical.
  • MILP for Security Analysis: Mixed Integer Linear Programming is a powerful tool for finding optimal differential characteristics and establishing lower bounds on security metrics (like active S-boxes) for complex designs.
  • State Size Matters: Larger internal states can facilitate greater parallelism, leading to higher throughput, but also increase hardware requirements.
  • Four Rounds as a Sweet Spot: The paper reinforces the idea that four AES rounds offer a good balance of security and efficiency, as demonstrated by previous designs and the AES's own wide-trail strategy. However, they push beyond this to achieve even greater speeds.

Key Results

The paper presents seven secure constructions that achieve excellent performance on modern Intel processors.

  • Record-Breaking Speeds: The fastest construction, using only two AES rounds per 16-byte message block, achieves speeds of 0.125 cycles per byte (c/B) on Intel Skylake processors. This is up to five times faster than AES-128.
  • Performance Across Architectures:
    • On Ivy Bridge, speeds range from 0.190 to 0.250 c/B.
  • On Haswell, speeds range from 0.136 to 0.219 c/B.
  • On Skylake, speeds range from 0.125 to 0.188 c/B.
  • Rate 2 Design: The most efficient design has a rate of 2 (two AES rounds per message block), uses 12 state words, and achieves the top speeds.
  • Security Guarantees: The designs are proven to have at least 22 active S-boxes in their best differential characteristics, ensuring a high level of security against collision attacks.

Limitations and Future Work

  • Hardware Dependency: The exceptional speeds are heavily reliant on the AES-NI instruction set. Performance on processors without these dedicated instructions will be significantly lower, though still faster than standard AES.
  • State Size: The most efficient designs have relatively large state sizes, making them less suitable for lightweight applications where memory is highly constrained.
  • Security Proof Complexity: While the paper focuses on collision resistance, a full security analysis of any primitive built using these blocks would require further investigation into other attack vectors.
  • Future Work: The authors suggest exploring ways to reduce the state size of their designs, which could improve suitability for resource-constrained environments. They also note that further reducing the rate (e.g., by increasing the number of message blocks processed per step) is a potential avenue, though it presents greater challenges for security analysis.

Summary updated

BibTeX
@article{jean2016efficient,
  author = {Jérémy Jean and Ivica Nikolic},
  title = {{Efficient Design Strategies Based on the AES Round Function}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}

Loading related content...

Figure