{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T16:12:44Z","timestamp":1778083964019,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:00:00Z","timestamp":1772496000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:00:00Z","timestamp":1772496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005717","name":"University of Haifa","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005717","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2026,4]]},"abstract":"Abstract<\/jats:title>\n \n Feistel structures are an extensively researched type of cryptographic schemes. In this paper, we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on\n n<\/jats:italic>\n -bit inputs with seven independent round keys of\n n<\/jats:italic>\n \/2 bits each, a MITM attack can use (\n \n \n $$2^{1.5n}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n 1.5<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$2^{1.5n}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n 1.5<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) time and memory, while dissection requires (\n \n \n $$2^{2n}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$2^{n}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) time and memory. Our new attack requires only (\n \n \n $$2^{1.5n}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n 1.5<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$2^{n}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) time and memory, using a few known plaintext\/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multi-collisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions\u2014in fact, we can use them to reduce the memory complexity of the best known attacks on several concrete cryptosystems such as round-reduced CAST-128 (where we reduce the complexity from\n \n \n $$2^{111} $$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 111<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n to\n \n \n $$2^{64}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 64<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) and full DEAL-256 (where we reduce the complexity from\n \n \n $$2^{200}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 200<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n to\n \n \n $$2^{144}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 144<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures\u2014for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of\n \n \n $$2^{16}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n 16<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s00145-026-09571-y","type":"journal-article","created":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T15:20:45Z","timestamp":1772551245000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["New Attacks on Feistel Structures with Improved Memory Complexities"],"prefix":"10.1007","volume":"39","author":[{"given":"Itai","family":"Dinur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Orr","family":"Dunkelman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Keller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Ross","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,3,3]]},"reference":[{"key":"9571_CR1","doi-asserted-by":"crossref","unstructured":"C.\u00a0Adams. The CAST-128 Encryption Algorithm. RFC 2144, 1997. https:\/\/tools.ietf.org\/html\/rfc2144.","DOI":"10.17487\/rfc2144"},{"key":"9571_CR2","doi-asserted-by":"crossref","unstructured":"O.\u00a0Amon, O.\u00a0Dunkelman, N.\u00a0Keller, E.\u00a0Ronen, and A.\u00a0Shamir. Three third generation attacks on the format preserving encryption scheme FF3. In EUROCRYPT 2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer Science, pages 127\u2013154. Springer, 2021.","DOI":"10.1007\/978-3-030-77886-6_5"},{"key":"9571_CR3","doi-asserted-by":"crossref","unstructured":"K.\u00a0Aoki and Y.\u00a0Sasaki. Preimage attacks on one-block md4, 63-step MD5 and more. In SAC 2008, Revised Selected Papers, volume 5381 of Lecture Notes in Computer Science, pages 103\u2013119. Springer, 2008.","DOI":"10.1007\/978-3-642-04159-4_7"},{"key":"9571_CR4","doi-asserted-by":"crossref","unstructured":"K.\u00a0Aoki and Y.\u00a0Sasaki. Preimage Attacks on One-Block MD4, 63-Step MD5 and More. In Selected Areas in Cryptography 2008, Revised Selected Papers, pages 103\u2013119, 2008.","DOI":"10.1007\/978-3-642-04159-4_7"},{"key":"9571_CR5","doi-asserted-by":"crossref","unstructured":"A.\u00a0Biryukov, G.\u00a0Leurent, and L.\u00a0Perrin. Cryptanalysis of Feistel networks with secret round functions. In Selected Areas in Cryptography, 2015, Revised Selected Papers, volume 9566 of Lecture Notes in Computer Science, pages 102\u2013121. Springer, 2015.","DOI":"10.1007\/978-3-319-31301-6_6"},{"key":"9571_CR6","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bogdanov, D.\u00a0Khovratovich, and C.\u00a0Rechberger. Biclique Cryptanalysis of the Full AES. In D.\u00a0H. Lee and X.\u00a0Wang, editors, ASIACRYPT, volume 7073 of Lecture Notes in Computer Science, pages 344\u2013371. Springer, 2011.","DOI":"10.1007\/978-3-642-25385-0_19"},{"key":"9571_CR7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bogdanov and C.\u00a0Rechberger. A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In A.\u00a0Biryukov, G.\u00a0Gong, and D.\u00a0R. Stinson, editors, Selected Areas in Cryptography, 2010, Revised Selected Papers, volume 6544 of Lecture Notes in Computer Science, pages 229\u2013240. Springer, 2010.","DOI":"10.1007\/978-3-642-19574-7_16"},{"key":"9571_CR8","unstructured":"C.\u00a0Bouillaguet. Nice attacks - but what is the cost? computational models for cryptanalysis. IACR Cryptol. ePrint Arch., 197, 2022."},{"key":"9571_CR9","doi-asserted-by":"crossref","unstructured":"C.\u00a0Boura, M.\u00a0Naya-Plasencia, and V.\u00a0Suder. Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon. In Sarkar and Iwata [33], pages 179\u2013199.","DOI":"10.1007\/978-3-662-45611-8_10"},{"key":"9571_CR10","doi-asserted-by":"crossref","unstructured":"A.\u00a0Canteaut, M.\u00a0Naya-Plasencia, and B.\u00a0Vayssi\u00e8re. Sieve-in-the-Middle: Improved MITM Attacks. In R.\u00a0Canetti and J.\u00a0A. Garay, editors, CRYPTO 2013, Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 222\u2013240. Springer, 2013.","DOI":"10.1007\/978-3-642-40041-4_13"},{"key":"9571_CR11","doi-asserted-by":"crossref","unstructured":"D.\u00a0Chaum and J.\u00a0Evertse. Crytanalysis of DES with a reduced number of rounds: Sequences of linear factors in block ciphers. In CRYPTO \u201985, Proceedings, volume 218 of Lecture Notes in Computer Science, pages 192\u2013211. Springer, 1985.","DOI":"10.1007\/3-540-39799-X_16"},{"issue":"6","key":"9571_CR12","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1109\/C-M.1977.217750","volume":"10","author":"W Diffie","year":"1977","unstructured":"W.\u00a0Diffie and M.\u00a0E. Hellman. Cryptanalysis of the NBS Data Encryption Standard. Computer, 10(6):74\u201384, 1977.","journal-title":"Computer"},{"key":"9571_CR13","doi-asserted-by":"crossref","unstructured":"I.\u00a0Dinur, O.\u00a0Dunkelman, N.\u00a0Keller, and A.\u00a0Shamir. Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. In R.\u00a0Safavi-Naini and R.\u00a0Canetti, editors, CRYPTO 2012, Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 719\u2013740. Springer, 2012.","DOI":"10.1007\/978-3-642-32009-5_42"},{"key":"9571_CR14","doi-asserted-by":"crossref","unstructured":"I.\u00a0Dinur, O.\u00a0Dunkelman, N.\u00a0Keller, and A.\u00a0Shamir. New attacks on Feistel structures with improved memory complexities. In CRYPTO 2015, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, pages 433\u2013454. Springer, 2015.","DOI":"10.1007\/978-3-662-47989-6_21"},{"key":"9571_CR15","doi-asserted-by":"crossref","unstructured":"I.\u00a0Dinur, O.\u00a0Dunkelman, N.\u00a0Keller, and A.\u00a0Shamir. Memory-efficient algorithms for finding needles in haystacks. In Proceedings of Crypto 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 185\u2013206. Springer, 2016.","DOI":"10.1007\/978-3-662-53008-5_7"},{"issue":"4","key":"9571_CR16","doi-asserted-by":"publisher","first-page":"1448","DOI":"10.1007\/s00145-018-9303-2","volume":"32","author":"I Dinur","year":"2019","unstructured":"I.\u00a0Dinur, O.\u00a0Dunkelman, N.\u00a0Keller, and A.\u00a0Shamir. Efficient dissection of bicomposite problems with cryptanalytic applications. J. Cryptol., 32(4):1448\u20131490, 2019.","journal-title":"J. Cryptol."},{"key":"9571_CR17","doi-asserted-by":"crossref","unstructured":"X.\u00a0Dong and X.\u00a0Wang. Quantum key-recovery attack on feistel structures. Sci. China Inf. Sci., 61(10):102501:1\u2013102501:7, 2018.","DOI":"10.1007\/s11432-017-9468-y"},{"key":"9571_CR18","doi-asserted-by":"crossref","unstructured":"F.\u00a0B. Durak and S.\u00a0Vaudenay. Breaking the FF3 format-preserving encryption standard over small domains. In CRYPTO 2017, Proceedings, Part II, volume 10402 of Lecture Notes in Computer Science, pages 679\u2013707. Springer, 2017.","DOI":"10.1007\/978-3-319-63715-0_23"},{"key":"9571_CR19","doi-asserted-by":"crossref","unstructured":"F.\u00a0B. Durak and S.\u00a0Vaudenay. Generic round-function-recovery attacks for feistel networks over small domains. In ACNS 2018, Proceedings, volume 10892 of Lecture Notes in Computer Science, pages 440\u2013458. Springer, 2018.","DOI":"10.1007\/978-3-319-93387-0_23"},{"key":"9571_CR20","doi-asserted-by":"crossref","unstructured":"J.\u00a0Guo, J.\u00a0Jean, I.\u00a0Nikolic, and Y.\u00a0Sasaki. Meet-in-the-Middle Attacks on Generic Feistel Constructions. In Sarkar and Iwata [33], pages 458\u2013477.","DOI":"10.1007\/978-3-662-45611-8_24"},{"key":"9571_CR21","doi-asserted-by":"crossref","unstructured":"V.\u00a0T. Hoang, D.\u00a0Miller, and N.\u00a0Trieu. Attacks only get better: How to break FF3 on large domains. In EUROCRYPT 2019, Proceedings, Part II, volume 11477 of Lecture Notes in Computer Science, pages 85\u2013116. Springer, 2019.","DOI":"10.1007\/978-3-030-17656-3_4"},{"key":"9571_CR22","doi-asserted-by":"crossref","unstructured":"A.\u00a0Hosoyamada and Y.\u00a0Sasaki. Quantum demiric-sel\u00e7uk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions. In SCN 2018, Proceedings, volume 11035 of Lecture Notes in Computer Science, pages 386\u2013403. Springer, 2018.","DOI":"10.1007\/978-3-319-98113-0_21"},{"key":"9571_CR23","doi-asserted-by":"crossref","unstructured":"T.\u00a0Isobe and K.\u00a0Shibutani. Generic key recovery attack on feistel scheme. In ASIACRYPT 2013, Proceedings, Part I, volume 8269 of Lecture Notes in Computer Science, pages 464\u2013485. Springer, 2013.","DOI":"10.1007\/978-3-642-42033-7_24"},{"key":"9571_CR24","doi-asserted-by":"crossref","unstructured":"T.\u00a0Isobe and K.\u00a0Shibutani. Improved all-subkeys recovery attacks on FOX, KATAN and SHACAL-2 block ciphers. In FSE 2014, Revised Selected Papers, volume 8540 of Lecture Notes in Computer Science, pages 104\u2013126. Springer, 2014.","DOI":"10.1007\/978-3-662-46706-0_6"},{"key":"9571_CR25","doi-asserted-by":"crossref","unstructured":"G.\u00a0Ito, A.\u00a0Hosoyamada, R.\u00a0Matsumoto, Y.\u00a0Sasaki, and T.\u00a0Iwata. Quantum chosen-ciphertext attacks against feistel ciphers. In CT-RSA 2019, Proceedings, volume 11405 of Lecture Notes in Computer Science, pages 391\u2013411. Springer, 2019.","DOI":"10.1007\/978-3-030-12612-4_20"},{"key":"9571_CR26","doi-asserted-by":"crossref","unstructured":"P.\u00a0Junod and S.\u00a0Vaudenay. FOX : A New Family of Block Ciphers. In H.\u00a0Handschuh and M.\u00a0A. Hasan, editors, SAC 2004, Revised Selected Papers, volume 3357 of Lecture Notes in Computer Science, pages 114\u2013129. Springer, 2004.","DOI":"10.1007\/978-3-540-30564-4_8"},{"key":"9571_CR27","doi-asserted-by":"crossref","unstructured":"D.\u00a0Khovratovich, C.\u00a0Rechberger, and A.\u00a0Savelieva. Bicliques for preimages: Attacks on skein-512 and the SHA-2 family. In FSE 2012, Revised Selected Papers, volume 7549 of Lecture Notes in Computer Science, pages 244\u2013263. Springer, 2012.","DOI":"10.1007\/978-3-642-34047-5_15"},{"key":"9571_CR28","unstructured":"L.\u00a0Knudsen. DEAL - A 128-bit Block Cipher, NIST AES Proposal, 1998."},{"issue":"2","key":"9571_CR29","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M Luby","year":"1988","unstructured":"M.\u00a0Luby and C.\u00a0Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput., 17(2):373\u2013386, 1988.","journal-title":"SIAM J. Comput."},{"key":"9571_CR30","doi-asserted-by":"crossref","unstructured":"S.\u00a0Lucks. Attacking triple encryption. In FSE \u201998, Proceedings, volume 1372 of Lecture Notes in Computer Science, pages 239\u2013253. Springer, 1998.","DOI":"10.1007\/3-540-69710-1_16"},{"key":"9571_CR31","unstructured":"National Bureau of Standards. Data encryption standard. Federal Information Processing Standards Publications (FIPS) 46, 1977."},{"key":"9571_CR32","doi-asserted-by":"crossref","unstructured":"B.\u00a0Ni, G.\u00a0Ito, X.\u00a0Dong, and T.\u00a0Iwata. Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256. In INDOCRYPT 2019, Proceedings, volume 11898 of Lecture Notes in Computer Science, pages 433\u2013455. Springer, 2019.","DOI":"10.1007\/978-3-030-35423-7_22"},{"key":"9571_CR33","doi-asserted-by":"crossref","unstructured":"P.\u00a0Sarkar and T.\u00a0Iwata, editors. Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Part I, volume 8873 of Lecture Notes in Computer Science. Springer, 2014.","DOI":"10.1007\/978-3-662-45608-8"},{"issue":"1","key":"9571_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"PC van Oorschot","year":"1999","unstructured":"P.\u00a0C. van Oorschot and M.\u00a0J. Wiener. Parallel collision search with cryptanalytic applications. J. Cryptol., 12(1):1\u201328, 1999.","journal-title":"J. Cryptol."},{"key":"9571_CR35","doi-asserted-by":"crossref","unstructured":"M.\u00a0Wang, X.\u00a0Wang, K.\u00a0Chow, and L.\u00a0C.\u00a0K. Hui. New Differential Cryptanalytic Results for Reduced-Round CAST-128. IEICE Transactions, 93-A(12):2744\u20132754, 2010.","DOI":"10.1587\/transfun.E93.A.2744"},{"key":"9571_CR36","doi-asserted-by":"crossref","unstructured":"B.-M. Zhou and Z.\u00a0Yuan. Quantum key-recovery attack on feistel constructions: Bernstein-Vazirani meet Grover algorithm. Quantum Information Processing, 20, 2021.","DOI":"10.1007\/s11128-021-03256-0"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-026-09571-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-026-09571-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-026-09571-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:17:20Z","timestamp":1778080640000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-026-09571-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,3]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["9571"],"URL":"https:\/\/doi.org\/10.1007\/s00145-026-09571-y","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,3]]},"assertion":[{"value":"24 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"18"}}