logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 7: 072101(2017) https://doi.org/10.1007/s11432-016-0165-6

A distinguisher on PRESENT-like permutations with application to SPONGENT

More info
  • ReceivedMar 10, 2016
  • AcceptedAug 12, 2016
  • PublishedJan 20, 2017

Abstract

At Crypto 2015, Blondeau et al. showed a known-key analysis on the full texttt{PRESENT} lightweight block cipher. Based on some of the best differential distinguishers, they introduced a meet in the middle (MitM) layer to pre-add the differential distinguisher, which extends the number of attacked rounds on texttt{PRESENT} from 26 rounds to full rounds without reducing differential probability. %They first started from some of the best differential distinguishers, and then introduced a meet-in-the-middle (MitM) layer to extend the number of attacked rounds without differential probability, which finally gave a known-key distinguisher on the full texttt{PRESENT} for both 80- and 128-bit secret key versions. %In their attack, the MitM layer was the key step to extend the attacked rounds, but their method only dealt with the ciphers with a power of 2-bit internal state. In this paper, we generalize their method and present a distinguisher on a kind of permutations called texttt{PRESENT}-like permutations. This generic distinguisher is divided into two phases. The first phase is a truncated differential distinguisher with strong bias, which describes the unbalance of the output collision on some fixed bits, given the fixed input in some bits, and we take advantage of the strong relation between truncated differential probability and capacity of multidimensional linear approximation to derive the best differential distinguishers. The second phase is the meet-in-the-middle layer, which is pre-added to the truncated differential to propagate the differential properties as far as possible. Different with Blondeau et al.'s work, we extend the MitM layers on a 64-bit internal state to states with any size, and we also give a concrete bound to estimate the attacked rounds of the MitM layer. As an illustration, we apply our technique to all versions of texttt{SPONGENT} permutations. In the truncated differential phase, as a result we reach one, two or three rounds more than the results shown by the designers. In the meet-in-the-middle phase, we get up to 11 rounds to pre-add to the differential distinguishers. Totally, we improve the previous distinguishers on all versions of texttt{SPONGENT} permutations by up to 13 rounds.


Funded by

National Basic Research Program of China(973 Program)

National Natural Science Foundation of China(61602276)

National Natural Science Foundation of China(61133013)

"source" : null , "contract" : "2013CB834205"

National Natural Science Foundation of China(61303258)

National Natural Science Foundation of China(61672516)

National Natural Science Foundation of China(61572293)

Strategic Priority Research Program of the Chinese Academy of Sciences(XDA06010701)

Program for New Century Excellent Talents in University of China(NCET-13-0350)


Acknowledgment

Acknowledgments

This work was supported by National Basic Research Program of China (973 Program) (Grant No. 2013CB834205), National Natural Science Foundation of China (Grant Nos. 61602276, 61672516, 61303258, 61133013, 61572293), Strategic Priority Research Program of the Chinese Academy of Sciences (Grant No. XDA06010701), and Program for New Century Excellent Talents in University of China (Grant No. NCET-13-0350). The authors are grateful to Lei WANG for inspiring this work and many helpful suggestions. The authors would also like to thank Jérémy JEAN for providing TikZ code of texttt{PRESENT} block cipher cite{Jean15}.


References

[1] de Cannere C. Trivium: a stream cipher construction inspired by block cipher design principles. Inf Secur, 2006, 4176: 171-186 CrossRef Google Scholar

[2] Hell M, Johansson T, Maximov A, et al. The grain family of stream ciphers. In: New Stream Cipher Designs. Berlin: Spring-Verlag, 2008. 4986: 179--190. Google Scholar

[3] de Canniere C, Dunkelman O, Kne{v{z}}evi{ć} M. KATAN and KTANTAN --- a family of small and efficient hardware-oriented block ciphers. In: Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems, Lausanne, 2009. 272--288. Google Scholar

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

[5] Guo J, Peyrin T, Poschmann A, et al. The LED block cipher. In: Proceedings of International Conference on Cryptographic Hardware Embedded Systems. Berlin: Spring-Verlag, 2011. 326--341. Google Scholar

[6] Aumasson J P, Henzen L, Meier W, et al. Quark: a lightweight hash. J Cryptol, 2010, 26: 1-15 Google Scholar

[7] Bogdanov A, Knezevic M, Leander G, et al. SPONGENT: a lightweight hash function. In: Proceedings of International Conference on Cryptographic Hardware Embedded Systems. Berlin: Spring-Verlag, 2011. 312--325. Google Scholar

