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

pairs, 2 24 will produce four-to-one active byte in the first half of the trail, leading
to a plaintext difference as the one in the trail. Out of these 2 24 , one will produce
four-to-one active in the second half of the trail and a ciphertext difference as
the one in the trail. Now, let us try to compare our complexity of 2 48 encryptions
to the complexity in a case of a random permutation. By Lemma 1, to find this
complexity we have to find the cardinalities of the plaintext and the ciphertext
differences in the truncated trails. Although some of the plaintext/ciphertext
differences in the trails have full active states, they are obtained by a linear
transformation of some state with a four active bytes. Hence the cardinalities in
all cases are 2 4 · 8 =2 32 , and the complexity of producing a pair for a random
permutation, that follows the trails, is at least min(2 12 2 − 2 , 2 128 − (32+32) − 3 )=2 61
encryptions.
To test the correctness of our results, we have constructed a chosen-key distin-
guisher on mCrypton [23], which has the same design as Crypton, but instead of
bytes (8-bit words), it works with nibbles (4-bit words), and uses a non-invertible
key schedule. The above distinguishers for Crypton can easily be applied to a
modified version of mCrypton with a (invertible) key schedule identical to the one
of Crypton. The chosen-key distinguisher for 9 rounds of this modified mCryp-
ton was implemented on a PC, and a differential pair was found. The results are
given in Appendix B.

5.2 SAFER++

SAFER++ [24] is a 128-bit SP block cipher. The version with 128-bit key has
7 rounds and the best published attack works for 5.5 rounds [4]. A round of
SAFER++ consists of: 1) a byte-wise subkey addition, 2) a byte-wise S-box
layer, 3) a byte-wise subkey addition, and 4) a state-wise linear-diffusion layer
in the form of four 4-PHT. The subkey additions are modular and xor, and
two different S-boxes are used. After the last round, there is an extra subkey
addition. The key schedule is linear.
When the subkeys are fixed, then the S-box layer can be merged with the
subkey additions to form another S-box layer, with the same input and output
size. In other words, the subkey addition together with S-box and the subkey
addition can be seen simply as some S-box (since the bytes of the subkeys are
different, the S-boxes are also different). Hence, we can assume that a round of
the cipher is composed of an S-box layer and a linear-diffusion layer, and all the
additions in the cipher are modular.
Our automatic search for the best round-reduced standard differentials has
found that there exist only two three-round trails with 10 active S-boxes (the
rest of the trails have more than 10 active S-boxes). The first trail has 4,2,4 while
the second has 2,3, and 5 active S-boxes in the first, the second, and the third
round, respectively. We have used two 4-2-4 trails in our standard differential
attack (see Fig.2). We attack 6.5 rounds of SAFER++, which is the full cipher,
except for the first round, where the three transforms: subkey addition, S-box
and subkey addition, are missing. As far as we know this is the first rebound
attack with standard differentials. Therefore, we will describe it in more details.