A Generic Approach to Invariant Subspace Attacks: Cryptanalysis of Robin, iSCREAM and Zorro

Gregor Leander; Brice Minaud; Sondre Rønjom

Paper 2015/068

A Generic Approach to Invariant Subspace Attacks: Cryptanalysis of Robin, iSCREAM and Zorro

Gregor Leander, Brice Minaud, and Sondre Rønjom

Abstract

Invariant subspace attacks were introduced at CRYPTO 2011 to cryptanalyze PRINTcipher. The invariant subspaces for PRINTcipher were discovered in an ad hoc fashion, leaving a generic technique to discover invariant subspaces in other ciphers as an open problem. Here, based on a rather simple observation, we introduce a generic algorithm to detect invariant subspaces. We apply this algorithm to the CAESAR candidate iSCREAM, the closely related LS-design Robin, as well as the lightweight cipher Zorro. For all three candidates invariant subspaces were detected, and result in practical breaks of the ciphers. A closer analysis of independent interest reveals that these invariant subspaces are underpinned by a new type of self-similarity property. For all ciphers, our strongest attack shows the existence of a weak key set of density $2^{-32}$. These weak keys lead to a simple property on the plaintexts going through the whole encryption process with probability one. All our attacks have been practically verified on reference implementations of the ciphers.

Note: Updated some references.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A minor revision of an IACR publication in EUROCRYPT 2015
Keywords: Cryptanalysis Lightweight Cryptography Invariant Subspace Self-Similarity iSCREAM LS-Designs Zorro CAESAR
Contact author(s): brice minaud @ gmail com
History: 2015-02-02: last of 2 revisions; 2015-01-29: received; See all versions
Short URL: https://ia.cr/2015/068
License: CC BY

BibTeX

@misc{cryptoeprint:2015/068,
      author = {Gregor Leander and Brice Minaud and Sondre Rønjom},
      title = {A Generic Approach to Invariant Subspace Attacks: Cryptanalysis of Robin, {iSCREAM} and Zorro},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/068},
      year = {2015},
      url = {https://eprint.iacr.org/2015/068}
}