An improvement of Davies’ attack on DES

In this paper we improve Davies’ attack [2] on DES to become capable of breaking the full 16-round DES faster than the exhaustive search. Our attack requires 2⁵⁰ known plaintexts and 2⁵⁰ complexity of analysis. If independent subkeys are used, a variant of this attack can find 26 bits out of the 768 key bits using 2⁵² known plaintexts. All the 768 bits of the subkeys can be found using 2⁶⁰ known plaintexts. The data analysis requires only several minutes on a SPARC workstation. Therefore, this is the third successful attack on DES, faster than brute force, after differential cryptanalysis [1] and linear cryptanalysis [5]. We also suggest criteria which make the S-boxes immune to this attack.