paradoxe des anniversaires et résistance des fonctions de hachage

Le
Kevin Denis
Bonjour,

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

Néanmoins, en prenant en compte le paradoxe des anniversaires, la
recherche d'une collision ne devrait elle pas être plus faible?

Si on prend n condensat, et chaque condensat devant être différent,
nous obtenons une probabilité qu chaque hash soit différent de:
1 2 n-1
1-(1- )(1- )(1- )
2^k 2^k 2^k

La question se pose, à partir de combien d'essais 'n' j'obtiens une
probabilité supérieure à 1/2 pour obtenir deux hash identiques.
Le résultat indique, pour un hash de 128 bits: n=1,5x10^19

Ce qui est inférieur au résultat précédent, i.e. k/2, donc
pour 128bits: 2^64. (les valeurs sont proches, à 20% près toutefois)

2^64 = 18446744073709551616
1,5x10^19 = 15000000000000000000

Ma question:
quelle valeur faut il donc prendre pour estimer la résistance d'une
fonction de hachage aux collisions? k/2 ou bien le paradoxe des
anniversaires? Est-ce important?

Merci
--
Kevin
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Thomas Pornin
Le #19045791
According to Kevin Denis
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
Kevin Denis
Le #19064851
Le 03-04-2009, 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



J'ai du mal à comprendre la notion A(h,n), que représente t'elle?

valeur commune. D'où :

Q(n) = h^(-n)*(h!)/((h-n)!)



Et j'ai du mal également à voir le lien de cause à effet

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



ok

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.



ok

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é,



Il y aurait un site web qui explicite le calcul?

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.



D'accord

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.



Ok.

--Thomas Pornin



Merci beaucoup.
--
Kevin
Thomas Pornin
Le #19065631
According to Kevin Denis
J'ai du mal à comprendre la notion A(h,n), que représente t'elle?



C'est le nombre d'arrangements (d'où le 'A') de n valeurs parmi h. Ça
correspond au nombre de tirages sans remise de h boules parmi n, en
conservant l'ordre des boules. Pour la première boule, on a h choix.
Pour la suivante, h-1, puisqu'on ne veut pas retomber sur la première.
Puis h-2, etc... d'où h*(h-1)*(h-2)*...*(h-n+1) combinaisons, ce qui
s'écrit aussi avec des factorielles : (h!)/((h-n)!)

Ici, on regarde les tirages possibles en considérant que chaque
valeur est aléatoire. Ça fait h^n combinaisons. Parmi ces h^n
combinaisons, il y en a A(h,n) qui ne réutilisent pas deux fois la
même valeur, d'où :

Q(n) = h^(-n)*(h!)/((h-n)!)


Il y aurait un site web qui explicite le calcul?



Cette page :
http://en.wikipedia.org/wiki/Birthday_problem
contient des explications et des références, mais je n'ai pas
regardé suffisamment pour savoir à quel point c'est explicite.


--Thomas Pornin
Publicité
Poster une réponse
Anonyme