19.7 Attacks on hash functions
Recall from Chapter 11, Hash Functions and Message Authentication Codes, that a hash function h maps a string of arbitrary length onto a string of fixed length. In this setting, collisions, that is, different inputs x1,x2 having the same output h(x1) = h(x2) have to occur at some point.
In Chapter 11, Hash Functions and Message Authentication Codes, we also defined two important properties for a hash function to be considered secure: Collision Resistance and the One-Way Property. In a nutshell, the first of these properties makes it difficult for Eve to actually find collisions, whereas the second makes it difficult to find pre-images, that is to find a matching input string x for a given hash value h(x). All of the attacks in the current section are aimed either at finding collisions or finding pre-images.
19.7.1 Birthday attack
A birthday attack exploits the probability of collisions in a hash function – a mathematical property of such...
