Compromis temps-mémoire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Les compromis temps-mémoire sont utilisés en cryptanalyse pour récupérer des clés à partir de leur trace crypté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 | modifier le code]

L'amélioration la plus connue est celle de Philippe Oechslin, en 2003, qui a optimisé 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 | modifier le code]