Can any message be decrypted using a given ciphertext and an appropriate key?

Does the following proposition hold for any deterministic, symmetric cryptosystem $$(\mathcal{M}, \mathcal{C}, \mathcal{K}, Enc, Dec)$$?

$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$

My reasoning until now is that this should be equivalent to

$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$

And if this was false, the opposite must hold:

$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$

Since all messages $$M \in \mathcal{M}$$ and keys $$K \in \mathcal{K}$$ can be used to create ciphertexts in $$\mathcal{C}$$, this would mean that there exist messages $$M_1, M_2, M_1 \ne M_2$$ which, given a key $$K$$, are encrypted to $$Enc_K(M_1)=Enc_K(M_2)=C$$, which defies the required injectivity of $$Enc$$. Therefore, the proposition must be true. Is it?

• What if the encryption is just the identity map? Feb 22, 2021 at 20:11
• You have made a lot of oversimplification (if I understand your question correctly)
– hola
Feb 22, 2021 at 20:32

Given a key and a potential ciphertext, is there a corresponding plaintext?

In other words, can decryption fail?

For authenticated decryption, the answer is an obvious yes: almost all ciphertexts are invalid. You need to know the secret key to produce a valid ciphertext. Without knowing the key, with very high probability, you can't generate a ciphertext that includes a valid authentication tag.

For unauthenticated decryption, it depends. A stream cipher has no invalid ciphertexts: you just xor the stream with the ciphertext and you get a plaintext. CBC-with-padding has invalid ciphertexts with common padding modes. Also, for CBC, not all bit-strings are valid ciphertexts regardless of padding: only bit-strings that consist of a whole number of blocks have a chance of being valid.

An encryption scheme where an adversary can generate ciphertexts with a probability of validity that is neither 1 nor infinitesimal is problematic because it opens the way to padding oracle attacks.

• If all bit-strings are valid ciphertexts, as with stream ciphers, then forging ciphertexts is trivial and won't provide the adversary with any useful information.
• More generally, if the set of possible ciphertexts that's independent of the key, the adversary can't learn anything by forging ciphertexts because using a forged ciphertext won't reveal any secret information.
• If there's no way to forge a valid ciphertext with non-negligible probability without knowing the key, as with authenticated encryption, then an adversary can't learn anything by forging ciphertexts because the only information the adversary will get is “no, you didn't manage to forge a valid ciphertext”.
• In between, there is a very dangerous spot where forging ciphertexts can reveal information. The details vary depending on the exact algorithm, but the general principle is that the adversary captures known ciphertext, tweaks it, sends it to a key holder and observes whether the recipient determines that the ciphertext is valid or not. Repeating this with different tweaks may allow the adversary to decrypt the ciphertext.

Given a potential ciphertext and a plaintext, is there a key that turns this ciphertext into this plaintext?

In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.

A scheme where for any plaintext-ciphertext pair, there exists a matching key, is either a one-time pad or a deviation from it that I think only adds useless complexity.

Given a potential ciphertext, is there a key that makes it valid?

This question is only meaningful for schemes where the space of valid ciphertexts depends on the key.

In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.

$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$

My reasoning until now is that this should be equivalent to

$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$

Not quite: if the second proposition is true, that means that every plaintext-ciphertext pair has a corresponding key. But even if this is true, there could be plaintext-ciphertext that are matches by multiple keys. This doesn't happen in realistic message encryption scenarios, but it can happen in some cryptographic schemes where the encryption is only a part of a bigger whole, for example a voting or commitment protocol.

$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$

And if this was false, the opposite must hold:

$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$

i.e.

$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \forall K \in \mathcal{K}: Enc_K(M) \ne C$$

Or in plain English, there exists a plaintext-ciphertext pair which no key matches. As we saw above, this is true of most encryption schemes.

Since all messages $$M \in \mathcal{M}$$ and keys $$K \in \mathcal{K}$$ can be used to create ciphertexts in $$\mathcal{C}$$, this would mean that there exist messages $$M_1, M_2, M_1 \ne M_2$$ which, given a key $$K$$, are encrypted to $$Enc_K(M_1)=Enc_K(M_2)=C$$, which defies the required injectivity of $$Enc$$. Therefore, the proposition must be true. Is it?

I don't see what reasoning led you from the statements above to this last paragraph. You changed from having a fixed plaintext and a fixed ciphertext and varying the key, to having a fixed ciphertext and key and varying the plaintext. Since the decryption function exists, $$Enc_K$$ (i.e. $$M \mapsto Enc_K(M)$$) is injective for every $$K$$. But $$K \mapsto Enc_K(M)$$ for a given $$M$$ does not need to be injective (though it usually is unless the message space is limited to very short messages).

• Thank you very much for your eloaborate answer. Regarding my last paragraph, I now understand that I was mistaken there. I don‘t see how my second proposition is ‚not quite’ equal to the first proposition, though. Since the set in the first proposition (let‘s call it S) is a subset of the set of cleartext and their cardinalities ought to be equal by the first proposition, S contains every possible cleartext. I therefore came to the reasoning you translated to plain english: „for every plaintext-ciphertext pair, there is a K such that Enc_K(M) = C“. Am I mistaken here? Feb 22, 2021 at 23:51
• FYI: This is an academic exercise. Feb 22, 2021 at 23:54