3
$\begingroup$

The question I'm wondering is whether the AES cipher is a closed cipher (which is equivalent to AES being a group). And this question interests me due to the lack of understanding of whether it is possible to encrypt using the AES algorithm with two different keys and hope for increased strength, as for example in 3DES. But for DES this is possible because DES does not form a group (and there are public publications to confirm this). So, can you give me a detailed answer to my question with obligatory confirmation from the scientific literature?

$\endgroup$
4
  • 1
    $\begingroup$ Compared to DES, Why is double encryption that's equivalent to single encryption no better than single encryption?. the blocksize is too big to test, imho $\endgroup$
    – kelalaka
    Mar 2 at 22:19
  • $\begingroup$ @kelalaka, With the general principle and DES the situation is clear. What about AES specifically? $\endgroup$
    – Ss1996
    Mar 3 at 4:04
  • $\begingroup$ Just for context (because it took me a bit): A block cipher can be considered a subset of the group of permutations (of the set of all blocks the right size), and the main question here is whether the composition of two encryptions can be written as a single encryption. [If that's the case, we'd automatically get the other properties of a group, I think, due to the finiteness – i.e. a key with a "null" encryption, and inverse elements.] $\endgroup$ Mar 4 at 6:55
  • $\begingroup$ @Paŭlo Ebermann it is interesting thought, thanks for you time $\endgroup$
    – Ss1996
    Mar 7 at 4:12

1 Answer 1

8
$\begingroup$

See the paper DES is not a group by Campbell and Wiener.

TL;DR There are computational proofs that DES is not a group. The point is to carry out the types of computations that established DES is not a group is not feasible for AES due to the much larger space involved and its better design. Maybe someone will discover a new property, but it is unknown as of now.

There are no weak keys or special short cycle properties that are currently known [Coppersmith used properties of encrypting alternatively all 1 and all 0 vectors with DES, see below].

Just mathematical properties were not enough without randomness assumptions as Kaliski et al found out:

Kaliski, Rivest, and Sherman developed novel cycling tests which gave evidence that the set of DES permutations is not closed [3]. However, their work relied upon randomness assumptions about either DES itself or a pseudo-random function which was used in cycling experiments. Because of the randomness assumptions, it is difficult to use the results of their cycling tests to make any claims about the probability that DES is not closed.

Afterwards, DES was shown not to be a group computationally:

We have developed our own DES cycling experiments which provide evidence that DES is not closed; this evidence does not rely upon randomness assumptions

and

Don Coppersmith has developed an approach to finding a lower bound on the size of the subgroup generated by the DES permutations [ 11. He has shown this lower bound to be greater than the number of DES permutations, providing conclusive proof that DES is not closed.

Coppersmith himself described his approach in a 1992 sci.crypt posting.

$\endgroup$
6
  • 1
    $\begingroup$ This doesn't rule out that some looked and did not find evidence, however,I've not seen a result on this. $\endgroup$
    – kelalaka
    Mar 3 at 12:16
  • $\begingroup$ @kelalaka, I agree, didn't mean to imply that $\endgroup$
    – kodlu
    Mar 3 at 13:18
  • $\begingroup$ @kodlu, In this case, the proof is that DES is not a consequence. Where is the information about whether the protocol is AES? $\endgroup$
    – Ss1996
    Mar 4 at 17:24
  • $\begingroup$ @Ss1996, I'm sorry I don't understand your exact question. If you are asking "this proof shows DES is not a group, where is the proof that AES is" then as my answer says, the state space is much larger and no weak key and like shortcuts are known; and no one has demonstrated it is not a group. It would be unexpected that it was a group, but it is open right now. $\endgroup$
    – kodlu
    Mar 4 at 19:02
  • $\begingroup$ @kodlu I have seen evidence that the AES round function forms a group. But, as I understand it, this does not automatically make the entire AES cipher a group. I'm right? Second question: If AES has not been proven to form a group, is it correct to assume that using Triple AES does not (proven) increase crypto currency as in 3DES? $\endgroup$
    – Ss1996
    Mar 4 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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