Information security is usually based on secrets known by authorized parties only, e.g., passwords, PIN codes, and cryptographic keys. Breaking a system means either circumventing the security mechanisms, or exploiting a weakness in these mechanisms, or retrieving the secrets by any other means, including through an exhautive search among all possible secrets. If secrets were long-enough and truly random, the latter attack would not be practical. It is unfortunately very common that real-life secrets do not fulfill these assumptions, meaning that they do not carry enough entropy.
A cryptanalytic time-memory trade-off (TMTO) is a technique introduced by Martin Hellman in 1980 to speed up exhaustive searches using stored precomputations. TMTOs were not efficient in the eighties due to the limited resources of that time’s computers, and they have no longer been considered until Philippe Oechslin resurrected them in 2003 to crack Windows passwords. His contribution was outstanding: he demonstrated his ability to crack any alphanumerical Windows password within a few seconds. Today, TMTOs belong to any security expert’s toolbox, e.g., to perform penetration tests, legal investigations, and to test users’ passwords on the fly when they are requested to refresh their passwords. TMTOs’ impact is not limited to passwords, though, and they have been successfully used to attack for example GSM’s security primitives and vehicule ignition systems.
This thesis aims at improving TMTOs along two axes: improving the precomputation phase using a distributed approach, and applying the technique to the field of data desanonymisation.
Indeed, the main bottleneck of TMTOs is today the precomputation phase, which requires large resources, while most of the precomputations are actually wasted (typically, 96% of the precomputations are eventually thrown away). This offers room for progress. Although there exits a method to make the precomputation phase more efficient, it cannnot be used when considering a distributed precomputation phase, which is yet an unavoidable setup for large-scale TMTOs. We already performed promising experiments on a new way to perform a distributed precomputation phase, and the thesis will formalize and optimize this approach, and discover new approaches.
Then, we would like to highlight that anonymisation of data is commonly achieved by applying a one-way function on the field that identifies the data. It can for example be names, email addresses, mac addresses, etc. Desanonymizing data is then very close from cracking passwords. However, no one attempted yet to apply the TMTO technique for desanonymizing data. We expect to do so in this thesis, which may lead to significant scientific advances and a high societal impact.
Sujet complet avec description scientifique : http://www.avoine.net/download/tmto.pdf
[1] Gildas Avoine, Xavier Carpent, and Cédric Lauradoux. Interleaving cryptanalytic time-memory trade-offs on non-uniform distributions. In Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part I, pages 165–184, 2015.
[2] Gildas Avoine, Pascal Junod, and Philippe Oechslin. Time-memory trade-offs: False alarm detection using checkpoints. In Progress in Cryptology – Indocrypt 2005, volume 3797 of Lecture Notes in Computer Science, pages 183–196, Bangalore, India, December 2005. Cryptology Research Society of India, Springer-Verlag.
[3] Martin Hellman. A cryptanalytic time-memory trade off. IEEE Transactions on Information Theory, IT-26(4):401–406, July 1980.
[4] Philippe Oechslin. Making a faster cryptanalytic time-memory trade-off. In Dan Boneh, editor, Advances in Cryptology – CRYPTO’03, volume 2729 of Lecture Notes in Computer Science, pages 617–630, Santa Barbara, California, USA, August 2003. IACR, Springer-Verlag.
[5] Philippe Oechslin. http://ophcrack.sourceforge.net/, Last Access: January 2020.