Cryptology ePrint Archive: Report 2013/521

Multiple Limited-Birthday Distinguishers and Applications

Jérémy Jean and María Naya-Plasencia and Thomas Peyrin

Abstract: In this article, we propose a new improvement of the rebound techniques, used for cryptanalyzing AES-like permutations during the past years. Our improvement, that allows to reduce the complexity of the attacks, increases the probability of the outbound part by considering a new type of differential paths. Moreover, we propose a new type of distinguisher, the multiple limited-birthday problem, based on the limited-birthday one, but where differences on the input and on the output might have randomized positions. We also discuss the generic complexity for solving this problem and provide a lower bound of it as well as we propose an efficient and generic algorithm for solving it. Our advances lead to improved distinguishing or collision results for many AES-based functions such as AES, ECHO, Grøstl, LED, PHOTON and Whirlpool.

Category / Keywords: secret-key cryptography / AES-like permutation, distinguishers, limited-birthday, rebound attack

Original Publication (with minor differences): SAC 2013

Date: received 22 Aug 2013

Contact author: thomas peyrin at gmail com

Available format(s): PDF | BibTeX Citation

Note: long version of the SAC 2013 article

Version: 20130830:083506 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]