logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032108(2018) https://doi.org/10.1007/s11432-016-9157-y

Improved meet-in-the-middle attacks on reduced-round Piccolo

More info
  • ReceivedDec 22, 2016
  • AcceptedJun 21, 2017
  • PublishedNov 20, 2017

Abstract

Piccolo is a lightweight block cipher that adopts a generalized Feistel network structure with 4 branches, each of which is 16 bit long. The key length is 80 or 128 bit, denoted by Piccolo-80 and Piccolo-128, respectively. In this paper, we mounted meet-in-the-middle attacks on 14-round Piccolo-80 without pre- and post-whitening keys and 18-round Piccolo-128 with post-whitening keys by exploiting the properties of the key schedule and Maximum Distance Separable (MDS) matrix. For Piccolo-80, we first constructed a 5-round distinguisher. Then 4 rounds and 5 rounds were appended at the beginning and at the end, respectively. Based on this structure, we mounted an attack on 14-round Piccolo-80 from the 5th round to the 18th round. The data, time, and memory complexities were $2^{52}$ chosen plaintexts, $2^{67.44}$ encryptions, and $2^{64.91}$ blocks, respectively. For Piccolo-128, we built a 7-round distinguisher to attack 18-round Piccolo-128 from the 4th round to the 21st round. The data, time, and memory complexities were $2^{52}$ chosen plaintexts, $2^{126.63}$ encryptions, and $2^{125.29}$ blocks, respectively. If not considering results on biclique cryptanalysis, these are currently the best public results on this reduced version of the Piccolo block cipher.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61402288, 61672347, 61772129, 61472250), National Basic Research Program of China (Grant No. 2013CB338004), Shanghai Natural Science Foundation (Grant Nos. 15ZR1400300, 16ZR1401100), Innovation Program of Shanghai Municipal Education Commission (Grant No. 14ZZ066), Opening Project of Shanghai Key Laboratory of Integrated Administration Technologies for Information Security(Grant No. AGK201703). The authors are grateful to Dr. Lei WANG and the reviewers for their valuable suggestions and comments.


References

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

[2] Wu W, Zhang L. LBlock: a lightweight block cipher. In: Applied Cryptography and Network Security-ACNS 2011. Berlin: Springer-Verlag, 2011. 327--344. Google Scholar

[3] Guo J, Peyrin T, Poschmann A, et al. The LED block cipher. In: Cryptographic Hardware and Embedded Systems-CHES 2011. Berlin: Springer-Verlag, 2011. 326--341. Google Scholar

[4] Shibutani K, Isobe T, Hiwatari H, et al. Piccolo: an ultra-lightweight blockcipher. In: Cryptographic Hardware and Embedded Systems-CHES 2011. Berlin: Springer-Verlag, 2011. 342--357. Google Scholar

[5] Suzaki T, Minematsu K, Morioka S, et al. TWINE: a lightweight block cipher for multiple platforms. In: Selected Areas in Cryptography-SAC 2012. Berlin: Springer-Verlag, 2013. 339--354. Google Scholar

[6] Isobe T, Shibutani K. Security analysis of the lightweight block ciphers XTEA, LED and Piccolo. In: Proceedings of Australasian Conference on Information Security and Privacy-ACISP 2012. Berlin: Springer-Verlag, 2012. 71--86. Google Scholar

[7] Minier M. On the security of Piccolo lightweight block cipher against related-key impossible differentials. In: Progress in Cryptology-INDOCRYPT 2013. Berlin: Springer-Verlag, 2013. 308--318. Google Scholar

[8] Azimi S, Ahmadian Z, Mohajeri J, et al. Impossible differential cryptanalysis of Piccolo lightweight block cipher. In: Proceedings of International ISC Conference on Information Security and Cryptology-ISCISC 2014. Piscataway: IEEE, 2014. 89--94. Google Scholar

[9] Huang J L, Lai X J. What is the effective key length for a block cipher: an attack on every practical block cipher. Sci China Inf Sci, 2014, 57: 072110. Google Scholar

