logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 3: 032108(2019) https://doi.org/10.1007/s11432-018-9527-8

New observation on the key schedule of RECTANGLE

More info
  • ReceivedMay 17, 2018
  • AcceptedJul 16, 2018
  • PublishedJan 29, 2019

Abstract

We evaluate the security of RECTANGLE from the perspective of actual key information (AKI).Insufficient AKI permits the attackers to deduce some subkey bits from some other subkey bits, thereby lowering the overall attack complexity or getting more attacked rounds. By considering the interaction between the key schedule's diffusion and the round function's diffusion, we find there exists AKI insufficiency in 4 consecutive rounds for RECTANGLE-80 and 6 consecutive rounds for RECTANGLE-128, although the master key bits achieve complete diffusion in 2 and 4 rounds, respectively. With such weakness of the key schedule, we give a generic meet-in-the-middle attack on 12-round reduced RECTANGLE-128 with only 8 known plaintexts. Moreover, we calculate AKI of variants of RECTANGLE as well as PRESENT. Surprisingly we find that both RECTANGLE-128 and PRESENT-128 with no key schedule involve more AKI than the original one. Based on this finding, we slightly modify the key schedule of RECTANGLE-128. Compared with the original one, this new key schedule matches better with the round function in terms of maximizing AKI. Our work adds more insight to the design of block ciphers' key schedule.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61702331, 61472251, 61402280, U1536101), China Postdoctoral Science Foundation (Grant No. 2017M621471), National Cryptography Development Fund (Grant No. MMJJ20170105), and Science and Technology on Communication Security Laboratory.


References

[1] Bogdanov A, Knudsen L R, Leander G, et al. PRESENT: an ultra-lightweight block cipher. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2007. 450--466. Google Scholar

[2] Guo J, Peyrin T, Poschmann A. The LED block cipher. In: Proceedings of Cryptographic Hardware and Embedded Systems-CHES 2011, 2011. Google Scholar

[3] Banik S, Bogdanov A, Isobe T, et al. Midori: a block cipher for low energy. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014. 411--436. Google Scholar

[4] Beierle C, Jean J, Kölbl S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Proceedings of Annual Cryptology Conference. Berlin: Springer, 2016. 123--153. Google Scholar

[5] Avanzi R. The QARMA block cipher family. IACR Trans Symmetric Cryptol, 2017, 2017: 4--44. Google Scholar

[6] Banik S, Pandey S K, Peyrin T, et al. GIFT: a small PRESENT. In: Proceedings of International Conference on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2017. 321--345. Google Scholar

[7] Beaulieu R, Treatman-Clark S, Shors D, et al. The SIMON and SPECK lightweight block ciphers. In: Proceedings of the 52nd ACM/EDAC/IEEE Design Automation Conference (DAC), 2015. 1--6. Google Scholar

[8] Wu W, Zhang L. LBlock: a lightweight block cipher. In: Proceedings of International Conference on Applied Cryptography and Network Security. Berlin: Springer, 2011. 327--344. Google Scholar

[9] Suzaki T, Minematsu K, Morioka S, et al. $\textnormal~{\textsc~{TWINE}}~$: a lightweight block cipher for multiple platforms. In: Proceedings of International Conference on Selected Areas in Cryptography. Berlin: Springer, 2012. 339--354. Google Scholar

[10] Hong D, Sung J, Hong S, et al. HIGHT: a new block cipher suitable for low-resource device. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2006. 46--59. Google Scholar

[11] Needham R M, Wheeler D J. Tea Extensions. Report. Cambridge: Cambridge University, 1997. Google Scholar

[12] Knudsen L, Leander G, Poschmann A, et al. PRINTcipher: a block cipher for IC-printing. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2010. 16--32. Google Scholar

[13] Diffie W, Hellman M E. Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer, 1977, 10: 74-84 CrossRef Google Scholar

[14] Huang J, Lai X. Revisiting key schedule's diffusion in relation with round function's diffusion. Des Codes Cryptogr, 2014, 73: 85-103 CrossRef Google Scholar

