Cryptography Reference
In-Depth Information
Result.
The following theorem gives an upper bound on the probability of find-
ing a collision of Lesamnta-LW in the ideal cipher model. A proof is given in
Appendix B.
Theorem 1.
Let
A
be a col-adversary against Lesamnta-LW asking at most
q
queries to
E
.Then,for
n
≥
4
and
q
≥
1
,
2
n
nq
2
2
n
q
2
2
2
n
q
Adv
col
LW
(
A
)
≤
q
+
q
+
.
−
−
n
!
·
2
n
4.2
(Second) Preimage Resistance
The preimage resistance of Lesamnta-LW can also be proved in the ideal cipher
model using the same technique. Since the compression function is invertible,
the Lesamnta-LW hash function also has a claimed security level of at least 2
120
block-cipher operations against (second-)preimage attacks. On the other hand,
Lesamnta-LW cannot provide security larger than 2
128
because of the LW1 mode.
We note that a second-preimage attack such as the Kelsey-Schneier attack [30]
is ineffective in attacking Lesamnta-LW because of the designed security level.
For example, consider the Kelsey-Schneier attack using a (2
64
1)-bit message,
which is the maximum acceptable length of a message. Then, the complexity
of the attack is about 2
192
. However, Lesamnta-LW provides at most the 2
128
security level against preimage-finding attacks.
−
4.3
Keyed Hashing Mode
Key-Prefix Mode.
The key-prefix (KP) mode is a method to construct a
pseudorandom function (PRF) from a given hash function. It simply feeds
K
M
to the hash function as an input, where
K
is a secret key and
M
is a message
input. This mode uses a hash function as a black box. In this sense, it is similar
to HMAC.
The KP mode of Lesamnta-LW with the first half of the output chopped off
resists any distinguishing attack that requires much fewer than 2
128
queries if
the underlying block cipher is a pseudorandom permutation (PRP) and it also
has a mild security property given later.
Definition.
Let
F
(
X
,
Y
) be a set of all functions from
X
to
Y
.Let
F
:
K×X →Y
be a keyed function from
is its key space. Let
A
be a probabilistic
algorithm which has oracle access to a function from
X
to
Y
,where
K
X
to
Y
and outputs 0 or
1. The prf-advantage of
A
against
F
is given by
(
A
)=
)]
Adv
prf
F
Pr[
A
F
K
=1
K
$
Pr[
A
ρ
=1
ρ
$
|
←K
]
−
|
←F
(
X
,
Y
,
where the probabilities are taken over the coin tosses by
A
and the uniform
distributions on
).
F
is called a PRF if Adv
prf
F
K
and
F
(
X
,
Y
(
A
) is negligible for
any ecient
A
.
Search WWH ::
Custom Search