Technical Report CS0708

Title: Differential Cryptanalysis of the Full 16-Round DES.
Authors: Eli Biham, Adi Shamir
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^{55}$ complexity of exhaustive search. The data analysis phase computes the key by analyzing about $2^{36}$ ciphertexts in $2^{37}$ time. The $2^{36}$ usable ciphertexts are obtained during the data collection phase from a larger pool of $2^{47}$ 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^{33}$ 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^{33}$ 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^{29}$ usable ciphertexts are generated from a smaller pool of $2^{40}$ plaintexts, the analysis time decreases to $2^{30}$ and the probability of success is about 1\%).
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion