AES: a question about dual ciphers and security

Question

I have recently learned of dual ciphers, in particular dual ciphers of AES. It seems there are many. Most of my information comes from:(1) Representations and Rijndael Descriptions.

In this paper the authors (which includes one of the designers of AES) discuss $256!$ equivalent ciphers of which $2^{62}$ are useful (4.1 and 4.2).

1. if dual ciphers are equivalent can we assume they are all just as secure?

Another paper (2) In How Many ways Can You Write Rijndael discusses different types of dual ciphers, such as Log Dual Ciphers and Square Dual Ciphers.

2. This paper refers to trivial dual ciphers, could anyone give a simple example using a very basic cipher? I could not understand the explanation in the paper.

In sec. 4 of paper (2) they mention changing the irreducible polynomial (there are 30 with each having 8 square dual ciphers, giving a total of 240 dual ciphers).

3. If we used a different irreducible polynomial for each round of AES to create a kind of multi-dual cipher (my own term), would that make it harder to cryptanalyse and therefore stronger against DCA and LCA? If so, could we use fewer rounds whilst retaining the same level of security?
4. And, further to 3. above, what if each round's irreducible polynomial were chosen at random and were changed for each full encryption? Again, would this allow for fewer rounds whilst retaining the same level (or at least adequate) security?

I understand that a so-called multi-dual cipher may have huge implementation problems and may slow the cipher considerably, but I am thinking purely in terms of security, i.e. resistance to analyse.

Answer 1

1. Are dual ciphers just as secure? Yes.

   The definition is:

   Two ciphers $E$ and $E'$ are called dual ciphers if they are isomorphic, i.e., if there exist invertible transformations $f(\cdot)$, $g(\cdot)$, $h(\cdot)$ such that $$\forall P, K \quad f(E_K(P)) = E'_{g(K)}(h(P)).$$

   Note that $f$, $g$, and $h$ are independent of the key and plaintext. If you had a random algorithm $\mathcal A(F)$ that can distinguish $P \mapsto E_K(P)$ from $P \mapsto U$ for uniform random $K$ and $U$ with some probability $p$, then the algorithm $\mathcal A'(F) = \mathcal A(P \mapsto f^{-1}(F(P)))$ distinguishes $P \mapsto f(E_K(P))$ from $P \mapsto U$ for uniform random $K$ and $U$ with the same probability $p$ and negligible additional cost, to evaluate $f^{-1}$.

2. The ciphers $E = \operatorname{AES}$ and $E' = \operatorname{AES}$ are trivially self-dual with $f(C) = C$, $g(K) = K$, and $h(P) = P$ for all $C, K, P$. Proof is left as an exercise for the reader. (Hint: It's trivial.)

3. Using a different representation for $\operatorname{GF}(2^8)$ in each round wouldn't substantively change the cipher. The algebraic structure would remain identical, but you would have a different S-box in each round.

   This would probably only make the crypto more expensive for the legitimate users without imposing any real hurdles on attackers—in fact, it would likely make the attacker's job easier by making implementations more likely to be vulnerable to timing side channel attacks.

4. Now you need to define a pseudorandom generator of irreducible degree-8 polynomials over $\mathbb Z/2\mathbb Z$, and somehow make it independent of everything else in the cipher that uses the same key. If you're lucky, that might make it harder to attack, at high cost to a cipher that's already painfully slow in software—and probably even make it significantly costlier in hardware.

   However, your job, as an aspiring cryptographer, is not to flail around proposing tweaks that might turn out to add security if you're lucky. Your job is to demonstrate that the changes thwart all existing techniques for cryptanalysis more thoroughly than the simpler approach taken by AES.

   Consider starting with smaller, simpler tweaks to AES. There's an entire book on the design and implementation of Rijndael by the authors, in addition to stacks of literature. What small tweaks to the design space documented in it can you break or prove resistant to existing cryptanalysis techniques?

   As poncho noted in a comment, the easiest way to make AES stronger is to add more rounds. If your tweak expands the security margin, is its expansion of the security margin greater than that of just adding more rounds? Is it cheaper than just adding more rounds?