Paper 2007/387

Analysis of Local Optima in Block Ciphers

John A. Clark and Juan M. E. Tapiador


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.

Available format(s)
-- withdrawn --
Secret-key cryptography
Publication info
Published elsewhere. Not yet published
Contact author(s)
jet @ cs york ac uk
2007-11-09: withdrawn
2007-10-04: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.