Cryptology ePrint Archive: Report 2015/1200

Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates

Christoph Dobraunig and Maria Eichlseder and Florian Mendel

Abstract: Differential and linear cryptanalysis are the general purpose tools to analyze various cryptographic primitives. Both techniques have in common that they rely on the existence of good differential or linear characteristics. The difficulty of finding such characteristics depends on the primitive. For instance, AES is designed to be resistant against differential and linear attacks and therefore, provides upper bounds on the probability of possible linear characteristics. On the other hand, we have primitives like SHA-1, SHA-2, and Keccak, where finding good and useful characteristics is an open problem. This becomes particularly interesting when considering, for example, competitions like CAESAR. In such competitions, many cryptographic primitives are waiting for analysis. Without suitable automatic tools, this is a virtually infeasible job. In recent years, various tools have been introduced to search for characteristics. The majority of these only deal with differential characteristics. In this work, we present a heuristic search tool which is capable of finding linear characteristics even for primitives with a relatively large state, and without a strongly aligned structure. As a proof of concept, we apply the presented tool on the underlying permutations of the first round CAESAR candidates Ascon, Icepole, Keyak, Minalpher and Proest.

Category / Keywords: secret-key cryptography / linear cryptanalysis, authenticated encryption, automated tools, guess-and-determine, CAESAR competition

Original Publication (with major differences): IACR-ASIACRYPT-2015

Date: received 15 Dec 2015

Contact author: christoph dobraunig at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20151218:222005 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]