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

• AcceptedJul 16, 2018
• PublishedJan 29, 2019
Share
Rating

### 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 TKI AKI TKI AKI TKI AKI TKI AKI $r=1$ 4 4 4 4 4 4 4 4 $r=2$ 20 18 20 20 20 18 20 20 $r=3$ 56 42 80 64 56 44 84 77 $r=4$ 80 73 80 80 120 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$-128 PRESENT-128 P-variant TKI AKI AKI AKI AKI TKI AKI AKI $r=1$ 4 4 4 4 4 4 4 4 $r=2$ 20 18 20 20 20 20 20 20 $r=3$ 56 44 52 52 54 84 77 80 $r=4$ 120 83 68 100 104 128 125 128 $r=5$ 128 103 80 128 128 128 128 – $r=6$ 128 120 92 – – – – – $r=7$ 128 128 104 – – – – – $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.

Citations

Altmetric