RSA Labs FAQ -- Q97: What is a compression function?

###

### Question 97. What is a compression function?

Damgård and Merkle [Dam90] [Mer90a] greatly influenced cryptographic hash function design by defining a hash function in terms of what is called a compression function. A compression function takes a fixed length input and returns a shorter, fixed-length output. Then a hash function can be defined by means of repeated applications of the compression function until the entire message has been processed. In this process, a message of arbitrary length is broken into blocks of a certain length which depends on the compression function, and "padded" (for security reasons) so that the size of the message is a multiple of the block size. The blocks are then processed sequentially, taking as input the result of the hash so far and the current message block, with the final output being the hash value for the message (see Figure 8).

Figure 8. Damgård/Merkle iterative structure for hash functions