Effet avalanche
Cet article concerne la propriété cryptographique. Pour le phénomène intervenant dans un semi-conducteur, voir Effet d'avalanche.
L'effet avalanche, ou effet d'avalanche est une propriété qui est recherchée pour les fonctions de hachage cryptographiques et les algorithmes de chiffrement par bloc : une petite modification de l'entrée doit produire une modification importante en sortie. Par exemple en modifiant 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.
Le terme a été introduit par Horst Feistel mais le concept est très lié à la notion de diffusion due à Claude Shannon sur la diffusion.
Le critère d'avalanche strict est une formalisation précise de l'effet d'avalanche.
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 strict
Le critère d'avalanche strict (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 quand, pour toute modification d'un seul bit en entrée, la probabilité qu'un bit en sortie soit modifiée est de 1/2.
Bibliographie
- (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, , 780 p. (ISBN 0-8493-8523-7, lire en ligne)
