Differential Cryptanalysis of the Full 16-round DES

Abstract

In this paper we develop the first known attack which is capable of breaking the full 16 round DES in less than the 2⁵⁵ complexity of exhaustive search. The data anlaysis phase computes the key by analyzing about 2³⁶ ciphertexts in 2³⁷ time. The 2³⁶ usable ciphertexts are obtained during the data collection phase from a larger pool of 2⁴⁷ chosen plaintexts by a simple bit repetition criteria which discards more than 99.9% of the ciphertexts as soon as they are generated. While earlier versions of differential attacks were based on huge counter arrays, the new attack requires negligible memory and can be carried out in parallel on up to 2³³ disconnected processors with linear speedup. In addition, the new attack can be carried out even if the analyzed ciphertexts are derived from up to 2³³ different keys due to frequent key changes during the data collection phase. The attack can be carried out incrementally with any number of available ciphertexts, and its probability of success grows linearly with this number (e.g., when 2²⁹ usable ciphertexts are generated from a smaller pool of 2⁴⁰ plaintexts, the analysis time decreases to 2³⁰ and the probability of success is about 1%).