Conditional Linear Cryptanalysis – Cryptanalysis of DES with Less Than 242 Complexity

Authors

  • Eli Biham Computer Science Department Technion – Israel Institute of Technology, Haifa, Israel
  • Stav Perle Computer Science Department Technion – Israel Institute of Technology, Haifa, Israel

DOI:

https://doi.org/10.13154/tosc.v2018.i3.215-264

Keywords:

new cryptanalytic techniques, linear cryptanalysis, DES, conditional approximations, scattered approximations

Abstract

In this paper we introduce a new extension of linear cryptanalysis that may reduce the complexity of attacks by conditioning linear approximations on other linear approximations. We show that the bias of some linear approximations may increase under such conditions, so that after discarding the known plaintexts that do not satisfy the conditions, the bias of the remaining known plaintexts increases. We show that this extension can lead to improvements of attacks, which may require fewer known plaintexts and time of analysis. We present several types of such conditions, including one that is especially useful for the analysis of Feistel ciphers. We exemplify the usage of such conditions for attacks by a careful application of our extension to Matsui’s attack on the full 16-round DES, which succeeds to reduce the complexity of the best attack on DES to less than 242. We programmed a test implementation of our attack and verified our claimed results with a large number of runs. We also introduce a new type of approximations, to which we call scattered approximations, and discuss its applications.

Published

2018-09-04

How to Cite

Biham, E., & Perle, S. (2018). Conditional Linear Cryptanalysis – Cryptanalysis of DES with Less Than 242 Complexity. IACR Transactions on Symmetric Cryptology, 2018(3), 215–264. https://doi.org/10.13154/tosc.v2018.i3.215-264

Issue

Section

Articles