{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T11:18:45Z","timestamp":1767611925549,"version":"3.37.3"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T00:00:00Z","timestamp":1647475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62122085","61872359","61936008","2020YFB1805402"],"award-info":[{"award-number":["62122085","61872359","61936008","2020YFB1805402"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The fast correlation attack (FCA) is one of the most important cryptanalytic techniques against LFSR-based stream ciphers. In CRYPTO 2018, Todo et al. found a new property for the FCA and proposed a novel algorithm which was successfully applied to the Grain family of stream ciphers. Nevertheless, these techniques cannot be directly applied to Grain-like small state stream ciphers with keyed update, such as Plantlet, Fruit-v2 and Fruit80. In this paper, we study the security of Grain-like small state stream ciphers by the FCA. We first observe that the number of required parity-check equations can be reduced when there are multiple different parity-check equations. With exploiting the Skellam distribution, we introduce a sufficient condition to identify the correct LFSR initial state and derive a new relationship between the number and bias of the required parity-check equations. Then, a modified algorithm is presented based on this new relationship, which can recover the LFSR initial state no matter what the round key bits are. Under the condition that the LFSR initial state is known, an algorithm is given against the degraded system and to recover the NFSR state at some time instant, along with the round key bits. As cases study, we apply our cryptanalytic techniques to Plantlet, Fruit-v2 and Fruit-80. As a result, for Plantlet, our attack takes $ 2^{73.75} $ time complexity and $ 2^{73.06} $ keystream bits to recover the full 80-bit key. Regarding Fruit-v2, $ 2^{55.34} $ time complexity and $ 2^{55.62} $ keystream bits are needed to determine the secret key. As for Fruit-80, $2^{64.47}$ time complexity and $2^{62.82}$ keystream bits are required to recover the secret key. More flexible attacks can be obtained with lower data complexity at the cost of increasing the attack time. Especially, for Fruit-v2, a key recovery attack can be launched with data complexity of $2^{42.38}$ and time complexity of $2^{73.31}$. Moreover, we have implemented our attack methods on a toy version of Fruit-v2. The attack matches the expected complexities predicted by our theoretical analysis quite well, which proves the validity of our cryptanalytic techniques.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac016","type":"journal-article","created":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T12:12:11Z","timestamp":1645531931000},"page":"1376-1399","source":"Crossref","is-referenced-by-count":4,"title":["On Grain-Like Small State Stream Ciphers Against Fast Correlation Attacks: Cryptanalysis of Plantlet, Fruit-v2 and Fruit-80"],"prefix":"10.1093","volume":"66","author":[{"given":"Shichang","family":"Wang","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Security , Institute of Information Engineering, Chinese Academy of Sciences, 89 Minzhuang Road, Haidian District, Beijing 10093 , China"},{"name":"School of Cyber Security , University of Chinese Academy of Sciences, No.19 (A), Yuquan Road, Shijingshan District, Beijing 100049 , China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meicheng","family":"Liu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security , Institute of Information Engineering, Chinese Academy of Sciences, 89 Minzhuang Road, Haidian District, Beijing 10093 , China"},{"name":"School of Cyber Security , University of Chinese Academy of Sciences, No.19 (A), Yuquan Road, Shijingshan District, Beijing 100049 , China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongdai","family":"Lin","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security , Institute of Information Engineering, Chinese Academy of Sciences, 89 Minzhuang Road, Haidian District, Beijing 10093 , China"},{"name":"School of Cyber Security , University of Chinese Academy of Sciences, No.19 (A), Yuquan Road, Shijingshan District, Beijing 100049 , China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Ma","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security , Institute of Information Engineering, Chinese Academy of Sciences, 89 Minzhuang Road, Haidian District, Beijing 10093 , China"},{"name":"School of Cyber Security , University of Chinese Academy of Sciences, No.19 (A), Yuquan Road, Shijingshan District, Beijing 100049 , China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,3,17]]},"reference":[{"key":"2023062010043638500_ref1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1504\/IJWMC.2007.013798","article-title":"Grain: a stream cipher for constrained environments","volume":"2","author":"Hell","year":"2007","journal-title":"Int. J. Wirel. Mob. Comput."},{"key":"2023062010043638500_ref2","first-page":"171","volume-title":"Information Security, 9th Int. Conf., ISC 2006, Samos Island, Greece, August 30 - September 2, 2006, Proc.","author":"Canni\u00e8re","year":"2006"},{"key":"2023062010043638500_ref3","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1504\/IJWMC.2011.044106","article-title":"Grain-128a: a new version of grain-128 with optional authentication","volume":"5","author":"\u00c5gren","year":"2011","journal-title":"Int. J. Wirel. Mob. Comput."},{"key":"2023062010043638500_ref4","first-page":"1","volume-title":"Advances in Cryptology - ASIACRYPT 2000, 6th Int. Conf. on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3\u20137, 2000, Proc","author":"Biryukov","year":"2000"},{"key":"2023062010043638500_ref5","first-page":"451","volume-title":"Fast Software Encryption - 22nd Int. Workshop, FSE 2015, Istanbul, Turkey, March 8\u201311, 2015, Revised Selected Papers","author":"Armknecht","year":"2015"},{"key":"2023062010043638500_ref6","first-page":"663","volume-title":"Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conf., Santa Barbara, CA, USA, August 16\u201320, 2015, Proc., Part I","author":"Lallemand","year":"2015"},{"key":"2023062010043638500_ref7","first-page":"561","volume-title":"Advances in Cryptology - ASIACRYPT 2015 - 21st Int. Conf. on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29\u2013December 3, 2015, Proc., Part II","author":"Zhang","year":"2015"},{"key":"2023062010043638500_ref8","first-page":"124","volume-title":"Progress in Cryptology - INDOCRYPT 2015 - 16th Int. Conf. on Cryptology in India, Bangalore, India, December 6\u20139, 2015, Proc.","author":"Banik","year":"2015"},{"key":"2023062010043638500_ref9","first-page":"67","volume-title":"Selected Areas in Cryptography - SAC 2015 - 22nd Int. Conf., Sackville, NB, Canada, August 12\u201314, 2015, Revised Selected Papers","author":"Esgin","year":"2015"},{"key":"2023062010043638500_ref10","first-page":"52","article-title":"On ciphers that continuously access the non-volatile key","volume":"2016","author":"Mikhalev","year":"2016","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2023062010043638500_ref11","article-title":"Fruit-v2: Ultra-lightweight stream cipher with shorter internal state","author":"Vahid Amin Ghafari","year":"2016","journal-title":"Cryptology ePrint Archive"},{"key":"2023062010043638500_ref12","doi-asserted-by":"crossref","first-page":"180","DOI":"10.3390\/e20030180","article-title":"Fruit-80: a secure ultra-lightweight stream cipher for constrained environments","volume":"20","author":"Ghafari","year":"2018","journal-title":"Entropy"},{"key":"2023062010043638500_ref13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.46586\/tosc.v2017.i1.45-79","article-title":"LIZARD - A lightweight stream cipher for power-constrained devices","volume":"2017","author":"Hamann","year":"2017","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2023062010043638500_ref14","doi-asserted-by":"crossref","first-page":"58","DOI":"10.46586\/tosc.v2017.i4.58-81","article-title":"Fast correlation attacks on grain-like small state stream ciphers","volume":"2017","author":"Zhang","year":"2017","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2023062010043638500_ref15","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1007\/s12095-017-0261-6","article-title":"Design and analysis of small-state grain-like stream ciphers","volume":"10","author":"Hamann","year":"2018","journal-title":"Cryptogr. Commun."},{"key":"2023062010043638500_ref16","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/TC.1985.1676518","article-title":"Decrypting a class of stream ciphers using ciphertext only","volume":"34","author":"Siegenthaler","year":"1985","journal-title":"IEEE Trans. Computers"},{"key":"2023062010043638500_ref17","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF02252874","article-title":"Fast correlation attacks on certain stream ciphers","volume":"1","author":"Meier","year":"1989","journal-title":"J. Cryptol."},{"key":"2023062010043638500_ref18","first-page":"347","volume-title":"Advances in Cryptology - EUROCRYPT \u201899, Int. Conf. on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2\u20136, 1999, Proc.","author":"Johansson","year":"1999"},{"key":"2023062010043638500_ref19","first-page":"573","volume-title":"Advances in Cryptology - EUROCRYPT 2000, Int. Conf. on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14\u201318, 2000, Proc.","author":"Canteaut","year":"2000"},{"key":"2023062010043638500_ref20","first-page":"181","volume-title":"Fast Software Encryption, 7th Int. Workshop, FSE 2000, New York, NY, USA, April 10\u201312, 2000, Proc.","author":"Chepyzhov","year":"2000"},{"key":"2023062010043638500_ref21","first-page":"300","volume-title":"Advances in Cryptology - CRYPTO 2000, 20th Annual Int. Cryptology Conf., Santa Barbara, California, USA, August 20\u201324, 2000, Proc.","author":"Johansson","year":"2000"},{"key":"2023062010043638500_ref22","first-page":"196","volume-title":"Fast Software Encryption, 8th Int. Workshop, FSE 2001 Yokohama, Japan, April 2\u20134, 2001, Revised Papers","author":"Mihaljevic","year":"2001"},{"key":"2023062010043638500_ref23","first-page":"15","volume-title":"Fast Software Encryption, 13th Int. Workshop, FSE 2006, Graz, Austria, March 15\u201317, 2006, Revised Selected Papers","author":"Berbain","year":"2006"},{"key":"2023062010043638500_ref24","first-page":"129","volume-title":"Advances in Cryptology - CRYPTO 2018 - 38th Annual Int. Cryptology Conf., Santa Barbara, CA, USA, August 19\u201323, 2018, Proc., Part II","author":"Todo","year":"2018"},{"key":"2023062010043638500_ref25","first-page":"209","volume-title":"Advances in Cryptology - EUROCRYPT 2002, Int. Conf. on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28\u2013May 2, 2002, Proc.","author":"Chose","year":"2002"},{"key":"2023062010043638500_ref26","first-page":"234","volume-title":"Selected Areas in Cryptography, 13th Int. Workshop, SAC 2006, Montreal, Canada, August 17\u201318, 2006 Revised Selected Papers","author":"Zhang","year":"2006"},{"key":"2023062010043638500_ref27","article-title":"Fast correlation attacks on grain-like small state stream ciphers and cryptanalysis of plantlet, Fruit-v2 and fruit-80","author":"Wang","year":"2019","journal-title":"Cryptology ePrint Archive"},{"key":"2023062010043638500_ref28","first-page":"365","volume-title":"Selected Areas in Cryptography - SAC 2019 - 26th Int. Conf., Waterloo, ON, Canada, August 12\u201316, 2019, Revised Selected Papers","author":"Todo","year":"2019"},{"key":"2023062010043638500_ref29","doi-asserted-by":"crossref","first-page":"103","DOI":"10.46586\/tosc.v2019.i3.103-120","article-title":"Cryptanalysis of plantlet","volume":"2019","author":"Banik","year":"2019","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2023062010043638500_ref30","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s10623-018-0533-y","article-title":"Some results on fruit","volume":"87","author":"Dey","year":"2019","journal-title":"Des. Codes Cryptogr."},{"key":"2023062010043638500_ref31","article-title":"Cryptanalysis of full round fruit","author":"Dey","year":"2017","journal-title":"Cryptology ePrint Archive"},{"key":"2023062010043638500_ref32","first-page":"184","volume-title":"Selected Areas in Cryptography, 15th Int. Workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14\u201315, Revised Selected Papers","author":"Berbain","year":"2008"},{"key":"2023062010043638500_ref33","first-page":"386","volume-title":"Advances in Cryptology - EUROCRYPT \u201893, Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23\u201327, 1993, Proc.","author":"Matsui","year":"1993"},{"key":"2023062010043638500_ref34","first-page":"1426","volume-title":"Advanced Information Networking and Applications \u2013 Proc. of the 34th Int. Conf. on Advanced Information Networking and Applications, AINA-2020, Caserta, Italy, 15\u201317 April","author":"Zhang","year":"2020"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/6\/1376\/50643544\/bxac016.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/6\/1376\/50643544\/bxac016.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T10:06:08Z","timestamp":1687255568000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/6\/1376\/6549846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,17]]},"references-count":34,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,3,17]]},"published-print":{"date-parts":[[2023,6,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac016","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,6]]},"published":{"date-parts":[[2022,3,17]]}}}