Paper 2015/507

Decomposing the ASASA Block Cipher Construction

Itai Dinur, Orr Dunkelman, Thorsten Kranz, and Gregor Leander

Abstract

We consider the problem of recovering the internal specification of a general SP-network consisting of three linear layers (A) interleaved with two Sbox layers (S) (denoted by ASASA for short), given only black-box access to the scheme. The decomposition of such general ASASA schemes was first considered at ASIACRYPT 2014 by Biryukov et al. which used the alleged difficulty of this problem to propose several concrete block cipher designs as candidates for white-box cryptography. In this paper, we present several attacks on general ASASA schemes that significantly outperform the analysis of Biryukov et al. As a result, we are able to break all the proposed concrete ASASA constructions with practical complexity. For example, we can decompose an ASASA structure that was supposed to provide $64$-bit security in roughly $2^{28}$ steps, and break the scheme that supposedly provides $128$-bit security in about $2^{41}$ time. Whenever possible, our findings are backed up with experimental verifications.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Block cipherASASAwhite-box cryptographyintegral cryptanalysisdifferential cryptanalysisBoomerang attack
Contact author(s)
thorsten kranz @ rub de
History
2015-05-27: received
Short URL
https://ia.cr/2015/507
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/507,
      author = {Itai Dinur and Orr Dunkelman and Thorsten Kranz and Gregor Leander},
      title = {Decomposing the ASASA Block Cipher Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2015/507},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/507}},
      url = {https://eprint.iacr.org/2015/507}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.