Dans la construction des fonctions de hachage universelles, il est demandé certaines propriétés combinatoires plus fortes que de randomizer n'importe comment. Du coup, ça se trouve pas sous le sabot d'un cheval : http://en.wikipedia.org/wiki/Universal_hashing
Plutôt que de saler, comme on dit dans ce forum, la solution propre est la notion de fonction de hachage universelle. C'est très perturbant quand on voit ça la première fois, mais c'est un concept puissant. Voir le Cormen et al, 2nd edition sous-section 11.3.3. Il s'agit d'une famille proprement randomisée de fonctions de hachage, et au départ de l'application, on en choisit une au hasard. Si la famille est bien construite, on évite des comportements de pire cas adverse comme celui décrit ici. Un cas d'école cette attaque.
[^] # Re: C'est dans le Cormen
Posté par DanielAugot . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 1. Dernière modification le 02 janvier 2012 à 15:49.
Dans la construction des fonctions de hachage universelles, il est demandé certaines propriétés combinatoires plus fortes que de randomizer n'importe comment. Du coup, ça se trouve pas sous le sabot d'un cheval : http://en.wikipedia.org/wiki/Universal_hashing
# C'est dans le Cormen
Posté par DanielAugot . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 1.
Plutôt que de saler, comme on dit dans ce forum, la solution propre est la notion de fonction de hachage universelle. C'est très perturbant quand on voit ça la première fois, mais c'est un concept puissant. Voir le Cormen et al, 2nd edition sous-section 11.3.3. Il s'agit d'une famille proprement randomisée de fonctions de hachage, et au départ de l'application, on en choisit une au hasard. Si la famille est bien construite, on évite des comportements de pire cas adverse comme celui décrit ici. Un cas d'école cette attaque.