Given a keyspace of $ 2^{80} $ and plaintext space of $2^{64}$. And two plaintext and ciphertext pairs $(x_1, y_1)$ , $(x_2, y_2)$. Now we have $2^{80}/2^{64} = 2^{16}$ keys that encrypt $x_1$ to $y_1$ and another $2^{16}$ keys that encrypt $x_2$ to $y_2$, with only one key that is supposed to be the target key (correct key).

What is the probability that once brute-force identifies a first key ($k_1$) this same key happen by mistake to also encrypt $x_2$ to $y_2$, that is this this key happen to be a False-positive (that is, this key will likely not encrypt $x_3$ correctly). What is the equation used and how is it derived?

  • $\begingroup$ Hint: when the wrong key was found by accident, we can consider that the cipher implements a random permutation among these that map $x_1$ to $y_1$, and therefore maps $x_2$ to a random element other than $y_1$. The probability that you want follows (because the question looks like homework, our policy require to only give hints). $\endgroup$ – fgrieu Nov 27 '20 at 6:53
  • $\begingroup$ @fgrieu I can't really see the hint here. this question is actually not a homework I just can't see how to calculate this possibility for any block cipher (either for ciphers having larger or smaller key space than plaintext) . $\endgroup$ – Khaled Gaber Nov 27 '20 at 7:51
  • $\begingroup$ your key space is higher than your plaintext (message space). now cipher function F may use F(K1,P1) = C1 and again once the plaintext is repeated F(K2,P1)=C2. Until you exhausted the key space. you can still decrypt the P1 correctly, with either K2 or K1. It is the Key space that is important. In short, every element e belongs to Key space K . uniquely determine a bijection from Message Space M to ciphertext C. $\endgroup$ – SSA Nov 27 '20 at 9:51

Under an ideal cipher model, every key implements a random permutation. A random wrong key that maps $x_1$ to $y_1$ thus maps $x_2\ne x_1$ to a random ciphertext $y_2'$ other than $y_1$. For a $b$-bit block cipher, there are $2^b-1$ such ciphertexts, thus the probability that $y_2'=y_2$ is $1/(2^b-1)$.

The probability that an incorrect key survives two tests is thus $p=1/(2^b\,(2^b-1))$.

A random $k$-bit key has probability $q=2^{-k}$ to be correct. It passes two tests with certainty if correct, with probability $p$ otherwise. Thus a random key has probability $q+(1-q)\,p$ to pass two tests [where the $q$ term is for the correct key, the $(1-q)\,p$ term is for incorrect keys, and obtained as the the probability that a key is incorrect, times the probability that it nevertheless passes the test with $(x_1,y_1)$ and $(x_2,y_2)$ ].

Thus a random key known to pass two tests has probability $q/(q+p\,(1-q))$ to be correct [where the numerator $q$ is the probability for a random key to be correct, and the denominator is the probability that a random key pass two tests]. That simplifies to $1/(1+p\,(1/q-1))$.

The desired probability of a false positive is the complement, that is $$\begin{align}1-1/(1+p\,(1/q-1))\,&=\,1/(1+1/(p\,(1/q-1)))\\&=\,1/(1+2^b\,(2^b-1)/(2^k-1))\end{align}$$

For $b$ and $k$ at least 7, that's $1/(1+2^{2b-k})$ within 1%. When further $2b-k$ is at least 7, that's $2^{k-2b}$ within 1%, here $2^{-48}$, that is less than one in 280 million million.

More generally, it can be shown that the probability of false positive after testing $n$ distinct plaintext/ciphertext pairs is $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. For common block ciphers like DES and wider, that's very close to $1/(1+2^{n\,b-k})$, and when $n\,b-k$ is at least 7, that's $2^{k-n\,b}$ within 1%.

  • $\begingroup$ thanks a lot first. I seems to follow well the answer until the part q+(1-q)p so if you can explain a little bit more this part will be really helpful. $\endgroup$ – Khaled Gaber Nov 27 '20 at 10:26
  • $\begingroup$ @Khaled Gaber: that's more detailed now. Also I made a last paragraph covering the case of $n$ plaintext/ciphertext pairs, and made the approximations in the last two paragraphs quantitative. $\endgroup$ – fgrieu Nov 27 '20 at 11:18
  • $\begingroup$ thanks a lot this answer couldn't be better explained, I got it now. $\endgroup$ – Khaled Gaber Nov 27 '20 at 12:24

From probability: Let X be an experiment with possible different outcomes $x_1 ,...,x_n$ with respective probabilities $P(x_1)=p_1,...P(x_n)=p_n $ . Let A be the subset of sample space ${ x_1..,x_n}$ with probability P(A)=p. Let K <= N integers with N >0 and K>=0, $$ \begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}$$ that A occurs in Exactly k of N trials.

now, if we use birthday attack, we are looking for the probability that after n trials at least 2 outcomes will be the same is at least $$ 1- e^ {-1/2(n-1)n/N} \tag{2}$$. hence, for $$ n >{\sqrt {2 ln 2}}{\sqrt N} \tag{3}$$. The probability is at least 1/2 that two outcomes will be the same.

For the proof it is better to compute the probability that no two outcomes are the same and subtract this result from 1 to obtain the desired result. we can consider the n trials in order and compute the probability of no two identical outcomes for n trials in terms of the result for n-1 trials.

For ex. after one trial probability is 1, as there is only one outcome. After two trials, there is only 1/N chance that the second trial had an outcome equal to the outcome of first one. which means , in our case,cipher function F has used same key K, so the probability is 1-(1/N) that outcomes of two trials will be different. so, P(n trials all different )= $${(1-1/N)(1-2/N)... (1-((n-1)/N)) }\tag{4}$$

Comparing with Taylor's Expansion for $$ e^x, where,{e^x = 1 + x} \tag{5}$$ for first order approximation. Taking $$ {x \approx -a/N} \tag{6} $$ equation (5) becomes $${e^ \frac{-a}{N}}\approx 1-\frac{a}{N} \tag{7}$$ , now the equation (4) is.. $${e^ \frac{-1}{N} \cdot e^\frac{-2}{N} }\cdots{e^\frac{-(n-1)} {N}\tag{8}}$$ , We take sum of n natural numbers $${e^ \frac{-(n(n-1))/2}{N}}$$ For a larger n, we can take $$n(n-1)\approx n^2 \tag{9}$$, now P(Same) = 1 - P(different) which is $${1- e^\frac{-n^2}{2N}\tag{10}}$$

  • $\begingroup$ How would your $n$ and $N$ relate to the 64 (or 128) bit block size and 80 bit key size of the question? I still do no see where the birthday bound matters in the question. $\endgroup$ – fgrieu Nov 29 '20 at 14:41
  • $\begingroup$ N is a key space 2^t, and n is the number of trials. It will give us the probability after how many trials a cipher may need for two same keys. $\endgroup$ – SSA Nov 30 '20 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.