[10] Tolba M, Abdelkhalek A, Youssef A M. Meet-in-the-middle attacks on reduced round Piccolo. In: Lightweight Cryptography for Security and Privacy-LightSec 2015. Berlin: Springer-Verlag, 2016. 3--20. Google Scholar

[11] Jeong K, Kang H, Lee C, et al. Biclique cryptanalysis of lightweight block ciphers PRESENT, Piccolo and LED. IACR Cryptology ePrint Archive, 2012, 2012: 621. Google Scholar

[12] Wang Y, Wu W, Yu X. Biclique cryptanalysis of reduced-round Piccolo block cipher. In: Information Security Practice and Experience-ISPEC 2012. Berlin: Springer-Verlag, 2012. 337--352. Google Scholar

[13] Ahmadi S, Ahmadian Z, Mohajeri J, et al. Low-data complexity biclique cryptanalysis of block ciphers with application to Piccolo and HIGHT. IEEE Trans Inf Foren Sec, 2014, 9: 1641--1652. Google Scholar

[14] Jeong K. Cryptanalysis of block cipher Piccolo suitable for cloud computing. J Supercomput, 2013, 66: 829--840. Google Scholar

[15] Song J, Lee K, Lee H. Biclique cryptanalysis on lightweight block cipher: HIGHT and Piccolo. Int J Comput Math, 2013, 90: 2564--2580. Google Scholar

[16] Gong Z, Liu S, Wen Y, et al. Biclique cryptanalysis using balanced complete bipartite subgraphs. Sci China Inf Sci, 2016, 59: 049101. Google Scholar

[17] Biryukov A, Derbez P, Perrin L. Differential analysis and meet-in-the-middle attack against round-reduced TWINE. In: Fast Software Encryption-FSE 2015. Berlin: Springer-Verlag, 2015. 3--27. Google Scholar

[18] Demirci H, Selçuk A A. A meet-in-the-middle attack on 8-round AES. In: Fast Software Encryption-FSE 2008. Berlin: Springer-Verlag, 2008. 116-126. Google Scholar

[19] Chen J, Li L. Low data complexity attack on reduced camellia-256. In: Proceedings of Australasian Conference on Information Security and Privacy-ACISP 2012. Berlin: Springer-Verlag, 2012. 101--114. Google Scholar

[20] Bogdanov A, Rechberger C. A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN. In: Selected Areas in Cryptography-SAC 2010. Berlin: Springer-Verlag, 2011. 229--240. Google Scholar

[21] Jia K, Yu H, Wang X. A meet-in-the-middle attack on the full kasumi. IACR Cryptol ePrint Archive, 2011, 2011: 466. Google Scholar

[22] Aoki K, Sasaki Y. Preimage attacks on one-block MD4, 63-step MD5 and more. In: Selected Areas in Cryptography-SAC 2008. Berlin: Springer-Verlag, 2009. 103--119. Google Scholar

[23] Sasaki Y, Aoki K. Finding preimages in full MD5 faster than exhaustive search. In: Advances in Cryptology-EUROCRYPT 2009. Berlin: Springer-Verlag, 2009. 134--152. Google Scholar

[24] Dunkelman O, Keller N, Shamir A. Improved single-key attacks on 8-round AES-192 and AES-256. In: Advances in Cryptology-ASIACRYPT 2010. Berlin: Springer-Verlag, 2010. 158--176. Google Scholar

[25] Derbez P, Fouque P -A, Jean J. Improved key recovery attacks on reduced-round AES in the single-key setting. In: Advances in Cryptology?CEUROCRYPT 2013. Berlin: Springer-Verlag, 2013. 371--387. Google Scholar

[26] Li L, Jia K, Wang X. Improved single-key attacks on 9-round AES-192/256. In: Fast Software Encryption-FSE 2015. Berlin: Springer-Verlag, 2015. 127--146. Google Scholar

[27] Guo J, Jean J, Nikolic I, et al. Meet-in-the-middle attacks on generic Feistel constructions. In: Advances in Cryptology-ASIACRYPT 2014. Berlin: Springer-Verlag, 2014. 458--477. Google Scholar

