Zorro Break by Linear and Differential Attacks.pdf
(
363 KB
)
Pobierz
Total Break of Zorro using Linear and
Dierential Attacks
Shahram Rasoolzadeh
1;2
, Zahra Ahmadian
1;2
, Mahmood Salmasizadeh
2
, and
Mohammad Reza Aref
1
1
Information Systems and Security Lab (ISSL), Department of Electrical Engineering,
2
Electronic Research Institute,
Sharif University of Technology, Tehran, Iran
{sh_rasoolzadeh,ahmadian}@ee.sharif.edu,{salmasi,aref}@sharif.edu
Abstract. An AES-like lightweight block cipher, namely Zorro, was
proposed in CHES 2013. While it has a 16-byte state, it uses only 4
S-Boxes per round. This weak nonlinearity was widely criticized, insofar
as it has been directly exploited in all the attacks on Zorro reported by
now, including the weak key, reduced round, and even full round attacks.
In this paper, Using some observations discovered by Wang et. al., we
present new dierential and linear attacks on Zorro, both of which recover
the full secret key with practical complexity. These attacks are based on
very ecient distinguishers that have only two active sboxes per four
rounds. The time complexity of our dierential and linear attacks are
2
52:74
and 2
57:85
and the data complexity are 2
55:15
chosen plaintexts
and 2
45:44
known plaintexts, respectively. The results clearly show that
the block cipher Zorro does not have enough security against dierential
and linear cryptanalysis.
Keywords: Zorro, Lightweight Block Cipher, Dierential Cryptanlysis,
Linear Cryptanlysis.
1
Introduction
Block ciphers are the most widely-studied primitives in the area of symmetric
cryptography. Among the dierent types of attacks, dierential cryptanalysis
[1] and linear cryptanalysis [2] can be regarded as two of the oldest and most
important statistical methods to analyse the security of the block ciphers.
Zorro is a newly proposed lightweight block cipher whose design is based on
AES [4]. It is basically designed with the aim of increasing the resistance against
side-channel attacks while still remaining a lightweight block cipher. In spite
of its 16-byte state, the SubByte layer of Zorro uses only 4 similar S-Boxes in
the rst row, which are dierent from AES S-Boxes. Similar to LED-64 [5], key
addition layer in Zorro is applied only after each four rounds. Besides, Shift Row
and Mix Column layers are exactly the same as AES ones.
For both dierential and linear cryptanalysis, desingers have evaluated the
security of the cipher and found a balance between the number of inactive S-
Boxes and the number of freedom degrees for dierential or linear paths. The
2
Shahram Rasoolzadeh et al.
designers concluded that 14 and 16 rounds are upper bound for any non-trivial
dierential or linear characteristics, respectively. Furthermore, they show that
in the single key model of Zorro, a 12 round meet-in-the-middle attack is the
most powerful attack.
1.1
Related work
During the past year, Zorro has attracted the attention of many cryptanalists
and some attacks have been lunched against it by now. The rst one, proposed
by Guo, is a key recovery attack on the full-round version of the algorithm, but
it works only for 2
64
weak keys of the whole key space 2
128
[6].
In the next attack, Wang et. al. presented a dierential key recovery attack
and a linear distinguisher for full-round Zorro. They observed an interesting
property for the Zorro's MixColumn: the forth power of the MDS matrix is
equal to the identity matrix. Using this property of Zorro along with its weak
nonlinearity, they found dierential and linear distinguishers for Zorro in which
only four S-Boxes are activated per four round. The resulted dierential crypt-
analysis can recover the randomly chosen key with time complexity of 2
108
and
data complexity of 2
112:4
chosen plaintexts, and linear distinguisher use 2
105:3
known plaintexts to successfully distinguish it from the random permutation [7].
Finally, Soleimany proposed a probabilistic variation of slide attack and ap-
plied it to 16 rounds of Zorro (out of 24 rounds) [8]. This attack requires 2
123:62
known plaintexts with the time complexity of 2
123:8
encryptions or 2
121:59
known
plaintexts with time complexity of 2
124:23
encryptions.
Very recently, Dunkelman et. al. briey reported their new results on Zorro in
FSE'14 rump session which is an improvement of Wang's dierential and linear
attacks [9]. As they stated, the gain of their attack is not in the probability of
distinguishers since the new distinguishers still have two active S-boxes per two
rounds (i.e. one Sbox per round in average which is similar to that of Wang's
attack). Instead, they achieved some improvements in the key recovery phase.
Consequently, a dierential attack with time and data complexity of 2
98
and 2
95
,
and a linear attack with time and data complexity of 2
88
and 2
83:3
are resulted.
1.2
Our contributions
In this paper, we break the full-round version of Zorro by using dierential and
linear cryptanalysis. Alongside the weak nonlinearity of Zorro (i.e. the limited
number of S-Boxes in each round), we use the fact discovered in [7] that the fourth
power of MDS matrix is equal to the identity matrix. We propose very ecient
iterated dierential characteristics and linear trails that have only two active
S-Boxes per four round. Using the 23, 22 and 21-round dierential characteristic
and linear trail, we can propose a key recovery attack for any randomly chosen
secret key of full-round Zorro. Dierential cryptanalysis has a time complexity
of 2
52:74
full round encryption and data complexity of 2
55:15
chosen plaintexts.
And linear cryptanalysis has a time complexity of 2
57:85
full round encryption
Total Break of Zorro using Linear and Dierential Attacks
3
and data complexity of 2
45:44
known plaintexts. Either in dierential cryptanal-
ysis or in linear cryptanalysis memory complexity is 2
17
. Tab. 1 summarizes the
complexities of existing attacks and ours. Our results show that the theoreti-
cal security of the full-round Zorro evaluated by designers does not hold up in
practice.
Table 1. Summary of cryptanalytic results on Zorro
Attack Type Rounds attacked Time Data Memory Ref.
Dierential Full-round* 2
54:3
2
54:3
CP 2
54:3
[6]
Statistical Slide 16 (out of 24) 2
123:8
2
123:62
CP - [8]
Statistical Slide 16 (out of 24) 2
124:23
2
121:59
CP - [8]
Linear (Distinguisher) Full-round 2
105:3
2
105:3
CP - [7]
Dierential Full-round 2
108
2
112:4
CP 2
32
[7]
Dierential Full-round 2
98
2
95
CP - [9]
Linear Full-round 2
88
2
83:3
KP 2
80
[9]
Dierential Full-round 2
52:74
2
55:15
CP 2
17
Sec. 3
Linear Full-round 2
57:85
2
45:44
KP 2
17
Sec. 4
*This attack works only for 2
64
keys of the whole key space 2
128
.
CP: Chosen Plaintext, KP: Known Plaintext.
1.3
Outline
This paper is organized as follows: Section 2 presents a brief description of Zorro.
Section 3 represents the outline of the dierential attack on full-round Zorro with
all details and evaluates its complexities. Also outline and detail of linear attack
and evaluation of its complexities are presented in Section 4. Finally, Section 5
concludes this paper.
2
A Brief Description of Zorro
The block cipher Zorro has a 128-bit key and a 128-bit block size. It has 24
rounds which is divided into 6 steps of 4 rounds each.
As in AES-128, the internal state in Zorro is a 44 matrix of bytes, and
every round consists of four transformations:
1. SB
is the S-Box layer where only 4 similar S-Boxes, which are dierent
from AES S-Boxes, are applied to the 4 bytes of the rst row in the state
matrix.
2. AC is the addition of round constants. Specically, in round i the four
constants (i, i, i, i << 3) are added to the four bytes of the rst row.
3. SR is similar to AES ShiftRow.
4. MC is similar to AES MixCol.
4
Shahram Rasoolzadeh et al.
The key schedule of Zorro is similar to that of LED. Before the rst and after
each step (i.e. each four rounds), the master key is xored to the state.
As Wang argued in [7], by focusing on MC layer used in Zorro, we will see
an exclusive feature of this layer. The fourth power of MC matrix equals the
identity matrix.
0
@
1
A
) M
4
=
0
@
1
A
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
01 00 00 00
00 01 00 00
00 00 01 00
00 00 00 01
M =
(1)
Since only 4 S-Boxes are applied to the rst row in each round, combined
with these features of MDS matrix iterated dierential characteristics and linear
trails are found for one step of Zorro.
3
Dierential Cryptanalysis
In this section, we rst nd some iterated dierential characteristics for one
step of Zorro with high probability. Then, using the conventional assumption
that the step functions are independent [7], we will construct three groups of
distinguishers for 23, 22 and 21 rounds of Zorro. The rst distinguisher is used
in the rst phase of the key recovery attack to reduce the key space of 2
128
to
2
96
. Having recovered 32 bits of key in the rst phase, we use the second and
third distinguishers in the next two phases to recover 64 more bits of the key.
Finally the 32 remaining bits of key are retrieved by an exhaustive search.
3.1
Iterated Dierential Characteristic
In order to nd an ecient iterated dierential characteristic for one step of Zorro
with the minimum number of active S-Boxes, we enjoy the maximum exibility
in the input dierence. To minimize the number of active S-Boxes, it is sensible
to set the dierence of the rst row equal to zero and to bypass the inuence
of SR transformation, we set the dierences of the third and fourth columns
equal to that of rst and second ones, respectively. We do not impose any more
conditions on the remaining six bytes now and let their dependency be utilized in
minimizing the number of active S-Boxes in the next rounds. We can extend this
input dierence to four rounds with only two active S-Boxes as shown in Fig. 1.
In this gure the AC transformation is omitted since it does not have any aect
on the dierentials. The active S-Boxes are shown in gray whose dierence value
is written inside. For attaining such a dierential characteristic, some conditions
in MC transformations between states (#3, #4), (#6, #7), (#12, #1), as well
as two conditions for SB
transformation between states (#10, #11) must be
satised. Satisfying mentioned MC conditions results in 24 independent linear
equations in 26 variables A;:::;Z. Hence, after some simplications, we can
represent all the variables based on A and B:
Total Break of Zorro using Linear and Dierential Attacks
5
Fig. 1. Iterated dierential characteristic of one step of Zorro
C = D = AB
E = 2AB
F = A 2B
G = 2A 3B
H = 3A 2B
I = A 5B
J = 5AB
K = 3A 4B
L = 4A 3B
M = A 8B
N = 8AB
O = P = 13(AB)
Q = 10AB
R = A 10B
S = 20A 4B
Plik z chomika:
rc51
Inne pliki z tego folderu:
Gaza Natural Gas - Why Israel Kills for It.zip
(28398 KB)
WikiLeaks Australian Suppression Order.pdf
(313 KB)
US-NSA Pays Israel $500,000 in 2004.pdf
(152 KB)
US-Estonian Cyber Partnership Agreement.pdf
(121 KB)
US-CERT Backoff Point-of-Sale Malware.pdf
(24 KB)
Inne foldery tego chomika:
- NOWE, 2015-01
- NOWE, 2015-02
- NOWE, 2015-03
- NOWE, 2015-04
- NOWE, 2015-05
Zgłoś jeśli
naruszono regulamin