Paper 2015/1200

Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates

Christoph Dobraunig, Maria Eichlseder, and Florian Mendel


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.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
linear cryptanalysisauthenticated encryptionautomated toolsguess-and-determineCAESAR competition
Contact author(s)
christoph dobraunig @ iaik tugraz at
2017-07-12: revised
2015-12-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christoph Dobraunig and Maria Eichlseder and Florian Mendel},
      title = {Heuristic Tool for Linear Cryptanalysis with Applications to  CAESAR Candidates},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1200},
      year = {2015},
      doi = {10.1007/978-3-662-48800-3_20},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.