Score:1

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

bs flag

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!

kelalaka avatar
in flag
Welcome to [cryptography.se]. Could you provide the origin of this question?
Score:4
ru flag

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).

Score:3
sa flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.