Cryptography Reference
In-Depth Information
-
The round constants consisting of two words are word-symmetric up to the
least significant bit.
-
In one round of the key scheduling function, if the two halves of the input
to non-linear function are swapped, then the output is also swapped.
In the case of Lesamnta-LW, the round constants are generated from an LFSR.
Therefore, it is dicult to find in them a structure useful for these attacks.
The non-linear function
Q
in the key scheduling function does not have this
symmetry due to the linear diffusion layer which uses a single MDS matrix
rather than two. On the other hand, the non-linear function
G
in the mixing
function has this symmetry but this is destroyed by the asymmetry introduced
from the fact that only 32 bits of round key are added to the 64-bit input to
G
.
Hence, the second property does not hold for Lesamnta-LW. We conclude from
the above discussions that these attacks are not relevant to Lesamnta-LW.
5.4
Collision Attack on the 11-Round Lesamnta-LW
We show how to construct collisions for 11-rounds of Lesamnta-LW by applying
the method used in collision attacks on Lesamnta in [25]. Now suppose that
we can find 2
96
messages
m
∗
such that all message blocks produce the same
value in the lowest 64-bit word of the chaining variable,
H
3
. Then, we know that
due to the birthday paradox two of these message blocks also lead to the same
values
H
0
,
H
1
,and
H
2
. In other words, we have constructed a collision for the
compression function.
Our attack uses the characteristic for 11 rounds given in Table 1. Note that
the symbol ? denotes an arbitrary difference and
Δ
denotes a message block
difference.
Table 1.
Characteristic for the collision attack
Round
message block
012345678910
Δ
−−
?
Δ
−
??
Δ
???
Inputs
Δ
−−
?
Δ
−
??
Δ
??
−
−
Δ
−−
?
Δ
−
??
Δ
?
−
−−
Δ
−−
?
Δ
−
??
Δ
−
It is easy to see that this characteristic can be used to fix 64 bits of the output
of the compression function. It can be summarized as follows.
1. Select an arbitary 64-bit value
d
.
2. Choose a random message block
m
=
M
0
M
1
M
2
M
3
and compute
H
=
H
0
H
1
H
2
H
3
.Checkif
H
3
=
d
for a predefined value
d
.
3. If
H
3
d
accordingly.
4. Nowwehavetoconstruct
m
∗
by adjusting
m
such that
H
3
=
d
as follows:
=
d
, then adjust
Δ
=
H
3
⊕
m
∗
=(
M
0
⊕
Δ
)
M
1
M
2
M
3
.
Search WWH ::
Custom Search