2
$\begingroup$

Lets say we have a message 'm'. We encrypt 'm' using a stream cipher or any other type of cipher with cryptographic security that produces an output equal in length to the length of 'm'. Then if we keep on on re-encrypting the output with same cipher (but different key each round) for eternity, what are the chances of it ever producing 'm' as the cipher-text.

$\endgroup$
  • 1
    $\begingroup$ A better answer is here Any theory about period length for AES applied to itself? $\endgroup$ – kelalaka Jul 21 at 20:15
  • $\begingroup$ The "different key each round" fragment leaves us uncertain about what's performed. The probability of reaching back the original message after $k$ encryptions is influenced by that. $\endgroup$ – fgrieu Jul 22 at 5:51
3
$\begingroup$

If the ciphertext is the same size as the plaintext, then yes with 100% probability.

There are only finitely many values the ciphertext can take. So repeatedly encrypting the ciphertext, means that a value must repeat eventually. If this cycle doesn't include the original message, then there is some ciphertext that has an ambiguous decryption (because two plaintexts encrypt to it). Since we know this isn't the case, the original message must be in the cycle.


You can easily tweak this argument to ignore padding (just take the padded message as your original message).

If the encryption scheme requires an IV/nonce, then this argument only applies if you reuse the same IV for each encryption, in other words, after the first encryption, the ciphertext size is constant.

I highly doubt there's a way to show this with an authenticated encryption scheme.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ "There are only finitely many values the ciphertext can take. So repeatedly encrypting the ciphertext, means that a value must repeat eventually" - actually, it's a tad more subtle than that - you have to prove that the state doesn't get trapped in a "cul-de-sac" that it cannot leave. It turns out that you can prove it (for any keyed finite permutation); it is a tad more involved; one way to start is to note that if $A -> B$ is a possible transform (for some series of keys), then $B -> A$ must also be possible (and if possible, it must have a bounded-from-zero probability) $\endgroup$ – poncho Jul 21 at 16:38
  • $\begingroup$ @poncho He addressed this when he wrote "If this cycle doesn't include the original message, then there is some ciphertext that has an ambiguous decryption (because two plaintexts encrypt to it)." That said, this whole discussion is moot since the probability of this happening is negligible. $\endgroup$ – Nemo Jul 22 at 0:15
  • 1
    $\begingroup$ "If the ciphertext is the same size as the plaintext" that kind of clashes with the"secure" part. $\endgroup$ – Maeher Jul 22 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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