9
$\begingroup$

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?

$\endgroup$
3
  • 6
    $\begingroup$ AES is not supposed to be a symmetric key block cipher. It is a block cipher. By definition, a block cipher is a keyed permutation, where each key select a different permutation for the set of all possible permutations. Formally, a block cipher is a family of permutations, indexed by the key. We believe that AES is a PRP at least no one showed the reverse during the 20 years, and the belief is more strong every day. The larger variant of AES? Your premises is not correct exactly. The last two sentences are not clear. Do you seek the formal definition of AES? $\endgroup$ – kelalaka Nov 12 '20 at 7:36
  • $\begingroup$ Not sure what exactly you are looking for, however, What is a block cipher? and What (precisely) is a block cipher? and replace block cipher with AES. $\endgroup$ – kelalaka Nov 12 '20 at 10:27
  • 3
    $\begingroup$ "while there are larger variants of AES, I don't see how the algorithm extends to ..." The consensus is that AES as a standard is limited to 128-, 192-, 256- bit keys and 128-bit blocks, whereas Rijndael as an algorithm is designed with extendability in mind to scale up arbitrarily by adding more columns and changing the key schedule. If this is what you seek, I'll provide an extended answer. $\endgroup$ – DannyNiu Nov 12 '20 at 13:58
20
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ I presume the other AES candidates and block ciphers with the same size parameters would fit the same function definition. The mapping would of course be different... $\endgroup$ – Maarten Bodewes Nov 12 '20 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.