# AES: a question about dual ciphers and security

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.

1. 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).

1. 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?
2. 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.

• Questions (3) and (4) are specific cases of "hey, if I take an existing cipher, and add this extra complexity, won't it make it stronger?". Unless someone is willing to spend a great deal of time exhaustively cryptanalyzing those changes, there is typically no answer. In any case, if you don't care about performance, just add additional rounds; that way, the current analysis will (mostly) still hold, and you know you won't have hurt anything... – poncho Oct 23 '17 at 18:55
• Assume all are secure (Q1). Since DCA needs large numbers of $P/C$ pairs to mount an attack, would it not be much harder at least in theory? Changing the irr. poly (say) in each round (and again for each new full encryption) would give distinct outputs even with key $K$ fixed. DCA relies on input $m$ always giving output $C$ (never $C'$ or $C''$, etc.). It also relies on knowing the cipher in question, esp. the S-box. I know ciphers with key-dependent S-boxes can be attacked with DCA up to a number of rounds (e.g. Twofish), but is this not quite a different case? – Red Book 1 Oct 24 '17 at 3:34
• Thank you. Try this: online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=13371 – Red Book 1 Oct 31 '17 at 8:34
• Please fix the link in the question instead of putting that in a comment. – Maarten Bodewes Nov 1 '17 at 12:26
• The link in the question should be all right now. – Red Book 1 Nov 1 '17 at 13:15

## 1 Answer

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?

• Nice answer. And would you be good enough to offer your views on?: crypto.stackexchange.com/questions/52733/… – Red Book 1 Nov 3 '17 at 15:11
• Would a 'small tweak' include (for instance) altering the shifts in the ShiftRow layer? As it is, there is a 0 shift, and then right shifts of 3, 2 and 1 position/s. If this were changed to, say, 3, 1, 0, 2 it should (I think) retain its diffusion. And would this be a dual cipher? Or would this simply be a variant? – Red Book 1 Nov 6 '17 at 15:40
• That's one example of a small tweak. can you find the fixed functions $f$, $g$, and $h$ to prove that it is a dual cipher? If so, then it is, and the security story is unchanged; if not, then you have to reanalyze. You can no doubt find existing literature that mentions the shift distances. How do the results in that literature change if you change the shift distances? – Squeamish Ossifrage Nov 6 '17 at 15:55