Cryptography Reference
In-Depth Information
(i.e., that many evaluations of the hash function). The storage required is expected to be
√
π
2
l
−
1
#
2
l
as above this would be about 2
l/
2
−
κ
bitstrings of storage.
For many more details on this topic see Section 7.5 of Joux [
283
], Section 9.7.1 of Menezes,
van Oorschot and Vanstone [
376
] or Section 3.2 of Vaudenay [
553
].
This approach also works if one wants to find collisions under some constraint on the
messages (e.g., all messages have a fixed prefix or suffix).
D
pairs (
x
0
,x
n
). For the choice of
3.3 Message authentication codes
Message authentication codes are a form of symmetric cryptography. The main purpose is
for a sender and receiver who share a secret key
k
to determine whether a communication
between them has been tampered with.
A
message authentication code
(
MAC
) is a set of functions
{
MAC
k
(
x
):
k
∈ K}
such
l
. Note that this is exactly the same definition as a hash fam-
ily. The difference between MACs and hash families lies in the security requirement; in
particular the security model for MACs assumes the adversary does not know the key
k
.
Informally, a MAC is secure against forgery if there is no efficient adversary that, given
pairs (
x
i
,y
i
)
{
}
∗
→{
}
that
MAC
k
:
0
,
1
0
,
1
}
∗
×{
l
such that
y
i
=
∈{
0
,
1
0
,
1
}
MAC
k
(
x
i
) (for some fixed, but secret, key
}
∗
×{
l
such that
y
k
)for1
≤
i
≤
n
, can output a pair (
x,y
)
∈{
0
,
1
0
,
1
}
=
MAC
k
(
x
)but
(
x,y
)
n
. For precise definitions and further details of MACs see
Section 4.3 of Katz and Lindell [
300
], Section 9.5 of Menezes, van Oorschot and Van-
stone [
376
], Section 6.7.2 of Shoup [
497
], Section 4.4 of Stinson [
532
] or Section 3.4 of
Vaudenay [
553
].
There are well-known constructions of MACs from hash functions (such as HMAC,
see Section 4.7 of [
300
], Section 4.4.1 of [
532
] or Section 3.4.6 of [
553
]) and from block
ciphers (such as CBC-MAC, see Section 4.5 of [
300
], Section 4.4.2 of [
532
]orSection
3.4.4 of [
553
]).
=
(
x
i
,y
i
) for all 1
≤
i
≤
3.4 Constructions of hash functions
There is a large literature on constructions of hash functions and it is beyond the scope of this
topic to give the details. The basic process is to first define a
compression function
(namely,
a function that takes bitstrings of a fixed length to bitstrings of some shorter fixed length)
and then to build a hash function on arbitrary length bitstrings by iterating the compression
function (e.g., using the Merkle-Damgard construction). We refer to Chapter 4 of Katz and
Lindell [
300
], Sections 9.3 and 9.4 of Menezes, van Oorschot and Vanstone [
376
], Chapter
10 of Smart [
513
], Chapter 4 of Stinson [
532
] or Chapter 3 of Vaudenay [
553
]forthe
details.
