Multi-user collisions: Applications to Discrete Logarithm, Even-Mansour and PRINCE (Full version * )

Abstract : In this paper, we investigate the multi-user setting both in public and in secret-key cryptanalytic applications. In this setting, the adversary tries to recover keys of many users in parallel more efficiently than with classical attacks, i.e., the number of recovered keys multiplied by the time complexity to find a single key, by amortizing the cost among several users. One possible scenario is to recover a single key in a large set of users more efficiently than to recover a key in the classical model. Another possibility is, after some shared precomputation, to be able to learn individual keys very efficiently. This latter model is close to traditional time/memory tradeoff attacks with precompu-tation. With these goals in mind, we introduce two new algorithmic ideas to improve collision-based attacks in the multi-user setting. Both ideas are derived from the paral-lelizable collision search as proposed by van Oorschot and Wiener. This collision search uses precomputed chains obtained by iterating some basic function. In our cryptanalytic application, each pair of merging chains can be used to correlate the key of two distinct users. The first idea is to construct a graph, whose vertices are keys and whose edges are these correlations. When the graph becomes connected, we simultaneously recover all the keys. Thanks to random graph analysis techniques, we can show that the num-ber of edges that are needed to make this event occurs is small enough to obtain some improved attacks. The second idea modifies the basic technique of van Oorschot and Wiener: instead of waiting for two chains to merge, we now require that they become parallel. We first show that, using the first idea alone, we can recover the discrete logarithms of L users in a group of size N in time O(√ N L). We put these two ideas together and we show that in the multi-user Even-Mansour scheme, all the keys of L = N 1/3 users can be found with N 1/3+ queries for each user (where N is the domain size). Finally, we consider the PRINCE block cipher (with 128-bit keys and 64-bit blocks) and find the keys of 2 users among a set of 2 32 users in time 2 65 . We also describe a new generic attack in the classical model for PRINCE.
Type de document :
Communication dans un congrès
Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2014, Kaoshiung, Taiwan. Springer, LNCS 8873, pp.20, ASIACRYPT 2014. 〈http://des.cse.nsysu.edu.tw/asiacrypt2014/〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094051
Contributeur : Pierre-Alain Fouque <>
Soumis le : jeudi 11 décembre 2014 - 15:35:07
Dernière modification le : mercredi 16 mai 2018 - 11:23:34
Document(s) archivé(s) le : jeudi 12 mars 2015 - 10:57:12

Fichier

761.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01094051, version 1

Citation

Pierre-Alain Fouque, Antoine Joux, Chrysanthi Mavromati. Multi-user collisions: Applications to Discrete Logarithm, Even-Mansour and PRINCE (Full version * ). Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2014, Kaoshiung, Taiwan. Springer, LNCS 8873, pp.20, ASIACRYPT 2014. 〈http://des.cse.nsysu.edu.tw/asiacrypt2014/〉. 〈hal-01094051〉

Partager

Métriques

Consultations de la notice

394

Téléchargements de fichiers

213