Probabilidad de clave falsa positiva que coincida con dos pares de texto plano / texto cifrado
Dado un espacio de claves de $ 2^{80} $ y espacio de texto plano de $2^{64}$. Y dos pares de texto plano y cifrado$(x_1, y_1)$ , $(x_2, y_2)$. Ahora tenemos$2^{80}/2^{64} = 2^{16}$ claves que cifran $x_1$ a $y_1$ y otro $2^{16}$ claves que cifran $x_2$ a $y_2$, con una sola clave que se supone que es la clave de destino (clave correcta).
¿Cuál es la probabilidad de que una vez que la fuerza bruta identifique una primera clave ($k_1$) esta misma clave sucede por error para cifrar también $x_2$ a $y_2$, es decir, esta clave resulta ser un falso positivo (es decir, es probable que esta clave no cifre$x_3$correctamente). ¿Cuál es la ecuación utilizada y cómo se deriva?
Respuestas
Bajo un modelo de cifrado ideal, cada clave implementa una permutación aleatoria. Una clave incorrecta aleatoria que mapea$x_1$ a $y_1$ así mapas $x_2\ne x_1$ a un texto cifrado aleatorio $y_2'$ otro que $y_1$. Para$b$-cifrado de bloque de bits, hay $2^b-1$ tales textos cifrados, por lo tanto, la probabilidad de que $y_2'=y_2$ es $1/(2^b-1)$.
Por tanto, la probabilidad de que una clave incorrecta sobreviva dos pruebas es $p=1/(2^b\,(2^b-1))$.
Cualquiera $k$-La clave de bit tiene probabilidad $q=2^{-k}$ser correcto. Pasa dos pruebas con certeza si es correcto, con probabilidad$p$de otra manera. Por tanto, una clave aleatoria tiene probabilidad$q+(1-q)\,p$ pasar dos pruebas [donde el $q$ término es para la clave correcta, el $(1-q)\,p$ El término es para claves incorrectas, y se obtiene como la probabilidad de que una clave sea incorrecta, multiplicada por la probabilidad de que, no obstante, pase la prueba con $(x_1,y_1)$ y $(x_2,y_2)$ ].
Por lo tanto, una clave aleatoria que se sabe que pasa dos pruebas tiene probabilidad $q/(q+p\,(1-q))$ para ser correcto [donde el numerador $q$es la probabilidad de que una clave aleatoria sea correcta, y el denominador es la probabilidad de que una clave aleatoria pase dos pruebas]. Eso simplifica a$1/(1+p\,(1/q-1))$.
La probabilidad deseada de un falso positivo es el complemento, es decir $$\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}$$
por $b$ y $k$ al menos 7, eso es $1/(1+2^{2b-k})$dentro del 1%. Cuando mas$2b-k$ es al menos 7, eso es $2^{k-2b}$ dentro del 1%, aquí $2^{-48}$, eso es menos de uno en 280 millones de millones.
De manera más general, se puede demostrar que la probabilidad de un falso positivo después de la prueba $n$ distintos pares de texto plano / cifrado es $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. Para cifrados de bloque comunes como DES y más anchos, eso es muy cercano a$1/(1+2^{n\,b-k})$, y cuando $n\,b-k$ es al menos 7, eso es $2^{k-n\,b}$ dentro del 1%.
De la probabilidad: Sea X un experimento con posibles resultados diferentes $x_1 ,...,x_n$ con probabilidades respectivas $P(x_1)=p_1,...P(x_n)=p_n $. Sea A el subconjunto del espacio muestral${ x_1..,x_n}$con probabilidad P (A) = p. Sea K <= N enteros con N> 0 y K> = 0,$$ \begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}$$ que A ocurre exactamente en k de N ensayos.
ahora, si usamos el ataque de cumpleaños, buscamos la probabilidad de que después de n ensayos al menos 2 resultados sean iguales es al menos $$ 1- e^ {-1/2(n-1)n/N} \tag{2}$$. por lo tanto, para$$ n >{\sqrt {2 ln 2}}{\sqrt N} \tag{3}$$. La probabilidad es al menos 1/2 de que dos resultados sean iguales.
Para la prueba, es mejor calcular la probabilidad de que no haya dos resultados iguales y restar este resultado de 1 para obtener el resultado deseado. podemos considerar los n ensayos en orden y calcular la probabilidad de que no haya dos resultados idénticos para n ensayos en términos del resultado de n-1 ensayos.
Por ej. después de un ensayo, la probabilidad es 1, ya que solo hay un resultado. Después de dos ensayos, hay solo 1 / N de posibilidades de que el segundo ensayo tenga un resultado igual al resultado del primero. lo que significa que, en nuestro caso, la función de cifrado F ha utilizado la misma clave K, por lo que la probabilidad es 1- (1 / N) de que los resultados de dos ensayos sean diferentes. entonces, P (n ensayos todos diferentes) =$${(1-1/N)(1-2/N)... (1-((n-1)/N)) }\tag{4}$$
Comparando con la expansión de Taylor para $$ e^x, where,{e^x = 1 + x} \tag{5}$$para aproximación de primer orden. Tomando$$ {x \approx -a/N} \tag{6} $$ la ecuación (5) se convierte en $${e^ \frac{-a}{N}}\approx 1-\frac{a}{N} \tag{7}$$ , ahora la ecuación (4) es .. $${e^ \frac{-1}{N} \cdot e^\frac{-2}{N} }\cdots{e^\frac{-(n-1)} {N}\tag{8}}$$ , Tomamos la suma de n números naturales $${e^ \frac{-(n(n-1))/2}{N}}$$ Para una n mayor, podemos tomar $$n(n-1)\approx n^2 \tag{9}$$, ahora P (igual) = 1 - P (diferente) que es $${1- e^\frac{-n^2}{2N}\tag{10}}$$