Considérations Pratiques sur les Compromis Temps-Mémoire Cryptanalytiques

A cryptanalytic time-memory tradeoff (TMTO) is a technique that aims to reduce the time needed to perform a set of cryptanalysis attacks, such as inverting a one-way function. Such an inversion constitutes one of the main applications of TMTOs, which is password cracking. The technique relies on a large-scale pre-computation which outputs tables that allow to significantly speed up the attack’s exhaustive search. The more memory is used by a TMTO, the faster the attack can be. In practice, the amount of memory available is often the limiting factor, so numerous approaches have been proposed to fit large tables in a restricted amount of memory. In this thesis, we focus on the rainbow tables variant, the most widely spread version of timememory trade-offs. When the considered cryptographic problem is overwhelmingly sized, using an external memory is eventually needed. We analyse the relevance of using an external memory instead of RAM, and we state that it is fully suited for practical cases, which are identified. We then introduce a new technique, based on minimal perfect hash functions, whose storage complexity is better than any previous optimisation. Finally, we analyse and compare existing TMTO approaches as well as their combinations, along with our newly introduced MPHF rainbow technique. We are then able to provide a set of practical recommendations on how to configure the implementation of a TMTO in an optimal way.Un compromis temps-mémoire cryptanalytique est une technique qui vise à réduire le temps nécessaire pour effectuer certaines attaques cryptographiques telles que l’inversion d’une fonction à sens unique. Une telle inversion intervient dans une des principales applications des compromis tempsmémoire : le cassage de mots de passe. La technique requiert un très lourd pré-calcul qui génère des tables utilisables pour accélérer la recherche exhaustive de l’attaque. L’attaque par compromis temps-mémoire est d’autant plus rapide qu’il y a de mémoire allouée à l’algorithme. Cependant, en pratique, la mémoire est souvent un facteur limitant. Nous évaluons l’impact d’un problème nécessitant une grande mémoire sur la technique des compromis temps-mémoire, notamment en se plaçant dans le contexte où une mémoire externe lente est utilisée à la place d’une mémoire rapide limitée (RAM). Nous établissons qu’une telle approche est applicable dans des cas pratiques, qui sont identifiés. Nous proposons ensuite une nouvelle construction de compromis temps-mémoire qui repose sur des fonctions de hachage minimales parfaites, et dont le stockage est moindre que sur les techniques de compression de tables existantes. Finalement, nous proposons une comparaison entre les améliorations existantes, possiblement combinées, et notre nouvelle technique