Compromis temps-mémoire
Les compromis temps-mémoire sont utilisés en cryptanalyse pour récupérer des clés à partir de leur trace chiffrée, en s'appuyant sur des tables précalculées. Cette méthode a été formalisée par Martin Hellman dans son article « A cryptanalytic time-memory trade-off » publié en 1980.
Comme son nom le suggère, cette méthode probabiliste se trouve à mi-chemin entre :
- une recherche exhaustive à la demande (demandant un temps excessif) ;
- et un stockage complet préalable de toutes les solutions possibles en mémoire par un annuaire inverse (demandant une capacité de stockage irréaliste).
La méthode utilise des tables précalculées (souvent plusieurs jours de calcul) pour accélérer considérablement un cassage de clé « à la demande » en fonction des caractéristiques de la clé brouillée.
Améliorations
L'amélioration la plus connue est celle de Philippe Oechslin, en 2003, qui a amélioré le principe pour aboutir à une structure nommée table arc-en-ciel. Sa méthode s'avère très efficace, par exemple, pour récupérer des mots de passe de LAN Manager depuis leur empreinte numérique.
Liens externes
- (en) « A cryptanalytic time-memory trade-off » [PDF] par Martin Hellman
- (fr) « Les compromis temps-mémoire et leur utilisation pour casser les mots de passe Windows » [PDF] par Philippe Oechslin (conférence SSTIC 2004)
Portail de la cryptologie