Paper 2019/714

Generalized Related-Key Rectangle Attacks on Block Ciphers with Linear Key Schedule: Applications to SKINNY and GIFT

Boxin Zhao, Xiaoyang Dong, Willi Meier, Keting Jia, and Gaoli Wang


This paper gives a new generalized key-recovery model of related-key rectangle attacks on block ciphers with linear key schedules. The model is quite optimized and applicable to various block ciphers with linear key schedule. As a proof of work, we apply the new model to two very important block ciphers, i.e. SKINNY and GIFT, which are basic modules of many candidates of the Lightweight Cryptography (LWC) standardization project by NIST. For SKINNY, we reduce the complexity of the best previous 27-round related-tweakey rectangle attack on SKINNY-128-384 from $2^{331}$ to $2^{294}$. In addition, the first 28-round related-tweakey rectangle attack on SKINNY-128-384 is given, which gains one more round than before. For the case of GIFT-64, we give the first 24-round related-key rectangle attack with a time complexity $2^{91.58}$, while the best previous attack on GIFT-64 only reaches 23 rounds at most.

Note: 1, Add an open problem in the conclusion section: For LOTUS-AEAD and LOCUS-AEAD \cite{LOTUS}, a Round 2 candidate of the NIST LWC, the designers state that ``the keys are computed by a predictable way in the mode and used with a fixed tweak. This implies that related-key security of TweGIFT-64 matters in the related-key security of the entire construction''. Hence, it is relevant to study GIFT-64 against related-key attack. The attacks in our paper do not cover the concrete impact on LOTUS-AEAD and LOCUS-AEAD. We would like to leave it as an open problem. 2, Remove the cryptanalysis on SKINNY-AEAD, due to error found by Sasaki at lwc-forum:!topic/lwc-forum/kCNjP0q64Bo.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Major revision. Designs, Codes and Cryptography
Key RecoveryRectangle AttackSKINNYGIFTRelated-Key
Contact author(s)
xiaoyangdong @ tsinghua edu cn
boxinzhao @ mail sdu edu cn
willi meier @ fhnw ch
ktjia @ tsinghua edu cn
glwang @ sei ecnu edu cn
2020-03-17: last of 4 revisions
2019-06-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Boxin Zhao and Xiaoyang Dong and Willi Meier and Keting Jia and Gaoli Wang},
      title = {Generalized Related-Key Rectangle Attacks on Block Ciphers with Linear Key Schedule: Applications to SKINNY and GIFT},
      howpublished = {Cryptology ePrint Archive, Paper 2019/714},
      year = {2019},
      doi = {10.1007/s10623-020-00730-1},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.