Easing collision finding in cryptographic primitives with genetic algorithms

Abstract

The finding of collisions (i.e. different inputs that map to the same output) in cryptographic primitives (hash functions or block ciphers) is an extremely difficult task. It generally requires hundreds or thousands of hours of a talented cryptanalyst. Even in this case, results are not always guaranteed. We present a new method for easing collision finding, based on genetic algorithms. Our method automatically seeks correlations between the input and the output bits that can be used for producing pseudocollisions (i.e. collisions of parts of the output). These pseudocollisions are then useful for creating a full output collision. These ideas are shown to work over a version of the block cipher TEA reduced to one round.