Hardness of Learning AES Key (Short Paper)

Sultan Nurmukhamedov, Artur Pak, Rustem Takhanov, Zhenisbek AssylbekovDP@AI*IA 2022 · OpenReview

TL;DR

This paper proves that learning the AES key from ciphertext pairs is computationally hard, assuming AES outputs are "computationally close" to random. This provides theoretical evidence for AES's resistance to machine learning-based attacks, a crucial aspect of its security.

What Problem Does This Paper Address?

The Advanced Encryption Standard (AES) is a cornerstone of modern digital security, used in everything from secure websites to classified government communications. Despite its widespread use, the theoretical guarantees of AES's security, particularly against sophisticated cryptanalytic attacks, have been somewhat limited. While practical attacks haven't broken AES, understanding why it's secure is an ongoing research challenge. This paper focuses on a specific type of attack: those leveraging machine learning to recover the secret encryption key from observed input-output pairs (plaintexts and ciphertexts). The authors aim to provide a theoretical foundation for AES's resistance to such attacks, building upon recent work that suggests AES outputs exhibit a property called "e-closeness to pairwise independence."

Methods

The core of the paper's contribution lies in a theoretical proof. The authors introduce a crucial assumption, Assumption 1, which states that for any two distinct inputs and a randomly chosen key, the pair of AES outputs is computationally indistinguishable from two independent random strings. This assumption is motivated by prior work showing AES outputs are close to uniform.

Based on this assumption, they construct a hypothetical "learner" algorithm. This learner, if it could efficiently recover the AES key from ciphertext pairs, would, in turn, allow the construction of a "distinguisher" algorithm. This distinguisher would be able to tell apart real AES ciphertext pairs from pairs of random strings. However, such a distinguisher would directly contradict Assumption 1, proving that the initial learner (and thus the ability to learn the AES key) must be computationally infeasible.

The proof involves a detailed probabilistic analysis of a proposed distinguisher algorithm (Algorithm 1). This algorithm uses a function h_xx'(y, y') that attempts to recover the key k given two ciphertexts y and y' that correspond to inputs x and x' under key k. The analysis carefully considers different scenarios and uses probability bounds to show that the distinguisher can effectively differentiate between real AES outputs and random strings, provided the key-learning assumption holds.

Datasets

Not discussed in the paper. The paper focuses on theoretical proofs and experimental verification of an assumption, rather than training on specific datasets.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper connects a theoretical property of AES (e-closeness to pairwise independence) to a practical security concern (resistance to machine learning attacks). This is a significant step in understanding AES's security from a theoretical standpoint.
  • Assumption 1 as a Foundation: The introduction of Assumption 1 is key. It's a plausible assumption, rooted in prior research, that allows for a rigorous proof of hardness. It suggests that AES's internal structure, even when only the initial key is random, provides strong security properties.
  • The Power of Indistinguishability: The proof elegantly demonstrates how the inability to distinguish real AES outputs from random strings implies the hardness of key recovery. This highlights a fundamental principle in modern cryptography.
  • Empirical Support: The authors go beyond theory by empirically testing Assumption 1. They show that statistical tests designed to detect deviations from pairwise independence fail to reject the null hypothesis for AES, providing confidence in their theoretical foundation.

Key Results

The main theoretical result is Theorem 1: Under Assumption 1, the distribution of AES outputs for two distinct inputs and a random key is computationally distinguishable from the distribution of two independent random strings. This implies that any algorithm that can efficiently recover the AES key from such pairs would lead to a contradiction.

The empirical verification section shows that statistical tests, when applied to AES-128 outputs, do not reject the hypothesis that these outputs are close to pairwise independent, especially as the number of tested bins increases. This supports the plausibility of Assumption 1.

Limitations and Future Work

  • Reliance on Assumption 1: The entire proof hinges on Assumption 1. While motivated by prior work and empirically supported, it's still an assumption about AES's internal behavior. The paper acknowledges that this assumption is "realistic" and a "reasonable alternative to common cryptographic assumptions," but it's not a proven property of AES itself.
  • Focus on Key Recovery: The paper specifically addresses attacks that aim to recover the entire AES key. It doesn't directly comment on the hardness of other types of cryptanalytic attacks that might not directly target key recovery.
  • Future Work: The authors suggest that their work provides a foundation for further research into the provable security of AES against machine learning-based attacks. They also imply that exploring other relevant assumptions for AES's security would be valuable.

Summary updated

BibTeX
@inproceedings{nurmukhamedov2022hardness,
  author = {Sultan Nurmukhamedov and Artur Pak and Rustem Takhanov and Zhenisbek Assylbekov},
  title = {{Hardness of Learning AES Key (Short Paper)}},
  booktitle = {DP@AI*IA},
  year = {2022},
  url = {https://openreview.net/forum?id=yVvl4KqCl0},
}
Figure