# 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 Oct 27, 2019 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. Oct 27, 2019 at 23:13

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}$$.
• 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. Oct 27, 2019 at 16:43