Cryptography Reference
In-Depth Information
5.2
Complexity Analysis
The probability of 24-round related-key rectangle distinguisher used in our at-
tack is 2
117
.
68
. So, we form the plaintext structures such that we are given 2
119
.
68
quartets satisfying the input differences of the distinguisher and expect approx-
imately 4 right quartets after guessing
K
1[0
,
1
,
2
,
5
,
6
,
10
,
12
,
13
,
14].
Since we use structures
S
i
includes 2
40
plaintexts and 16 kinds of input dif-
ferences of distinguisher(set
whichisdefinedinSection4.2)isassumed,we
have 2
44
pairs per structure and we can consider 2
2
m
+88
quartets from 2
m
struc-
tures thus the number of required structures is 2
m
=2
15
.
84
. Hence, our attack
requires 2
15
.
84+40
=2
55
.
84
plaintexts and encrypts them with four encryption
oracles defined by four related keys to get 2
57
.
84
ciphertexts and that is the data
complexity of our attack.
In the first step of the attack procedure in the above section, the number of
queries to four encryption oracles with related keys is 2
57
.
84
but this is negligible
in total complexity.
Weguess9bytesof
K
1[0
,
1
,
2
,
5
,
6
,
10
,
12
,
13
,
14] in step 2 with a restriction
on
K
1[6] that
SK
1[82]
∈D
, so total number of guessed key is 2
70
. Moreover, an
attack procedure and tested quartets when 9 bytes of
K
are guessed as
K
1is
identical to an attack procedure and tested quartets when 9 bytes of
K
A
Δ
+
K
are
guessed as
K
1, so the total number of key guessing for
K
1[0
,
1
,
2
,
5
,
6
,
10
,
12
,
13
,
14]
is reduced to 2
69
.
From step 2-(a) to 2-(d), we explain how we make 2
119
.
68
quartets from 2
15
.
84
structures and step (e), we explain how we filter out the wrong quartets. For
steps from 2-(a) to 2-(d), we partially encrypt all plaintexts in each structure
for 6/128 HIGHT with 4 related keys and choose the pairs satisfying the input
differences of distinguisher, so these steps require
2
−
7
2
55
.
840+69
2
122
.
425
4
×
6
×
×
≈
of 2
59
.
84
ciphertext pairs, respec-
tively. In step 2-(e), we partially decrypt for 1/128 HIGHT and 2/128 HIGHT
to compute (
l
X
31
[3]
encryptions and yields two hash tables
H
and
I
u
X
31
[3],
v
X
31
[3]
j
w
X
31
[3]) and (
ΔT, ΔT
), respectively,
⊕
⊕
so these step requires
2
−
7
2
57
.
840+69
2
121
.
425
3
×
×
≈
decryptions.
In step 2-(e)-i, we check that two bytes of ciphertext differences are 0, and
another one byte of ciphertext difference is equal to one of 8 elements in
E
,so
the filtering ratio of this step is 2
−
2
×
2
×
8
−
2
×
5
=2
−
42
.
In step 2-(e)-ii,
l
X
31
[3]
u
X
31
[3] and
v
X
31
[3]
j
w
X
31
[3] must be one of 16
⊕
⊕
elements in
F
, because
SK
1[120]
⊕
SK
3[120] =
SK
2[120]
⊕
SK
4[120] =
,
0x10
and
SK
1[116]
⊕
SK
3[116] =
SK
2[116]
⊕
SK
4[116] =
, so the filtering ratio
0x68
of this step is 2
−
2
×
4
=2
−
8
.
Since the average ratio of
Δx
and
Δz
which satisfy that Pr[(
Δx,
0)
Δz
]
>
0
is 2
−
2
.
82757
, the filtering ratios of step 2-(e)-iii and iv are both 2
−
5
.
65514
, and since
→
Search WWH ::
Custom Search