[15] Huang J, Vaudenay S, Lai X. On the key schedule of lightweight block ciphers. In: Proceedings of International Conference in Cryptology in India. Berlin: Springer, 2014. 124--142. Google Scholar

[16] Lin L, Wu W, Zheng Y. Automatic search for key-bridging technique: applications to LBlock and TWINE. In: Proceedings of International Conference on Fast Software Encryption. Berlin: Springer, 2016. 247--267. Google Scholar

[17] Dunkelman O, Keller N, Shamir A. Improved single-key attacks on 8-round AES-192 and AES-256. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010. 158--176. Google Scholar

[18] Zhang W T, Bao Z Z, Lin D D. RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. Sci China Inf Sci, 2015, 58: 1-15 CrossRef Google Scholar

[19] Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. J Cryptology, 1991, 4: 3-72 CrossRef Google Scholar

[20] Biham E, Biryukov A, Shamir A. Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1999. 12--23. Google Scholar

[21] Matsui M. Linear cryptanalysis method for DES cipher. In: Proceedings of Workshop on the Theory and Application of of Cryptographic Techniques. Berlin: Springer, 1993. 386--397. Google Scholar

[22] Daemen J, Knudsen L, Rijmen V. The block cipher Square. In: Proceedings of International Workshop on Fast Software Encryption. Berlin: Springer, 1997. 149--165. Google Scholar

[23] Knudsen L, Wagner D. Integral cryptanalysis. In: Proceedings of International Workshop on Fast Software Encryption. Berlin: Springer, 2002. 112--127. Google Scholar

[24] Collard B, Standaert F X. A statistical saturation attack against the block cipher PRESENT. In: Proceedings of Cryptographers' Track at the RSA Conference. Berlin: Springer, 2009. 195--210. Google Scholar

[25] Shan J Y, Hu L, Song L, et al. Related-key differential attack on round reduced RECTANGLE-80. IACR Cryptol ePrint Archive, 2014, 2014: 986. Google Scholar

[26] Kosuge H, Tanaka H, Iwai K, et al. Integral attack on reduced-round Rectangle. In: Proceedings of IEEE 2nd International Conference on Cyber Security and Cloud Computing (CSCloud), 2015. 68--73. Google Scholar

[27] Sun L, Wang M. Toward a further understanding of bit-based division property. Sci China Inf Sci, 2017, 60: 128101 CrossRef Google Scholar

[28] Xiang Z, Zhang W, Bao Z, et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2016. 648--678. Google Scholar

[29] Sasaki Y, Todo Y. New impossible differential search tool from design and cryptanalysis aspects. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2017. 185--215. Google Scholar

[30] Zhang W, Bao Z, Rijmen V, et al. A new classification of 4-bit optimal s-boxes and its application to PRESENT, RECTANGLE and SPONGENT. In: Proceedings of International Workshop on Fast Software Encryption. Berlin: Springer, 2015. 494--515. Google Scholar

[31] Stoffelen K. Optimizing s-box implementations for several criteria using SAT solvers. In: Proceedings of International Conference on Fast Software Encryption. Berlin: Springer, 2016. 140--160. Google Scholar

[32] Bao Z, Luo P, Lin D. Bitsliced implementations of the PRINCE, LED and RECTANGLE block ciphers on AVR 8-bit microcontrollers. In: Proceedings of International Conference on Information and Communications Security. Berlin: Springer, 2015. 18--36. Google Scholar

[33] Maene P, Verbauwhede I. Single-cycle implementations of block ciphers. In: Proceedings of International Workshop on Lightweight Cryptography for Security and Privacy. Berlin: Springer, 2015. 131--147. Google Scholar

[34] Feizi S, Nemati A, Ahmadi A, et al. A high-speed FPGA implementation of a Bit-slice Ultra-Lightweight block cipher, RECTANGLE. In: Proceedings of the 5th International Conference on Computer and Knowledge Engineering (ICCKE), 2015. 206--211. Google Scholar

[35] Biryukov A, Derbez P, Perrin L. Differential analysis and meet-in-the-middle attack against round-reduced TWINE. In: Proceedings of International Workshop on Fast Software Encryption. Berlin: Springer, 2015. 3--27. Google Scholar

