Compromis temps-mémoire
Cet article est une ébauche concernant la cryptologie.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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 modifier
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 modifier
- (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)
