# Probability of false positive key matching two plaintext/ciphertext pairs

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?

• 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).
– fgrieu
Nov 27 '20 at 6:53
• @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) .
– KMG
Nov 27 '20 at 7:51
• 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.
– 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%.

• 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.
– KMG
Nov 27 '20 at 10:26
• @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.
– fgrieu
Nov 27 '20 at 11:18
• thanks a lot this answer couldn't be better explained, I got it now.
– KMG
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}}$$

• 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.
– fgrieu
Nov 29 '20 at 14:41
• 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.
– SSA
Nov 30 '20 at 6:26