[8] Bogdanov A, Knezevic M, Leander G, et al. SPONGENT: the design space of lightweight cryptographic hashing. IEEE Trans Comput, 2013, 62: 2041-2053 CrossRef Google Scholar

[9] Guo J, Peyrin T, Poschmann A. The PHOTON family of lightweight hash functions. In: Advances in Cryptology-CRYPTO 2011. Berlin: Spring-Verlag, 2011. 222--239. Google Scholar

[10] Borghoff J, Knudsen L R, Leander G, et al. Cryptanalysis of PRESENT-like ciphers with secret S-boxes. In: Fast Software Encryption-FSE 2011. Berlin: Spring-Verlag, 2011. 270--289. Google Scholar

[11] Lauridsen M M, Rechberger C. Linear distinguishers in the key-less setting: application to PRESENT. In: Fast Software Encryption-FSE 2015. Berlin: Spring-Verlag, 2015. 217--240. Google Scholar

[12] Abdelraheem M A. Estimating the probabilities of low-weight differential and linear approximations on PRESENT-like ciphers. In: Information Security and Cryptology-ICISC 2012. Berlin: Spring-Verlag, 2012. 368--382. Google Scholar

[13] Bulygin S. More on linear hulls of PRESENT-like ciphers and a cryptanalysis of full-round EPCBC--96. Cryptology ePrint Archive, Report 2013/028. http://eprint.iacr.org/2013/028.pdf. Google Scholar

[14] Nikolic I, Wang L, Wu S. Cryptanalysis of round-reduced LED. In: Fast Software Encryption-FSE 2013. Berlin: Spring-Verlag, 2013. 112--129. Google Scholar

[15] Blondeau C, Peyrin T, Wang L. Known-key distinguisher on full PRESENT. In: Advances in Cryptology-CRYPTO 2015. Berlin: Spring-Verlag, 2015. 455--474. Google Scholar

[16] ISO/IEC . Information technology --- Security techniques --- Lightweight cryptography --- Part 2: Block ciphers. ISO/IEC, 2012, 29192-2: 2012-2053 Google Scholar

[17] Cheng H, Heys H M, Wang C. PUFFIN: a novel compact block cipher targeted to embedded digital systems. In: Proceedings of the 11th EUROMICRO Conference on Digital System Design Architectures, Methods and Tools. Washington: IEEE Computer Society, 2008. 383--390. Google Scholar

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

[19] Gomathisankaran M, Lee R B. Maya: a novel block encryption function. In: Proceedings of International Workshop on Coding and Cryptography, Ullensvang, 2009. Google Scholar

[20] Yap H, Khoo K, Poschmann A, et al. EPCBC-a block cipher suitable for electronic product code encryption. In: Proceedings of the 10th International Conference on Cryptology and Network Security, Sanya, 2011. 76--97. Google Scholar

[21] Zhang W, Bao Z, Lin D, et al. RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. Sci China Inf Sci, 2015, 58: 122103-2053 Google Scholar

[22] ISO/IEC . Information technology --- Security techniques --- Lightweight cryptography --- Part 5: Hash-functions. ISO/IEC DIS, 2015, 29192-5: 2015-2053 Google Scholar

[23] Cho J Y. Linear cryptanalysis of reduced-round PRESENT. In: Topics in Cryptology-CT-RSA 2010. Berlin: Springer-Verlag, 2010. 302--317. Google Scholar

[24] Blondeau C, Nyberg K. Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities. In: Advances in Cryptology-EUROCRYPT 2014. Berlin: Springer-Verlag, 2014. 165--182. Google Scholar

[25] Bertoni G, Daemen J, Peeters M, et al. Sponge-based pseudo-random number generators. In: Proceedings of the 12th International Conference on Cryptographic Hardware and Embedded Systems, Santa Barbara, 2010. 33--47. Google Scholar

[26] Bertoni G, Daemen J, Peeters M, et al. On the Indifferentiability of the Sponge Construction. In: Advances in Cryptology-EUROCRYPT 2008. Berlin: Springer-Verlag, 2008. 181--197. Google Scholar

[27] Bao Z Z, Zhang W T, Lin D D. Speeding up the search algorithm for the best differential and best linear trails. In: Information Security and Cryptology-ICISC 2014. Berlin: Springer-Verlag, 2014. 259--285. Google Scholar

[28] Knudsen L R. Truncated and higher order differentials. In: Fast Software Encryption-FSE 2015. Berlin: Springer-Verlag, 1995. 196--211. Google Scholar

[29] Jean J. TikZ for Cryptographers. Asiacrypt 2015 Rump Session, 2015. http://www.di.ens.fr/${sim}$jean/latex_crypto/. Google Scholar

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

京ICP备18024590号-1