11.4 Hash functions
A hash function is some function hash that maps an arbitrarily long input string onto an output string of fixed length n. More formally, we have hash : {0,1}∗→{0,1}n.
A simplistic example of a hash function would be a function that always outputs the last n bits of an arbitrary input string m. Or, if n = 1, one could use the bitwise XOR of all input bits as the hash value.
However, these simple hash functions do not possess any of the properties required from a cryptographically secure hash function. We will now first discuss these properties, and afterward look at how secure hash functions are actually constructed.
11.4.1 Collision resistance
Cryptographic hash functions are hard to construct because they have to fulfill stringent requirements, which are motivated by their use within Message Authentication Codes (MACs) (see Section 11.5, Message Authentication Codes) and Digital Signatures (see Chapter 9, Digital Signatures).
Recall, for example...
