Do key collisions for symmetric ciphers exist? I'm not sure if I'm calling the thing (key collisions) correctly, and that's probably why I couldn't find any information about it on Google. Still, my question is as follows. Note that I don't work with encryption right now and I'm not going to implement anything based on this knowledge; this is a purely theoretical question which I found very interesting.

Suppose that you have a key K and a plain text P. Then you use some symmetric algorithm A like one of AES variants to obtain a ciphertext C = A_encrypt(P, K). Is it possible that some key K* != K exists which can be used to get back the plain text out of the same ciphertext, i.e. P = A_decrypt(C, K*)? How it depends, if it does, on the type of the cipher (block vs stream), on the exact algorithm and on the size of the key and the size of the plain text? My intuition suggests that impossibility or, at least, improbability of such thing is the reason of existence of symmetric ciphers, but still this is not stated explicitly anywhere I could find.

What surprises me that I couldn't find anything which answers such question directly; moreover, I couldn't find anyone asking such question. All I could find are questions like this which seem to be related but not exactly the same as my question, and questions like "how to generate two keys to decipher the same data" which are somewhat opposite to my question.
The number of possible permutations of a block cipher are $2^n!$ where $n$ is the block size. A permutation maps all $2^n$ possible input blocks to $2^n$ possible output blocks. A key, with key space $2^k$ selects one of them. Although that's a huge number of keys, it is dwarfed by the amount of possible permutations.

Now it's not by definition impossible that the same permutation can be chosen by a key, but it is pretty unlikely. Such a key would be considered an equivalent key or - less specifically - a weak key. Many algorithms are designed to disallow weak keys. If it is possible to have the same permutation then it is likely to be present by design; you won't find one by chance alone.

Finding two keys that map a single specific plaintext to identical ciphertext or vice versa is much more likely. It depends on the block cipher details if this is anywhere near possible see this discussion on AES for more information.



For stream ciphers the question is somewhat more difficult. It probably suffices to say that the output of the stream cipher is determined by a key and an IV (sometimes fused into one, for instance in RC4). If the size of the key, IV and internal state of the stream cipher are large enough, you should not be able to find a large amount of repetition in the key streams generated for separate key / IV pairs.

It will be possible to find keys that generate small amounts of identical key streams. This is easy to see; about half of the keys should decrypt a single bit correctly. It may be impossible to determine if you'd have generated the correct plaintext though; you'd have to determine the two keys in advance.

The idea expressed above would also work for a block cipher in a streaming mode of operation such as CTR (counter mode).



These kind of questions have been asked, but they are tricky to find if you don't know the right terms - and probably even if you do.

Related is the question if algorithms contain back doors. In that case the attacker should be able to decrypt whatever the key value is though. 

Deniable encryption is another somewhat related term.