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!
$\begingroup$
$\endgroup$
4
-
$\begingroup$ possible duplicate of Block cipher and parity of permutation $\endgroup$– D.W.Aug 19, 2014 at 8:18
-
1$\begingroup$ @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? $\endgroup$– Gilles 'SO- stop being evil'Aug 19, 2014 at 11:33
-
$\begingroup$ @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. $\endgroup$– D.W.Aug 19, 2014 at 16:03
-
$\begingroup$ 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. $\endgroup$– otusAug 19, 2014 at 18:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
There is no uniform permutation; there is a permutation uniformly chosen from the set of all possible permutations over $Z_2^{128}$.
It is evident that AES is not a uniformly chosen permutation, since its permutation is fixed for any key.
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}}. $$
answered Aug 18, 2014 at 13:09
-
1$\begingroup$ You could expand the last part by showing that the number of AES permutations is less than the number of permutations. $\endgroup$– otusAug 18, 2014 at 13:19
-
$\begingroup$ I read a paper (an extract, actually) once that showed how all permutations used in cryptology have the same sign (positive , if I remember correctly). I cannot find it now, but that will show that AES permutations are strictly included into all possible permutations. $\endgroup$ Aug 18, 2014 at 13:33
-
$\begingroup$ an partial answer can be found in this question and its answer: crypto.stackexchange.com/questions/15612/… $\endgroup$ Aug 18, 2014 at 13:39
-
$\begingroup$ @ddddavidee: actually, there are block ciphers that can implement an odd permutation; they're not common, but they most certainly do exist. AES (as well as the vast majority of block ciphers) will always do an even permutation. $\endgroup$– ponchoAug 24, 2014 at 16:06