Cryptography Reference
In-Depth Information
(
,
,
,
,
, ...,
)
→
(
,
,
,
, ...,
,
)
0x2a
0x43
0x80
0x0
0x0
0x0
0x43
0x80
0x0
0x0
0x0
0x0
is 2
−
3
. This probability arise from the following equation (4).
]=2
−
3
.
Pr
x,k
[(
x
k
)
⊕
((
x
⊕
0x2a
)
k
)=
(4)
0x2a
Here, we can observe that for a fixed
k
, the probability in equation (4) can be
different from 2
−
3
, moreover, the probability in equation (4) is 0 for 148 out of
256 keys. Also, the probability of the related-key differential trail for
E
1hasthe
same flaws. The number of
k
such that the probability of the first round of
E
1
is 0 is 158.
In block cipher cryptanalysis, a target secret key is assumed to be fixed,
so in some cases the related-key differential trails for
E
0and
E
1in[10]are
not satisfied with suggested probabilities. Thus, the related-key rectangle attack
in [10] is regarded as an attack valid only for weak keys.
B Exhaustive Key Searching in the Related-Key Model
The validity of an attack on a cipher is usually proved through comparison of
the complexities with those of an exhaustive key searching in the same attack
model. Let
f
1
, ..., f
t−
1
be simple bijective relations. We assume that we are given
t
distinct encryption oracles
E
f
0
(
K
)
,
E
f
1
(
K
)
, ...,
E
f
t−
1
(
K
)
for a related-key tuple
(
f
0
(
K
)
,f
1
(
K
)
, ..., f
t−
1
(
K
)), where
f
0
is the identity function. We also assume
that the encryption oracle has the block size
n
and the key space
has 2
k
K
elements. Especially, we focus on the case of
k/
2
n<k
because our target is
HIGHT. In this setting, the exhaustive key searching consists of the following
phase.
≤
1. Choose and fix two plaintexts
P
and
P
∗
, and get the ciphertexts
C
i
and
C
i
for each encryption oracle
E
f
i
(
K
)
.
2. Repeat the following phases.
(a) Randomly pick one
K
of key candidates, compute
C
=
E
K
(
P
), and
check whether there exists a
C
i
such that
C
=
C
i
.
(b) If such
C
i
is found, compute
C
∗
=
E
K
(
P
∗
), and check whether
C
i
=
C
∗
.
(c) If a match (
C, C
∗
)=(
C
i
,C
i
) is found, halt and output
K
as the right
value of
f
i
(
K
). Otherwise, discard
K
,f
−
1
(
K
)
, ..., f
−
1
t−
1
(
K
) from search
space, and go to (a) and try again.
This is not new and similar approaches were mentioned in [1,14]. We can expect a
match is found with 2
k−
log
2
t
trials. The match yields one of
f
0
(
K
)
,f
1
(
K
)
, ..., f
t−
1
(
K
) with a high probability. So, the time complexity of this attack is dominated
by 2
k−
log
2
t
encryptions. Therefore our attack is forced to have the time com-
plexity less than 2
126
,sinceweuse
t
=4relatedkeysof
k
=128 bits.
Search WWH ::
Custom Search