# 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?

-

– mikeazo♦ Sep 15 '11 at 12:09

## 2 Answers

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

1
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

1
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

1
@D.W.: The correct statement is with at most r. – fgrieu Sep 15 '11 at 18:10
show 5 more comments

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

This question really asks:

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.

The Landau function give us the worst possible number of steps we would need to take to get a permeation to repeat itself. This is our upper bound and the answer to question 1.

Question 2 I don't have an exact answer for you but there has been a lot of mathematic work in this area (Paul Erdos worked on this a bit). There is a mathoverflow question/answer on the average order of a permutation as well.

-

The statements about Question 2, the birthday paradox, and the probability of a collision are not correct.  This is a random permutation, not a random function.  The birthday paradox does not apply. – D.W. Sep 15 '11 at 17:40
– D.W. Sep 15 '11 at 17:41
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9267190098762512, "perplexity_flag": "middle"}