Cryptography Reference
In-Depth Information
3.6
Exercises
Exercise 3.1.
We modify MD5 by suppressing the padding scheme (we pad with 0 bits
only). Exhibit a collision.
Exercise 3.2.
We modify MD5 by suppressing the Davies-Meyer scheme: C is C
0
.
Prove that we can mount an inversion attack within a complexity of
2
64
: for any target
digest h, we can find a message m for which MD5
(
m
)
=
h.
(Hint: perform a meet-in-the-middle attack.)
{
,
,...,
}
Exercise 3.3.
We iteratively pick random elements in
in an independent
and uniformly distributedway until we obtain a collision. Compute the expected number
of trials.
1
2
N
Exercise 3.4.
Let x be a set. We call
(
p
q
)
-multipermutation on X any function f from
X
p
to X
q
with the following property: for any two different tuples
(
x
1
,...,
,
x
p
+
q
)
such
that
(
x
p
+
1
,...,
x
p
+
q
)
=
f
(
x
1
,...,
x
p
)
at least q
+
1
coordinates take different values.
Show that f
1
and f
2
in MD4 are not
(3
,
1)
-multipermutations. Show that f
3
is a
(3
,
1)
-multipermutation.
Show that the 2-PHT transform in SAFER is not a
(2
,
2)
-multipermutation. Show
2)
-multipermutation.
7
that the M function in CSC is a
(2
,
Exercise 3.5.
Let
K
be a finite field of order k. We define H
(
x
)
=
Ax for a random
variable A uniformly distributed in
K
.
Show that H is
k
-universal. Is it strongly-universal? How would you modify H to
make it so?
}
as a finite field of order
2
. Show that H is
2
−
-XOR-
We now consider
K
={
0
,
1
universal.
7
This exercise was inspired by Ref. [179].
Search WWH ::
Custom Search