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

5.1 Crypton, Hierocrypt-3 and Square

Crypton [22], Hierocrypt-3 [28], and Square [9] are 128-bit SP block ciphers and
have a various number of internal rounds depending on the length of the key. The
best published attacks in the secret-key model are on 8 rounds of Crypton [15],
3-3.5 rounds of Hierocrypt-3 [1], and 8 rounds of Square [19].
The internal state of each cipher can be seen as 4 4 matrix of bytes, while

a round consists of three types of transformations of the state: 1) byte-wise ap-
plication of a non-linear S-box, 2) matrix-wise linear-diffusion (LD) layer that
applies different linear transformations of various bytes of the matrix to intro-
duce a sucient diffusion among the bytes of the state, 3) subkey addition -
a simple xor of the round key to the matrix. A round of Crypton consists of
an S-box layer γ , LD layer composed of two transforms π and τ , and subkey
addition σ . Hierocrypt-3 has six round transforms: two S-box layers [ S ], two LD
layers [ MDS L ]and[ MDS H ], and two subkey additions [ AK ]. A round of Square
consists of four transforms: S-box layer γ , LD layer with two transforms θ and
π , and a subkey addition σ . It is important to notice that all three ciphers have
a non-linear, but invertible, key schedule. The 256-bit key versions of Crypton
and Hierocrypt-3, have a key schedule such that each two consecutive 128-bit
subkeys are independent.
For each cipher, we can build 7-round truncated differential trails (7 S-box
layer trail in case of Hierocript), that have a full active state in the middle
round, but only a few active S-boxes in the rest of the 3+3 rounds (S-box layers
of Hierocript). These trails can be used to construct known-key distinguishers
on 7 rounds of the ciphers, based on the rebound technique. Since the ciphers
have invertible key schedules, we can increase the number of attacked rounds by
switching from the known-key to the chosen-key attacks and using the degrees
of freedom of the subkeys. Hence, we can construct a chosen-key differential
distinguisher on 8 rounds of Crypton with 128-bit keys, and 9 rounds of Crypton
with 256-bit keys (the additional round comes from extra 128-bit freedom of
the key; the chosen-key has

×

256

128

= 2 more rounds than the known-key, see
Section 2.3). For Hierocrypt-3, the result is a chosen-key distinguisher on 8 S-box
layers = 4 rounds for 128-bit keys, and on 9 S-box layers=4.5 rounds for 256-
bit keys. Square only supports 128-bit keys, hence the chosen-key distinguisher
works on 8 rounds, which is indeed the total number of rounds of this cipher.
The trails used in the chosen-key distinguishers for 9, 4.5 and 8 rounds of
Crypton, Hierocrypt-3, and Square, respectively are given in the Appendix A.
Since the middle full-active state round(s) are covered by the rebound attack and
by fixing the subkeys used in these rounds, we can assume that the probability
of the trails in these rounds is 1. Hence, we count only the probability of the
rest of the rounds. In each of the three trails, we have twice 2 − 24 - that is the
probability that the linear-diffusion transformation will turn four active bytes
into one active byte. The probability of the trail in the rest of the layers is
1. Therefore, to find pairs of plaintexts and ciphertexts that will follow the
truncated differential trails, one has to start with 2 48 pairs of states that pass
the middle rounds (each pair can be build with negligible complexity). Out of 2 48