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 presume that the encryption algorithm should be considered to be identical, right? Note that the algorithm is usually called the cipher and the outcome the ciphertext. In above it seems you confuse the two - please edit the question if this is correct. – Maarten Bodewes Feb 19 '18 at 13:53
• Are you trying to find one of the right keys, using the fact that two ciphertexts are encryptions of the same plaintext or, find any two keys which will decrypt a ciphertext to the same value? – Elias Feb 19 '18 at 16:29

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.

• Would you mind deriving that $2^{k+1}/3$? – Elias Feb 19 '18 at 17:28
• I get approximately the same using explicit calculation, was just curious about the specifics. – Elias Feb 19 '18 at 19:39
• In case you care I get $X - X/3 + 1/2 - 1/{6X}$ for $X = 2^k$. – Elias Feb 19 '18 at 19:55
• Plus a constant? – Q-Club Feb 20 '18 at 7:53

The cost is the same if the cipher is secure.

Just consider that otherwise, if I know you encrypted an answer of "yes" or "no" to somebodys question, I could just encrypt "yes" and "no" with a random key and it would help me find your key.

• "The cost is the same" is valid as a rough approximation. But if we dive in details, expected cost is increased by at least $1/3$, perhaps much more. – fgrieu Feb 19 '18 at 11:57