Differential Cryptanalysis of the Full 16-round DES

In this talk we describe the first published 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 in $2^{37}$ time and negligible space by analysing a small subset of the $2^{47}$ ciphertexts generated during the data collection phase from appropriately chosen messages. Unlike earlier versions of differential attacks, the new attack can be carried out even if the analysed ciphertexts are derived from many different keys due to frequent key changes, and can be carried out incrementally with any number of available ciphertexts with a linearly growing probability of success. Joint work with Eli Biham.