A generalized framework for accelerating exhaustive search utilizing deterministic related-key differential characteristics

The deterministic related-key characteristic in DES can be used to accelerate the exhaustive search in the single-key setting even if an adversary cannot obtain the ciphertexts for arbitrary plaintexts in the related-keymodel. Inspired by this observation, it has become a common belief that if there exist 2(m) deterministic differential characteristics for a block cipher with the key size of k, they can be employed to decrease the security to k - m bits. The adversary should be able to efficiently partition the key space according to eliminated related keys in order to accelerate the exhaustive search. However, the conventional technique utilized to exploit one deterministic related-key differential characteristic is not extendable. Several deterministic related-key differential properties, regardless of the differences' values cannot be exploited by applying this technique. In this paper, we describe a precise framework for utilizing several deterministic related-key differential distinguishers, which provides a general methodology to reduce the security of cryptographic primitives. It takes the advantage of deterministic related-key properties. We demonstrate our proposed framework can be used to evaluate the security of block ciphers by presenting straightforward applications of our framework on different variants of block ciphers. In particular, we present a new attack on the well-known FX and Even-Mansour constructions. The latter is quite simpler than the former.