[36] Bouillaguet C, Derbez P, Fouque P A. Automatic search of attacks on round-reduced AES and applications. In: Proceedings of Annual Cryptology Conference. Berlin: Springer, 2011. 169--187. Google Scholar

  • Figure 1

    (Color online) The round transformation of RECTANGLE, taking the 80-bit version as an example.

  • Figure 4

    (Color online) Main idea of guess-and-determine attacks (a) and MITM attacks (b) on block ciphers.

  • Figure 5

    Cipher8: a toy block cipher with an SPN structure.

  • Figure 6

    (Color online) The reduced sets of key-guessing set in three cases.

  • Figure 7

    (Color online) The ratio of AKI to its theoretical value (on the $y$-axis) on paths of different rounds (on the $x$-axis) for RECTANGLE.

  • Figure 8

    A 3-round path and the corresponding key-guessing set of RECTANGLE-80.

  • Figure 9

    A 6-round forward path and backward path (left) and the corresponding key-guessing set (right) for RECTANGLE-128.

  • Figure 10

    (Color online) A new key schedule proposal for RECTANGLE-128.

  • Figure 11

    (Color online) The generalized Feistel transformation of the original RECTANGLE-128 key schedule (left) and our new key schedule proposal (right).

  •   

    Algorithm 1 Meet-in-the-middle attack on 12-round RECTANGLE-128

    for each possible value of 124 bits for $K^{\prime}_t$

    Deduce the corresponding subkey bits in $K_t$;

    Encrypt $P_i$ to get $X^i_6[0,4,8,12]$, $i=1,\dots,8$;

    Store corresponding key values for $K^{\prime}_t$ in $T_1$ indexed by $X^1_6[0,4,8,12]||\dots||X^8_6[0,4,8,12]$;

    end for

    for each possible value of 124 bits for $K^{\prime}_b$

    Deduce the corresponding subkey bits in $K_b$;

    Decrypt $C_i$ to get $X^i_6[0,4,8,12]$, $i=1,\dots,9$;

    if this $X^1_6[0,4,8,12]||\dots||X^8_6[0,4,8,12]$ exists in $T_1$ then

    Take the corresponding key values for $K^{\prime}_t$ as well as current $K^{\prime}_b$ value as candidate key materials;

    end if

    end for

    Exhaustively search each remaining candidate key.

  • Table 1   Comparison between the least AKI and its theoretical value TKI on different rounds of forward paths for RECTANGLE-80, PRESENT-80, RECTANGLE-128 and PRESENT-128 (Unit: bit)$^{\rm~a)}$
    RECTANGLE-80 PRESENT-80 RECTANGLE-128 PRESENT-128
    TKIAKITKIAKITKIAKITKIAKI
    $r=1$44444444
    $r=2$20 1820 202018 20 20
    $r=3$56 42 80 6456 44 84 77
    $r=4$80 73 80 80120 83 128 125
    $r=5$80 80 128 103 128 128
    $r=6$128 120
    $r=7$128 128

    a) The bold numbers denote the insufficient AKI. Our search aborts when the AKI covers the whole key space.

  • Table 2   Comparison between the least AKI and its theoretical value TKI on different rounds of forward paths for RECTANGLE-128 and its three variants, PRESENT-128 and its variant without key schedule$^{\rm~a)b)}$
    RECTANGLE-128 $T_1$-128$T_2$-128$T_3$-128PRESENT-128P-variant
    TKIAKIAKIAKIAKITKIAKIAKI
    $r=1$44444444
    $r=2$2018202020202020
    $r=3$56 44 525254847780
    $r=4$120 83 68100104128125128
    $r=5$128 103 80128128128128
    $r=6$128 12092
    $r=7$128 128104
    $r=8$128 116
    $r=9$128 125
    $r=10$128 128

    a) $T_1$-128 is RECTANGLE-128 variant with PRESENT-128 key schedule, $T_2$-128 is RECTANGLE-128 variant without key schedule, $T_3$-128 is RECTANGLE-128 variant with our new key schedule proposal. b) The bold numbers denote the insufficient AKI. Our search aborts when the AKI covers the whole key space.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1