Keying Merkle-Damgård at the Suffix

A classical way to turn a cryptographic hash function into a MAC (message authentication code) function is by concatenating key and message and interpreting the result as a tag. For the Merkle-Damgård hash function construction, the approach to prepend the key to the message is known to be insecure, as it is vulnerable to the length extension attack. This observation eventually resulted in the introduction of the HMAC construction. The alternative approach to append the key to the message, even though it already dates back to a work of Tsudik from 1992, has never been investigated in detail. In this work, we perform an in-depth treatment on the possibilities to design a MAC function from the Merkle-Damgård hash function construction by processing the key at the suffix. We formalize two constructions: the suffix keyed Merkle-Damgård construction that simply appends key to message, and the suffix blinded Merkle-Damgård construction that blinds the state before compressing the last message, much like the suffix keyed sponge construction (SuKS). We subsequently prove that both constructions are secure in the standard model under reasonable assumptions on the underlying compression function. We finally investigate the security of these constructions in the leaky setting, and demonstrate that the suffix keyed Merkle-Damgård construction is not leakage resilient, but the suffix blinded Merkle-Damgård construction is leakage resilient as long as an appropriate padding rule is adopted and as long as the underlying building blocks are processing secret data in a leakage resilient manner.