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

time the adversary is assumed to have a full control over the key . A chosen-key
attack was launched on 8-round reduced AES-128 in [6].
Both the known-key and chosen-key distinguishers are collectively known
open-key distinguishers . The adversary has the knowledge of the key or even
can choose a value of the key. To succeed, the adversary has to discover some
property of the attacked cipher that holds with a probability higher than for a
random permutation.
Differential distinguishers in the open-key model are defined in similar way as
in the secret-key model. The adversary builds a differential trail ( Δ P ,Δ K ) Δ 2

for the block cipher E K ( P ). In other words, he finds a pair 1 of plaintexts ( P 1 , P 2 )
and a pair of keys ( K 1 ,K 2 ), together known as a differential pair, such that
P 1 ⊕

→

E K 2 ( P 2 )= Δ 2 . The pair ( Δ P ,Δ K )
is the input difference, while Δ 2 is the output difference. At least one of Δ P and
Δ K has to be non-zero. For example, the trails given in [6,13,26] have differences
only in the plaintext, while the trail from [5] has differences in both the key and
the plaintext.

P 2 = Δ P ,K 1 ⊕ K 2 = Δ K and E K 1 ( P 1 ) ⊕

2.2 Design of Differential Distinguishers for Block Ciphers

We will focus our analysis on substitution-permutation (SP) block ciphers. Each
round of such ciphers consists of two types of transformations: 1) a non-linear
layer of S-boxes, and 2) a linear-diffusion layer (LD). The non-linear layer oper-
ates on bytes, i.e. the inputs to the S-boxes are bytes of the state. The linear-
diffusion layer may apply different transformations such as multiplications of the
columns/rows of the state matrix by a fixed diffusion matrix, transpositions of
rows/columns, rotations of elements of the state matrix, subkey additions, and
others.
Differential trails for ciphers are given as a sequence of input-output word
differences of each transformation of the state. Since SP ciphers are usually
byte-oriented, these trails can be given as a sequence of active bytes, i.e. bytes
that have differences. Depending on the properties of the S-box layer and the
linear-diffusion layer, the adversary can built two types of trails.
Thefirsttypeisa standard differential trail, where the exact values of the
input-output differences for each layer and for each round of the trail are fixed.
The probability of these trails depends on the differential properties of the S-
boxes, i.e. the probability that a given input difference to the S-box will produce
a given output difference. Note that when these differences are fixed, then the
trail in the linear-diffusion layer holds with probability 1.
The second type is a truncated differential trail [16]. In this trail only the
position of the active bytes is important, while the actual difference values are
ignored. Since, the S-box operates on a single byte, it means it cannot change an
active byte to a non-active and vice-versa. Hence the adversary concentrates only
on the linear-diffusion layer and finds the probability of a particular configuration
of input-output active bytes.

1 Actually the adversary can build many pairs of plaintexts and keys.