Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
possible duplicate of Block cipher and parity of permutation –  D.W. Aug 19 at 8:18
1  
@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 Aug 19 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 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 at 18:45

1 Answer 1

up vote 6 down vote accepted

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}}. $$

share|improve this answer
1  
You could expand the last part by showing that the number of AES permutations is less than the number of permutations. –  otus Aug 18 at 13:19
    
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. –  ddddavidee Aug 18 at 13:33
    
an partial answer can be found in this question and its answer: crypto.stackexchange.com/questions/15612/… –  ddddavidee Aug 18 at 13:39
    
@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. –  poncho Aug 24 at 16:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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