Imaginons une fonction de hachage produisant 'k' bits en sortie.
Sa résistance est de 2^k pour les recherches de préimage.
J'ai coutume de lire que la recherche d'une collision n'est que de
2^(k/2).
Imaginons une fonction de hachage produisant 'k' bits en sortie.
Sa résistance est de 2^k pour les recherches de préimage.
J'ai coutume de lire que la recherche d'une collision n'est que de
2^(k/2).
Imaginons une fonction de hachage produisant 'k' bits en sortie.
Sa résistance est de 2^k pour les recherches de préimage.
J'ai coutume de lire que la recherche d'une collision n'est que de
2^(k/2).
Imaginons une fonction de hachage produisant 'k' bits en sortie.
Sa résistance est de 2^k pour les recherches de préimage.
J'ai coutume de lire que la recherche d'une collision n'est que de
2^(k/2).
En fait des facteurs de 20%, on s'en fiche. Il y a des conditions
d'application pratique qui écrasent ce genre de facteur. Par exemple, si
on fait l'attaque "naïvement", alors on calcule des valeurs, en les
stockant dans en RAM dans une structure apte aux recherches rapides, et
à chaque essai on regarde dans cette structure si la valeur n'a pas déjà
été obtenue. Cette méthode suppose qu'on a une quantité énorme de RAM,
et que cette RAM est très rapide, ce qui est contredit par la
technologie actuelle (la seule RAM rapide dans un PC, c'est le cache L1
du processeur). Donc, si on veut rechercher une collision, on utilisera
plutôt l'algorithme de recherche de cycle de Floyd, qui triple le nombre
d'évaluations de la fonction, mais permet de rester dans le cache L1
(voire dans les registres seulement), ce qui est moult rentable et rend
l'attaque beaucoup plus efficace, voire même faisable.
Ceci étant :
Soit P(n) la probabilité d'avoir au moins une collision avec n essais.
On a clairement P(0) = P(1) = 0 (il faut au moins deux essais pour avoir
une collision). Je note h la taille de l'ensemble de sortie de la fonction
(h = 2^k dans vos notations).
On a P(n) = 1 - Q(n) où Q(n) est la probabilité ne n'avoir aucune
collision dans ces n essais. n tirages aléatoires dans un espace de
taille h représentent h^n combinaisons (en prenant en compte l'ordre
des tirages), parmi lesquels A(h,n) = (h!)/((h-n)!) n'ont pas de
valeur commune. D'où :
Q(n) = h^(-n)*(h!)/((h-n)!)
Pour h grand et n grand mais petit devant h, on peut appliquer
le développement limité au premier ordre de l'exponentielle
(i.e. e^x ~= 1 + x) et obtenir :
Q(n) ~= e^(-(n^2)/(2*h))
Quand n = sqrt(h) (i.e. n = 2^(k/2)) on obtient que Q(n) ~= 1/sqrt(e),
soit P(n) ~= 1 - 1/sqrt(e) ~= 0.39. On a P(n) = 0.5 quand n est
égal à sqrt((2*ln 2)*h) ~= 1.177 * sqrt(h).
(Donc votre évaluation me semble incorrecte quelque part : la probabilité
1/2 est atteinte quand n est 17.7% _au-dessus_ de 2^(k/2). En revanche,
votre formule de base à l'air belle et bonne.)
Maintenant, le n tel que P(n) = 0.5 n'est pas exactement le coût de
l'attaque. Si on refait l'attaque un grand nombre de fois, on va
réussir avant ce n une fois sur deux. Donc n est la _médiane_ du nombre
moyen d'essais. Le coût de l'attaque est la _moyenne_ du nombre d'essais.
Précisément, le coût est :
C = sum_{i=1}^{+inf} i*Q(i-1)*(i-1)/h
(on réussit en précisément i essais si on a raté en i-1 essais, soit
une probabilité de Q(i-1), et que le i-ème essai tombe sur une des
i-1 valeurs précédente, soit (i-1)/h pour cet essai.)
Le calcul est un peu compliqué,
mais ça donne :
C ~= sqrt((pi/2)*h) ~= 1.253*sqrt(h)
donc un coût moyen qui excède la racine carré de h (donc 2^(k/2)) par
environ 25%. En termes de puissances de deux, ça veut dire que le
coût pour k = 128 est proche de 2^64.326. C'est suffisamment proche
de 2^64 pour qu'on se contente de cette approximation.
Un point important est que ces moyennes et médianes ne disent rien sur
la forme de la distribution du nombre d'essais. Avec k = 128, la
probabilité de succès à n= 2^64 est de l'ordre de 39%. Avec huit fois
moins d'essais (n=2^61), la probabilité chute à 0.78%, soit environ 50
fois moins, pour seulement 8 fois moins d'essais. En revanche, avec
n=2^67 essais, la probabilité de succès est à 99.999999...%. Ceci veut
dire que les coûts à chaque attaque sont très resserrés autour du temps
moyen. Le coût moyen est 1.253*2^(k/2), et il est hautement improbable
de beaucoup s'en éloigner.
--Thomas Pornin
Imaginons une fonction de hachage produisant 'k' bits en sortie.
Sa résistance est de 2^k pour les recherches de préimage.
J'ai coutume de lire que la recherche d'une collision n'est que de
2^(k/2).
En fait des facteurs de 20%, on s'en fiche. Il y a des conditions
d'application pratique qui écrasent ce genre de facteur. Par exemple, si
on fait l'attaque "naïvement", alors on calcule des valeurs, en les
stockant dans en RAM dans une structure apte aux recherches rapides, et
à chaque essai on regarde dans cette structure si la valeur n'a pas déjà
été obtenue. Cette méthode suppose qu'on a une quantité énorme de RAM,
et que cette RAM est très rapide, ce qui est contredit par la
technologie actuelle (la seule RAM rapide dans un PC, c'est le cache L1
du processeur). Donc, si on veut rechercher une collision, on utilisera
plutôt l'algorithme de recherche de cycle de Floyd, qui triple le nombre
d'évaluations de la fonction, mais permet de rester dans le cache L1
(voire dans les registres seulement), ce qui est moult rentable et rend
l'attaque beaucoup plus efficace, voire même faisable.
Ceci étant :
Soit P(n) la probabilité d'avoir au moins une collision avec n essais.
On a clairement P(0) = P(1) = 0 (il faut au moins deux essais pour avoir
une collision). Je note h la taille de l'ensemble de sortie de la fonction
(h = 2^k dans vos notations).
On a P(n) = 1 - Q(n) où Q(n) est la probabilité ne n'avoir aucune
collision dans ces n essais. n tirages aléatoires dans un espace de
taille h représentent h^n combinaisons (en prenant en compte l'ordre
des tirages), parmi lesquels A(h,n) = (h!)/((h-n)!) n'ont pas de
valeur commune. D'où :
Q(n) = h^(-n)*(h!)/((h-n)!)
Pour h grand et n grand mais petit devant h, on peut appliquer
le développement limité au premier ordre de l'exponentielle
(i.e. e^x ~= 1 + x) et obtenir :
Q(n) ~= e^(-(n^2)/(2*h))
Quand n = sqrt(h) (i.e. n = 2^(k/2)) on obtient que Q(n) ~= 1/sqrt(e),
soit P(n) ~= 1 - 1/sqrt(e) ~= 0.39. On a P(n) = 0.5 quand n est
égal à sqrt((2*ln 2)*h) ~= 1.177 * sqrt(h).
(Donc votre évaluation me semble incorrecte quelque part : la probabilité
1/2 est atteinte quand n est 17.7% _au-dessus_ de 2^(k/2). En revanche,
votre formule de base à l'air belle et bonne.)
Maintenant, le n tel que P(n) = 0.5 n'est pas exactement le coût de
l'attaque. Si on refait l'attaque un grand nombre de fois, on va
réussir avant ce n une fois sur deux. Donc n est la _médiane_ du nombre
moyen d'essais. Le coût de l'attaque est la _moyenne_ du nombre d'essais.
Précisément, le coût est :
C = sum_{i=1}^{+inf} i*Q(i-1)*(i-1)/h
(on réussit en précisément i essais si on a raté en i-1 essais, soit
une probabilité de Q(i-1), et que le i-ème essai tombe sur une des
i-1 valeurs précédente, soit (i-1)/h pour cet essai.)
Le calcul est un peu compliqué,
mais ça donne :
C ~= sqrt((pi/2)*h) ~= 1.253*sqrt(h)
donc un coût moyen qui excède la racine carré de h (donc 2^(k/2)) par
environ 25%. En termes de puissances de deux, ça veut dire que le
coût pour k = 128 est proche de 2^64.326. C'est suffisamment proche
de 2^64 pour qu'on se contente de cette approximation.
Un point important est que ces moyennes et médianes ne disent rien sur
la forme de la distribution du nombre d'essais. Avec k = 128, la
probabilité de succès à n= 2^64 est de l'ordre de 39%. Avec huit fois
moins d'essais (n=2^61), la probabilité chute à 0.78%, soit environ 50
fois moins, pour seulement 8 fois moins d'essais. En revanche, avec
n=2^67 essais, la probabilité de succès est à 99.999999...%. Ceci veut
dire que les coûts à chaque attaque sont très resserrés autour du temps
moyen. Le coût moyen est 1.253*2^(k/2), et il est hautement improbable
de beaucoup s'en éloigner.
--Thomas Pornin
Imaginons une fonction de hachage produisant 'k' bits en sortie.
Sa résistance est de 2^k pour les recherches de préimage.
J'ai coutume de lire que la recherche d'une collision n'est que de
2^(k/2).
En fait des facteurs de 20%, on s'en fiche. Il y a des conditions
d'application pratique qui écrasent ce genre de facteur. Par exemple, si
on fait l'attaque "naïvement", alors on calcule des valeurs, en les
stockant dans en RAM dans une structure apte aux recherches rapides, et
à chaque essai on regarde dans cette structure si la valeur n'a pas déjà
été obtenue. Cette méthode suppose qu'on a une quantité énorme de RAM,
et que cette RAM est très rapide, ce qui est contredit par la
technologie actuelle (la seule RAM rapide dans un PC, c'est le cache L1
du processeur). Donc, si on veut rechercher une collision, on utilisera
plutôt l'algorithme de recherche de cycle de Floyd, qui triple le nombre
d'évaluations de la fonction, mais permet de rester dans le cache L1
(voire dans les registres seulement), ce qui est moult rentable et rend
l'attaque beaucoup plus efficace, voire même faisable.
Ceci étant :
Soit P(n) la probabilité d'avoir au moins une collision avec n essais.
On a clairement P(0) = P(1) = 0 (il faut au moins deux essais pour avoir
une collision). Je note h la taille de l'ensemble de sortie de la fonction
(h = 2^k dans vos notations).
On a P(n) = 1 - Q(n) où Q(n) est la probabilité ne n'avoir aucune
collision dans ces n essais. n tirages aléatoires dans un espace de
taille h représentent h^n combinaisons (en prenant en compte l'ordre
des tirages), parmi lesquels A(h,n) = (h!)/((h-n)!) n'ont pas de
valeur commune. D'où :
Q(n) = h^(-n)*(h!)/((h-n)!)
Pour h grand et n grand mais petit devant h, on peut appliquer
le développement limité au premier ordre de l'exponentielle
(i.e. e^x ~= 1 + x) et obtenir :
Q(n) ~= e^(-(n^2)/(2*h))
Quand n = sqrt(h) (i.e. n = 2^(k/2)) on obtient que Q(n) ~= 1/sqrt(e),
soit P(n) ~= 1 - 1/sqrt(e) ~= 0.39. On a P(n) = 0.5 quand n est
égal à sqrt((2*ln 2)*h) ~= 1.177 * sqrt(h).
(Donc votre évaluation me semble incorrecte quelque part : la probabilité
1/2 est atteinte quand n est 17.7% _au-dessus_ de 2^(k/2). En revanche,
votre formule de base à l'air belle et bonne.)
Maintenant, le n tel que P(n) = 0.5 n'est pas exactement le coût de
l'attaque. Si on refait l'attaque un grand nombre de fois, on va
réussir avant ce n une fois sur deux. Donc n est la _médiane_ du nombre
moyen d'essais. Le coût de l'attaque est la _moyenne_ du nombre d'essais.
Précisément, le coût est :
C = sum_{i=1}^{+inf} i*Q(i-1)*(i-1)/h
(on réussit en précisément i essais si on a raté en i-1 essais, soit
une probabilité de Q(i-1), et que le i-ème essai tombe sur une des
i-1 valeurs précédente, soit (i-1)/h pour cet essai.)
Le calcul est un peu compliqué,
mais ça donne :
C ~= sqrt((pi/2)*h) ~= 1.253*sqrt(h)
donc un coût moyen qui excède la racine carré de h (donc 2^(k/2)) par
environ 25%. En termes de puissances de deux, ça veut dire que le
coût pour k = 128 est proche de 2^64.326. C'est suffisamment proche
de 2^64 pour qu'on se contente de cette approximation.
Un point important est que ces moyennes et médianes ne disent rien sur
la forme de la distribution du nombre d'essais. Avec k = 128, la
probabilité de succès à n= 2^64 est de l'ordre de 39%. Avec huit fois
moins d'essais (n=2^61), la probabilité chute à 0.78%, soit environ 50
fois moins, pour seulement 8 fois moins d'essais. En revanche, avec
n=2^67 essais, la probabilité de succès est à 99.999999...%. Ceci veut
dire que les coûts à chaque attaque sont très resserrés autour du temps
moyen. Le coût moyen est 1.253*2^(k/2), et il est hautement improbable
de beaucoup s'en éloigner.
--Thomas Pornin
J'ai du mal à comprendre la notion A(h,n), que représente t'elle?
Il y aurait un site web qui explicite le calcul?
J'ai du mal à comprendre la notion A(h,n), que représente t'elle?
Il y aurait un site web qui explicite le calcul?
J'ai du mal à comprendre la notion A(h,n), que représente t'elle?
Il y aurait un site web qui explicite le calcul?