What is the computational cost of guessing symmetric keys for two ciphers that decrypt to the same input? A message m is encrypted with two symmetric keys, resulting in two ciphers c,

c1 = encrypt(m, key1)

c2 = encrypt(m, key2)

What is the computational cost of guessing symmetric keys for both ciphers that decrypt to the same message?
I stick to a symmetric, non-authenticated cipher; and unless otherwise specified I consider it as a black box.

By an entropy argument, for the problem to be consistently solvable, we need $m$ to be slightly larger than the key size if $m$ is known, or slightly larger than twice the key size if $m$ is unknown (I'll suppose that); otherwise, chance is that there are multiple solutions, and we have no way to find which is correct.



Things  depends on if $m$ is given or not, and if the cipher is deterministic (e.g. a block cipher, or one in ECB mode) or randomized (e.g. a stream cipher or a block cipher in CTR mode).

If $m$ is given and the cipher is deterministic, we can enumerate keys $K$ among $2^k$ (say incrementally), encipher $m$ with $K$, and conclude that $K$ is neither the desired $K_1$ nor $K_2$ when the ciphertext matches neither $c_1$ not $c_2$ (which is, most of the time). Our explored $K$ will include both $K_1$ and $K_2$ with probability $1/2$ after exploring $2^{k-1/2}$ keys (rather than $2^{k-1}$ for one key). The expected number of encryptions to find both keys is $2^{k+1}/3$ (rather than $2^{k-1}$ ), an increase by $1/3$. The expected work is increased slightly more (because of the extra comparison).

Per request: The number of encryptions is $\max(K_1,K_2)+1$. The keys behave as two uniform and independent discrete variables in $[0,2^k[$. As $k$ grows, the ratio of the expected number of encryptions to $2^k$ thus converges (quickly) to the mean value of the largest of two continuous variables in $[0,1[$. Thus a first-order approximation of the expected number of encryptions to find both keys is
$$2^k\int_{x=0}^1\int_{y=0}^1\max(x,y)\ \mathrm dx\ \mathrm dy=2^k\int_{x=0}^1\left(\left(\int_{y=0}^x x\ \mathrm dy\right)+\left(\int_{y=x}^1 y\ \mathrm dy\right)\right)\mathrm dx\\=2^k\int_{x=0}^1\left(x^2+1/2-x^2/2\right)\mathrm dx=2^k(1/6+1/2)=2^{k+1}/3$$



If $m$ is given and the cipher is non-deterministic, we can enumerate keys $K$ as above, decipher $c_1$ and $c_2$ with this key, and compare against $m$. As above, our explored $K$ will include both $K_1$ and $K_2$ with probability $1/2$ after exploring $2^{k-1/2}$ keys. However, until we have found one of the key, we need to decipher twice with each $K$. The expected number of decryption is $2^k$, twice as much as for one key. The expected work might be increased rather less, depending on internals of the cipher (e.g. for AES, the derivation of round subkeys can be shared between the two decryptions in the phase where neither key is available).



If $m$ is unknown, we can use a Meet-in-the-Middle attack: we decipher $c_1$ using all (or most) $K$, building a dictionary of possible $m$; then we decipher $c_2$ enumerating $K$, until we find the resulting $m$ in the dictionary. The expected number of decryption is $2^{k+1/2}$, three times as much as for one key and known $m$. A lot of memory is necessary, but there are workarounds at the cost of only moderately more work; see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website)



If we "open" the cipher's black box, things change, possibly sizably. In particular, for ciphers allowing on-the-fly encryption/decryption, we need not fully encipher/decipher a large $m$ in full. And for some ciphers (e.g. 3DES), there might be shortcuts.