Cryptography Reference
In-Depth Information
three properties are still not sufficient. Many cryptographic protocols
using one-way hash functions additionally require the following prereq-
uisite:
4. With a given byte sequence, it is not possible to find a second byte
sequence with the same hash value at reasonable cost. A pair of byte
sequences with an identical hash value is also called a
collision
.
This relates to the birthday attack, which will be discussed in Section 6.3.3.
One-way hash functions are sometimes also referred to as
compression func-
tions, concentration functions, message digests, cryptographic checksums, mes-
sage integrity checks
(
MIC
), and there are more names. You can see quickly
from the context what each one is about.
One-way hash functions do not use secret keys. This corresponds to their pur-
pose of use — they should be computable for everybody. We will see this in the
following section. However, there are non-reversible hash functions with secret
keys. They are called
MACs
(
message authentication codes
) and serve for
creating signatures that can be verified only provided one knows the secret key.
Such signatures are useful, for example, to detect virus infection or other manip-
ulations to your software with certainty. We won't discuss MACs any further
here; you can find all the details in [SchnCr, 18.14] and [MenOoVan, 9.5].
Research on one-way hash functions began only around 1990. With one-way
hash functions, cryptanalysis concentrates on different goals than it does with
encryption algorithms. The reversion of a hash function (Property 3) has been
successful only once so far, namely for a reduced variant of MD4 (see below).
One tries instead to compute collisions, i.e., to find different byte sequences
with the same hash value (Property 4).
Examples of One-Way Hash Functions
The structure of one-way hash functions appears very complicated at first, and
their design is not easy to understand. I spare you the detailed description of
such difficult hash functions as MD5 and will present only the most simple
(MD2) which is, however, pretty outdated. The important things to remem-
ber are statements on the cryptanalysis of these functions. The following list
mentions several known one-way hash functions.
•
Snefru
: This function was developed by Merkle in 1990 (it was probably
the first algorithm of this type). Its major drawback is that, if SneFru is
to be secure at all, it gets extremely slow.
