Cryptology ePrint Archive: Report 2015/068

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

Gregor Leander and 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.

Category / Keywords: secret-key cryptography / Cryptanalysis, Lightweight Cryptography, Invariant Subspace, Self-Similarity, iSCREAM, LS-Designs, Zorro, CAESAR

Original Publication (with minor differences): IACR-EUROCRYPT-2015

Date: received 29 Jan 2015, last revised 2 Feb 2015

Contact author: brice minaud at gmail com

Available format(s): PDF | BibTeX Citation

Note: Updated some references.

Version: 20150202:084930 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]