[28] Guo J, Yu S. Extended meet-in-the-middle attacks on some Feistel constructions. Design Code Cryptogr, 2016, 80: 587--618. Google Scholar

[29] Guo J, Jean J, Nikolic I, et al. Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions. IACR Transact Symmetric Cryptol, 2017, 2016: 307--337. Google Scholar

  • Figure 1

    The property of the diffusion matrix $M$.

  • Figure 2

    A 5-round distinguisher on Piccolo-80.

  • Figure 3

    Meet-in-the-middle attacks on 14-round Piccolo-80.

  • Figure 4

    A 7-round distinguisher on Piccolo-128.

  • Figure 5

    Meet-in-the-middle attacks on 18-round Piccolo-128.

  •   

    Algorithm 1 Encryption algorithm

    Let $P$ be the plaintext.

    $P=X_{0(64)}=x_{0(16)}\parallel~x_{1(16)}\parallel~x_{2(16)}\parallel~x_{3(16)}$.

    $x_{0(16)}=x_{0(16)}~\oplus~\omega~k_0,~x_{2(16)}=x_{2(16)}~\oplus~\omega~k_1.$

    for $i=0$ to $r-2$

    $y_{0(16)}=x_{0(16)}$, $y_{1(16)}=x_{1(16)}\oplus~F(x_{0(16)})\oplus~rk_{2i}$,$y_{2(16)}=x_{2(16)}$, $y_{3(16)}=x_{3(16)}\oplus~F(x_{2(16)})\oplus~rk_{2i+1}$.

    $x_{0(16)}\parallel~x_{1(16)}\parallel~x_{2(16)}\parallel~x_{3(16)}=RP(y_{0(16)}\parallel~y_{1(16)}\parallel~y_{2(16)}\parallel~y_{3(16)})$.

    end for

    $y_{0(16)}=x_{0(16)}\oplus~wk_2$, $y_{1(16)}=x_{1(16)}\oplus~F(x_{0(16)})\oplus~rk_{2r-2}$, $y_{2(16)}=x_{2(16)}\oplus~wk_3$, $y_{3(16)}=x_{3(16)}\oplus~F(x_{2(16)})\oplus~rk_{2r-1}$.

    $C=y_{0(16)}\parallel~y_{1(16)}\parallel~y_{2(16)}\parallel~y_{3(16)}$.

  •   

    Algorithm 2 Key schedule employed in Piccolo-80

    Require:$K=k_{0(16)}\parallel~k_{1(16)}\parallel~k_{2(16)}\parallel~k_{3(16)}\parallel~k_{4(16)}$.

    Output:$wk_i,~0\leq~i\leq~3$ and $rk_i,~0\leq~i\leq~49$.

    $wk_0=k_0^L\parallel~k_1^R,$ $wk_1=k_1^L\parallel~k_0^R$, $wk_2=k_4^L\parallel~k_3^R,$ $wk_3=k_3^L\parallel~k_4^R$.

    for $i=$ 0 to 24

    end for

  •   

    Algorithm 3 Key schedule employed in Piccolo-128

    Require:$K=k_{0(16)}\parallel~k_{1(16)}\parallel~k_{2(16)}\parallel~k_{3(16)}\parallel~k_{4(16)}\parallel~k_{5(16)}\parallel~k_{6(16)}\parallel~k_{7(16)}$.

    Output:$wk_i,~0\leq~i\leq~3$ and $rk_i,~0\leq~i\leq~61$.

    $wk_0=k_0^L\parallel~k_1^R,$ $wk_1=k_1^L\parallel~k_0^R$, $wk_2=k_4^L\parallel~k_7^R,$ $wk_3=k_7^L\parallel~k_4^R$.

    for $i=$ 0 to 61

    if $(i+2)$ mod 8=0 then

    $(k_0,~k_1,~k_2,~k_3,~k_4,~k_5,~k_6,~k_7)=(k_2,~k_1,~k_6,~k_7,~k_0,~k_3,~k_4,~k_5)$.

    end if

    $rk_i=k_{(i+2)~\mod~8}\oplus~{\rm~con}_i^{128}$.

    end for

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

京ICP备18024590号-1