Paper 2007/387

Analysis of Local Optima in Block Ciphers

John A. Clark and Juan M. E. Tapiador

Abstract

We present a technique to perform key distinguishing attacks on block ciphers. The method is based on profiling the behaviour of a simple search algorithm when it is applied to recover the key under which a set of known plaintexts has been encrypted. Even though the probability of finding the correct key is negligible, it is observed that the solutions (local optima) yielded by successive searches can be highly dependent on the key, forming patterns that can be unequivocally (in a statistical sense) associated with each particular key. When a cipher suffers from such a weakness, this provides us with an effective procedure to tell apart ciphertexts generated by different and unknown keys. We illustrate the method by applying it to the TEA block cipher, for which attacks of this kind can be successfully mounted against the full version (64 rounds) with extremely simple profiling methods. The technique itself is completely black-box and admits a number of refinements. We suspect it might be applied to many other ciphers by using the same or more complex profiling schemes.