Known and Chosen Key Differential Distinguishers for Block Ciphers - Information Security and Cryptology-ICISC 2010 - page 30

cipher is used to build hash functions. Note that the ideal cipher is related to
the concept of pseudo-random permutation, where the adversary does not know
the cryptographic key. Clearly, for hash function constructions based on block
ciphers, the adversary fully controls the key.
Biham and Shamir introduced differential analysis in [3] and successfully an-
alyzed DES. The idea is to follow the propagation of a difference in the state
of the cipher throughout consecutive rounds. When the input-output differences
can be predicted with a suciently high probability, then the cipher can be
distinguished from a pseudo-random permutation. This concept can trivially be
adjusted for the case, where the adversary knows/controls the key of the cipher
(open-key differential distinguishers). The goal of adversary in this case would
be to find an input-output pair of differences for the cipher that can be predicted
with a probability higher than in a random permutation.
Unlike in the secret-key model, where the complexity of an attack is usually
bounded by the size of the key space (i.e. 2 k for a k -bit key), the attacks in
the open-key model are bounded by the size of the state space (i.e. 2 n for an
n -bit state). Therefore, some of the published attacks in the secret-key model
(precisely, the attacks with a complexity higher than 2 n ) become worse than
simple generic attacks, when applied in the open-key model.
Our Contributions. We investigate the impact of block cipher open-key differen-
tial distinguishers on hash function modes of operation. Our main contributions
can be summarized as follows:
1. For a variety of hash function modes based on block-ciphers, we determine
which collision finding attack variants (collisions, pseudo collisions, semi-
free start collisions, or free start collisions) are feasible, assuming that the
adversary is given a specific differential trail for the underlying block cipher
intheopen-keymodel.WetargetallPreneel-Govaerts-Vandewalle (PGV)
single-block-length compression modes, as well as four double-block-length
modes.
2. We examine several well known block ciphers (Crypton, Hierocrypt-3,
SAFER++, Square, and generic Feistel ciphers) and for each of them, we
present new known-key and chosen-key differential distinguishers - see Table
1. Our distinguishers use the rebound attack [25] as a starting point, but
we obtain substantial improvements in the number of attacked rounds by
exploiting some cipher-specific properties that allow us to manipulate bits
of the subkeys (a similar technique was used in the context of analysing
the Whirlpool function [21]). In the chosen-key model, for substitution-
permutation (SP) ciphers, we obtain an explicit formula for the number of
additional rounds that can be attacked for free, when the cipher has an
invertible key schedule.
3. To show the eciency of our distinguishers, we give a proof of a lower bound
on the complexity of differential distinguishers in the case of a black-box
random permutation. Although this bound has been used for a while (mainly
as an upper bound, e.g. in [13] it is called a limited-birthday distinguisher),
as far as we know, it has never been formally proved.