Cryptography Reference
In-Depth Information
Hash functions are publicly computable
. We always assume that an attacker
knows the details of a hash function. Just as for encryption algorithms, this
is the safest security assumption, for all the same reasons that we discussed
in Section 1.5.3. Since hash functions do not involve a secret key, this means
that anyone (in particular an attacker) can compute a valid hash for any input
value.
PRACTICAL PROPERTY 1: COMPRESSES ARBITRARY LONG INPUTS
INTO A FIXED LENGTH OUTPUT
What this means is that regardless of how much data is input, a hash function
generates an output (or
hash
) that is always the same fixed length. This process
of applying the hash function to the input data is often referred to as
hashing
the data. In general this hash is much smaller than the data that was input to
the hash function. Thus a hash function performs the useful task of
compressing
data. Functions with this property are sometimes called
compression functions
.
Because a hash is a small piece of data that represents a larger piece of data, it is
sometimes referred to as a
digest
, and the hash function referred to as a
message
digest function
.
Most of the hash functions that we are likely to come across in cryptography
convert binary inputs into binary outputs. If the binary output of a particular hash
function is
n
bits long then we refer to the hash function as an
n-bit hash function
.
Popular practical values for
n
lie between 160 and 512 bits (we discuss this issue
further in Section 6.2.3).
Note that an immediate consequence of the fact that the output of a hash
function is (much) smaller than the input is that for any given hash there are
likely to be many inputs that compress to the same hash value. To see that this is
true, consider PINs for payment cards. The process of taking a client's personal
information (name, address, bank details) and using a PIN derivation function to
generate from this a four-digit PIN is a good example of a compression function.
In practice, a PIN derivation function may or may not be a hash function (see,
for example, Section 10.6) but it must be a compression function. If a country has
60 million bank users and PINs consist of only four digits (a maximum of 10 000
different PINs) then there will be many people who end up with the same PIN.
If we do this process randomly then, on average, there will be 6000 people with
the same PIN.
PRACTICAL PROPERTY 2: EASY TO COMPUTE
This means that it should be 'easy' (in terms of efficiency and speed) to compute
a hash function. In other words, for a hash function
h
and input
x
it should be a
fast operation to compute
h
(
x
). The ubiquitous use of hash functions would not
be appropriate if hash functions did not have this property.
Note that in Section 3.2.3 we provided a simple classification of ease of
computation of operations. In terms of complexity theory, practical property 2
demands that a hash function can be computed in polynomial time. In fact any
