Probabilité d'une fausse clé positive correspondant à deux paires de texte brut / texte chiffré
Étant donné un espace de clés de $ 2^{80} $ et espace en clair de $2^{64}$. Et deux paires de texte en clair et de texte chiffré$(x_1, y_1)$ , $(x_2, y_2)$. Maintenant nous avons$2^{80}/2^{64} = 2^{16}$ clés qui chiffrent $x_1$ à $y_1$ et un autre $2^{16}$ clés qui chiffrent $x_2$ à $y_2$, avec une seule clé qui est censée être la clé cible (clé correcte).
Quelle est la probabilité qu'une fois que la force brute identifie une première clé ($k_1$) cette même clé arrive par erreur pour chiffrer également $x_2$ à $y_2$, c'est-à-dire que cette clé se trouve être un faux positif (c'est-à-dire que cette clé ne chiffrera probablement pas$x_3$correctement). Quelle est l'équation utilisée et comment est-elle dérivée?
Réponses
Dans un modèle de chiffrement idéal, chaque clé implémente une permutation aléatoire. Une mauvaise clé aléatoire qui correspond$x_1$ à $y_1$ donc des cartes $x_2\ne x_1$ à un texte chiffré aléatoire $y_2'$ autre que $y_1$. Pour un$b$chiffrement par bloc -bit, il y a $2^b-1$ ces textes chiffrés, donc la probabilité que $y_2'=y_2$ est $1/(2^b-1)$.
La probabilité qu'une clé incorrecte survit à deux tests est donc $p=1/(2^b\,(2^b-1))$.
Un hasard $k$-bit clé a une probabilité $q=2^{-k}$être correct. Il passe deux tests avec certitude s'il est correct, avec probabilité$p$autrement. Ainsi, une clé aléatoire a une probabilité$q+(1-q)\,p$ passer deux tests [où le $q$ le terme est pour la clé correcte, le $(1-q)\,p$ terme est pour les clés incorrectes, et obtenu comme la probabilité qu'une clé soit incorrecte, multipliée par la probabilité qu'elle réussisse néanmoins le test avec $(x_1,y_1)$ et $(x_2,y_2)$ ].
Ainsi, une clé aléatoire connue pour passer deux tests a une probabilité $q/(q+p\,(1-q))$ pour être correct [où le numérateur $q$est la probabilité qu'une clé aléatoire soit correcte, et le dénominateur est la probabilité qu'une clé aléatoire passe deux tests]. Cela simplifie à$1/(1+p\,(1/q-1))$.
La probabilité souhaitée d'un faux positif est le complément, c'est-à-dire $$\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}$$
Pour $b$ et $k$ au moins 7, c'est $1/(1+2^{2b-k})$à moins de 1%. Quand plus loin$2b-k$ est au moins 7, c'est $2^{k-2b}$ à moins de 1%, ici $2^{-48}$, c'est moins d'un sur 280 millions de millions.
Plus généralement, on peut montrer que la probabilité de faux positifs après le test $n$ les paires distinctes de texte brut / texte chiffré sont $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. Pour les chiffrements par blocs courants comme DES et plus larges, c'est très proche de$1/(1+2^{n\,b-k})$, et quand $n\,b-k$ est au moins 7, c'est $2^{k-n\,b}$ à moins de 1%.
De la probabilité: Soit X une expérience avec des résultats différents possibles $x_1 ,...,x_n$ avec des probabilités respectives $P(x_1)=p_1,...P(x_n)=p_n $. Soit A le sous-ensemble de l'espace échantillon${ x_1..,x_n}$avec probabilité P (A) = p. Soit K <= N entiers avec N> 0 et K> = 0,$$ \begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}$$ que A se produit dans exactement k de N essais.
maintenant, si nous utilisons l'attaque d'anniversaire, nous recherchons la probabilité qu'après n essais, au moins 2 résultats soient les mêmes est au moins $$ 1- e^ {-1/2(n-1)n/N} \tag{2}$$. par conséquent, pour $$ n >{\sqrt {2 ln 2}}{\sqrt N} \tag{3}$$. La probabilité est d'au moins 1/2 que deux résultats soient les mêmes.
Pour la preuve, il est préférable de calculer la probabilité qu'il n'y ait pas deux résultats identiques et de soustraire ce résultat de 1 pour obtenir le résultat souhaité. nous pouvons considérer les n essais dans l'ordre et calculer la probabilité qu'il n'y ait pas deux résultats identiques pour n essais en termes de résultat pour n-1 essais.
Par ex. après un essai, la probabilité est de 1, car il n'y a qu'un seul résultat. Après deux essais, il y a seulement 1 / N chance que le deuxième essai ait un résultat égal au résultat du premier. ce qui signifie que, dans notre cas, la fonction de chiffrement F a utilisé la même clé K, donc la probabilité est 1- (1 / N) que les résultats de deux essais soient différents. donc, P (n essais tous différents) =$${(1-1/N)(1-2/N)... (1-((n-1)/N)) }\tag{4}$$
Comparaison avec l'expansion de Taylor pour $$ e^x, where,{e^x = 1 + x} \tag{5}$$pour une approximation de premier ordre. Prise$$ {x \approx -a/N} \tag{6} $$ l'équation (5) devient $${e^ \frac{-a}{N}}\approx 1-\frac{a}{N} \tag{7}$$ , maintenant l'équation (4) est .. $${e^ \frac{-1}{N} \cdot e^\frac{-2}{N} }\cdots{e^\frac{-(n-1)} {N}\tag{8}}$$ , On prend la somme de n nombres naturels $${e^ \frac{-(n(n-1))/2}{N}}$$ Pour un n plus grand, nous pouvons prendre $$n(n-1)\approx n^2 \tag{9}$$, maintenant P (identique) = 1 - P (différent) qui est $${1- e^\frac{-n^2}{2N}\tag{10}}$$