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

Table 1. Summary of attacks on the ciphers examined in the paper. The “Encryptions”
column gives the expected number of encriptions in the case of a SP cipher, while the
“Lower bound” column - the expected number of encryptions required in the case of
a random permutation. In case of n -bit Feistel cipher r is a number of covered rounds,
and 2 c is the complexity of some differential attack.

Cipher Distinguisher Rounds Encryptions Lower bound Reference

2 48 2 61 Crypton Known-key 7 Section 5.1

2 48 2 61 Chosen-key 9 Section 5.1

2 48 2 61 Hierocrypt-3 Known-key 3.5 Section 5.1

2 48 2 61 Chosen-key 4.5 Section 5.1

2 120 2 128 SAFER++ Known-key 6.5 Section 5.2

2 112 2 128 Chosen-key 6.5 Section 5.2

2 48 2 61

Square Known-key 7 Section 5.1

2 48 2 61

Chosen-key 8 Section 5.1

2 c

n -bit Feistel Differential attack r

2 c

with k -bit key

r +2

Known-key Section 5.3

r + 2 n 2 c Chosen-key Section 5.3

Organization. The paper is organized as follows. In Section 2 we define the open-
key distinguishers and review techniques for constructing differential trails. In
Section 3, we present our findings about the impact of block cipher differential
trails on the security of hash function modes. Section 4 contains our lower bound
on the complexity of differential distinguishers for black-box random permuta-
tions. In Section 5, we present our cipher specific known-key and chosen-key
differential distinguishers for various block ciphers. Section 6 concludes the pa-
per.

2 Preliminaries

2.1 Open-Key Distinguishers for Block Ciphers

A distinguisher is one of the weakest cryptographic attacks that can be launched
against a secret-key cipher. In this attack, there are two oracles: one that sim-
ulates the cipher for which the cryptographic key has been chosen at random
and the other simulates a truly random permutation. The adversary can query
both oracles and their task is to decide which oracle is the cipher (or random
permutation). The attack is considered to be successful if the number of queries
required to make a correct decision is below a well defined level.
The idea of open-key distinguishers was introduced by Knudsen and Rijmen
in [18] for analysis of AES and a class of Feistel ciphers. They examined the
security of these block ciphers in a model where the adversary knows the key .
Later, the same approach was used in the attack on 8-round reduced AES-
128 [13] and for analysis of Rijndael with large blocks [26], where the authors
defined a new security notion for a known-key cipher. The idea of chosen-key
distinguishers was introduced in the attack on the full-round AES-256 [5]. This