# Analysis of Repeatedly Enciphered Plaintext using Same Algorithm / Key

Please forgive the impracticality of this question, but I'm curious about the behaviors of encryption algorithms applied to their own output.

Suppose I have an encryption algorithm E and (using the same key(s)) I repeatedly encrypt its output for a given plaintext: E(E(E(E(...E(plaintext)

Would a modern encryption algorithm, such as some variant of AES, display any kind of cycling with respect to its output for arbitrarily long compositions of itself? Is there some known number of compositions where the final output is itself the plaintext?

-
You say the question is impractical, but I've actually seen this construction used in real life in KeePass. In their write up on security they say "KeePass first hashes the user's password using SHA-256, encrypts the result N times using the Advanced Encryption Standard (AES) algorithm (called key transformation rounds from on now), and then hashes it again using SHA-256". They do this to protect against dictionary attacks. –  mikeazo Sep 15 '11 at 12:09

Eventually, it will cycle, but it'll almost certainly take far longer than your lifetime to do so.

If that sounds too flip, here's the mathematics. Assuming AES is secure, then the probability it will revisit the original plaintext after at most r repeated encryptions is just r/2128. (This follows from a standard fact about the cycle structure of a random permutation.) For the values of r that can realistically arise in practice, this probability is negligible: less than the chances of getting hit by lightning, twice.

Is there some known number r such that r repeated encryptions are guaranteed to bring you back to the plaintext you started with? Yes, for instance: r = (2128)!, i.e., 2128 factorial. Or, r = lcm(1, 2, 3, ..., 2128) also works. However, this is a stupendously, ridiculously large number. So it's completely irrelevant in practice.

Bottom line. If you've got a secure block cipher, you don't need to worry about cycling. It's not an issue. It just ain't gonna happen.

-
A clearer way to write your third sentence would be the probability to reach the original plain text after at most r repeated encryptions is r/2^128. –  Paŭlo Ebermann Sep 15 '11 at 9:47
Or even more precisely than that: the probability to reach the original plaintext after at most r repeated encryptions is exactly r/2^128 for all r<=2^128 (assuming that the block cipher acts as a random permutation). –  poncho Sep 15 '11 at 15:58
Thanks for the analysis! –  Michael Petito Sep 15 '11 at 16:42
Thanks for all the comments, everyone. Three nitpicks: 1. The correct statement of the fact is about the probability of hitting the original plaintext after exactly r repeated encryptions, not at most r. 2. Yeah, yeah, yeah. Fine, so the lcm is smaller than the factorial. It's still a stupendously, ridiculously, impractically large number. My conclusion still holds. 3. e501, your statement about 2^64 is not correct. The birthday paradox is not relevant here. –  D.W. Sep 15 '11 at 17:38
@D.W.: The correct statement is with at most r. –  fgrieu Sep 15 '11 at 18:10

Your question essentially asks, given a function $f$ that takes an input $i$ of length $k$ and produces an output $o$ of length $k$.

$$i \in \{0, 1\}^k, o \in \{0, 1\}^k$$ $$f(i) = o$$

How many times on average will $f$ have to be recursively called on itself such that it collides with one of it's inputs or outputs (all previous outputs are also inputs).

$$f(f(f(...f(i)...))) = i$$.

Since we are assuming $f$ is a cipher, lets be generous and assume that $f$ randomly maps $i$s to $o$ (that is, lets assume $f$ is secure) such that the same $i$ always produces the same $o$. This is, $f$ is a random permutation over $2^k$ possible $i$s (remember $i$ is a binary number of $k$ digits).

1. how many times must a permutation on $2^k$ elements be applied to itself such that it repeats (that is the "order of a permutation")
2. and what is the average order of a random permutation on $2^k$ elements.