International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Analysis of Local Optima in Block Ciphers

John A. Clark
Juan M. Estévez-Tapiador
Search ePrint
Search Google
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.
  title={Analysis of Local Optima in Block Ciphers},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography /},
  note={Not yet published 13826 received 1 Oct 2007, withdrawn 9 Nov 2007},
  author={John A. Clark and Juan M. Estévez-Tapiador},