# Attack on Even-Mansour on top of 10 rounds of AESENC

Consider a block cipher with 128-bit block and 128-bit key, built per the one-key Even-Mansour construction on top of a permutation consisting of 10 rounds of AESENC:

1. XOR the 16-byte input block with the key, as in the initial AddRoundKey of AES-128
2. repeat 10 times what the AESENC instruction does, that is:
• SubBytes (apply the AES S-box to each of the 16 state bytes)
• ShiftRows (structured permutation of the 16 state bytes)
• MixColumns (linear mixing involving field arithmetic in $$\mathbb F_{2^8}$$)
3. XOR with the key to produce the 16-byte output block

If the 16 state bytes are equal before step 2, they also are until after. That's trivial for SubBytes and ShiftRows, and holds for MixColumns due to it's matrix being circulant.

How does that impact security?

What other weaknesses?

How does that impact security?

Well, right off the bat we can say that the original proof for the Even-Mansour proof won't work, since clearly the middle permutation doesnt' behave like a random one. That is not a proof of insecurity per se, but definitely a bad sign.

It will definitely be weak to quantum attacks if an adversary has a quantum access to the oracle, but I'm not sure this is what you're looking for. But this has nothing to do with the middle permutation per se, Even-Mansour in itself is weak to Simon's algorithm.

Also, the usual Even-Mansour scheme uses two different keys, while you mention a single one. Is it on purpose?

Without further analysis on the middle permutation, I think we can still prove the security of this scheme. Something along the lines of:

Let $$P$$ be a permutation such that for all byte $$a$$, there exists a byte $$b$$ such that $$P(a\parallel\cdots \parallel a)=b\parallel\cdots\parallel b$$. Let $$P$$ be chosen at random on all other inputs such that $$P$$ is a permutation. Then instantiating the Even-Mansour scheme with $$P$$ yields a secure block cipher.

Is is not formal of course, but the idea is that on inputs other than those with all bytes equal, we may assume that $$P$$ behaves randomly with enough rounds (once again, without further analysis! It's well possible that there are actually more distinguishers for $$P$$).

To prove this, I think it is possible to argue that the whole block cipher is indistinguishable from an Even-Mansour scheme instantiated with a random permutation. Of course, this can be made formal I think but the reasoning could go like this:

• Since $$P$$ behaves like a random permutation on all but $$256$$ inputs, if the adversary doesn't query one such input, they can't distinguish $$P$$ from a random permutation with probability greater than $$\frac12$$ (not entirely true though, a random permutation could give you a string with all $$16$$ bytes equal on a non-uniform input, but this represents a negligle portion of the permutations I think)
• So, this amounts to computing the probability that $$\mathcal{A}$$ queries an input $$m$$ such that $$m\oplus k_1$$ is uniform. With overwhelming probability, they don't do so on their first query. Thus, they only get a random string out of the block cipher, which they can't use to find such an input.

As you saw, this is clearly not formal enough to be called a proof, but I think this gives enough intuition to argue that, assuming no other distinguishers on the middle permutation, the scheme is secure.

One can challenge this assumption though: as mentioned in the comments, there is a lot of structure for these operations, so there's no guarantee that some other, much stronger, invariants could be found.

• MixColumns does more than shuffling bytes; it transforms them in a non-obious way involving field arithmetic in $\mathbb F_{2^8}$. I don't see that discussed in the current answer. If something breaks my intuition, that will be it.
– fgrieu
Commented Jul 31 at 11:51
• @fgrieu Ah, my memory was flawed indeed, that kills the analysis. Sorry for that! Commented Jul 31 at 11:54
• No problem. Notice I changed the question after confirming that my intuition holds, since MixColumns is highly regular! So lots of your answer holds.
– fgrieu
Commented Jul 31 at 12:49
• @fgrieu Your intuition clearly beats mine! I was left convinced that this property wouldn't hold, but I wanted to do a Python code to test whether that was the case this evening Commented Jul 31 at 12:56
• The question now states it uses one-key Even-Mansour, a standard variant. I wanted something minimalist.
– fgrieu
Commented Jul 31 at 13:06