In this paper we improve Davies' attack [2] on DES to become capable o
f breaking the full 16-round DES faster than the exhaustive search. Ou
r attack requires 2(50) known plaintexts and 2(50) complexity of analy
sis. If independent subkeys are used, a variant of this attack can fin
d 26 bits out of the 768 key bits using 2(52) known plaintexts. All th
e 768 bits of the subkeys can be found using 2(60) known plaintexts. T
he data analysis requires only several minutes on a SPARC workstation.
Therefore, this is the third successful attack on DES, faster than br
ute force, after differential cryptanalysis [1] and linear cryptanalys
is [5]. We also suggest criteria which make the S-boxes immune to this
attack.