New Techniques for Analyzing Differentials with Application to AES

We propose new techniques for estimating the probability that an input difference leads to an output difference in a block cipher (i.e., the probability of a differential) under the assumption of independent round-keys. We apply our techniques to AES, and show that the probability of every non-trivial differential in 8-round AES is within an additive factor of $2^{-128} \cdot \frac{1}{50}$ from the expected value of $\frac{1}{2^{128} - 1}$.

We further apply our techniques to prove that 40-round AES is at most $2^{-135}$-close to a pairwise independent permutation. This improves upon the work of Liu, Tessaro and Vaikuntanathan [CRYPTO 2021], who proved a similar bound for 9000-round AES.

To obtain our results, we develop and adapt a variety of techniques for analyzing differentials using functional analysis. We expect these techniques to be useful for analyzing differentials in additional block ciphers besides the AES.