Building a BBB Pseudorandom Permutation using Lai-Massey Networks
Authors
Ritam Bhaumik, Mohammad Amin Raeisi
Ritam Bhaumik
Technology Innovation Institute, Abu Dhabi, UAE
bhaumik dot ritam at gmail dot com
bhaumik dot ritam at gmail dot com
Abstract
In spite of being a popular technique for designing block ciphers, Lai-Massey networks have received considerably less attention from a security analysis point of view than Feistel networks and Substitution-Permutation networks. In this paper we study the beyond-birthday-bound (BBB) security of Lai-Massey networks with independent random round functions against chosen-plaintext adversaries. Concretely, we show that five rounds are necessary and sufficient to achieve BBB security.
References
[AV96]
William Aiello and Ramarathnam Venkatesan. Foiling Birthday Attacks in Length-Doubling Transformations - Benes: A Non-Reversible Alternative to Feistel. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, pages 307–320. 1996. Springer. DOI: 10.1007/3-540-68339-9_27
[CS22]
Amit Kumar Chauhan and Somitra Sanadhya. Quantum Security of FOX Construction based on Lai-Massey Scheme. IACR Cryptol. ePrint Arch., 2022.
[FJ14]
Lishi Fu and Chenhui Jin. Practical Security Evaluation against Differential and Linear Cryptanalyses for the Lai-Massey Scheme with an SPS F-function. KSII Trans. Internet Inf. Syst., 8(10):3624–3637, 2014. DOI: 10.3837/TIIS.2014.10.020
[Gra22]
Lorenzo Grassi. On Generalizations of the Lai-Massey Scheme: the Birth of Amaryllises. IACR Cryptol. ePrint Arch., 2022.
[HR10]
Viet Tung Hoang and Phillip Rogaway. On Generalized Feistel Networks. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 613–630. 2010. Springer. DOI: 10.1007/978-3-642-14623-7_33
[IS14]
Takanori Isobe and Kyoji Shibutani. Improved All-Subkeys Recovery Attacks on FOX, KATAN and SHACAL-2 Block Ciphers. In Carlos Cid and Christian Rechberger, editors, Fast Software Encryption - 21st International Workshop, FSE 2014, London, UK, March 3-5, 2014. Revised Selected Papers, volume 8540 of Lecture Notes in Computer Science, pages 104–126. 2014. Springer. DOI: 10.1007/978-3-662-46706-0_6
[JM09]
Pascal Junod and Marco Macchetti. Revisiting the IDEA Philosophy. In Orr Dunkelman, editor, Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, February 22-25, 2009, Revised Selected Papers, volume 5665 of Lecture Notes in Computer Science, pages 277–295. 2009. Springer. DOI: 10.1007/978-3-642-03317-9_17
[JN18]
Ashwin Jha and Mridul Nandi. Applications of H-Technique: Revisiting Symmetric Key Security Analysis. IACR Cryptol. ePrint Arch., 2018.
[JRPV03]
Jorge Nakahara Jr., Vincent Rijmen, Bart Preneel, and Joos Vandewalle. The MESH Block Ciphers. In Kijoon Chae and Moti Yung, editors, Information Security Applications, 4th International Workshop, WISA 2003, Jeju Island, Korea, August 25-27, 2003, Revised Papers, volume 2908 of Lecture Notes in Computer Science, pages 458–473. 2003. Springer. DOI: 10.1007/978-3-540-24591-9_34
[JV04]
Pascal Junod and Serge Vaudenay. FOX : A New Family of Block Ciphers. In Helena Handschuh and M. Anwar Hasan, editors, Selected Areas in Cryptography, 11th International Workshop, SAC 2004, Waterloo, Canada, August 9-10, 2004, Revised Selected Papers, volume 3357 of Lecture Notes in Computer Science, pages 114–129. 2004. Springer. DOI: 10.1007/978-3-540-30564-4_8
[Lai92]
Xuejia Lai. On the design and security of block ciphers. PhD thesis, ETH Zurich, Zürich, Switzerland, 1992.
[LLG10]
Yiyuan Luo, Xuejia Lai, and Zheng Gong. Pseudorandomness analysis of the (extended) Lai-Massey scheme. Inf. Process. Lett., 111(2):90–96, 2010. DOI: 10.1016/J.IPL.2010.10.012
[LLH15]
Yiyuan Luo, Xuejia Lai, and Jing Hu. The Pseudorandomness of Many-Round Lai-Massey Scheme. J. Inf. Sci. Eng., 31(3):1085–1096, 2015.
[LLZ17]
Yiyuan Luo, Xuejia Lai, and Yujie Zhou. Generic attacks on the Lai-Massey scheme. Des. Codes Cryptogr., 83(2):407–423, 2017. DOI: 10.1007/S10623-016-0235-2
[LM90]
Xuejia Lai and James L. Massey. A Proposal for a New Block Encryption Standard. In Ivan Damgård, editor, Advances in Cryptology - EUROCRYPT '90, Workshop on the Theory and Application of of Cryptographic Techniques, Aarhus, Denmark, May 21-24, 1990, Proceedings, volume 473 of Lecture Notes in Computer Science, pages 389–404. 1990. Springer. DOI: 10.1007/3-540-46877-3_35
[LR88]
Michael Luby and Charles Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput., 17(2):373–386, 1988. DOI: 10.1137/0217022
[LYSL13]
Ruilin Li, Jianxiong You, Bing Sun, and Chao Li. Fault analysis study of the block cipher FOX64. Multim. Tools Appl., 63(3):691–708, 2013. DOI: 10.1007/S11042-011-0895-X
[MGWH22]
Shuping Mao, Tingting Guo, Peng Wang, and Lei Hu. Quantum Attacks on Lai-Massey Structure. In Jung Hee Cheon and Thomas Johansson, editors, Post-Quantum Cryptography - 13th International Workshop, PQCrypto 2022, Virtual Event, September 28-30, 2022, Proceedings, volume 13512 of Lecture Notes in Computer Science, pages 205–229. 2022. Springer. DOI: 10.1007/978-3-031-17234-2_11
[Pat91]
Jacques Patarin. New Results on Pseudorandom Permutation Generators Based on the DES Scheme. In Joan Feigenbaum, editor, Advances in Cryptology - CRYPTO '91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1991, Proceedings, volume 576 of Lecture Notes in Computer Science, pages 301–312. 1991. Springer. DOI: 10.1007/3-540-46766-1_25
[Pat98]
Jacques Patarin. About Feistel Schemes with Six (or More) Rounds. In Serge Vaudenay, editor, Fast Software Encryption, 5th International Workshop, FSE '98, Paris, France, March 23-25, 1998, Proceedings, volume 1372 of Lecture Notes in Computer Science, pages 103–121. 1998. Springer. DOI: 10.1007/3-540-69710-1_8
[Pat01]
Jacques Patarin. Generic Attacks on Feistel Schemes. In Colin Boyd, editor, ASIACRYPT 2001, volume 2248 of LNCS, pages 222–238. December 2001. Springer, Heidelberg. DOI: 10.1007/3-540-45682-1_14
[Pat03]
Jacques Patarin. Luby-Rackoff: 7 Rounds Are Enough for 2\({}^{\mbox{n(1-epsilon)}}\)Security. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 513–529. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_30
[Pat04]
Jacques Patarin. Security of Random Feistel Schemes with 5 or More Rounds. In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 106–122. 2004. Springer. DOI: 10.1007/978-3-540-28628-8_7
[Pat08]
Jacques Patarin. The "Coefficients H" Technique. In Roberto Maria Avanzi, Liam Keliher, and Francesco Sica, editors, Selected Areas in Cryptography, 15th International Workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14-15, Revised Selected Papers, volume 5381 of Lecture Notes in Computer Science, pages 328–345. 2008. Springer. DOI: 10.1007/978-3-642-04159-4_21
[PNB06]
Jacques Patarin, Valérie Nachef, and Côme Berbain. Generic Attacks on Unbalanced Feistel Schemes with Contracting Functions. In Xuejia Lai and Kefei Chen, editors, ASIACRYPT 2006, volume 4284 of LNCS, pages 396–411. December 2006. Springer, Heidelberg. DOI: 10.1007/11935230_26
[PNB07]
Jacques Patarin, Valérie Nachef, and Côme Berbain. Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions. In Kaoru Kurosawa, editor, ASIACRYPT 2007, volume 4833 of LNCS, pages 325–341. December 2007. Springer, Heidelberg. DOI: 10.1007/978-3-540-76900-2_20
[SD20]
M. R. Mirzaee Shamsabad and Seyed Mojtaba Dehnavi. Lai-Massey Scheme Revisited. IACR Cryptol. ePrint Arch., 2020.
[SL14]
Shenghui Su and Shuwang Lü. A 128-bit Block Cipher Based on Three Group Arithmetics. IACR Cryptol. ePrint Arch., 2014.
[TP09]
Joana Treger and Jacques Patarin. Generic Attacks on Feistel Networks with Internal Permutations. In Bart Preneel, editor, Progress in Cryptology – AFRICACRYPT 2009, pages 41–59, Berlin, Heidelberg. 2009. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-02384-2_4
[Vau99]
Serge Vaudenay. On the Lai-Massey Scheme. In Kwok-Yan Lam, Eiji Okamoto, and Chaoping Xing, editors, ASIACRYPT'99, volume 1716 of LNCS, pages 8–19. November 1999. Springer, Heidelberg. DOI: 10.1007/978-3-540-48000-6_2
[Vau03]
Serge Vaudenay. Decorrelation: A Theory for Block Cipher Security. J. Cryptol., 16(4):249–286, 2003. DOI: 10.1007/S00145-003-0220-6
[VNP10]
Emmanuel Volte, Valérie Nachef, and Jacques Patarin. Improved Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 94–111. December 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-17373-8_6
[WZF05]
Wenling Wu, Wentao Zhang, and Dengguo Feng. Integral Cryptanalysis of Reduced FOX Block Cipher. In Dongho Won and Seungjoo Kim, editors, Information Security and Cryptology - ICISC 2005, 8th International Conference, Seoul, Korea, December 1-2, 2005, Revised Selected Papers, volume 3935 of Lecture Notes in Computer Science, pages 229–241. 2005. Springer. DOI: 10.1007/11734727_20
[Yil03]
Hamdi Murat Yildirim. Nonlinearity Properties of the Mixing Operations of the Block Cipher IDEA. In Thomas Johansson and Subhamoy Maitra, editors, Progress in Cryptology - INDOCRYPT 2003, 4th International Conference on Cryptology in India, New Delhi, India, December 8-10, 2003, Proceedings, volume 2904 of Lecture Notes in Computer Science, pages 68–81. 2003. Springer. DOI: 10.1007/978-3-540-24582-7_5
[YPL11]
Aaram Yun, Je Hong Park, and Jooyoung Lee. On Lai-Massey and quasi-Feistel ciphers. Des. Codes Cryptogr., 58(1):45–72, 2011. DOI: 10.1007/S10623-010-9386-8
[ZWSW23]
Zhongya Zhang, Wenling Wu, Han Sui, and Bolin Wang. Post-quantum security on the Lai-Massey scheme. Des. Codes Cryptogr., 91(8):2687–2704, 2023. DOI: 10.1007/S10623-023-01225-5
PDF
History
Submitted: 2024-10-08
Accepted: 2024-12-03
Published: 2025-01-13
Accepted: 2024-12-03
Published: 2025-01-13
How to cite
Ritam Bhaumik and Mohammad Amin Raeisi, Building a BBB Pseudorandom Permutation using Lai-Massey Networks. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0wahey6b.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.