Cryptology ePrint Archive: Report 2014/228

Improved Analysis of Zorro-Like Ciphers

Achiya Bar-On and Itai Dinur and Orr Dunkelman and Virginie Lallemand and Boaz Tsaban

Abstract: Zorro is a 128-bit lightweight block cipher supporting 128-bit keys, presented at CHES~2013 by G\'erard et al. One of the main design goals of the cipher was to allow efficient masking, which is a common way to protect against side-channel attacks. This led to a very unconventional design, which resembles AES, but uses only partial non-linear layers. Despite the security claims of the designers, the cipher was recently broken by differential and linear attacks due to Wang et al., recovering its 128-bit key with complexity of about $2^{108}$. These attacks are based on high-probability iterative characteristics that are made possible due to a special property of the linear layer of Zorro, which is shown to be devastating in combination with its partial non-linear layer.

In this paper, we analyze the security of Zorro-like ciphers with partial non-linear layers by devising differential and linear characteristic search algorithms and key recovery algorithms. These algorithms exploit in a generic way the small number of Sboxes in a Zorro-like round, and are independent of any specific property of its linear layer (such as the one exploited by Wang et al.), or its Sbox implementation. When applied to the Zorro block cipher itself, we were able to find \emph{the highest} probability characteristics for the full cipher and devise significantly improved attacks. Our differential attack has a time complexity of about $2^{45}$, requiring about $2^{41.5}$ chosen plaintexts, and our linear attack has a time complexity of about $2^{45}$, requiring about $2^{45}$ known plaintexts.

Independently of our results, the recently published paper by Rasoolzadeh et al. found similar iterative characteristics for Zorro by exploiting in a different way the devastating property of its linear layer, described by Wang et al. However, our improved key recovery techniques result in differential and linear attacks which are at least $2^{11}$ times faster. More significantly, the surprisingly large number of Zorro-like rounds analyzed by some of our generic techniques raises questions over the general design strategy of Zorro, namely, the use of partial non-linear layers.

Category / Keywords: secret-key cryptography / Block cipher, lightweight, Zorro, cryptanalysis, differential attack, linear attack.

Date: received 29 Mar 2014, last revised 1 Apr 2014

Contact author: dinur at di ens fr

Available format(s): PDF | BibTeX Citation

Note: Small corrections and optimizations.

Version: 20140401:213031 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]