6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Sep 15, 2011 at 12:09

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Paŭlo Ebermann
    Sep 15, 2011 at 9:47
  • 1
    $\begingroup$ 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). $\endgroup$
    – poncho
    Sep 15, 2011 at 15:58
  • $\begingroup$ While it is true that (2^128)! is not the minimal number of iterations where you are guaranteed that the output will be the input (that'd be lcm(1, 2, 3, ..., 2^128)), what is not true is that the birthday paradox applies to iterated AES. AES is a permutation, not a function; this means that there is 0 probability that, if you haven't seen a repeat yet, that the next output will be a value you've seen before, unless it's the original input. $\endgroup$
    – poncho
    Sep 15, 2011 at 17:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 15, 2011 at 17:38
  • 1
    $\begingroup$ @D.W.: The correct statement is with at most r. $\endgroup$
    – fgrieu ♦
    Sep 15, 2011 at 18:10
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 15, 2011 at 17:40
  • $\begingroup$ P.S. Regarding Question 2: The expectation is (2^128 + 1)/2, per a standard fact on random permutations. This fact about the expectation was on the same page as the fact I linked to in my answer. $\endgroup$
    – D.W.
    Sep 15, 2011 at 17:41

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.