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

Known and Chosen Key Differential
Distinguishers for Block Ciphers

Ivica Nikolic 1 , , Josef Pieprzyk 2 , Przemyslaw Sokolowski 2 , 3 , and Ron Steinfeld 2

1 University of Luxembourg, Luxembourg
2 Macquarie University, Australia
3 Adam Mickiewicz University, Poland
[e-mail],
{ josef.pieprzyk,przemyslaw.sokolowski,ron.steinfeld } @mq.edu.au

Abstract. In this paper we investigate the differential properties of
block ciphers in hash function modes of operation. First we show the
impact of differential trails for block ciphers on collision attacks for vari-
ous hash function constructions based on block ciphers. Further, we prove
the lower bound for finding a pair that follows some truncated differential
in case of a random permutation. Then we present open-key differential
distinguishers for some well known round-reduced block ciphers.

Keywords: Block cipher, differential attack, open-key distinguisher, Cryp-
ton, Hierocrypt, SAFER++, Square.

1 Introduction

Block ciphers play an important role in symmetric cryptography providing the
basic tool for encryption. They are the oldest and most scrutinized cryptographic
tool. Consequently, they are the most trusted cryptographic algorithms that are
often used as the underlying tool to construct other cryptographic algorithms.
One such application of block ciphers is for building compression functions for
the hash functions.
There are many constructions (also called hash function modes )forturning
a block cipher into a compression function. Probably the most popular is the
well-known Davies-Meyer mode. Preneel et al. in [27] have considered all possible
modes that can be defined for a single application of n -bit block cipher in order to
produce an n -bit compression function. They have found that there are 12 modes
that are resistant against generic attacks. Later these findings have been formally
proven in [7]. To make hash functions resistant against the birthday-paradox
attack, it is better to use double-block modes. Basic double-block modes have
been proposed in [8,14,20]. Note that the Tandem-DM mode has been proven to
be collision resistant in [12], while a weakness in MDC-2 was found in [17].
Proofs of security of the above modes are performed under the assumption
that the underlying block cipher is ideal. This assumption is not satisfied if the

The work was done while this author was visiting Macquarie University.