Pour un hash, deux caratéristiques importantes sont:
La résistance aux secondes pré-images: s'il est difficile de trouver
un message "B" produisant la même empreinte "H" que le message "A", en
connaissant "H" et "A".
La résistance aux collisions: s'il est difficile de trouver 2 messages
distincts "A" et "B" produisant une même empreinte "H".
Les collisions sont beaucoup plus facile à mettre en oeuvre que les
pré-images. mais ces deux caractéristiques ne sont pas indépendantes
du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes
pré-images, la connaissance à la résistance aux collisions me
permet-elle de déduire (ou au moins d'approximer) la resistance aux
premières pre-images?
Existe-t-il de la littérature sur le lien probabiliste entre ces deux
éléments?
Je recherche des éléments me permettant de faire ce genre de
conclusion: (il faut 300 000 essais pour trouver une collision (avec
une certaine confiance)donc il me faudra au moins 500 000 000 d'essais
pour trouver une seconde pré-image ayant le même hash qu'une pré-image
donnée (avec la même confiance)
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Kevin Drapel
Les collisions sont beaucoup plus facile à mettre en oeuvre que les pré-images. mais ces deux caractéristiques ne sont pas indépendantes du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes pré-images, la connaissance à la résistance aux collisions me permet-elle de déduire (ou au moins d'approximer) la resistance aux premières pre-images?
Je ne crois pas qu'il y aie un lien "quantifiable". Par exemple, le MD5 n'est plus résistant aux collisions quelconques mais il n'y a toujours pas d'attaques sur les premières préimages. De ce fait, la complexité pour trouver une première préimage n'a pas changé et elle est toujours de l'ordre de 2^128 opérations. S'il existait un lien probabiliste, alors cette complexité serait diminuée et l'algo serait considéré comme cassé. Maintenant, il se peut que les attaques sur les collisions ouvrent des portes pour des attaques sur les préimages, mais cela reste spécifique à la fonction de hachage et à la méthode utilisée.
Les collisions sont beaucoup plus facile à mettre en oeuvre que les
pré-images. mais ces deux caractéristiques ne sont pas indépendantes
du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes
pré-images, la connaissance à la résistance aux collisions me
permet-elle de déduire (ou au moins d'approximer) la resistance aux
premières pre-images?
Je ne crois pas qu'il y aie un lien "quantifiable". Par exemple, le MD5
n'est plus résistant aux collisions quelconques mais il n'y a toujours
pas d'attaques sur les premières préimages. De ce fait, la complexité
pour trouver une première préimage n'a pas changé et elle est toujours
de l'ordre de 2^128 opérations. S'il existait un lien probabiliste,
alors cette complexité serait diminuée et l'algo serait considéré comme
cassé. Maintenant, il se peut que les attaques sur les collisions
ouvrent des portes pour des attaques sur les préimages, mais cela reste
spécifique à la fonction de hachage et à la méthode utilisée.
Les collisions sont beaucoup plus facile à mettre en oeuvre que les pré-images. mais ces deux caractéristiques ne sont pas indépendantes du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes pré-images, la connaissance à la résistance aux collisions me permet-elle de déduire (ou au moins d'approximer) la resistance aux premières pre-images?
Je ne crois pas qu'il y aie un lien "quantifiable". Par exemple, le MD5 n'est plus résistant aux collisions quelconques mais il n'y a toujours pas d'attaques sur les premières préimages. De ce fait, la complexité pour trouver une première préimage n'a pas changé et elle est toujours de l'ordre de 2^128 opérations. S'il existait un lien probabiliste, alors cette complexité serait diminuée et l'algo serait considéré comme cassé. Maintenant, il se peut que les attaques sur les collisions ouvrent des portes pour des attaques sur les préimages, mais cela reste spécifique à la fonction de hachage et à la méthode utilisée.
Shal
Les collisions sont beaucoup plus facile à mettre en oeuvre que les pré-images. mais ces deux caractéristiques ne sont pas indépendantes du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes pré-images, la connaissance à la résistance aux collisions me permet-elle de déduire (ou au moins d'approximer) la resistance aux premières pre-images?
Je ne crois pas qu'il y aie un lien "quantifiable". Par exemple, le MD5 n'est plus résistant aux collisions quelconques mais il n'y a toujours pas d'attaques sur les premières préimages. De ce fait, la complexité pour trouver une première préimage n'a pas changé et elle est toujours de l'ordre de 2^128 opérations. S'il existait un lien probabiliste, alors cette complexité serait diminuée et l'algo serait considéré comme cassé. Maintenant, il se peut que les attaques sur les collisions ouvrent des portes pour des attaques sur les préimages, mais cela reste spécifique à la fonction de hachage et à la méthode utilisée.
Je crois pas qu'on parle de la même chose:
Je suis d'accord pour dire que les algos utilisés pour trouver une collision ne réduisent peut-être pas la compléxité a trouver une pré-image différente avec le même hash.
Mais si je raméne mon problème en un problème de boules dans une urne (les boules sont des hashs de l'ensemble des nombre entier inférieure à 2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules portant le même nombre, plus il est aisé de trouver une boule qui comporte le même numéro qu'une boule donnée.". Je pense que cette assertion est vrai, mon problème est de quantifier ce rapport.
Les collisions sont beaucoup plus facile à mettre en oeuvre que les
pré-images. mais ces deux caractéristiques ne sont pas indépendantes
du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes
pré-images, la connaissance à la résistance aux collisions me
permet-elle de déduire (ou au moins d'approximer) la resistance aux
premières pre-images?
Je ne crois pas qu'il y aie un lien "quantifiable". Par exemple, le MD5
n'est plus résistant aux collisions quelconques mais il n'y a toujours
pas d'attaques sur les premières préimages. De ce fait, la complexité
pour trouver une première préimage n'a pas changé et elle est toujours
de l'ordre de 2^128 opérations. S'il existait un lien probabiliste,
alors cette complexité serait diminuée et l'algo serait considéré comme
cassé. Maintenant, il se peut que les attaques sur les collisions
ouvrent des portes pour des attaques sur les préimages, mais cela reste
spécifique à la fonction de hachage et à la méthode utilisée.
Je crois pas qu'on parle de la même chose:
Je suis d'accord pour dire que les algos utilisés pour trouver une
collision ne réduisent peut-être pas la compléxité a trouver une
pré-image différente avec le même hash.
Mais si je raméne mon problème en un problème de boules dans une urne
(les boules sont des hashs de l'ensemble des nombre entier inférieure à
2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules
portant le même nombre, plus il est aisé de trouver une boule qui
comporte le même numéro qu'une boule donnée.". Je pense que cette
assertion est vrai, mon problème est de quantifier ce rapport.
Les collisions sont beaucoup plus facile à mettre en oeuvre que les pré-images. mais ces deux caractéristiques ne sont pas indépendantes du point de vue probabiliste.
Si je veux tester la résistance à un algorithme de hash aux secondes pré-images, la connaissance à la résistance aux collisions me permet-elle de déduire (ou au moins d'approximer) la resistance aux premières pre-images?
Je ne crois pas qu'il y aie un lien "quantifiable". Par exemple, le MD5 n'est plus résistant aux collisions quelconques mais il n'y a toujours pas d'attaques sur les premières préimages. De ce fait, la complexité pour trouver une première préimage n'a pas changé et elle est toujours de l'ordre de 2^128 opérations. S'il existait un lien probabiliste, alors cette complexité serait diminuée et l'algo serait considéré comme cassé. Maintenant, il se peut que les attaques sur les collisions ouvrent des portes pour des attaques sur les préimages, mais cela reste spécifique à la fonction de hachage et à la méthode utilisée.
Je crois pas qu'on parle de la même chose:
Je suis d'accord pour dire que les algos utilisés pour trouver une collision ne réduisent peut-être pas la compléxité a trouver une pré-image différente avec le même hash.
Mais si je raméne mon problème en un problème de boules dans une urne (les boules sont des hashs de l'ensemble des nombre entier inférieure à 2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules portant le même nombre, plus il est aisé de trouver une boule qui comporte le même numéro qu'une boule donnée.". Je pense que cette assertion est vrai, mon problème est de quantifier ce rapport.
Kevin Drapel
Mais si je raméne mon problème en un problème de boules dans une urne (les boules sont des hashs de l'ensemble des nombre entier inférieure à 2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules portant le même nombre, plus il est aisé de trouver une boule qui comporte le même numéro qu'une boule donnée.". Je pense que cette assertion est vrai, mon problème est de quantifier ce rapport.
Ok, je vois ton idée. A mon avis, cela revient à montrer qu'il y a un biais dans la distribution des sorties. Si la fonction de hachage distribue uniformément les sorties, alors ton attaque sur la préimage aura la complexité maximale de 2^N avec N le nombre de bits dans les signatures. Trouver une collision ne t'aidera pas dans ce cas, car justement, tu auras besoin de générer toutes les collisions possibles pour trouver la préimage qu'il te faut.
Maintenant, avec une mauvaise fonction de hachage, la distribution ne sera plus uniforme et il y aura plus de risques de collisions dans la zone privilégiée pour les sorties (c'est d'ailleurs un peu comme des urnes avec certaines qui seraient privilégiés par rapport aux autres et donc plus de collisions dans celles qui sont avantagées).
Je pense qu'un moyen de quantifier ce principe est de conduire des tests statistiques sur les sorties, par exemple ceux utilisés pour les générateurs de nombres aléatoires et de tirer des conclusions d'après les biais observés.
Mais si je raméne mon problème en un problème de boules dans une urne
(les boules sont des hashs de l'ensemble des nombre entier inférieure à
2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules
portant le même nombre, plus il est aisé de trouver une boule qui
comporte le même numéro qu'une boule donnée.". Je pense que cette
assertion est vrai, mon problème est de quantifier ce rapport.
Ok, je vois ton idée. A mon avis, cela revient à montrer qu'il y a un
biais dans la distribution des sorties. Si la fonction de hachage
distribue uniformément les sorties, alors ton attaque sur la préimage
aura la complexité maximale de 2^N avec N le nombre de bits dans les
signatures. Trouver une collision ne t'aidera pas dans ce cas, car
justement, tu auras besoin de générer toutes les collisions possibles
pour trouver la préimage qu'il te faut.
Maintenant, avec une mauvaise fonction de hachage, la distribution ne
sera plus uniforme et il y aura plus de risques de collisions dans la
zone privilégiée pour les sorties (c'est d'ailleurs un peu comme des
urnes avec certaines qui seraient privilégiés par rapport aux autres et
donc plus de collisions dans celles qui sont avantagées).
Je pense qu'un moyen de quantifier ce principe est de conduire des tests
statistiques sur les sorties, par exemple ceux utilisés pour les
générateurs de nombres aléatoires et de tirer des conclusions d'après
les biais observés.
Mais si je raméne mon problème en un problème de boules dans une urne (les boules sont des hashs de l'ensemble des nombre entier inférieure à 2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules portant le même nombre, plus il est aisé de trouver une boule qui comporte le même numéro qu'une boule donnée.". Je pense que cette assertion est vrai, mon problème est de quantifier ce rapport.
Ok, je vois ton idée. A mon avis, cela revient à montrer qu'il y a un biais dans la distribution des sorties. Si la fonction de hachage distribue uniformément les sorties, alors ton attaque sur la préimage aura la complexité maximale de 2^N avec N le nombre de bits dans les signatures. Trouver une collision ne t'aidera pas dans ce cas, car justement, tu auras besoin de générer toutes les collisions possibles pour trouver la préimage qu'il te faut.
Maintenant, avec une mauvaise fonction de hachage, la distribution ne sera plus uniforme et il y aura plus de risques de collisions dans la zone privilégiée pour les sorties (c'est d'ailleurs un peu comme des urnes avec certaines qui seraient privilégiés par rapport aux autres et donc plus de collisions dans celles qui sont avantagées).
Je pense qu'un moyen de quantifier ce principe est de conduire des tests statistiques sur les sorties, par exemple ceux utilisés pour les générateurs de nombres aléatoires et de tirer des conclusions d'après les biais observés.
Shal
Mais si je raméne mon problème en un problème de boules dans une urne (les boules sont des hashs de l'ensemble des nombre entier inférieure à 2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules portant le même nombre, plus il est aisé de trouver une boule qui comporte le même numéro qu'une boule donnée.". Je pense que cette assertion est vrai, mon problème est de quantifier ce rapport.
Ok, je vois ton idée. A mon avis, cela revient à montrer qu'il y a un biais dans la distribution des sorties. Si la fonction de hachage distribue uniformément les sorties, alors ton attaque sur la préimage aura la complexité maximale de 2^N avec N le nombre de bits dans les signatures. Trouver une collision ne t'aidera pas dans ce cas, car justement, tu auras besoin de générer toutes les collisions possibles pour trouver la préimage qu'il te faut.
Maintenant, avec une mauvaise fonction de hachage, la distribution ne sera plus uniforme et il y aura plus de risques de collisions dans la zone privilégiée pour les sorties (c'est d'ailleurs un peu comme des urnes avec certaines qui seraient privilégiés par rapport aux autres et donc plus de collisions dans celles qui sont avantagées).
Je pense qu'un moyen de quantifier ce principe est de conduire des tests statistiques sur les sorties, par exemple ceux utilisés pour les générateurs de nombres aléatoires et de tirer des conclusions d'après les biais observés.
C'est tout a fait la demarche que j'essaye d'entreprendre: j'ai une fonction qui dans l'ideal est injective, mais je pense pas qu'elle le soit vraiment. Je veux donc mesurer le biais de cette fonction pour connaître sa resistance aux attaques sur la seconde pré-image. Je pense qu'il est trés difficile de tenter directement cette attaque donc j'essaye de mener à bien l'attaque des collisions pour evaluer le degré de solidité de ma fonction aux attaques sur les secondes pré-image. Si au bout de x semaines de calculs intensifs je n'arrive pas a trouver une seul collision, puis-je supposer que trouver une seconde pré-image mettra des années?
Je pense que ce problème a deja été étudié dans la littérature de la cryptologie, non? existe-t-il une référence?
Merci
Mais si je raméne mon problème en un problème de boules dans une urne
(les boules sont des hashs de l'ensemble des nombre entier inférieure à
2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules
portant le même nombre, plus il est aisé de trouver une boule qui
comporte le même numéro qu'une boule donnée.". Je pense que cette
assertion est vrai, mon problème est de quantifier ce rapport.
Ok, je vois ton idée. A mon avis, cela revient à montrer qu'il y a un
biais dans la distribution des sorties. Si la fonction de hachage
distribue uniformément les sorties, alors ton attaque sur la préimage
aura la complexité maximale de 2^N avec N le nombre de bits dans les
signatures. Trouver une collision ne t'aidera pas dans ce cas, car
justement, tu auras besoin de générer toutes les collisions possibles
pour trouver la préimage qu'il te faut.
Maintenant, avec une mauvaise fonction de hachage, la distribution ne
sera plus uniforme et il y aura plus de risques de collisions dans la
zone privilégiée pour les sorties (c'est d'ailleurs un peu comme des
urnes avec certaines qui seraient privilégiés par rapport aux autres et
donc plus de collisions dans celles qui sont avantagées).
Je pense qu'un moyen de quantifier ce principe est de conduire des tests
statistiques sur les sorties, par exemple ceux utilisés pour les
générateurs de nombres aléatoires et de tirer des conclusions d'après
les biais observés.
C'est tout a fait la demarche que j'essaye d'entreprendre:
j'ai une fonction qui dans l'ideal est injective, mais je pense pas
qu'elle le soit vraiment. Je veux donc mesurer le biais de cette
fonction pour connaître sa resistance aux attaques sur la seconde pré-image.
Je pense qu'il est trés difficile de tenter directement cette attaque
donc j'essaye de mener à bien l'attaque des collisions pour evaluer le
degré de solidité de ma fonction aux attaques sur les secondes pré-image.
Si au bout de x semaines de calculs intensifs je n'arrive pas a trouver
une seul collision, puis-je supposer que trouver une seconde pré-image
mettra des années?
Je pense que ce problème a deja été étudié dans la littérature de la
cryptologie, non? existe-t-il une référence?
Mais si je raméne mon problème en un problème de boules dans une urne (les boules sont des hashs de l'ensemble des nombre entier inférieure à 2^1024 par exemple), on a: "Plus on a de chance d'avoir deux boules portant le même nombre, plus il est aisé de trouver une boule qui comporte le même numéro qu'une boule donnée.". Je pense que cette assertion est vrai, mon problème est de quantifier ce rapport.
Ok, je vois ton idée. A mon avis, cela revient à montrer qu'il y a un biais dans la distribution des sorties. Si la fonction de hachage distribue uniformément les sorties, alors ton attaque sur la préimage aura la complexité maximale de 2^N avec N le nombre de bits dans les signatures. Trouver une collision ne t'aidera pas dans ce cas, car justement, tu auras besoin de générer toutes les collisions possibles pour trouver la préimage qu'il te faut.
Maintenant, avec une mauvaise fonction de hachage, la distribution ne sera plus uniforme et il y aura plus de risques de collisions dans la zone privilégiée pour les sorties (c'est d'ailleurs un peu comme des urnes avec certaines qui seraient privilégiés par rapport aux autres et donc plus de collisions dans celles qui sont avantagées).
Je pense qu'un moyen de quantifier ce principe est de conduire des tests statistiques sur les sorties, par exemple ceux utilisés pour les générateurs de nombres aléatoires et de tirer des conclusions d'après les biais observés.
C'est tout a fait la demarche que j'essaye d'entreprendre: j'ai une fonction qui dans l'ideal est injective, mais je pense pas qu'elle le soit vraiment. Je veux donc mesurer le biais de cette fonction pour connaître sa resistance aux attaques sur la seconde pré-image. Je pense qu'il est trés difficile de tenter directement cette attaque donc j'essaye de mener à bien l'attaque des collisions pour evaluer le degré de solidité de ma fonction aux attaques sur les secondes pré-image. Si au bout de x semaines de calculs intensifs je n'arrive pas a trouver une seul collision, puis-je supposer que trouver une seconde pré-image mettra des années?
Je pense que ce problème a deja été étudié dans la littérature de la cryptologie, non? existe-t-il une référence?
Merci
Kevin Drapel
Si au bout de x semaines de calculs intensifs je n'arrive pas a trouver une seul collision, puis-je supposer que trouver une seconde pré-image mettra des années?
Difficile à dire sans faire une analyse précise des sorties de la fonction de hachage. Avec une fonction idéale, la recherche de collision nécessite de 2^(N/2) opérations alors que la recherche de préimage prend 2^N opérations. Cela dépend aussi de la manière de conduire la recherche de collisions, est-ce que la méthode explore une partie de l'espace (et dans ce cas, on manquerait des zones statistiquement plus faibles) ?
Je pense que ce problème a deja été étudié dans la littérature de la cryptologie, non? existe-t-il une référence?
Sur Google, j'ai trouvé quelques analyses statistiques des fonctions de hachage, par exemple celle de Filiol mais sa démarche a été critiquée dans d'autres papiers
Le papier de Filiol : http://eprint.iacr.org/2002/099/ Et la "contre-expertise" : http://eprint.iacr.org/2002/149.pdf
Un autre document (section 8.5) : http://www.winlab.rutgers.edu/~trappe/Courses/AdvSec05/ChHashFunctions.pdf
Si au bout de x semaines de calculs intensifs je n'arrive pas a trouver
une seul collision, puis-je supposer que trouver une seconde pré-image
mettra des années?
Difficile à dire sans faire une analyse précise des sorties de la
fonction de hachage. Avec une fonction idéale, la recherche de collision
nécessite de 2^(N/2) opérations alors que la recherche de préimage prend
2^N opérations. Cela dépend aussi de la manière de conduire la recherche
de collisions, est-ce que la méthode explore une partie de l'espace (et
dans ce cas, on manquerait des zones statistiquement plus faibles) ?
Je pense que ce problème a deja été étudié dans la littérature de la
cryptologie, non? existe-t-il une référence?
Sur Google, j'ai trouvé quelques analyses statistiques des fonctions de
hachage, par exemple celle de Filiol mais sa démarche a été critiquée
dans d'autres papiers
Le papier de Filiol : http://eprint.iacr.org/2002/099/
Et la "contre-expertise" : http://eprint.iacr.org/2002/149.pdf
Un autre document (section 8.5) :
http://www.winlab.rutgers.edu/~trappe/Courses/AdvSec05/ChHashFunctions.pdf
Si au bout de x semaines de calculs intensifs je n'arrive pas a trouver une seul collision, puis-je supposer que trouver une seconde pré-image mettra des années?
Difficile à dire sans faire une analyse précise des sorties de la fonction de hachage. Avec une fonction idéale, la recherche de collision nécessite de 2^(N/2) opérations alors que la recherche de préimage prend 2^N opérations. Cela dépend aussi de la manière de conduire la recherche de collisions, est-ce que la méthode explore une partie de l'espace (et dans ce cas, on manquerait des zones statistiquement plus faibles) ?
Je pense que ce problème a deja été étudié dans la littérature de la cryptologie, non? existe-t-il une référence?
Sur Google, j'ai trouvé quelques analyses statistiques des fonctions de hachage, par exemple celle de Filiol mais sa démarche a été critiquée dans d'autres papiers
Le papier de Filiol : http://eprint.iacr.org/2002/099/ Et la "contre-expertise" : http://eprint.iacr.org/2002/149.pdf
Un autre document (section 8.5) : http://www.winlab.rutgers.edu/~trappe/Courses/AdvSec05/ChHashFunctions.pdf
