{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:29:24Z","timestamp":1740180564293,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,8]],"date-time":"2023-10-08T00:00:00Z","timestamp":1696723200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,8]],"date-time":"2023-10-08T00:00:00Z","timestamp":1696723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62022036","62132008"],"award-info":[{"award-number":["62022036","62132008"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Small-state stream ciphers (SSCs), which violate the principle that the state size should exceed the key size by a factor of two, still demonstrate robust security properties while maintaining a lightweight design. These ciphers can be classified into several constructions and their basic security requirement is to resist generic attacks, i.e., the time\u2013memory\u2013data tradeoff (TMDTO) attack. In this paper, we investigate the security of small-state constructions in the multi-user setting. Based on it, the TMDTO distinguishing attack and the TMDTO key recovery attack are developed for such a setting. It is shown that SSCs which continuously use the key can not resist the TMDTO distinguishing attack. Moreover, SSCs based on the continuous-IV-key-use construction cannot withstand the TMDTO key recovery attack when the key length is shorter than the IV length, no matter whether the keystream length is limited or not. Finally, we apply these two generic attacks to TinyJAMBU and DRACO in the multi-user setting. The TMDTO distinguishing attack on TinyJAMBU with a 128-bit key can be mounted with time, memory, and data complexities of <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{64}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mn>64<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{48}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mn>48<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{32}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mn>32<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively. This attack is comparable with a recent work on ToSC 2022, where partial key bits of TinyJAMBU are recovered with more than <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{50}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mn>50<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> users (or keys). As DRACO\u2019s IV length is smaller than its key length, it is vulnerable to the TMDTO key recovery attack. The resulting attack has a time and memory complexity of both <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{112}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mn>112<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which means DRACO does not provide 128-bit security in the multi-user setting.<\/jats:p>","DOI":"10.1186\/s42400-023-00188-3","type":"journal-article","created":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T07:55:27Z","timestamp":1696838127000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Generic attacks on small-state stream cipher constructions in the multi-user setting"],"prefix":"10.1186","volume":"6","author":[{"given":"Jianfu","family":"Huang","sequence":"first","affiliation":[]},{"given":"Ye","family":"Luo","sequence":"additional","affiliation":[]},{"given":"Qinggan","family":"Fu","sequence":"additional","affiliation":[]},{"given":"Yincen","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Chao","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9298-7313","authenticated-orcid":false,"given":"Ling","family":"Song","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,8]]},"reference":[{"issue":"3","key":"188_CR1","doi-asserted-by":"publisher","first-page":"180","DOI":"10.3390\/e20030180","volume":"20","author":"GV Amin","year":"2018","unstructured":"Amin GV, Honggang H (2018) Fruit-80: a secure ultra-lightweight stream cipher for constrained environments. Entropy 20(3):180. https:\/\/doi.org\/10.3390\/e20030180","journal-title":"Entropy"},{"key":"188_CR2","unstructured":"Amin GV, Honggang H, Fujiang L (2019) On designing secure small-state stream ciphers against time-memory-data tradeoff attacks. Cryptology ePrint Archive, Preprint https:\/\/eprint.iacr.org\/2019\/670"},{"key":"188_CR3","doi-asserted-by":"publisher","unstructured":"Armknecht F, Mikhalev V (2015) On lightweight stream ciphers with shorter internal states. In: Fast software encryption\u201422nd international workshop\u2014FSE 2015\u2014Istanbul, Revised Selected Papers. Lecture Notes in Computer Science, vol 9054, pp 451\u2013470. https:\/\/doi.org\/10.1007\/978-3-662-48116-5_22","DOI":"10.1007\/978-3-662-48116-5_22"},{"key":"188_CR4","doi-asserted-by":"publisher","unstructured":"Babbage SH (1995) Improved \u201cexhaustive search\u201d attacks on stream ciphers. In: European convention on security and detection 1995, pp 161\u2013166. https:\/\/doi.org\/10.1049\/cp:19950490","DOI":"10.1049\/cp:19950490"},{"key":"188_CR5","doi-asserted-by":"publisher","unstructured":"Banik S (2022) Cryptanalysis of draco. IACR Transactions on symmetric cryptology, pp 92\u2013104. https:\/\/doi.org\/10.46586\/tosc.v2022.i4.92-104","DOI":"10.46586\/tosc.v2022.i4.92-104"},{"key":"188_CR6","doi-asserted-by":"publisher","unstructured":"Bellare M, Tackmann B (2016) The multi-user security of authenticated encryption: AES-GCM in TLS 1.3. In: Robshaw M, Katz J (eds) Advances in cryptology\u2014CRYPTO 2016\u201436th annual international cryptology conference, Santa Barbara, Part I. Lecture Notes in Computer Science, vol 9814, pp 247\u2013276. https:\/\/doi.org\/10.1007\/978-3-662-53018-4_10","DOI":"10.1007\/978-3-662-53018-4_10"},{"key":"188_CR7","doi-asserted-by":"publisher","unstructured":"Bellare M, Boldyreva A, Micali S (2000) Public-key encryption in a multi-user setting: security proofs and improvements. In: Preneel B (ed) Advances in Cryptology\u2014EUROCRYPT 2000, International conference on the theory and application of cryptographic techniques, Bruges, Lecture Notes in Computer Science, vol 1807, pp 259\u2013274. doi: https:\/\/doi.org\/10.1007\/3-540-45539-6_18","DOI":"10.1007\/3-540-45539-6_18"},{"key":"188_CR8","doi-asserted-by":"publisher","unstructured":"Biham E, Shamir A (1997) Differential fault analysis of secret key cryptosystems. In: Jr. BSK (ed) Advances in cryptology\u2014CRYPTO \u201997, 17th annual international cryptology conference, Santa Barbara, Lecture Notes in Computer Science, vol 1294, pp 513\u2013525. doi: https:\/\/doi.org\/10.1007\/BFb0052259","DOI":"10.1007\/BFb0052259"},{"key":"188_CR9","doi-asserted-by":"publisher","unstructured":"Biryukov A, Shamir A (2000) Cryptanalytic time\/memory\/data tradeoffs for stream ciphers. In: Tatsuaki O (ed) Advances in cryptology\u2014ASIACRYPT 2000. ASIACRYPT 2000. Lecture Notes in Computer Science, pp 1\u201313. doi: https:\/\/doi.org\/10.1007\/3-540-44448-3_1","DOI":"10.1007\/3-540-44448-3_1"},{"key":"188_CR10","doi-asserted-by":"publisher","unstructured":"Bose P, Hoang VT, Tessaro S (2018) Revisiting AES-GCM-SIV: multi-user security, faster key derivation, and better bounds. In: Nielsen JB, Rijmen V (eds) Advances in cryptology\u2014EUROCRYPT 2018\u201437th annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Part I, pp 468\u2013499. doi: https:\/\/doi.org\/10.1007\/978-3-319-78381-9_18","DOI":"10.1007\/978-3-319-78381-9_18"},{"key":"188_CR11","doi-asserted-by":"publisher","unstructured":"Dinur I, Shamir A (2009) Cube attacks on tweakable black box polynomials. In: Joux A (ed) Advances in Cryptology\u2014EUROCRYPT 2009, 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, Lecture Notes in Computer Science, vol 5479, pp 278\u2013299. doi: https:\/\/doi.org\/10.1007\/978-3-642-01001-9_16","DOI":"10.1007\/978-3-642-01001-9_16"},{"key":"188_CR12","doi-asserted-by":"publisher","unstructured":"Englund H, Hell M, Johansson T (2007) A note on distinguishing attacks. In: Proceedings of the IEEE Information theory workshop on information theory for wireless networks, Solstrand, pp 1\u20134. doi: https:\/\/doi.org\/10.1109\/ITWITWN.2007.4318038","DOI":"10.1109\/ITWITWN.2007.4318038"},{"key":"188_CR13","doi-asserted-by":"publisher","unstructured":"Englund H, Hell M, Johansson T (2007) Two general attacks on pomaranch-like keystream generators. In: Fast software encryption, 14th international workshop\u2014FSE 2007\u2014Luxembourg, Revised Selected Papers, pp 274\u2013289. doi: https:\/\/doi.org\/10.1007\/978-3-540-74619-5_18","DOI":"10.1007\/978-3-540-74619-5_18"},{"key":"188_CR14","doi-asserted-by":"publisher","unstructured":"Golic JD (1997) Cryptanalysis of alleged A5 stream cipher. In: Fumy W (ed) Advances in cryptology\u2014EUROCRYPT \u201997, International conference on the theory and application of cryptographic techniques, Konstanz, Lecture Notes in Computer Science, vol 1233, pp 239\u2013255. doi: https:\/\/doi.org\/10.1007\/3-540-69053-0_17","DOI":"10.1007\/3-540-69053-0_17"},{"key":"188_CR15","unstructured":"Hamann M, Krause M, Meier W (2017) A note on stream ciphers that continuously use the IV. Cryptology ePrint Archive, Preprint https:\/\/eprint.iacr.org\/2017\/1172"},{"key":"188_CR16","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/s12095-017-0261-6","volume":"10","author":"M Hamann","year":"2018","unstructured":"Hamann M, Krause M, Meier W, Zhang B (2018) Design and analysis of small-state grain-like stream ciphers. Cryptogr Commun 10:803\u2013834. https:\/\/doi.org\/10.1007\/s12095-017-0261-6","journal-title":"Cryptogr Commun"},{"key":"188_CR17","doi-asserted-by":"publisher","unstructured":"Hamann M, Krause M, Moch A (2020) Tight security bounds for generic stream cipher constructions. In: Paterson KG, Stebila D (eds) Selected Areas in cryptography\u2014SAC 2019\u201426th international conference, Waterloo, pp 335\u2013364. doi: https:\/\/doi.org\/10.1007\/978-3-030-38471-5_14","DOI":"10.1007\/978-3-030-38471-5_14"},{"key":"188_CR18","doi-asserted-by":"publisher","unstructured":"Hamann M, Moch A, Krause M, Mikhalev V (2022) The DRACO stream cipher: a power-efficient small-state stream cipher with full provable security against TMDTO attacks. IACR transactions on symmetric cryptology, pp 1\u201342. doi: https:\/\/doi.org\/10.46586\/tosc.v2022.i2.1-42","DOI":"10.46586\/tosc.v2022.i2.1-42"},{"key":"188_CR19","doi-asserted-by":"publisher","unstructured":"Hawkes P, Rose GG (2002) Guess-and-determine attacks on snow. In: Nyberg K, Heys HM (eds) Selected areas in cryptography, 9th annual international workshop, SAC 2002, St. John\u2019s, Newfoundland, Canada, Revised Papers. Lecture Notes in Computer Science, vol 2595, pp 37\u201346. doi: https:\/\/doi.org\/10.1007\/3-540-36492-7_4","DOI":"10.1007\/3-540-36492-7_4"},{"issue":"4","key":"188_CR20","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"M Hellman","year":"1980","unstructured":"Hellman M (1980) A cryptanalytic time-memory trade-off. IEEE Trans Inf Theory 26(4):401\u2013406. https:\/\/doi.org\/10.1109\/TIT.1980.1056220","journal-title":"IEEE Trans Inf Theory"},{"key":"188_CR21","doi-asserted-by":"publisher","unstructured":"Hoang VT, Tessaro S (2016) Key-alternating ciphers and key-length extension: exact bounds and multi-user security. In: Robshaw M, Katz J (eds) Advances in cryptology\u2014CRYPTO 2016\u201436th annual international cryptology conference, Santa Barbara, Part I. Lecture Notes in Computer Science, vol 9814, pp 3\u201332. doi: https:\/\/doi.org\/10.1007\/978-3-662-53018-4_1","DOI":"10.1007\/978-3-662-53018-4_1"},{"key":"188_CR22","doi-asserted-by":"publisher","unstructured":"Hoang VT, Tessaro S (2017) The multi-user security of double encryption. In: Coron J, Nielsen JB (eds) Advances in Cryptology\u2014EUROCRYPT 2017\u201436th annual international conference on the theory and applications of cryptographic techniques, Paris, Part II. Lecture Notes in Computer Science, vol 10211, pp 381\u2013411. doi: https:\/\/doi.org\/10.1007\/978-3-319-56614-6_13","DOI":"10.1007\/978-3-319-56614-6_13"},{"key":"188_CR23","doi-asserted-by":"publisher","unstructured":"Hong J, Sarkar P (2005) New applications of time memory data tradeoffs. In: Roy BK (ed) Advances in Cryptology\u2014ASIACRYPT 2005, 11th international conference on the theory and application of cryptology and information security, Chennai, Lecture Notes in Computer Science, vol 3788, pp 353\u2013372. doi: https:\/\/doi.org\/10.1007\/11593447_19","DOI":"10.1007\/11593447_19"},{"key":"188_CR24","unstructured":"Hongjun W, Tao H (2019) TinyJAMBU: a family of lightweight authenticated encryption algorithms. The NIST lightweight cryptography competition. https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Lightweight-Cryptography\/documents\/round-1\/ip-statements\/TinyJAMBU-Statements.pdf"},{"key":"188_CR25","unstructured":"Hongjun W, Tao H (2021) TinyJAMBU: A family of lightweight authenticated encryption algorithms (Version 2). The NIST lightweight cryptography competition. https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/lightweight-cryptography\/documents\/finalist-round\/updated-spec-doc\/tinyjambu-spec-final.pdf"},{"issue":"3","key":"188_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-018-9929-x","volume":"63","author":"L Jiao","year":"2020","unstructured":"Jiao L, Hao Y, Feng D (2020) Stream cipher designs: a review. Sci China Inf Sci 63(3):1\u201325. https:\/\/doi.org\/10.1007\/s11432-018-9929-x","journal-title":"Sci China Inf Sci"},{"key":"188_CR27","doi-asserted-by":"publisher","unstructured":"Mouha N, Luykx A (2015) Multi-key security: the even-mansour construction revisited. In: Gennaro R, Robshaw M (eds) Advances in Cryptology\u2014CRYPTO 2015\u201435th annual cryptology conference, Santa Barbara, Part I. Lecture Notes in Computer Science, vol 9215, pp 209\u2013223. doi: https:\/\/doi.org\/10.1007\/978-3-662-47989-6_10","DOI":"10.1007\/978-3-662-47989-6_10"},{"key":"188_CR28","doi-asserted-by":"publisher","unstructured":"Muzhou L, Nicky M, Ling S, Meiqin W (2022) Revisiting the extension of Matsui\u2019s algorithm 1 to linear hulls: application to TinyJAMBU. IACR transactions on symmetric cryptology, pp 161\u2013200. doi: https:\/\/doi.org\/10.46586\/tosc.v2022.i2.161-200","DOI":"10.46586\/tosc.v2022.i2.161-200"},{"key":"188_CR29","doi-asserted-by":"publisher","unstructured":"Philip MA, Vaithiyanathan (2017) A survey on lightweight ciphers for IoT devices. In: 2017 international conference on technological advancements in power and energy (TAP Energy), pp 1\u20134. doi: https:\/\/doi.org\/10.1109\/TAPENERGY.2017.8397271","DOI":"10.1109\/TAPENERGY.2017.8397271"},{"key":"188_CR30","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-642-82865-2_2","volume-title":"Analysis and design of stream ciphers","author":"RA Rueppel","year":"1986","unstructured":"Rueppel RA (1986) Analysis and design of stream ciphers. Springer, Berlin, Heidelberg, pp 5\u201316. https:\/\/doi.org\/10.1007\/978-3-642-82865-2_2"},{"issue":"5","key":"188_CR31","first-page":"2258","volume":"13","author":"D Sehrawat","year":"2018","unstructured":"Sehrawat D, Gill NS (2018) Lightweight block ciphers for IoT based applications: a review. Int J Appl Eng Res 13(5):2258\u20132270","journal-title":"Int J Appl Eng Res"},{"key":"188_CR32","doi-asserted-by":"publisher","first-page":"1032761","DOI":"10.1155\/2018\/1032761","volume":"2018","author":"M Seliem","year":"2018","unstructured":"Seliem M, Elgazzar K, Khalil K (2018) Towards privacy preserving IoT environments: a survey. Wirel Commun Mob Comput 2018:1032761. https:\/\/doi.org\/10.1155\/2018\/1032761","journal-title":"Wirel Commun Mob Comput"},{"key":"188_CR33","doi-asserted-by":"publisher","unstructured":"Shah A, Engineer M (2019) A survey of lightweight cryptographic algorithms for IoT-based applications. In: Smart innovations in communication and computational sciences: proceedings of ICSICCS-2018, Springer, pp 283\u2013293. doi: https:\/\/doi.org\/10.1007\/978-981-13-2414-7_27","DOI":"10.1007\/978-981-13-2414-7_27"},{"issue":"4","key":"188_CR34","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1002\/j.1538-7305.1949.tb00928.x","volume":"28","author":"CE Shannon","year":"1949","unstructured":"Shannon CE (1949) Communication theory of secrecy systems. Bell Syst Tech J 28(4):656\u2013715","journal-title":"Bell Syst Tech J"},{"key":"188_CR35","doi-asserted-by":"publisher","unstructured":"Tessaro S (2015) Optimally secure block ciphers from ideal primitives. In: Iwata T, Cheon JH (eds) Advances in cryptology\u2014 ASIACRYPT 2015\u201421st international conference on the theory and application of cryptology and information security, Auckland, Part II. Lecture Notes in Computer Science, vol 9453, pp 437\u2013462. doi: https:\/\/doi.org\/10.1007\/978-3-662-48800-3_18","DOI":"10.1007\/978-3-662-48800-3_18"},{"key":"188_CR36","doi-asserted-by":"publisher","unstructured":"Vasily M, Frederik A, Christian M (2016) On ciphers that continuously access the non-volatile key. IACR transactions on symmetric cryptology, pp 52\u201379. doi: https:\/\/doi.org\/10.13154\/tosc.v2016.i2.52-79","DOI":"10.13154\/tosc.v2016.i2.52-79"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-023-00188-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-023-00188-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-023-00188-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T21:28:42Z","timestamp":1700256522000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-023-00188-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,8]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1186\/s42400-023-00188-3","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2023,10,8]]},"assertion":[{"value":"16 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"53"}}