Cet article concerne la propriété cryptographique. Pour le phénomène intervenant dans un semi-conducteur, voir Effet d'avalanche.
L'effet avalanche est une propriété recherchée dans les fonctions de hachage cryptographiques et les algorithmes de chiffrement par bloc. Elle provoque des modifications de plus en plus importantes au fur et à mesure que les données se propagent dans la structure de l'algorithme. De ce fait, en perturbant un seul bit en entrée, on obtient idéalement une sortie totalement différente, (soit environ 1 bit sur deux de changé) d'où le nom de ce phénomène. L'effet avalanche permet de rendre l'inversion de la fonction plus difficile grâce à ses propriétés chaotiques (s'il est bien conçu).
Le terme a été inventé par Horst Feistel mais le concept remonte à la théorie de Shannon sur la diffusion. En 1985, le concept se voit précisé avec le « critère d'avalanche stricte ».
Motivations
La diffusion des modifications sur les entrées est très importante. Si ce n'est pas le cas et que les sorties présentent un biais statistique, il serait possible d'établir des prédictions sur les entrées à partir de l'observation des sorties. L'effet avalanche est donc recherché lors de la conception d'une primitive de chiffrement. Pour ces raisons, la plupart des chiffrements par bloc utilisent le produit de plusieurs sous-chiffrements. Les fonctions de hachage emploient des blocs de grande taille pour faciliter la diffusion.
Critère d'avalanche stricte
Le critère d'avalanche stricte (Strict Avalanche Criterion) est une propriété des fonctions booléennes utilisées en cryptographie. Il a été introduit par Webster et Tavares en 1985. Une fonction satisfait ce critère si pour toute inversion d'un seul bit en entrée alors chaque bit en sortie a une chance sur deux d'être modifié. L'uniformisation des sorties a pour but d'empêcher les prédictions dues à un biais statistique.
