Probability of false positive key matching two plaintext/ciphertext pairs

Question

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?

Answer 1

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

Answer 2

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}}$$