2
$\begingroup$

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<i$

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)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$
    – kelalaka
    Oct 27, 2019 at 13:42
  • $\begingroup$ @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. $\endgroup$
    – J. Doe
    Oct 27, 2019 at 23:13

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – J. Doe
    Oct 27, 2019 at 15:49
  • 2
    $\begingroup$ @J.Doe Any substantial deviation from this would imply an attack on AES. $\endgroup$
    – Squeamish Ossifrage
    Oct 27, 2019 at 15:52
  • $\begingroup$ Not sure why that is that case (the attack thing). But this might be the topic of a new question. $\endgroup$
    – J. Doe
    Oct 27, 2019 at 16:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Squeamish Ossifrage
    Oct 27, 2019 at 16:43
  • $\begingroup$ @SqueamishOssifrage so not an answer? But your answer makes more sense than fgrieu comment oO. $\endgroup$
    – J. Doe
    Oct 27, 2019 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.