Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 64

Adversary

Message
X

X

Hashing Hashing

d

Digest
d

Compare

INTEGER

Figure 3.1. Integrity channel.

Cryptographic hash functions are sometimes called manipulation detection codes
(MDC).

For security, we have to ensure that a change in the data content without a change
in the hashed result is an impossible scenario. Actually, the forgery of two different data
with the same hashed value must be intractable. Therefore, we need the collisions to be
intractable. We improperly say that the hash function is collision-free . This qualification
is improper because collisions do exist. They are simply hard to find. A more correct way
is to say that it is collision-resistant . The difference between cryptographic hash func-
tions and regular hash functions (which are used in the hash table data structure) is that
collisions are intractable for a malicious adversary instead of just being unlikely events.

Cryptographic hash functions are also used for commitment . Someone who wants
to commit on data x without revealing it (for instance a bid for a contract) can just reveal
h ( x r ) where r is a random string. He can later open the commitment by revealing x

and r . In this case, we need the hash function to be one-way: we need that given h ( x

||

|| r ),

it is intractable to recover x or any information about x .

3.1.2 Threat Models

As we had several classical attack models for block ciphers (like known or chosen
plaintext attacks), here are three important attack models for cryptographic hash func-
tions.

First preimage attack: from a fixed y we try to get x such that h ( x ) = y .

Second preimage attack: from a fixed x we try to get x = h ( x ). x such that h ( x ) =

Collision: we try to get x = h ( x ).

x such that h ( x ) =

Depending on the application, these attack models are relevant or not.