# (DES) What is the probability that two keys (k1, k2) produce the same ciphertext given the same plaintext?

Basically, I need to find the probability that DES(p, k1) = DES(p, k2) = c

My guess is that probability = 1 / 2^64 since that's the total number of possible outputs, but honestly I have no clue about crypto. Thanks in advance for any help!

• Welcome to Cryptography. Could you provide the origin of this question? Commented Oct 28, 2022 at 10:21

It depends on what you mean. There are $$2^{56}$$ different DES keys and so if $$k_1$$ and $$k_2$$ are both chosen uniformly and independently at random, then there is a $$2^{-56}$$ chance that they are the same key in which case $$\mathrm{DES}(p,k_1)=\mathrm{DES}(p,k_2)$$ independently of the choice of $$p$$. (With non-causal cases being a second-order effect).
If on the other hand $$k_1$$ and $$k_2$$ are distinct and $$p$$ is chosen uniformly at random then @kodlu's analysis holds.
However, if we choose distinct $$k_1$$ and $$k_2$$ then ask for the probability that there exists some $$p$$ such that $$\mathrm{DES}(p,k_1)=\mathrm{DES}(p,k_2)$$ is the probability that $$\pi_{k_1}^{-1}(\pi_{k_2}(x))$$ is not a derangement which is roughly $$(1-1/e)$$ (assuming that the DES operation is indistinguishable from a random permutation).
Let $$DES(p,k)$$ be modeled by the pseudorandom permutation $$\pi_{k}:\{0,1\}^{64}\rightarrow \{0,1\}^{64}.$$ Then $$DES(p,k_1)=DES(p,k_2) \Leftrightarrow \pi_{k_2}^{-1}(\pi_{k_1}(p))=p.$$ Since $$\pi_{k_2}^{-1}(\pi_{k_1}(\cdot))$$ is itself a pseudorandom permutation. The probability that a given point $$p$$ is fixed by this permutation is $$1/2^{64}$$ which is the ratio $$(n-1)!/n!$$ with $$n=2^{64}$$ since there are $$(n-1)!$$ permutations on $$n$$ points which fix a given point.