{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:46:21Z","timestamp":1740181581057,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T00:00:00Z","timestamp":1687824000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T00:00:00Z","timestamp":1687824000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>PudgyTurtle is not a cipher, but rather an alternative way to utilize the keystream in binary-additive stream-cipher cryptosystems. Instead of modulo-2 adding the keystream to the plaintext, PudgyTurtle uses the keystream to encode 4-bit groups of plaintext, and then to encipher each codeword. One goal of PudgyTurtle is to make time\u2013memory tradeoff attacks more difficult. Here, we investigate one such attack (a modification of the well-known Babbage\u2013Goli\u0107 method), and show that its time-complexity is harder on average than an analogous tradeoff attack against a standard binary-additive stream cipher; may approach that of a \u2019brute-force\u2019 attack; can be reduced by certain parameter choices; and can be formulated in terms of a probability distribution which is amenable to simulation.<\/jats:p>","DOI":"10.1007\/s42979-023-01919-6","type":"journal-article","created":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T15:12:37Z","timestamp":1687878757000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterizing a Time\u2013Memory Tradeoff Against PudgyTurtle"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2732-5983","authenticated-orcid":false,"given":"David A.","family":"August","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne C.","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,27]]},"reference":[{"key":"1919_CR1","doi-asserted-by":"crossref","unstructured":"Armknecht F, Mikhalev V. On lightweight stream ciphers with shorter internal states. In: Fast software encryption\u201422nd international workshop, FSE 2015, Istanbul, Turkey, March 8\u201311, 2015, revised selected papers. 2015. pp. 451\u201370.","DOI":"10.1007\/978-3-662-48116-5_22"},{"key":"1919_CR2","unstructured":"August D, Smith A. Pudgyturtle GitHub repository, 2021. https:\/\/github.com\/smaugust\/PudgyTurtle."},{"key":"1919_CR3","doi-asserted-by":"publisher","unstructured":"August DA, Smith AC. Pudgyturtle: using keystream to encode and encrypt. SN Comput Sci. 2020;1(4):Article#226. https:\/\/doi.org\/10.1007\/s42979-020-00221-z","DOI":"10.1007\/s42979-020-00221-z"},{"key":"1919_CR4","unstructured":"August DA, Smith AC. Pudgyturtle: variable-length, keystream-dependent encoding to resist time-memory tradeoff attacks. IACR Cryptology ePrint Archive, Report 2020\/838. 2020. https:\/\/eprint.iacr.org\/2020\/838."},{"key":"1919_CR5","doi-asserted-by":"crossref","unstructured":"Babbage S. Improved \u201cexhaustive search\u201d attacks on stream ciphers. In: European convention on security and detection, 1995, Institution of Engineering and Technology. 1995. pp. 161\u201366.","DOI":"10.1049\/cp:19950490"},{"key":"1919_CR6","doi-asserted-by":"crossref","unstructured":"Banik S. Some results on Sprout. In: Biryukov A, Goyal V (eds) 16th international conference on cryptology in India, INDOCRYPT 2015. Lecture notes in computer science INDOCRYPT \u201915. Springer International Publishing, Berlin; 2015. pp. 124\u201339.","DOI":"10.1007\/978-3-319-26617-6_7"},{"key":"1919_CR7","doi-asserted-by":"crossref","unstructured":"Banik S, Bogdanov A, Isobe T, Shibutani K, Hiwatari H, Akishita T, Regazzoni F. Midori: a block cipher for low energy. In: Iwata T, Cheon JH, editors. Advances in cryptology\u2014ASIACRYPT 2015. Springer, Berlin; 2015. pp. 411\u201336.","DOI":"10.1007\/978-3-662-48800-3_17"},{"key":"1919_CR8","doi-asserted-by":"publisher","unstructured":"Beaulieu R, Treatman-Clark S, Shors D, Weeks B, Smith J, Wingers L. The SIMON and SPECK lightweight block ciphers. In: 2015 52nd ACM\/EDAC\/IEEE design automation conference (DAC), 2015. pp. 1\u20136. https:\/\/doi.org\/10.1145\/2744769.2747946.","DOI":"10.1145\/2744769.2747946"},{"key":"1919_CR9","unstructured":"Bernstein DJ. Cache-timing attacks on AES. 2005. http:\/\/cr.yp.to\/antiforgery\/cachetiming-20050414.pdf."},{"key":"1919_CR10","doi-asserted-by":"crossref","unstructured":"Biryukov A, Shamir A. Cryptanalytic time\/memory\/data tradeoffs for stream ciphers. In: Okamoto T, editor. Advances in cryptology\u2014ASIACRYPT 2000. Springer, Berlin; 2000. pp. 1\u201313.","DOI":"10.1007\/3-540-44448-3_1"},{"key":"1919_CR11","doi-asserted-by":"crossref","unstructured":"Biryukov A, Shamir A, Wagner D. Real time cryptanalysis of A5\/1 on a PC. In: Goos G, Hartmanis J, van Leeuwen J, Schneier B, editors. Fast software encryption. Springer, Berlin; 2001. pp. 1\u201318.","DOI":"10.1007\/3-540-44706-7_1"},{"key":"1919_CR12","doi-asserted-by":"crossref","unstructured":"Bogdanov A, Knudsen LR, Leander G, Paar C, Poschmann A, Robshaw MJB, Seurin Y, Vikkelsoe C. PRESENT: an ultra-lightweight block cipher. In: Paillier P, Verbauwhede I, editors. Cryptographic hardware and embedded systems\u2014CHES 2007. Springer, Berlin; 2007. pp. 450\u201366.","DOI":"10.1007\/978-3-540-74735-2_31"},{"key":"1919_CR13","doi-asserted-by":"crossref","unstructured":"Bonneau J, Mironov I. Cache-collision timing attacks against aes. In: Goubin L, Matsui M, editors. Cryptographic hardware and embedded systems\u2014CHES 2006. Springer, Berlin; 2006. pp. 201\u201315.","DOI":"10.1007\/11894063_16"},{"key":"1919_CR14","doi-asserted-by":"crossref","unstructured":"Borghoff J, Canteaut A, G\u00fcneysu T, Kavun EB, Knezevic M, Knudsen LR, Leander G, Nikov V, Paar C, Rechberger C, Rombouts P, Thomsen SS, Yal\u00e7\u0131n T. PRINCE\u2014a low-latency block cipher for pervasive computing applications. In: Wang X, Sako K, editors. Advances in cryptology\u2014ASIACRYPT 2012. Springer, Berlin; 2012. pp. 208\u201325.","DOI":"10.1007\/978-3-642-34961-4_14"},{"key":"1919_CR15","doi-asserted-by":"crossref","unstructured":"van den Broek F, Poll E. A comparison of time-memory trade-off attacks on stream ciphers. In: Youssef A, Nitaj A, Hassanien AE, editors. Progress in cryptology\u2014AFRICACRYPT 2013. Springer, Berlin; 2013. pp. 406\u201323.","DOI":"10.1007\/978-3-642-38553-7_24"},{"key":"1919_CR16","doi-asserted-by":"crossref","unstructured":"Canni\u00e8re CD, Preneel B. Trivium. In: Billet O, Robshaw M (eds) New stream cipher designs. Lecture notes in computer science, vol. 4986. Springer, Berlin; 2008. pp. 244\u201366.","DOI":"10.1007\/978-3-540-68351-3_18"},{"key":"1919_CR17","doi-asserted-by":"publisher","unstructured":"Copeland J, Simpson L. Finding slid pairs for the Plantlet stream cipher. In: Proceedings of the Australasian computer science week multiconference, association for computing machinery, New York, NY, USA, ACSW \u201920, 2020. https:\/\/doi.org\/10.1145\/3373017.3373024.","DOI":"10.1145\/3373017.3373024"},{"key":"1919_CR18","doi-asserted-by":"crossref","unstructured":"De Canni\u00e8re C, Dunkelman O, Kne\u017eevi\u0107 M. KATAN and KTANTAN\u2014a family of small and efficient hardware-oriented block ciphers. In: Clavier C, Gaj K, editors. Cryptographic hardware and embedded systems\u2014CHES 2009. Springer, Berlin; 2009. pp. 272\u201388.","DOI":"10.1007\/978-3-642-04138-9_20"},{"key":"1919_CR19","unstructured":"Dinu D, Biryukov A, Gro\u00dfsch\u00e4dl J, Khovratovich D, Le\u00a0Corre Y, Perrin L. FELICS\u2014fair evaluation of lightweight cryptographic systems. 2015. https:\/\/www.cryptolux.org\/index.php\/FELICS. Accessed 2 Oct 2022."},{"key":"1919_CR20","unstructured":"Dubrova E. A list of maximum period NLFSRs. IACR Cryptology ePrint Archive, Report 2012\/166, 2012. https:\/\/eprint.iacr.org\/2012\/166."},{"issue":"5","key":"1919_CR21","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.ipl.2008.01.011","volume":"107","author":"O Dunkelman","year":"2008","unstructured":"Dunkelman O, Keller N. Treatment of the initial value in time-memory-data tradeoff attacks on stream ciphers. Inf Process Lett. 2008;107(5):133\u20137.","journal-title":"Inf Process Lett"},{"key":"1919_CR22","doi-asserted-by":"crossref","unstructured":"Engels DW, Fan X, Gong G, Hu H, Smith EM. Hummingbird: ultra-lightweight cryptography for resource-constrained devices. In: Financial cryptography workshops 2010.","DOI":"10.1007\/978-3-642-14992-4_2"},{"key":"1919_CR23","unstructured":"Esgin MF, Kara O. Practical cryptanalysis of full Sprout with TMD tradeoff attacks. Cryptology ePrint Archive, Report 2015\/289, 2015. https:\/\/eprint.iacr.org\/2015\/289."},{"key":"1919_CR24","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-69053-0_17","volume-title":"Advances in cryptology\u2014EUROCRYPT \u201997","author":"JD Goli\u0107","year":"1997","unstructured":"Goli\u0107 JD. Cryptanalysis of alleged A5 stream cipher. In: Fumy W, editor. Advances in cryptology\u2014EUROCRYPT \u201997. Berlin: Springer; 1997. p. 239\u201355."},{"key":"1919_CR25","first-page":"1","volume-title":"RFID: security and privacy","author":"Z Gong","year":"2012","unstructured":"Gong Z, Nikova S, Law YW. KLEIN: a new family of lightweight block ciphers. In: Juels A, Paar C, editors. RFID: security and privacy. Berlin: Springer; 2012. p. 1\u201318."},{"key":"1919_CR26","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-642-23951-9_22","volume-title":"Cryptographic hardware and embedded systems\u2014CHES 2011","author":"J Guo","year":"2011","unstructured":"Guo J, Peyrin T, Poschmann A, Robshaw M. The LED block cipher. In: Preneel B, Takagi T, editors. Cryptographic hardware and embedded systems\u2014CHES 2011. Berlin: Springer; 2011. p. 326\u201341."},{"key":"1919_CR27","doi-asserted-by":"publisher","first-page":"45","DOI":"10.46586\/tosc.v2017.i1.45-79","volume":"1","author":"M Hamann","year":"2017","unstructured":"Hamann M, Krause M, Meier W. LIZARD\u2014a lightweight stream cipher for power-constrained devices. IACR Trans Symm Cryptol. 2017;1:45\u201379.","journal-title":"IACR Trans Symm Cryptol"},{"key":"1919_CR28","unstructured":"Hao Y. A related-key chosen-IV distinguishing attack on full Sprout stream cipher. Cryptology ePrint Archive, Report 2015\/231, 2015. https:\/\/ia.cr\/2015\/231"},{"issue":"4","key":"1919_CR29","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"M Hellman","year":"1980","unstructured":"Hellman M. A cryptanalytic time-memory trade-off. IEEE Trans Inf Theor. 1980;26(4):401\u20136.","journal-title":"IEEE Trans Inf Theor"},{"key":"1919_CR30","doi-asserted-by":"crossref","unstructured":"Kalenderi M, Pnevmatikatos D, Papaefstathiou I, Manifavas C. Breaking the GSM A5\/1 cryptography algorithm with rainbow tables and high-end FPGAS. In: 22nd international conference on field programmable logic and applications (FPL); 2012. pp. 747\u201353.","DOI":"10.1109\/FPL.2012.6339146"},{"issue":"1","key":"1919_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1109\/TC.2018.2851239","volume":"68","author":"O Kara","year":"2019","unstructured":"Kara O, Esgin MF. On analysis of lightweight stream ciphers with keyed update. IEEE Trans Comput. 2019;68(1):99\u2013110. https:\/\/doi.org\/10.1109\/TC.2018.2851239.","journal-title":"IEEE Trans Comput"},{"key":"1919_CR32","doi-asserted-by":"crossref","unstructured":"Kobayashi E, Suzaki T, Minematsu K, Morioka S. TWINE: a lightweight block cipher for multiple platforms. In: Selected areas in cryptography, 19th international conference (SAC 2012), vol. 7707. Lecture notes in computer science. Springer, Berlin; 2012. pp. 339\u201354.","DOI":"10.1007\/978-3-642-35999-6_22"},{"key":"1919_CR33","doi-asserted-by":"publisher","unstructured":"Kumar N, Ojha S, Jain K, Lal S. Bean: a lightweight stream cipher. In: Proceedings of the 2nd international conference on security of information and networks, association for computing machinery, New York, NY, USA, SIN \u201909, 2009. pp. 168\u201371. https:\/\/doi.org\/10.1145\/1626195.1626238.","DOI":"10.1145\/1626195.1626238"},{"key":"1919_CR34","doi-asserted-by":"crossref","unstructured":"Lallemand V, Naya-Plasencia M. Cryptanalysis of full Sprout. In: Gennaro R, Robshaw M (eds) Advances in cryptology\u2014CRYPTO 2015, Part 1. lecture notes in computer science, vol. 9215. Springer, Berlin; 2015;663\u201382.","DOI":"10.1007\/978-3-662-47989-6_32"},{"key":"1919_CR35","doi-asserted-by":"crossref","unstructured":"Li Z. Optimization of rainbow tables for practically cracking GSM A5\/1 based on validated success rate modeling. In: Proceedings of the RSA conference on topics in cryptology\u2014CT-RSA 2016\u2014volume 9610. Springer, Berlin; 2016. pp. 359\u201377.","DOI":"10.1007\/978-3-319-29485-8_21"},{"key":"1919_CR36","unstructured":"Maitra S, Sarkar S, Baksi A, Dey P. Key recovery from state information of sprout: application to cryptanalysis and fault attack. IACR cryptology ePrint Archive, Report 2015\/236, 2015. https:\/\/ia.cr\/2015\/236."},{"key":"1919_CR37","doi-asserted-by":"publisher","first-page":"52","DOI":"10.46586\/tosc.v2016.i2.52-79","volume":"2016","author":"V Mikhalev","year":"2017","unstructured":"Mikhalev V, Armknecht F, Muller C. On ciphers that continually access the non-volatile key. IACR Trans Symmet Cryptol. 2017;2016:52\u201379.","journal-title":"IACR Trans Symmet Cryptol"},{"key":"1919_CR38","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-030-10591-4_2","volume-title":"Security of ubiquitous computing systems: selected topics","author":"A Mileva","year":"2021","unstructured":"Mileva A, Dimitrova V, Kara O, Mihaljevi\u0107 MJ. Catalog and illustrative examples of lightweight cryptographic primitives. In: Avoine G, Hernandez-Castro J, editors. Security of ubiquitous computing systems: selected topics. Cham: Springer International Publishing; 2021. p. 21\u201347."},{"key":"1919_CR39","doi-asserted-by":"publisher","unstructured":"Mohandas NA, Swathi A, R A, Nazar A, Sharath G. A4: a lightweight stream cipher. In: 2020 5th international conference on communication and electronics systems (ICCES), 2020. pp. 573\u201377. https:\/\/doi.org\/10.1109\/ICCES48766.2020.9138048.","DOI":"10.1109\/ICCES48766.2020.9138048"},{"key":"1919_CR40","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-540-45146-4_36","volume-title":"Advances in cryptology\u2014CRYPTO 2003","author":"P Oechslin","year":"2003","unstructured":"Oechslin P. Making a faster cryptanalytic time-memory trade-off. In: Boneh D, editor. Advances in cryptology\u2014CRYPTO 2003. Berlin: Springer; 2003. p. 617\u201330."},{"key":"1919_CR41","doi-asserted-by":"publisher","unstructured":"Papantonakis P, Pnevmatikatos D, Papaefstathiou I, Manifavas C. Fast, FPGA-based rainbow table creation for attacking encrypted mobile communications. In: 2013 23rd international conference on field programmable logic and applications, 2013. pp. 1\u20136. https:\/\/doi.org\/10.1109\/FPL.2013.6645525.","DOI":"10.1109\/FPL.2013.6645525"},{"key":"1919_CR42","doi-asserted-by":"crossref","unstructured":"Rivest RL, Sherman AT. Randomized encryption techniques. In: Chaum D, Rivest RL, Sherman AT (eds) Advances in cryptology: Proceedings of Crypto \u201982, Springer US, Boston, MA; 1983. pp. 145\u201363.","DOI":"10.1007\/978-1-4757-0602-4_14"},{"key":"1919_CR43","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/3-540-45661-9_18","volume-title":"Fast software encryption","author":"MJO Saarinen","year":"2002","unstructured":"Saarinen MJO. A time-memory tradeoff attack against LILI-128. In: Daemen J, Rijmen V, editors. Fast software encryption. Berlin: Springer; 2002. p. 231\u20136."},{"key":"1919_CR44","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-642-23951-9_23","volume-title":"Cryptographic hardware and embedded systems\u2014CHES 2011","author":"K Shibutani","year":"2011","unstructured":"Shibutani K, Isobe T, Hiwatari H, Mitsuda A, Akishita T, Shirai T. Piccolo: an ultra-lightweight blockcipher. In: Preneel B, Takagi T, editors. Cryptographic hardware and embedded systems\u2014CHES 2011. Berlin: Springer; 2011. p. 342\u201357."},{"key":"1919_CR45","unstructured":"Smith A. An Inquiry into the Nature and Causes of the Wealth of Nations. Project Gutenberg. 2002. http:\/\/www.gutenberg.org\/ebooks\/3300. Retrieved 2 Jan 2021. Urbana, Illinois. 2002."},{"key":"1919_CR46","unstructured":"of\u00a0Standards NI, Technology MD. Recommendations for block cipher modes of operation: Methods and techniques. Tech. Rep. NIST Special Publication SP 800-38A, U.S. Department of Commerce, Washington, D.C. 2001."},{"key":"1919_CR47","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-540-45238-6_6","volume-title":"Cryptographic hardware and embedded systems\u2014CHES 2003","author":"Y Tsunoo","year":"2003","unstructured":"Tsunoo Y, Saito T, Suzaki T, Shigeri M, Miyauchi H. Cryptanalysis of des implemented on computers with cache. In: Walter CD, Ko\u00e7 \u00c7K, Paar C, editors. Cryptographic hardware and embedded systems\u2014CHES 2003. Berlin: Springer; 2003. p. 62\u201376."},{"key":"1919_CR48","doi-asserted-by":"crossref","unstructured":"Vaudenay S. Security flaws induced by CBC padding\u2014applications to SSL, IPSEC, WTLS... In: Proceedings of the international conference on the theory and applications of cryptographic techniques: advances in cryptology, EUROCRYPT \u201902, 2002. . Springer, Berlin. pp. 534\u201346.","DOI":"10.1007\/3-540-46035-7_35"},{"key":"1919_CR49","unstructured":"Wang S, Liu M, Lin D, Ma L. Fast correlation attacks on Grain-like small state stream ciphers and cryptanalysis of Plantlet, Fruit-v2 and Fruit-80. IACR Cryptology ePrint Archive, Report 2019\/763, 2019. https:\/\/ia.cr\/2019\/763."},{"key":"1919_CR50","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-21554-4_19","volume-title":"Applied cryptography and network security","author":"W Wu","year":"2011","unstructured":"Wu W, Zhang L. Lblock: a lightweight block cipher. In: Lopez J, Tsudik G, editors. Applied cryptography and network security. Berlin: Springer; 2011. p. 327\u201344."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-023-01919-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-023-01919-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-023-01919-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T15:15:46Z","timestamp":1687878946000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-023-01919-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,27]]},"references-count":50,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,9]]}},"alternative-id":["1919"],"URL":"https:\/\/doi.org\/10.1007\/s42979-023-01919-6","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2023,6,27]]},"assertion":[{"value":"19 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 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":"Both authors declare that no funding or grants were received to assist with the preparation of this manuscript, and confirm that no human or animal subjects were involved in this research. Opinions and results contained herein do not imply any official position or endorsement by the Massachusetts General Hospital, Mass General Brigham, McKnight Brain Institute, or the University of Arizona.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"486"}}