{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T06:24:04Z","timestamp":1766298244394,"version":"3.46.0"},"reference-count":33,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Recent lightweight hardware-based stream cipher designs keep an external non-volatile internal state that is\n                    <jats:italic>not<\/jats:italic>\n                    part of the cipher\u2019s hardware module. The purpose of these so-called small-state ciphers is to keep the size of the hardware and the power consumption low. We propose a random oracle model for stream ciphers. This will allow us to analyse the recent small-state stream cipher designs\u2019 resistance against generic attacks and, in particular, time-memory-data tradeoff attacks. We analyse the conventional construction underlying stream ciphers like Grain and Trivium, constructions continuously using the external non-volatile secret key during keystream generation like Sprout, Plantlet, Fruit, and Atom, constructions continuously using the external non-volatile IV, and constructions using a combination of the IV and the key like DRACO. We show the tightness of all bounds by first presenting the time-memory-data tradeoff attacks on the respective constructions, establishing the upper bound on security, and then presenting the proof of security to establish the lower bound on security. In this work, we extend the theoretical work done by Hamann et al. who introduced the DRACO stream cipher at FSE 2023. We use the same random oracle model as the aforementioned work and apply it to the earlier work by Hamann et al. presented at SAC 2019, which showed security for two of the four constructions we consider in this work. Our model is equivalent but allows for a much simpler proof of security. Furthermore, we provide a proof of security for stream ciphers continuously using the secret key during keystream generation, giving upper and lower bounds for all four generic stream cipher constructions proposed so far.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2022-0033","type":"journal-article","created":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T09:52:35Z","timestamp":1688118755000},"source":"Crossref","is-referenced-by-count":2,"title":["Provable security against generic attacks on stream ciphers"],"prefix":"10.1515","volume":"17","author":[{"given":"Alexander","family":"Moch","sequence":"first","affiliation":[{"name":"Lehrstuhl f\u00fcr Theoretische Informatik, Universit\u00e4t Mannheim , 68131 Mannheim , Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2023,6,30]]},"reference":[{"key":"2025120600280450500_j_jmc-2022-0033_ref_001","doi-asserted-by":"crossref","unstructured":"Hell M, Johansson T, Meier W. Grain - A Stream Cipher for Constrained Environments; 2006. eSTREAM: the ECRYPT Stream Cipher Project. http:\/\/www.ecrypt.eu.org\/stream\/p3ciphers\/grain\/Grain_p3.pdf.","DOI":"10.1504\/IJWMC.2007.013798"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_002","unstructured":"Canni\u00e9re CD, Preneel B. Trivium - Specifications; 2005. eSTREAM: the ECRYPT Stream Cipher Project. http:\/\/www.ecrypt.eu.org\/stream\/p3ciphers\/trivium\/trivium_p3.pdf."},{"key":"2025120600280450500_j_jmc-2022-0033_ref_003","doi-asserted-by":"crossref","unstructured":"Amin Ghafari V, Hu H. Fruit-80: A secure ultra-lightweight stream cipher for constrained environments. Entropy. 2018;20(3):180.","DOI":"10.3390\/e20030180"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_004","doi-asserted-by":"crossref","unstructured":"Banik S, Caforio A, Isobe T, Liu F, Meier W, Sakamoto K, et al. Atom: a stream cipher with double key filter. IACR Trans Symmetric Cryptol. 2021(1):5\u201336.","DOI":"10.46586\/tosc.v2021.i1.5-36"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_005","doi-asserted-by":"crossref","unstructured":"Armknecht F, Mikhalev V. On lightweight stream ciphers with shorter internal states. In: FSE 2015. Berlin, Heidelberg: Springer; 2015. p. 451\u201370.","DOI":"10.1007\/978-3-662-48116-5_22"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_006","doi-asserted-by":"crossref","unstructured":"Mikhalev V, Armknecht F, M\u00fc ller C. On ciphers that continuously access the non-volatile key. IACR ToSC. 2016;2016(2):52\u201379. https:\/\/dblp.org\/rec\/journals\/tosc\/MikhalevAM16.html.","DOI":"10.46586\/tosc.v2016.i2.52-79"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_007","unstructured":"Aumasson JP. Serious cryptography: a practical introduction to modern encryption. San Francisco, CA 94103 USA: No Starch Press; 2017."},{"key":"2025120600280450500_j_jmc-2022-0033_ref_008","doi-asserted-by":"crossref","unstructured":"Klein A. Stream ciphers. London: Springer; 2013.","DOI":"10.1007\/978-1-4471-5079-4"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_009","doi-asserted-by":"crossref","unstructured":"Babbage SH. Improved \u201cexhaustive search\u201d attacks on stream ciphers. In: European Convertion on Security and Detection 1995; 1995. p. 161\u20136.","DOI":"10.1049\/cp:19950490"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_010","doi-asserted-by":"crossref","unstructured":"Goli\u0107 JD. On the security of nonlinear filter generators. In: Gollmann D, editor. FSE 1996. Berlin, Heidelberg: Springer; 1996. p. 173\u201388. 10.1007\/3-540-60865-6_52.","DOI":"10.1007\/3-540-60865-6_52"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_011","doi-asserted-by":"crossref","unstructured":"Hamann M, Krause M, Meier W, Zhang B. Design and analysis of small-state grain-like stream ciphers. Cryptography Commun. 2018;10(5):803\u201334.","DOI":"10.1007\/s12095-017-0261-6"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_012","unstructured":"Hamann M, Krause M, Meier W. A note on stream ciphers that continuously use the IV. IACR Cryptol ePrint Archive. 2017;2017:1172."},{"key":"2025120600280450500_j_jmc-2022-0033_ref_013","doi-asserted-by":"crossref","unstructured":"Hamann M, Krause M, Moch A. Tight security bounds for generic stream cipher constructions. In: SAC 2019. Cham: Springer; 2019. p. 335\u201364.","DOI":"10.1007\/978-3-030-38471-5_14"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_014","doi-asserted-by":"crossref","unstructured":"Hamann M, Moch A, Krause M, Mikhalev V. The DRACO stream cipher: a power-efficient small-state stream cipher with full provable security against TMDTO attacks. IACR Trans Symmetric Cryptol. 2022;2022(2):1\u201342. https:\/\/tosc.iacr.org\/index.php\/ToSC\/article\/view\/9712.","DOI":"10.46586\/tosc.v2022.i2.1-42"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_015","doi-asserted-by":"crossref","unstructured":"Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation. J Cryptol. 1997;10(3):151\u201361.","DOI":"10.1007\/s001459900025"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_016","doi-asserted-by":"crossref","unstructured":"Chen S, Steinberger J. Tight security bounds for key-alternating ciphers. In: EUROCRYPT 2014. Berlin, Heidelberg: Springer; 2014. p. 327\u201350.","DOI":"10.1007\/978-3-642-55220-5_19"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_017","doi-asserted-by":"crossref","unstructured":"Chen S, Lampe R, Lee J, Seurin Y, Steinberger J. Minimizing the two-round even-Mansour cipher. In: CRYPTO 2014. Berlin, Heidelberg: Springer; 2014. p. 39\u201356.","DOI":"10.1007\/978-3-662-44371-2_3"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_018","doi-asserted-by":"crossref","unstructured":"Dunkelman O, Keller N, Shamir A. Minimalism in cryptography: the even-Mansour scheme revisited. In: EUROCRYPT 2012. Berlin, Heidelberg: Springer; 2012. p. 336\u201354.","DOI":"10.1007\/978-3-642-29011-4_21"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_019","doi-asserted-by":"crossref","unstructured":"Lampe R, Patarin J, Seurin Y. An asymptotically tight security analysis of the iterated even-Mansour cipher. In: ASIACRYPT 2012. Berlin, Heidelberg: Springer; 2012. p. 278\u201395.","DOI":"10.1007\/978-3-642-34961-4_18"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_020","doi-asserted-by":"crossref","unstructured":"Bogdanov A, Knudsen LR, Leander G, Standaert FX, Steinberger J, Tischhauser E. Key-alternating ciphers in a provable setting: encryption using a small number of public permutations. In: EUROCRYPT 2012. Berlin, Heidelberg: Springer; 2012. p. 45\u201362.","DOI":"10.1007\/978-3-642-29011-4_5"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_021","doi-asserted-by":"crossref","unstructured":"Andreeva E, Bogdanov A, Dodis Y, Mennink B, Steinberger JP. On the indifferentiability of key-alternating ciphers. In: CRYPTO 2013. Berlin, Heidelberg: Springer; 2013. p. 531\u201350.","DOI":"10.1007\/978-3-642-40041-4_29"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_022","doi-asserted-by":"crossref","unstructured":"Patarin J. The \u201ccoefficients H\u201d technique. In: SAC 2008. Springer; 2008. p. 328\u201345.","DOI":"10.1007\/978-3-642-04159-4_21"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_023","doi-asserted-by":"crossref","unstructured":"Bellare M, Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols. In: Denning DE, Pyle R, Ganesan R, Sandhu RS, Ashby V, editors.CCS \u201993, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3\u20135, 1993. ACM; 1993. p. 62\u201373. 10.1145\/168588.168596.","DOI":"10.1145\/168588.168596"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_024","doi-asserted-by":"crossref","unstructured":"Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited. J ACM (JACM). 2004;51(4):557\u201394.","DOI":"10.1145\/1008731.1008734"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_025","doi-asserted-by":"crossref","unstructured":"\u00c5gren M, Hell M, Johansson T, Meier W. Grain-128a: a new version of grain-128 with optional authentication. IJWMC. 2011 Dec;5(1):48\u201359. 10.1504\/IJWMC.2011.044106.","DOI":"10.1504\/IJWMC.2011.044106"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_026","unstructured":"Babbage S, Dodd M. The stream cipher MICKEY 2.0; 2006. eSTREAM: the ECRYPT Stream Cipher Project. http:\/\/www.ecrypt.eu.org\/stream\/p3ciphers\/mickey\/mickey_p3.pdf."},{"key":"2025120600280450500_j_jmc-2022-0033_ref_027","unstructured":"Institute of Electrical and Electronics Engineers. IEEE Standard for Information Technology \u2013 Telecommunications and Information Exchange between Systems \u2013 Local and Metropolitan Area Networks \u2013 Specific Requirements \u2013 Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Std 80211-2020 (Revision of IEEE Std 80211-2016). 2021:1\u20134379."},{"key":"2025120600280450500_j_jmc-2022-0033_ref_028","doi-asserted-by":"crossref","unstructured":"Rescorla E. The transport layer security (TLS) protocol version 1.3. RFC Editor; 2018. RFC 8446. https:\/\/rfc-editor.org\/rfc\/rfc8446.txt.","DOI":"10.17487\/RFC8446"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_029","doi-asserted-by":"crossref","unstructured":"Popov A. Prohibiting RC4 cipher suites. IETF; 2015. RFC 7465 (Proposed Standard). http:\/\/www.ietf.org\/rfc\/rfc7465.txt.","DOI":"10.17487\/rfc7465"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_030","doi-asserted-by":"crossref","unstructured":"Biryukov A, Shamir A. Cryptanalytic time\/memory\/data tradeoffs for stream ciphers. In: Okamoto T, editor. ASIACRYPT 2000. Berlin, Heidelberg: Springer; 2000. p. 1\u201313. http:\/\/dx.doi.org\/10.1007\/3-540-44448-3_1.","DOI":"10.1007\/3-540-44448-3_1"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_031","doi-asserted-by":"crossref","unstructured":"Hellman M. A cryptanalytic time-memory trade-off. IEEE Trans Inform Theory. 1980 Jul;26(4):401\u20136.","DOI":"10.1109\/TIT.1980.1056220"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_032","doi-asserted-by":"crossref","unstructured":"Biryukov A, Shamir A, Wagner D. Real time cryptanalysis of A5\/1 on a PC. In: FSE 2000. Berlin, Heidelberg: Springer; 2001. p. 1\u201318. http:\/\/dx.doi.org\/10.1007\/3-540-44706-7_1.","DOI":"10.1007\/3-540-44706-7_1"},{"key":"2025120600280450500_j_jmc-2022-0033_ref_033","doi-asserted-by":"crossref","unstructured":"Hong J, Sarkar P. New applications of time memory data tradeoffs. In: Roy B, editor. ASIACRYPT 2005. Berlin, Heidelberg: Springer; 2005. p. 353\u201372.","DOI":"10.1007\/11593447_19"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2022-0033\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2022-0033\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:28:24Z","timestamp":1764980904000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2022-0033\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,1]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,6,5]]},"published-print":{"date-parts":[[2023,6,5]]}},"alternative-id":["10.1515\/jmc-2022-0033"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2022-0033","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2023,1,1]]},"article-number":"20220033"}}