Formally, what is AES?

Question

AES is supposed to be a symmetric key block cipher. The theoretical counterpart to this is a pseudorandom permutation.

I'd like to say that AES is a PRP (well, supposedly at least), but that doesn't seem correct; while there are larger variants of AES, I don't see how the algorithm extends to arbitrarily large security parameters.

How do I view AES theoretically?

Answer 1

Applied cryptographers often see one of the three variants of AES, say AES-256, as a function: $$\begin{align}E:\ \{0,1\}^{256}\times\{0,1\}^{128}&\to\{0,1\}^{128}\\ (k,p)\quad &\mapsto c=E(k,p)\end{align}$$ such that:

1. for all $k\in\{0,1\}^{256}$, encryption with key $k$ defined as follows $$\begin{align}E_k:\ \{0,1\}^{128}&\to\{0,1\}^{128}\\ p\quad &\mapsto c=E_k(p)\underset{\text{def}}=E(k,p)\end{align}$$ is injective, surjective, and bijective (the three are equivalent for any function over a finite set), that is a permutation of $\{0,1\}^{128}$
2. there's an efficient encryption algorithm computing $E_k(p)$ from $k$ and $p$
3. there's an efficient decryption algorithm computing $p$ with $c=E_k(p)$ from $k$ and $c$ (note: not quite as efficient, but close).
4. it is practically impossible to distinguish a challenger/oracle implementing these algorithms with a fixed unknown value of the key $k$ chosen at random, from an oracle implementing a random permutation and its inverse.

Note: Condition 4 is only good for keys chosen independently at random, which is the main design criteria for AES. It's not applicable to related-key attacks or the ideal cipher model.

Note: The quantitative security-oriented cryptographer compares the advantage of a distinguisher succeeding at 4 to that of a generic attack requiring the same work and trying keys in sequence, and to a no-nonsense threshold.

---

The more theoretical-oriented cryptographers want to formally define "efficient" and "practically impossible". They do so by stating that the algorithms involved are in the class of polynomial-time algorithms; and using the notion of negligible probability. But these require a "security parameter" that goes to $+\infty$ as the input of a polynomial, and AES is only defined for $|k|\in\{128,192,256\}$ and $|p|=128$, which are bounded.

To solve that, we can use that AES is formally defined as a restriction of Rijndael, and section 12.1 of that observes:

The key schedule supports any key length that is a multiple of 4 bytes. (…) The cipher structure lends itself for any block length that is a multiple of 4 bytes, with a minimum of 16 bytes.

That section also tells how many rounds there should be, and how ShiftRow can be extended for 128, 192 and 256-bit block, that we can further extend.

For parameter $n\ge128$, we can take block size $|p|=32\,N_b=32\,\lfloor n/32\rfloor$ and key size $|k|=32\,N_k=32\,(N_b-3+(n\bmod 32))$, with $N_r=N_k+6$ rounds. We are back to a standard framework where algorithms are written for arbitrarily high security parameter $n$, fed as input to polynomial-time algorithms as a bitstring of $n$ bits, conventionally at 1. When $n=131$ (resp. $n=133$ and $n=135$) we get AES-128 (resp. AES-192 and AES-256). For $n=128$, we get a 128-bit cipher with a toy-sized 32-bit key.

But I do not know any security analysis of AES that cares to do something remotely similar and study attack on large $n$. This shows the gap between theory and practice!

Note: There would be other ways to make AES a family of block ciphers indexed by a security parameter. In particular, we could define variants working for more granular values of $|k|$ and $|p|$, and working in $\mathbb F(2^j)$ for $j$ variable, rather than $j=8$ as in AES; and/or tweak the $32=4\, j$ to another multiple of $j$. However that matches AES even less than the above, which is somewhat supported by a document referenced in appendix D of the formal definition of AES.