Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer
    
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
    
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. –  D.W. Sep 15 '11 at 17:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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