Advances in Cryptology — CRYPTO ’94

This paper drrcribes ail improved version of linear cryptanalysis and its applicat,ion t,o t .hr first, successful coniput,er experiment in breaking the full 16-round DES. ‘Ihe scenario is a known-p]a.intext at,ta.ck based on t,wo new linear approximate equations, each of which provides candidates for 13 secret. key bits wit,h negligible memory. Moreover, reliability of the key candidates is taken into consideration, which increases the siicccss r a k . As a result, the full 16-round DES is breakable wit,h high success probability if 243 random plaintexts and their ciphertexts are available. Thc aiit,hor ca.rried out, the first experimental attack iisiiig twrlvr computers to confirm t , l i k : t i c lirially reached all of the 56 secret, key bit.s i n fifty days, out o f which f0rt.y clays were spent for generating plaintexts and t,heir ciphertexts and only t>en days were spent for tshe actual key search.