# Any theory about period length for AES applied to itself?

For example AES-128 starting with a 128-bit message $$m_0$$ and static 128 key $$k$$

$$AES128(m_0,k)\rightarrow c_0$$
$$c_0\rightarrow m_1$$
$$AES128(m_1,k)\rightarrow c_1$$
$$c_1\rightarrow m_2$$
...
continue until $$m_i$$ is equal to any $$m_j, j

The period length would be $$l = i-j$$

Any theory about how big that $$l$$ will be?
Will it be equal for any possible $$m_0$$?
Is $$l=j$$ for every $$m_0$$?

(edit: in AES $$j$$ is always 0 because symmetric algorithm. Each cipher value has only one possible plain text)

• Yes, there is a theory about this. By fixing the key randomly you selected a random permutation among the permutations of AES. Actually, you are asking about the distribution of the cycles of a permutation. See this answer of Cycles in SHA256 They i.e. Squeamish Ossifrage – kelalaka Oct 27 '19 at 13:42
• @kelalaka sure about this? Sha256 is a hash algorithm. AES a symmetric block cipher. SHA256 can have many inverse results (or many values can give one SHA256 value). At AES only one inverse value. AES not a normal permutation. – J. Doe Oct 27 '19 at 23:13

## 1 Answer

Since AES under any fixed key is a permutation, we necessarily have $$j = 0$$ and $$i = l$$—iterating a permutation enough times will always return you to the starting point.

From Harris 1960 (paywall-free), if we model AES as a uniform random permutation, every period length $$l$$ has equal probability $$1/n$$ (Eq. 5.2) for any particular starting point, where $$n = 2^{128}$$ is the size of the domain, so the expected cycle length is $$\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{127}$$.

(Any substantial deviation from this would imply an attack on AES.)

• So it is same as a real uniform random permutation? "if we model AES as a uniform random permutation" <-- Is it proven that this can be done. With this an assumption is made there is no kind of inner structure. – J. Doe Oct 27 '19 at 15:49
• @J.Doe Any substantial deviation from this would imply an attack on AES. – Squeamish Ossifrage Oct 27 '19 at 15:52
• Not sure why that is that case (the attack thing). But this might be the topic of a new question. – J. Doe Oct 27 '19 at 16:39
• It would imply a PRP distinguisher: Given an oracle $\mathcal O$ (which may be either $\operatorname{AES}_k$ for uniform random $k$, or a uniform random permutation), pick an arbitrary input $x$, query the oracle for $\mathcal O(x)$, $\mathcal O(\mathcal O(x))$, $\dotsc$, $\mathcal O^q(x)$, and check for a duplicate (maybe use a constant-memory cycle-detection algorithm). If there's a duplicate substantially more often, or substantially less often, for AES than for a uniform random permutation, then that's a distinguishing attack on the central security conjecture of AES. – Squeamish Ossifrage Oct 27 '19 at 16:43
• @SqueamishOssifrage so not an answer? But your answer makes more sense than fgrieu comment oO. – J. Doe Oct 27 '19 at 17:18