Upgrade 2021: CIS LAB Speakers

September 21, 2021 // Upgrade 2021: CIS LAB Speakers

Is AES Really Secure? Proving the Effectiveness of Block Ciphers with t-wise Independence

Stefano Tessaro: Associate Professor | University of Washington


The most important cipher in the world today is the Advanced Encryption Standard, AES. It underlies thousands of applications in the economy, communications, archiving, and more, and consequently its security is a matter of great importance. Despite this, no proof of its security has been found to date. On the other hand, no cryptanalytical attack has been successful against properly implemented AES, despite 20 years of attempts.

Block ciphers such as AES are composed of multiple rounds of encryption, each round being simple in itself. Typically a round consists of some sequence of application of the key (by XOR), application of substitution via an S-box function, and a mixing function. Only the key is assumed to be secret, and a sufficient number of rounds is believed to produce output that is indistinguishable from a random string, while still allowing recovery of the original message by a receiver equipped with the key. Block ciphers are fast, highly parallelizable and implementable on chip.

At Upgrade 2021, Professor Stefano Tessaro (University of Washington) reported on joint work with Tianren Liu (University of Washington) and Vinod Vaikuntanathan (MIT) on the theoretical foundations of the security of block ciphers such as AES. Their work takes a different approach to the classical idea of reduction of a known hard problem to breaking of the cipher.

Instead, they measure the indistinguishability of the output of a cipher from a random string of length t by the concept of ε-closeness to t-wise independence. For small ε, this property promises that output strings are statistically very close to random (high entropy). In this way known classes of attacks can be ruled out without ever proving security against all possible attacks.

Tessaro presented technical results on 2-wise independence for various concrete cases, including a non-trivial statistical bound of ε=0.472 for AES with six rounds, block size 8 and key size 128 bits. A standard amplification theorem means that any ε bound is therefore achievable for AES with a sufficient number of rounds. He gave a sketch of the proof methods behind this and other results, with lemmas giving bounds on the increase of entropy to be expected after each round.

Professor Tessaro concluded with remarks placing his team’s work in the context of other approaches and on future work. He emphasized the importance of reuniting the theoretical and cryptanalytical branches of cryptography, which he believes have grown apart, and combining the insights provided by both fields.

Click below for the full transcript.

Stefano Tessaro

Associate Professor | University of Washington

Stefano Tessaro is an Associate Professor in the Paul G. Allen School of Computer Science & Engineering at the University of Washington, where he co-leads the cryptography group. He works primarily on cryptography, computer security and theoretical computer science. Earlier, he was an assistant professor at UC Santa Barbara for five years, where he held the Glen and Susanne Culler chair. He obtained a PhD from ETH Zurich in 2010, and held postdoctoral appointments at UCSD and MIT. He received several awards for his research, including a Sloan Research Fellowship, an NSF CAREER award, and a Hellman Fellowship, as well as a best-paper award at EUROCRYPT 2017.