Cryptography Reference
In-Depth Information
(perhaps if Alice's bid is so high that Bob decides it is strategically advantageous
to make her spend all her money).
The difference between this application and the file download application is
that in this case there are many different collisions in the hash function that it
could be useful for a cheating party to find. They are not just concerned with
finding a collision for a
specific
input, but in fact collisions for a
range
of inputs.
We thus need our hash function to offer
collision resistance
.
Note that this application requires
all three
security properties:
Preimage resistance
. We need preimage resistance, otherwise each party might
be able to determine the bid of the other party from the hash commitment.
Second preimage resistance
. We need second preimage resistance for the same
reasons that we need collision resistance (second preimages are just special
types of collisions, as we observed in Section 6.2.1).
This example is of course a slightly artificial scenario, both in its simplicity and
applicability. However, such commitments form genuine components of many
more sophisticated cryptographic protocols, including complex applications such
as electronic voting schemes.
Another important application of hash functions that relies on collision
resistance is to digital signature schemes. We will examine this application in
more detail in Section 7.3.4.
6.2.3
Attacking hash functions in theory
In Section 6.2.1 we noted that, from the attacker's perspective, finding collisions
is normally the 'easiest' attack to conduct. In fact it is protection against collisions
that primarily determines the output lengths of practical hash functions. Thus we
will focus on finding collisions during our discussion of hash function attacks.
We will focus on the question: howmany bits long should the hash of amessage
be in order for it to be regarded as secure? Since we are really worried about
collision resistance, this question could be phrased as: how long does a hash have
to be before finding collisions is hard?
Throughout this discussion we will keep in mind that, as we will see in
Section 7.3.4, a popular application of hash functions is to apply them before
creating a digital signature on a message. In other words, the digital signature
is on the
hash
of the message and not the message itself. The consequences of
finding a collision are serious for this type of application since if two messages can
be found with the same hash then a badly behaving user could sign one message
and then claim that the signature was on the other.
THE DANGERS OF A
VERY
SMALL HASH
Clearly a very small hash is a bad idea. For example, suppose that before digitally
signing the message
Bruce owes Sheila $10
we hash it using a 2-bit hash function.
