Paper 2015/146

New Attacks on Feistel Structures with Improved Memory Complexities

Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir

Abstract

Feistel structures are an extremely important and 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-bit inputs with seven independent round keys of n/2 bits each), a MITM attack can use (2^1.5n ,2^1.5n) time and memory, while dissection requires (2^2n, 2^n) time and memory. Our new attack requires only (2^1.5n, 2^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 multicollisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions - in fact, we can use them to improve the best known attacks on several concrete cryptosystems such as CAST-128 (where we reduce the memory complexity from 2^111 to 2^64) and DEAL-256 (where we reduce the memory complexity from 2^200 to 2^144), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures - for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of 2^16.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Cryptanalysisblock cipherFeistel structuredissectionmeet-in-the-middlesplice-and-cutCAST-128DEAL
Contact author(s)
orrd @ cs haifa ac il
History
2015-02-27: received
Short URL
https://ia.cr/2015/146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/146,
      author = {Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir},
      title = {New Attacks on Feistel Structures with Improved Memory Complexities},
      howpublished = {Cryptology ePrint Archive, Paper 2015/146},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/146}},
      url = {https://eprint.iacr.org/2015/146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.