# Simple proof that shows AES is not a uniform permutation on any n-bit string?

Is there a simple proof that shows AES is not a uniform permutation on any $n$-bit string?

Since I'm just starting with crypto, I'd like to see a simple yet elegant proof for the said property. Thanks!

• possible duplicate of Block cipher and parity of permutation – D.W. Aug 19 '14 at 8:18
• @D.W. While this thread is surely related, I don't understand how it answers this question. What does it mean for a specific permutation to be uniform anyway? – Gilles 'SO- stop being evil' Aug 19 '14 at 11:33
• @Gilles, assuming the author means that it is uniformly distributed on the set of all permutations (when the key is randomly chosen)... the other thread proves that AES does not have this property. Of course, Dimitry's answer is an excellent answer, too. – D.W. Aug 19 '14 at 16:03
• That question may be used to prove the answer to this, but it doesn't actually answer this one, so I don't think it's a dupe. – otus Aug 19 '14 at 18:45

There is no uniform permutation; there is a permutation uniformly chosen from the set of all possible permutations over $Z_2^{128}$.
One can consider a family $\{AES_K\}$ of AES permutations under all possible keys $K$. Even if the key is chosen uniformly, the resulting permutation is not uniformly chosen, as not every permutation is an AES permutation with some key. This comes from a simple counting argument: there are $2^{128}$ 128-bit keys and thus $2^{128}$ AES-128 permutations, but the total number of bijections over $Z_2^{128}$ is $$(2^{128})! \approx \frac{2^{128\cdot 2^{128}}}{e^{2^{128}}} \approx 2^{2^{133.5}}.$$