Cryptography Reference
In-Depth Information
11.4.
We define the rate of a block cipher-based hash function as follows: A block
cipher-based hash function that processes
u
input bits at a time, produces
v
output
bits and performs
w
block cipher encryptions per input block has a rate of
v
/
(
u
·
w
)
.
What is the rate of the four block cipher constructions introduced in Section 11.3.2?
11.5.
We consider three different hash functions which produce outputs of lengths
64, 128 and 160 bit. After how many random inputs do we have a probability of
ε
= 0
.
5 for a collision? After how many random inputs do we have a probability of
ε
= 0
.
1 for a collision?
11.6.
Describe how exactly you would perform a collision search to find a pair
x
1
,
x
2
, such that
h
(
x
1
)=
h
(
x
2
) for a given hash function
h
. What are the memory re-
quirements for this type of search if the hash function has an output length of
n
bits?
11.7.
Assume the block cipher PRESENT (block length 64 bits, 128-bit key) is used
in a Hirose hash function construction. The algorithm is used to store the hashes of
passwords in a computer system. For each user
i
with password
PW
i
, the system
stores:
h
(
PW
i
)=
y
i
where the passwords (or passphrases) have an arbitrary length. Within the computer
system only the values
y
i
are actually used for identifying users and giving them
access.
Unfortunately, the password file that contains all hash values falls into your hands
and you are widely known as a very dangerous hacker. This in itself should not pose
a serious problem as it should be impossible to recover the passwords from the
hashes due to the one-wayness of the hash function. However, you discovered a
small but momentous implementation flaw in the software: The constant
c
in the
hash scheme is assigned the value
c
= 0. Assume you also know the initial values
(
H
0
,
L
and
H
0
,
R
).
1. What is the size of each entry
y
i
?
2. Assume you want to log in as user U (you might be the CEO of the organization).
Provide a detailed description that shows that finding a value
PW
hack
for which
PW
hack
=
y
U
takes only about 2
64
steps.
3. Which of the three general attacks against hash functions do you perform?
4. Why is the attack not possible if
c
= 0?
11.8.
In this problem, we will examine why techniques that work nicely for error
correction codes are not suited as cryptographic hash functions. We look at a hash
function that computes an 8-bit hash value by applying the following equation:
