Interleaving Cryptanalytic Time-memory Trade-offs on Non-Uniform Distributions

Abstract : Cryptanalytic time-memory trade-offs (TMTO) are well-known tools available in any security expert toolbox. They have been used to break ciphers such as A5/1, but their efficiency to crack passwords made them even more popular in the security community. While symmetric keys are generated randomly according to a uniform distribution, pass- words chosen by users are in practice far from being random, as con- firmed by recent leakage of databases. Unfortunately, the technique used to build TMTOs is not appropriate to deal with non-uniform distribu- tions. In this paper, we introduce an efficient construction that consists in partitioning the search set into subsets of close densities, and a strategy to explore the TMTOs associated to the subsets based on an interleaved traversal. This approach results in a significant improvement compared to currently used TMTOs. We experimented our approach on a classical problem, namely cracking 7-character NTLM Hash passwords using an alphabet with 34 special characters, which resulted in a 16 × speedup over rainbow tables, which are considered as the most efficient variant of time-memory trade-offs.
Type de document :
Communication dans un congrès
European Symposium on Research in Computer Security - ESORICS 2015, Sep 2015, Vienna, Austria. 9326 et 9327, 2015, LNCS
Liste complète des métadonnées

https://hal.inria.fr/hal-01199151
Contributeur : Cédric Lauradoux <>
Soumis le : mardi 15 septembre 2015 - 08:08:01
Dernière modification le : vendredi 1 décembre 2017 - 01:22:27

Identifiants

  • HAL Id : hal-01199151, version 1

Citation

Gildas Avoine, Xavier Carpent, Cédric Lauradoux. Interleaving Cryptanalytic Time-memory Trade-offs on Non-Uniform Distributions. European Symposium on Research in Computer Security - ESORICS 2015, Sep 2015, Vienna, Austria. 9326 et 9327, 2015, LNCS. 〈hal-01199151〉

Partager

Métriques

Consultations de la notice

356